package org.apache.lucene.index;/** * Licensed to the Apache Software Foundation (ASF) under one or more * contributor license agreements.  See the NOTICE file distributed with * this work for additional information regarding copyright ownership. * The ASF licenses this file to You under the Apache License, Version 2.0 * (the "License"); you may not use this file except in compliance with * the License.  You may obtain a copy of the License at * *     http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */import java.io.IOException;import org.apache.lucene.store.IndexOutput;import org.apache.lucene.store.RAMOutputStream;/** * This abstract class writes skip lists with multiple levels. *  * Example for skipInterval = 3: *                                                     c            (skip level 2) *                 c                 c                 c            (skip level 1)  *     x     x     x     x     x     x     x     x     x     x      (skip level 0) * d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d d  (posting list) *     3     6     9     12    15    18    21    24    27    30     (df) *  * d - document * x - skip data * c - skip data with child pointer *  * Skip level i contains every skipInterval-th entry from skip level i-1. * Therefore the number of entries on level i is: floor(df / ((skipInterval ^ (i + 1))). *  * Each skip entry on a level i>0 contains a pointer to the corresponding skip entry in list i-1. * This guarantess a logarithmic amount of skips to find the target document. *  * While this class takes care of writing the different skip levels, * subclasses must define the actual format of the skip data. *  */abstract class MultiLevelSkipListWriter {  // number of levels in this skip list  private int numberOfSkipLevels;    // the skip interval in the list with level = 0  private int skipInterval;    // for every skip level a different buffer is used   private RAMOutputStream[] skipBuffer;  protected MultiLevelSkipListWriter(int skipInterval, int maxSkipLevels, int df) {    this.skipInterval = skipInterval;        // calculate the maximum number of skip levels for this document frequency    numberOfSkipLevels = df == 0 ? 0 : (int) Math.floor(Math.log(df) / Math.log(skipInterval));        // make sure it does not exceed maxSkipLevels    if (numberOfSkipLevels > maxSkipLevels) {      numberOfSkipLevels = maxSkipLevels;    }  }    protected void init() {    skipBuffer = new RAMOutputStream[numberOfSkipLevels];    for (int i = 0; i < numberOfSkipLevels; i++) {      skipBuffer[i] = new RAMOutputStream();    }  }  protected void resetSkip() {    // creates new buffers or empties the existing ones    if (skipBuffer == null) {      init();    } else {      for (int i = 0; i < skipBuffer.length; i++) {        skipBuffer[i].reset();      }    }        }  /**   * Subclasses must implement the actual skip data encoding in this method.   *     * @param level the level skip data shall be writting for   * @param skipBuffer the skip buffer to write to   */  protected abstract void writeSkipData(int level, IndexOutput skipBuffer) throws IOException;    /**   * Writes the current skip data to the buffers. The current document frequency determines   * the max level is skip data is to be written to.    *    * @param df the current document frequency    * @throws IOException   */  void bufferSkip(int df) throws IOException {    int numLevels;       // determine max level    for (numLevels = 0; (df % skipInterval) == 0 && numLevels < numberOfSkipLevels; df /= skipInterval) {      numLevels++;    }        long childPointer = 0;        for (int level = 0; level < numLevels; level++) {      writeSkipData(level, skipBuffer[level]);            long newChildPointer = skipBuffer[level].getFilePointer();            if (level != 0) {        // store child pointers for all levels except the lowest        skipBuffer[level].writeVLong(childPointer);      }            //remember the childPointer for the next level      childPointer = newChildPointer;    }  }  /**   * Writes the buffered skip lists to the given output.   *    * @param output the IndexOutput the skip lists shall be written to    * @return the pointer the skip list starts   */  long writeSkip(IndexOutput output) throws IOException {    long skipPointer = output.getFilePointer();    if (skipBuffer == null || skipBuffer.length == 0) return skipPointer;        for (int level = numberOfSkipLevels - 1; level > 0; level--) {      long length = skipBuffer[level].getFilePointer();      if (length > 0) {        output.writeVLong(length);        skipBuffer[level].writeTo(output);      }    }    skipBuffer[0].writeTo(output);        return skipPointer;  }}