lucene-java-3.4.0/lucene/src/java/org/apache/lucene/util/OpenBitSetIterator.java

   1 /**
   2  * Licensed to the Apache Software Foundation (ASF) under one or more
   3  * contributor license agreements.  See the NOTICE file distributed with
   4  * this work for additional information regarding copyright ownership.
   5  * The ASF licenses this file to You under the Apache License, Version 2.0
   6  * (the "License"); you may not use this file except in compliance with
   7  * the License.  You may obtain a copy of the License at
   8  *
   9  *     http://www.apache.org/licenses/LICENSE-2.0
  10  *
  11  * Unless required by applicable law or agreed to in writing, software
  12  * distributed under the License is distributed on an "AS IS" BASIS,
  13  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14  * See the License for the specific language governing permissions and
  15  * limitations under the License.
  16  */
  17
  18 package org.apache.lucene.util;
  19
  20 import org.apache.lucene.search.DocIdSetIterator;
  21
  22 /** An iterator to iterate over set bits in an OpenBitSet.
  23  * This is faster than nextSetBit() for iterating over the complete set of bits,
  24  * especially when the density of the bits set is high.
  25  */
  26 public class OpenBitSetIterator extends DocIdSetIterator {
  27
  28   // The General Idea: instead of having an array per byte that has
  29   // the offsets of the next set bit, that array could be
  30   // packed inside a 32 bit integer (8 4 bit numbers).  That
  31   // should be faster than accessing an array for each index, and
  32   // the total array size is kept smaller (256*sizeof(int))=1K
  33   protected final static int[] bitlist={
  34     0x0, 0x1, 0x2, 0x21, 0x3, 0x31, 0x32, 0x321, 0x4, 0x41, 0x42, 0x421, 0x43,
  35     0x431, 0x432, 0x4321, 0x5, 0x51, 0x52, 0x521, 0x53, 0x531, 0x532, 0x5321,
  36     0x54, 0x541, 0x542, 0x5421, 0x543, 0x5431, 0x5432, 0x54321, 0x6, 0x61, 0x62,
  37     0x621, 0x63, 0x631, 0x632, 0x6321, 0x64, 0x641, 0x642, 0x6421, 0x643,
  38     0x6431, 0x6432, 0x64321, 0x65, 0x651, 0x652, 0x6521, 0x653, 0x6531, 0x6532,
  39     0x65321, 0x654, 0x6541, 0x6542, 0x65421, 0x6543, 0x65431, 0x65432, 0x654321,
  40     0x7, 0x71, 0x72, 0x721, 0x73, 0x731, 0x732, 0x7321, 0x74, 0x741, 0x742,
  41     0x7421, 0x743, 0x7431, 0x7432, 0x74321, 0x75, 0x751, 0x752, 0x7521, 0x753,
  42     0x7531, 0x7532, 0x75321, 0x754, 0x7541, 0x7542, 0x75421, 0x7543, 0x75431,
  43     0x75432, 0x754321, 0x76, 0x761, 0x762, 0x7621, 0x763, 0x7631, 0x7632,
  44     0x76321, 0x764, 0x7641, 0x7642, 0x76421, 0x7643, 0x76431, 0x76432, 0x764321,
  45     0x765, 0x7651, 0x7652, 0x76521, 0x7653, 0x76531, 0x76532, 0x765321, 0x7654,
  46     0x76541, 0x76542, 0x765421, 0x76543, 0x765431, 0x765432, 0x7654321, 0x8,
  47     0x81, 0x82, 0x821, 0x83, 0x831, 0x832, 0x8321, 0x84, 0x841, 0x842, 0x8421,
  48     0x843, 0x8431, 0x8432, 0x84321, 0x85, 0x851, 0x852, 0x8521, 0x853, 0x8531,
  49     0x8532, 0x85321, 0x854, 0x8541, 0x8542, 0x85421, 0x8543, 0x85431, 0x85432,
  50     0x854321, 0x86, 0x861, 0x862, 0x8621, 0x863, 0x8631, 0x8632, 0x86321, 0x864,
  51     0x8641, 0x8642, 0x86421, 0x8643, 0x86431, 0x86432, 0x864321, 0x865, 0x8651,
  52     0x8652, 0x86521, 0x8653, 0x86531, 0x86532, 0x865321, 0x8654, 0x86541,
  53     0x86542, 0x865421, 0x86543, 0x865431, 0x865432, 0x8654321, 0x87, 0x871,
  54     0x872, 0x8721, 0x873, 0x8731, 0x8732, 0x87321, 0x874, 0x8741, 0x8742,
  55     0x87421, 0x8743, 0x87431, 0x87432, 0x874321, 0x875, 0x8751, 0x8752, 0x87521,
  56     0x8753, 0x87531, 0x87532, 0x875321, 0x8754, 0x87541, 0x87542, 0x875421,
  57     0x87543, 0x875431, 0x875432, 0x8754321, 0x876, 0x8761, 0x8762, 0x87621,
  58     0x8763, 0x87631, 0x87632, 0x876321, 0x8764, 0x87641, 0x87642, 0x876421,
  59     0x87643, 0x876431, 0x876432, 0x8764321, 0x8765, 0x87651, 0x87652, 0x876521,
  60     0x87653, 0x876531, 0x876532, 0x8765321, 0x87654, 0x876541, 0x876542,
  61     0x8765421, 0x876543, 0x8765431, 0x8765432, 0x87654321
  62   };
  63   /***** the python code that generated bitlist
  64   def bits2int(val):
  65   arr=0
  66   for shift in range(8,0,-1):
  67     if val & 0x80:
  68       arr = (arr << 4) | shift
  69     val = val << 1
  70   return arr
  71
  72   def int_table():
  73     tbl = [ hex(bits2int(val)).strip('L') for val in range(256) ]
  74     return ','.join(tbl)
  75   ******/
  76
  77   // hmmm, what about an iterator that finds zeros though,
  78   // or a reverse iterator... should they be separate classes
  79   // for efficiency, or have a common root interface?  (or
  80   // maybe both?  could ask for a SetBitsIterator, etc...
  81
  82   private final long[] arr;
  83   private final int words;
  84   private int i=-1;
  85   private long word;
  86   private int wordShift;
  87   private int indexArray;
  88   private int curDocId = -1;
  89
  90   public OpenBitSetIterator(OpenBitSet obs) {
  91     this(obs.getBits(), obs.getNumWords());
  92   }
  93
  94   public OpenBitSetIterator(long[] bits, int numWords) {
  95     arr = bits;
  96     words = numWords;
  97   }
  98
  99   // 64 bit shifts
 100   private void shift() {
 101     if ((int)word ==0) {wordShift +=32; word = word >>>32; }
 102     if ((word & 0x0000FFFF) == 0) { wordShift +=16; word >>>=16; }
 103     if ((word & 0x000000FF) == 0) { wordShift +=8; word >>>=8; }
 104     indexArray = bitlist[(int)word & 0xff];
 105   }
 106
 107   /***** alternate shift implementations
 108   // 32 bit shifts, but a long shift needed at the end
 109   private void shift2() {
 110     int y = (int)word;
 111     if (y==0) {wordShift +=32; y = (int)(word >>>32); }
 112     if ((y & 0x0000FFFF) == 0) { wordShift +=16; y>>>=16; }
 113     if ((y & 0x000000FF) == 0) { wordShift +=8; y>>>=8; }
 114     indexArray = bitlist[y & 0xff];
 115     word >>>= (wordShift +1);
 116   }
 117
 118   private void shift3() {
 119     int lower = (int)word;
 120     int lowByte = lower & 0xff;
 121     if (lowByte != 0) {
 122       indexArray=bitlist[lowByte];
 123       return;
 124     }
 125     shift();
 126   }
 127   ******/
 128
 129   @Override
 130   public int nextDoc() {
 131     if (indexArray == 0) {
 132       if (word != 0) {
 133         word >>>= 8;
 134         wordShift += 8;
 135       }
 136
 137       while (word == 0) {
 138         if (++i >= words) {
 139           return curDocId = NO_MORE_DOCS;
 140         }
 141         word = arr[i];
 142         wordShift = -1; // loop invariant code motion should move this
 143       }
 144
 145       // after the first time, should I go with a linear search, or
 146       // stick with the binary search in shift?
 147       shift();
 148     }
 149
 150     int bitIndex = (indexArray & 0x0f) + wordShift;
 151     indexArray >>>= 4;
 152     // should i<<6 be cached as a separate variable?
 153     // it would only save one cycle in the best circumstances.
 154     return curDocId = (i<<6) + bitIndex;
 155   }
 156
 157   @Override
 158   public int advance(int target) {
 159     indexArray = 0;
 160     i = target >> 6;
 161     if (i >= words) {
 162       word = 0; // setup so next() will also return -1
 163       return curDocId = NO_MORE_DOCS;
 164     }
 165     wordShift = target & 0x3f;
 166     word = arr[i] >>> wordShift;
 167     if (word != 0) {
 168       wordShift--; // compensate for 1 based arrIndex
 169     } else {
 170       while (word == 0) {
 171         if (++i >= words) {
 172           return curDocId = NO_MORE_DOCS;
 173         }
 174         word = arr[i];
 175       }
 176       wordShift = -1;
 177     }
 178
 179     shift();
 180
 181     int bitIndex = (indexArray & 0x0f) + wordShift;
 182     indexArray >>>= 4;
 183     // should i<<6 be cached as a separate variable?
 184     // it would only save one cycle in the best circumstances.
 185     return curDocId = (i<<6) + bitIndex;
 186   }
 187
 188   @Override
 189   public int docID() {
 190     return curDocId;
 191   }
 192
 193 }