lucene-java-3.4.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 {
  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     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   public int prevSetBit(int index) {
 161     assert index >= 0 && index < numBits: "index=" + index + " numBits=" + numBits;
 162     int i = index >> 6;
 163     final int subIndex;
 164     long word;
 165     subIndex = index & 0x3f;  // index within the word
 166     word = (bits[i] << (63-subIndex));  // skip all the bits to the left of index
 167
 168     if (word != 0) {
 169       return (i << 6) + subIndex - Long.numberOfLeadingZeros(word); // See LUCENE-3197
 170     }
 171
 172     while (--i >= 0) {
 173       word = bits[i];
 174       if (word !=0 ) {
 175         return (i << 6) + 63 - Long.numberOfLeadingZeros(word);
 176       }
 177     }
 178
 179     return -1;
 180   }
 181
 182   /** Does in-place OR of the bits provided by the
 183    *  iterator. */
 184   public void or(DocIdSetIterator iter) throws IOException {
 185     int doc;
 186     while ((doc = iter.nextDoc()) != DocIdSetIterator.NO_MORE_DOCS) {
 187       set(doc);
 188     }
 189   }
 190
 191   public void or(FixedBitSet other) {
 192     long[] thisArr = this.bits;
 193     long[] otherArr = other.bits;
 194     int pos = Math.min(thisArr.length, otherArr.length);
 195     while (--pos >= 0) {
 196       thisArr[pos] |= otherArr[pos];
 197     }
 198   }
 199
 200   // NOTE: no .isEmpty() here because that's trappy (ie,
 201   // typically isEmpty is low cost, but this one wouldn't
 202   // be)
 203
 204   /** Flips a range of bits
 205    *
 206    * @param startIndex lower index
 207    * @param endIndex one-past the last bit to flip
 208    */
 209   public void flip(int startIndex, int endIndex) {
 210     assert startIndex >= 0 && startIndex < numBits;
 211     assert endIndex >= 0 && endIndex <= numBits;
 212     if (endIndex <= startIndex) {
 213       return;
 214     }
 215
 216     int startWord = startIndex >> 6;
 217     int endWord = (endIndex-1) >> 6;
 218
 219     /*** Grrr, java shifting wraps around so -1L>>>64 == -1
 220      * for that reason, make sure not to use endmask if the bits to flip will
 221      * be zero in the last word (redefine endWord to be the last changed...)
 222     long startmask = -1L << (startIndex & 0x3f);     // example: 11111...111000
 223     long endmask = -1L >>> (64-(endIndex & 0x3f));   // example: 00111...111111
 224     ***/
 225
 226     long startmask = -1L << startIndex;
 227     long endmask = -1L >>> -endIndex;  // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
 228
 229     if (startWord == endWord) {
 230       bits[startWord] ^= (startmask & endmask);
 231       return;
 232     }
 233
 234     bits[startWord] ^= startmask;
 235
 236     for (int i=startWord+1; i<endWord; i++) {
 237       bits[i] = ~bits[i];
 238     }
 239
 240     bits[endWord] ^= endmask;
 241   }
 242
 243   /** Sets a range of bits
 244    *
 245    * @param startIndex lower index
 246    * @param endIndex one-past the last bit to set
 247    */
 248   public void set(int startIndex, int endIndex) {
 249     assert startIndex >= 0 && startIndex < numBits;
 250     assert endIndex >= 0 && endIndex <= numBits;
 251     if (endIndex <= startIndex) {
 252       return;
 253     }
 254
 255     int startWord = startIndex >> 6;
 256     int endWord = (endIndex-1) >> 6;
 257
 258     long startmask = -1L << startIndex;
 259     long endmask = -1L >>> -endIndex;  // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
 260
 261     if (startWord == endWord) {
 262       bits[startWord] |= (startmask & endmask);
 263       return;
 264     }
 265
 266     bits[startWord] |= startmask;
 267     Arrays.fill(bits, startWord+1, endWord, -1L);
 268     bits[endWord] |= endmask;
 269   }
 270
 271   /** Clears a range of bits.
 272    *
 273    * @param startIndex lower index
 274    * @param endIndex one-past the last bit to clear
 275    */
 276   public void clear(int startIndex, int endIndex) {
 277     assert startIndex >= 0 && startIndex < numBits;
 278     assert endIndex >= 0 && endIndex <= numBits;
 279     if (endIndex <= startIndex) {
 280       return;
 281     }
 282
 283     int startWord = startIndex >> 6;
 284     int endWord = (endIndex-1) >> 6;
 285
 286     long startmask = -1L << startIndex;
 287     long endmask = -1L >>> -endIndex;  // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
 288
 289     // invert masks since we are clearing
 290     startmask = ~startmask;
 291     endmask = ~endmask;
 292
 293     if (startWord == endWord) {
 294       bits[startWord] &= (startmask | endmask);
 295       return;
 296     }
 297
 298     bits[startWord] &= startmask;
 299     Arrays.fill(bits, startWord+1, endWord, 0L);
 300     bits[endWord] &= endmask;
 301   }
 302
 303   @Override
 304   public Object clone() {
 305     return new FixedBitSet(this);
 306   }
 307
 308   /** returns true if both sets have the same bits set */
 309   @Override
 310   public boolean equals(Object o) {
 311     if (this == o) {
 312       return true;
 313     }
 314     if (!(o instanceof FixedBitSet)) {
 315       return false;
 316     }
 317     FixedBitSet other = (FixedBitSet) o;
 318     if (numBits != other.length()) {
 319       return false;
 320     }
 321     return Arrays.equals(bits, other.bits);
 322   }
 323
 324   @Override
 325   public int hashCode() {
 326     long h = 0;
 327     for (int i = bits.length; --i>=0;) {
 328       h ^= bits[i];
 329       h = (h << 1) | (h >>> 63); // rotate left
 330     }
 331     // fold leftmost bits into right and add a constant to prevent
 332     // empty sets from returning 0, which is too common.
 333     return (int) ((h>>32) ^ h) + 0x98761234;
 334   }
 335 }