content: /**
   * 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.
   */
  
  package org.apache.solr.util;
  
  import org.apache.lucene.util.OpenBitSet;
  
  /** An iterator to iterate over set bits in an OpenBitSet.
   * This is faster than nextSetBit() for iterating over the complete set of bits,
   * especially when the density of the bits set is high.
   *
   * @deprecated Use {@link org.apache.lucene.util.OpenBitSetIterator} instead.
   * @version $Id$
   */
  @Deprecated
  public class BitSetIterator {
  
    // The General Idea: instead of having an array per byte that has
    // the offsets of the next set bit, that array could be
    // packed inside a 32 bit integer (8 4 bit numbers).  That
    // should be faster than accessing an array for each index, and
    // the total array size is kept smaller (256*sizeof(int))=1K
    protected final static int[] bitlist={
      0x0,0x1,0x2,0x21,0x3,0x31,0x32,0x321,0x4,0x41,0x42,0x421,0x43,0x431,0x432,0x4321,0x5,0x51,0x52,0x521,0x53,0x531,0x532,0x5321,0x54,0x541,0x542,0x5421,0x543,0x5431,0x5432,0x54321,0x6,0x61,0x62,0x621,0x63,0x631,0x632,0x6321,0x64,0x641,0x642,0x6421,0x643,0x6431,0x6432,0x64321,0x65,0x651,0x652,0x6521,0x653,0x6531,0x6532,0x65321,0x654,0x6541,0x6542,0x65421,0x6543,0x65431,0x65432,0x654321,0x7,0x71,0x72,0x721,0x73,0x731,0x732,0x7321,0x74,0x741,0x742,0x7421,0x743,0x7431,0x7432,0x74321,0x75,0x751,0x752,0x7521,0x753,0x7531,0x7532,0x75321,0x754,0x7541,0x7542,0x75421,0x7543,0x75431,0x75432,0x754321,0x76,0x761,0x762,0x7621,0x763,0x7631,0x7632,0x76321,0x764,0x7641,0x7642,0x76421,0x7643,0x76431,0x76432,0x764321,0x765,0x7651,0x7652,0x76521,0x7653,0x76531,0x76532,0x765321,0x7654,0x76541,0x76542,0x765421,0x76543,0x765431,0x765432,0x7654321,0x8,0x81,0x82,0x821,0x83,0x831,0x832,0x8321,0x84,0x841,0x842,0x8421,0x843,0x8431,0x8432,0x84321,0x85,0x851,0x852,0x8521,0x853,0x8531,0x8532,0x85321,0x854,0x8541,0x8542,0x85421,0x8543,0x85431,0x85432,0x854321,0x86,0x861,0x862,0x8621,0x863,0x8631,0x8632,0x86321,0x864,0x8641,0x8642,0x86421,0x8643,0x86431,0x86432,0x864321,0x865,0x8651,0x8652,0x86521,0x8653,0x86531,0x86532,0x865321,0x8654,0x86541,0x86542,0x865421,0x86543,0x865431,0x865432,0x8654321,0x87,0x871,0x872,0x8721,0x873,0x8731,0x8732,0x87321,0x874,0x8741,0x8742,0x87421,0x8743,0x87431,0x87432,0x874321,0x875,0x8751,0x8752,0x87521,0x8753,0x87531,0x87532,0x875321,0x8754,0x87541,0x87542,0x875421,0x87543,0x875431,0x875432,0x8754321,0x876,0x8761,0x8762,0x87621,0x8763,0x87631,0x87632,0x876321,0x8764,0x87641,0x87642,0x876421,0x87643,0x876431,0x876432,0x8764321,0x8765,0x87651,0x87652,0x876521,0x87653,0x876531,0x876532,0x8765321,0x87654,0x876541,0x876542,0x8765421,0x876543,0x8765431,0x8765432,0x87654321
    };
    /***** the python code that generated bitlist
    def bits2int(val):
    arr=0
    for shift in range(8,0,-1):
      if val & 0x80:
        arr = (arr << 4) | shift
      val = val << 1
    return arr
  
    def int_table():
      tbl = [ hex(bits2int(val)).strip('L') for val in range(256) ]
      return ','.join(tbl)
    ******/
  
    // hmmm, what about an iterator that finds zeros though,
    // or a reverse iterator... should they be separate classes
    // for efficiency, or have a common root interface?  (or
    // maybe both?  could ask for a SetBitsIterator, etc...
  
  
    private final long[] arr;
    private final int words;
    private int i=-1;
    private long word;
    private int wordShift;
    private int indexArray;
  
    public BitSetIterator(OpenBitSet obs) {
      this(obs.getBits(), obs.getNumWords());
    }
  
    public BitSetIterator(long[] bits, int numWords) {
      arr = bits;
      words = numWords;
    }
  
    // 64 bit shifts
    private void shift() {
      if ((int)word ==0) {wordShift +=32; word = word >>>32; }
      if ((word & 0x0000FFFF) == 0) { wordShift +=16; word >>>=16; }
      if ((word & 0x000000FF) == 0) { wordShift +=8; word >>>=8; }
      indexArray = bitlist[(int)word & 0xff];
    }
  
    /***** alternate shift implementations
    // 32 bit shifts, but a long shift needed at the end
    private void shift2() {
      int y = (int)word;
      if (y==0) {wordShift +=32; y = (int)(word >>>32); }
      if ((y & 0x0000FFFF) == 0) { wordShift +=16; y>>>=16; }
      if ((y & 0x000000FF) == 0) { wordShift +=8; y>>>=8; }
      indexArray = bitlist[y & 0xff];
      word >>>= (wordShift +1);
    }
  
    private void shift3() {
      int lower = (int)word;
      int lowByte = lower & 0xff;
      if (lowByte != 0) {
        indexArray=bitlist[lowByte];
        return;
      }
      shift();
    }
    ******/
  
    public int next() {
      if (indexArray==0) {
        if (word!=0) {
          word >>>= 8;
          wordShift += 8;
        }
  
        while (word==0) {
          if (++i >= words) return -1;
          word = arr[i];
          wordShift =-1;  // loop invariant code motion should move this
        }
  
        // after the first time, should I go with a linear search, or
        // stick with the binary search in shift?
        shift();
      }
  
      int bitIndex = (indexArray & 0x0f) + wordShift;
      indexArray >>>= 4;
      // should i<<6 be cached as a separate variable?
      // it would only save one cycle in the best circumstances.
      return (i<<6) + bitIndex;
    }
  
    public int next(int fromIndex) {
      indexArray=0;
      i = fromIndex >> 6;
      if (i>=words) {
        word =0; // setup so next() will also return -1
        return -1;
      }
      wordShift = fromIndex & 0x3f;
      word = arr[i] >>> wordShift;
      if (word !=0) {
        wordShift--; // compensate for 1 based arrIndex
      } else {
        while (word ==0) {
          if (++i >= words) return -1;
          word = arr[i];
        }
        wordShift =-1;
      }
  
      shift();
  
      int bitIndex = (indexArray & 0x0f) + wordShift;
      indexArray >>>= 4;
      // should i<<6 be cached as a separate variable?
      // it would only save one cycle in the best circumstances.
      return (i<<6) + bitIndex;
    }
  
  }
  