content: package org.apache.lucene.util;
  
  /**
   * 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 java.util.BitSet;
  
  import org.apache.lucene.search.DocIdSet;
  import org.apache.lucene.search.DocIdSetIterator;
  
  /**
   * Stores and iterate on sorted integers in compressed form in RAM. <br>
   * The code for compressing the differences between ascending integers was
   * borrowed from {@link org.apache.lucene.store.IndexInput} and
   * {@link org.apache.lucene.store.IndexOutput}.
   * <p>
   * <b>NOTE:</b> this class assumes the stored integers are doc Ids (hence why it
   * extends {@link DocIdSet}). Therefore its {@link #iterator()} assumes {@link
   * DocIdSetIterator#NO_MORE_DOCS} can be used as sentinel. If you intent to use
   * this value, then make sure it's not used during search
   * flow.
   *
   * @lucene.internal
   */
  public class SortedVIntList extends DocIdSet {
    /** When a BitSet has fewer than 1 in BITS2VINTLIST_SIZE bits set,
     * a SortedVIntList representing the index numbers of the set bits
     * will be smaller than that BitSet.
     */
    final static int BITS2VINTLIST_SIZE = 8;
  
    private int size;
    private byte[] bytes;
    private int lastBytePos;
      
    /**
     *  Create a SortedVIntList from all elements of an array of integers.
     *
     * @param  sortedInts  A sorted array of non negative integers.
     */
    public SortedVIntList(int... sortedInts) {
      this(sortedInts, sortedInts.length);
    }
  
    /**
     * Create a SortedVIntList from an array of integers.
     * @param  sortedInts  An array of sorted non negative integers.
     * @param  inputSize   The number of integers to be used from the array.
     */
    public SortedVIntList(int[] sortedInts, int inputSize) {
      SortedVIntListBuilder builder = new SortedVIntListBuilder();
      for (int i = 0; i < inputSize; i++) {
        builder.addInt(sortedInts[i]);
      }
      builder.done();
    }
  
    /**
     * Create a SortedVIntList from a BitSet.
     * @param  bits  A bit set representing a set of integers.
     */
    public SortedVIntList(BitSet bits) {
      SortedVIntListBuilder builder = new SortedVIntListBuilder();
      int nextInt = bits.nextSetBit(0);
      while (nextInt != -1) {
        builder.addInt(nextInt);
        nextInt = bits.nextSetBit(nextInt + 1);
      }
      builder.done();
    }
  
    /**
     * Create a SortedVIntList.
     * @param  docIdSetIterator  An iterator providing document numbers as a set of integers.
     *                  This DocIdSetIterator is iterated completely when this constructor
     *                  is called and it must provide the integers in non
     *                  decreasing order.
     */
    public SortedVIntList(DocIdSetIterator docIdSetIterator) throws IOException {
      SortedVIntListBuilder builder = new SortedVIntListBuilder();
      int doc;
      while ((doc = docIdSetIterator.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
        builder.addInt(doc);
      }
      builder.done();
    }
  
  
    private class SortedVIntListBuilder {
      private int lastInt = 0;
      
      SortedVIntListBuilder() {
        initBytes();
        lastInt = 0;
      }
  
      void addInt(int nextInt) {
        int diff = nextInt - lastInt;
        if (diff < 0) {
          throw new IllegalArgumentException(
              "Input not sorted or first element negative.");
        }
    
        if ((lastBytePos + MAX_BYTES_PER_INT) > bytes.length) {
          // Biggest possible int does not fit.
          resizeBytes(ArrayUtil.oversize(lastBytePos + MAX_BYTES_PER_INT, 1));
        }
    
        // See org.apache.lucene.store.IndexOutput.writeVInt()
        while ((diff & ~VB1) != 0) { // The high bit of the next byte needs to be set.
          bytes[lastBytePos++] = (byte) ((diff & VB1) | ~VB1);
          diff >>>= BIT_SHIFT;
        }
        bytes[lastBytePos++] = (byte) diff; // Last byte, high bit not set.
        size++;
        lastInt = nextInt;
      }
      
      void done() {
        resizeBytes(lastBytePos);
      }
    }
  
  
    private void initBytes() {
      size = 0;
      bytes = new byte[128]; // initial byte size
      lastBytePos = 0;
    }
  
    private void resizeBytes(int newSize) {
      if (newSize != bytes.length) {
        byte[] newBytes = new byte[newSize];
        System.arraycopy(bytes, 0, newBytes, 0, lastBytePos);
        bytes = newBytes;
      }
    }
  
    private static final int VB1 = 0x7F;
    private static final int BIT_SHIFT = 7;
    private final int MAX_BYTES_PER_INT = (31 / BIT_SHIFT) + 1;
  
    /**
     * @return    The total number of sorted integers.
     */
    public int size() {
      return size;
    }
  
    /**
     * @return The size of the byte array storing the compressed sorted integers.
     */
    public int getByteSize() {
      return bytes.length;
    }
  
    /** This DocIdSet implementation is cacheable. */
    @Override
    public boolean isCacheable() {
      return true;
    }
  
    /**
     * @return    An iterator over the sorted integers.
     */
    @Override
    public DocIdSetIterator iterator() {
      return new DocIdSetIterator() {
        int bytePos = 0;
        int lastInt = 0;
        int doc = -1;
        
        private void advance() {
          // See org.apache.lucene.store.IndexInput.readVInt()
          byte b = bytes[bytePos++];
          lastInt += b & VB1;
          for (int s = BIT_SHIFT; (b & ~VB1) != 0; s += BIT_SHIFT) {
            b = bytes[bytePos++];
            lastInt += (b & VB1) << s;
          }
        }
        
        @Override
        public int docID() {
          return doc;
        }
        
        @Override
        public int nextDoc() {
          if (bytePos >= lastBytePos) {
            doc = NO_MORE_DOCS;
          } else {
            advance();
            doc = lastInt;
          }
          return doc;
        }
        
        @Override
        public int advance(int target) {
          while (bytePos < lastBytePos) {
            advance();
            if (lastInt >= target) {
              return doc = lastInt;
            }
          }
          return doc = NO_MORE_DOCS;
        }
        
      };
    }
  }
  
  