lucene-java-3.5.0/lucene/src/java/org/apache/lucene/util/FixedBitSet.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 java.io.IOException;
  21 import java.util.Arrays;
  22
  23 import org.apache.lucene.search.DocIdSet;
  24 import org.apache.lucene.search.DocIdSetIterator;
  25
  26 // TODO: maybe merge with BitVector?  Problem is BitVector
  27 // caches its cardinality...
  28
  29 /** BitSet of fixed length (numBits), backed by accessible
  30  *  ({@link #getBits}) long[], accessed with an int index,
  31  *  implementing Bits and DocIdSet.  Unlike {@link
  32  *  OpenBitSet} this bit set does not auto-expand, cannot
  33  *  handle long index, and does not have fastXX/XX variants
  34  *  (just X).
  35  *
  36  * @lucene.internal
  37  **/
  38
  39 public final class FixedBitSet extends DocIdSet implements Bits {
  40   private final long[] bits;
  41   private int numBits;
  42
  43   /** returns the number of 64 bit words it would take to hold numBits */
  44   public static int bits2words(int numBits) {
  45     int numLong = numBits >>> 6;
  46     if ((numBits & 63) != 0) {
  47       numLong++;
  48     }
  49     return numLong;
  50   }
  51
  52   public FixedBitSet(int numBits) {
  53     this.numBits = numBits;
  54     bits = new long[bits2words(numBits)];
  55   }
  56
  57   /** Makes full copy. */
  58   public FixedBitSet(FixedBitSet other) {
  59     bits = new long[other.bits.length];
  60     System.arraycopy(other.bits, 0, bits, 0, bits.length);
  61     numBits = other.numBits;
  62   }
  63
  64   @Override
  65   public DocIdSetIterator iterator() {
  66     return new OpenBitSetIterator(bits, bits.length);
  67   }
  68
  69   public int length() {
  70     return numBits;
  71   }
  72
  73   /** This DocIdSet implementation is cacheable. */
  74   @Override
  75   public boolean isCacheable() {
  76     return true;
  77   }
  78
  79   /** Expert. */
  80   public long[] getBits() {
  81     return bits;
  82   }
  83
  84   /** Returns number of set bits.  NOTE: this visits every
  85    *  long in the backing bits array, and the result is not
  86    *  internally cached! */
  87   public int cardinality() {
  88     return (int) BitUtil.pop_array(bits, 0, bits.length);
  89   }
  90
  91   public boolean get(int index) {
  92     assert index >= 0 && index < numBits;
  93     int i = index >> 6;               // div 64
  94     // signed shift will keep a negative index and force an
  95     // array-index-out-of-bounds-exception, removing the need for an explicit check.
  96     int bit = index & 0x3f;           // mod 64
  97     long bitmask = 1L << bit;
  98     return (bits[i] & bitmask) != 0;
  99   }
 100
 101   public void set(int index) {
 102     assert index >= 0 && index < numBits;
 103     int wordNum = index >> 6;      // div 64
 104     int bit = index & 0x3f;     // mod 64
 105     long bitmask = 1L << bit;
 106     bits[wordNum] |= bitmask;
 107   }
 108
 109   public boolean getAndSet(int index) {
 110     assert index >= 0 && index < numBits;
 111     int wordNum = index >> 6;      // div 64
 112     int bit = index & 0x3f;     // mod 64
 113     long bitmask = 1L << bit;
 114     boolean val = (bits[wordNum] & bitmask) != 0;
 115     bits[wordNum] |= bitmask;
 116     return val;
 117   }
 118
 119   public void clear(int index) {
 120     assert index >= 0 && index < numBits;
 121     int wordNum = index >> 6;
 122     int bit = index & 0x03f;
 123     long bitmask = 1L << bit;
 124     bits[wordNum] &= ~bitmask;
 125   }
 126
 127   public boolean getAndClear(int index) {
 128     assert index >= 0 && index < numBits;
 129     int wordNum = index >> 6;      // div 64
 130     int bit = index & 0x3f;     // mod 64
 131     long bitmask = 1L << bit;
 132     boolean val = (bits[wordNum] & bitmask) != 0;
 133     bits[wordNum] &= ~bitmask;
 134     return val;
 135   }
 136
 137   /** Returns the index of the first set bit starting at the index specified.
 138    *  -1 is returned if there are no more set bits.
 139    */
 140   public int nextSetBit(int index) {
 141     assert index >= 0 && index < numBits;
 142     int i = index >> 6;
 143     final int subIndex = index & 0x3f;      // index within the word
 144     long word = bits[i] >> subIndex;  // skip all the bits to the right of index
 145
 146     if (word!=0) {
 147       return (i<<6) + subIndex + BitUtil.ntz(word);
 148     }
 149
 150     while(++i < bits.length) {
 151       word = bits[i];
 152       if (word != 0) {
 153         return (i<<6) + BitUtil.ntz(word);
 154       }
 155     }
 156
 157     return -1;
 158   }
 159
 160   /** Returns the index of the last set bit before or on the index specified.
 161    *  -1 is returned if there are no more set bits.
 162    */
 163   public int prevSetBit(int index) {
 164     assert index >= 0 && index < numBits: "index=" + index + " numBits=" + numBits;
 165     int i = index >> 6;
 166     final int subIndex = index & 0x3f;  // index within the word
 167     long word = (bits[i] << (63-subIndex));  // skip all the bits to the left of index
 168
 169     if (word != 0) {
 170       return (i << 6) + subIndex - Long.numberOfLeadingZeros(word); // See LUCENE-3197
 171     }
 172
 173     while (--i >= 0) {
 174       word = bits[i];
 175       if (word !=0 ) {
 176         return (i << 6) + 63 - Long.numberOfLeadingZeros(word);
 177       }
 178     }
 179
 180     return -1;
 181   }
 182
 183   /** Does in-place OR of the bits provided by the
 184    *  iterator. */
 185   public void or(DocIdSetIterator iter) throws IOException {
 186     if (iter instanceof OpenBitSetIterator && iter.docID() == -1) {
 187       final OpenBitSetIterator obs = (OpenBitSetIterator) iter;
 188       or(obs.arr, obs.words);
 189       // advance after last doc that would be accepted if standard
 190       // iteration is used (to exhaust it):
 191       obs.advance(numBits);
 192     } else {
 193       int doc;
 194       while ((doc = iter.nextDoc()) < numBits) {
 195         set(doc);
 196       }
 197     }
 198   }
 199
 200   /** this = this OR other */
 201   public void or(FixedBitSet other) {
 202     or(other.bits, other.bits.length);
 203   }
 204
 205   private void or(final long[] otherArr, final int otherLen) {
 206     final long[] thisArr = this.bits;
 207     int pos = Math.min(thisArr.length, otherLen);
 208     while (--pos >= 0) {
 209       thisArr[pos] |= otherArr[pos];
 210     }
 211   }
 212
 213   /** Does in-place AND of the bits provided by the
 214    *  iterator. */
 215   public void and(DocIdSetIterator iter) throws IOException {
 216     if (iter instanceof OpenBitSetIterator && iter.docID() == -1) {
 217       final OpenBitSetIterator obs = (OpenBitSetIterator) iter;
 218       and(obs.arr, obs.words);
 219       // advance after last doc that would be accepted if standard
 220       // iteration is used (to exhaust it):
 221       obs.advance(numBits);
 222     } else {
 223       if (numBits == 0) return;
 224       int disiDoc, bitSetDoc = nextSetBit(0);
 225       while (bitSetDoc != -1 && (disiDoc = iter.advance(bitSetDoc)) < numBits) {
 226         clear(bitSetDoc, disiDoc);
 227         disiDoc++;
 228         bitSetDoc = (disiDoc < numBits) ? nextSetBit(disiDoc) : -1;
 229       }
 230       if (bitSetDoc != -1) {
 231         clear(bitSetDoc, numBits);
 232       }
 233     }
 234   }
 235
 236   /** this = this AND other */
 237   public void and(FixedBitSet other) {
 238     and(other.bits, other.bits.length);
 239   }
 240
 241   private void and(final long[] otherArr, final int otherLen) {
 242     final long[] thisArr = this.bits;
 243     int pos = Math.min(thisArr.length, otherLen);
 244     while(--pos >= 0) {
 245       thisArr[pos] &= otherArr[pos];
 246     }
 247     if (thisArr.length > otherLen) {
 248       Arrays.fill(thisArr, otherLen, thisArr.length, 0L);
 249     }
 250   }
 251
 252   /** Does in-place AND NOT of the bits provided by the
 253    *  iterator. */
 254   public void andNot(DocIdSetIterator iter) throws IOException {
 255     if (iter instanceof OpenBitSetIterator && iter.docID() == -1) {
 256       final OpenBitSetIterator obs = (OpenBitSetIterator) iter;
 257       andNot(obs.arr, obs.words);
 258       // advance after last doc that would be accepted if standard
 259       // iteration is used (to exhaust it):
 260       obs.advance(numBits);
 261     } else {
 262       int doc;
 263       while ((doc = iter.nextDoc()) < numBits) {
 264         clear(doc);
 265       }
 266     }
 267   }
 268
 269   /** this = this AND NOT other */
 270   public void andNot(FixedBitSet other) {
 271     andNot(other.bits, other.bits.length);
 272   }
 273
 274   private void andNot(final long[] otherArr, final int otherLen) {
 275     final long[] thisArr = this.bits;
 276     int pos = Math.min(thisArr.length, otherLen);
 277     while(--pos >= 0) {
 278       thisArr[pos] &= ~otherArr[pos];
 279     }
 280   }
 281
 282   // NOTE: no .isEmpty() here because that's trappy (ie,
 283   // typically isEmpty is low cost, but this one wouldn't
 284   // be)
 285
 286   /** Flips a range of bits
 287    *
 288    * @param startIndex lower index
 289    * @param endIndex one-past the last bit to flip
 290    */
 291   public void flip(int startIndex, int endIndex) {
 292     assert startIndex >= 0 && startIndex < numBits;
 293     assert endIndex >= 0 && endIndex <= numBits;
 294     if (endIndex <= startIndex) {
 295       return;
 296     }
 297
 298     int startWord = startIndex >> 6;
 299     int endWord = (endIndex-1) >> 6;
 300
 301     /*** Grrr, java shifting wraps around so -1L>>>64 == -1
 302      * for that reason, make sure not to use endmask if the bits to flip will
 303      * be zero in the last word (redefine endWord to be the last changed...)
 304     long startmask = -1L << (startIndex & 0x3f);     // example: 11111...111000
 305     long endmask = -1L >>> (64-(endIndex & 0x3f));   // example: 00111...111111
 306     ***/
 307
 308     long startmask = -1L << startIndex;
 309     long endmask = -1L >>> -endIndex;  // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
 310
 311     if (startWord == endWord) {
 312       bits[startWord] ^= (startmask & endmask);
 313       return;
 314     }
 315
 316     bits[startWord] ^= startmask;
 317
 318     for (int i=startWord+1; i<endWord; i++) {
 319       bits[i] = ~bits[i];
 320     }
 321
 322     bits[endWord] ^= endmask;
 323   }
 324
 325   /** Sets a range of bits
 326    *
 327    * @param startIndex lower index
 328    * @param endIndex one-past the last bit to set
 329    */
 330   public void set(int startIndex, int endIndex) {
 331     assert startIndex >= 0 && startIndex < numBits;
 332     assert endIndex >= 0 && endIndex <= numBits;
 333     if (endIndex <= startIndex) {
 334       return;
 335     }
 336
 337     int startWord = startIndex >> 6;
 338     int endWord = (endIndex-1) >> 6;
 339
 340     long startmask = -1L << startIndex;
 341     long endmask = -1L >>> -endIndex;  // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
 342
 343     if (startWord == endWord) {
 344       bits[startWord] |= (startmask & endmask);
 345       return;
 346     }
 347
 348     bits[startWord] |= startmask;
 349     Arrays.fill(bits, startWord+1, endWord, -1L);
 350     bits[endWord] |= endmask;
 351   }
 352
 353   /** Clears a range of bits.
 354    *
 355    * @param startIndex lower index
 356    * @param endIndex one-past the last bit to clear
 357    */
 358   public void clear(int startIndex, int endIndex) {
 359     assert startIndex >= 0 && startIndex < numBits;
 360     assert endIndex >= 0 && endIndex <= numBits;
 361     if (endIndex <= startIndex) {
 362       return;
 363     }
 364
 365     int startWord = startIndex >> 6;
 366     int endWord = (endIndex-1) >> 6;
 367
 368     long startmask = -1L << startIndex;
 369     long endmask = -1L >>> -endIndex;  // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
 370
 371     // invert masks since we are clearing
 372     startmask = ~startmask;
 373     endmask = ~endmask;
 374
 375     if (startWord == endWord) {
 376       bits[startWord] &= (startmask | endmask);
 377       return;
 378     }
 379
 380     bits[startWord] &= startmask;
 381     Arrays.fill(bits, startWord+1, endWord, 0L);
 382     bits[endWord] &= endmask;
 383   }
 384
 385   @Override
 386   public Object clone() {
 387     return new FixedBitSet(this);
 388   }
 389
 390   /** returns true if both sets have the same bits set */
 391   @Override
 392   public boolean equals(Object o) {
 393     if (this == o) {
 394       return true;
 395     }
 396     if (!(o instanceof FixedBitSet)) {
 397       return false;
 398     }
 399     FixedBitSet other = (FixedBitSet) o;
 400     if (numBits != other.length()) {
 401       return false;
 402     }
 403     return Arrays.equals(bits, other.bits);
 404   }
 405
 406   @Override
 407   public int hashCode() {
 408     long h = 0;
 409     for (int i = bits.length; --i>=0;) {
 410       h ^= bits[i];
 411       h = (h << 1) | (h >>> 63); // rotate left
 412     }
 413     // fold leftmost bits into right and add a constant to prevent
 414     // empty sets from returning 0, which is too common.
 415     return (int) ((h>>32) ^ h) + 0x98761234;
 416   }
 417 }