lucene-java-3.5.0/lucene/src/java/org/apache/lucene/util/OpenBitSet.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.util.Arrays;
  21 import java.io.Serializable;
  22
  23 import org.apache.lucene.search.DocIdSet;
  24 import org.apache.lucene.search.DocIdSetIterator;
  25
  26 /** An "open" BitSet implementation that allows direct access to the array of words
  27  * storing the bits.
  28  * <p/>
  29  * Unlike java.util.bitset, the fact that bits are packed into an array of longs
  30  * is part of the interface.  This allows efficient implementation of other algorithms
  31  * by someone other than the author.  It also allows one to efficiently implement
  32  * alternate serialization or interchange formats.
  33  * <p/>
  34  * <code>OpenBitSet</code> is faster than <code>java.util.BitSet</code> in most operations
  35  * and *much* faster at calculating cardinality of sets and results of set operations.
  36  * It can also handle sets of larger cardinality (up to 64 * 2**32-1)
  37  * <p/>
  38  * The goals of <code>OpenBitSet</code> are the fastest implementation possible, and
  39  * maximum code reuse.  Extra safety and encapsulation
  40  * may always be built on top, but if that's built in, the cost can never be removed (and
  41  * hence people re-implement their own version in order to get better performance).
  42  * If you want a "safe", totally encapsulated (and slower and limited) BitSet
  43  * class, use <code>java.util.BitSet</code>.
  44  * <p/>
  45  * <h3>Performance Results</h3>
  46  *
  47  Test system: Pentium 4, Sun Java 1.5_06 -server -Xbatch -Xmx64M
  48 <br/>BitSet size = 1,000,000
  49 <br/>Results are java.util.BitSet time divided by OpenBitSet time.
  50 <table border="1">
  51  <tr>
  52   <th></th> <th>cardinality</th> <th>intersect_count</th> <th>union</th> <th>nextSetBit</th> <th>get</th> <th>iterator</th>
  53  </tr>
  54  <tr>
  55   <th>50% full</th> <td>3.36</td> <td>3.96</td> <td>1.44</td> <td>1.46</td> <td>1.99</td> <td>1.58</td>
  56  </tr>
  57  <tr>
  58    <th>1% full</th> <td>3.31</td> <td>3.90</td> <td>&nbsp;</td> <td>1.04</td> <td>&nbsp;</td> <td>0.99</td>
  59  </tr>
  60 </table>
  61 <br/>
  62 Test system: AMD Opteron, 64 bit linux, Sun Java 1.5_06 -server -Xbatch -Xmx64M
  63 <br/>BitSet size = 1,000,000
  64 <br/>Results are java.util.BitSet time divided by OpenBitSet time.
  65 <table border="1">
  66  <tr>
  67   <th></th> <th>cardinality</th> <th>intersect_count</th> <th>union</th> <th>nextSetBit</th> <th>get</th> <th>iterator</th>
  68  </tr>
  69  <tr>
  70   <th>50% full</th> <td>2.50</td> <td>3.50</td> <td>1.00</td> <td>1.03</td> <td>1.12</td> <td>1.25</td>
  71  </tr>
  72  <tr>
  73    <th>1% full</th> <td>2.51</td> <td>3.49</td> <td>&nbsp;</td> <td>1.00</td> <td>&nbsp;</td> <td>1.02</td>
  74  </tr>
  75 </table>
  76  */
  77
  78 public class OpenBitSet extends DocIdSet implements Cloneable, Serializable, Bits {
  79   protected long[] bits;
  80   protected int wlen;   // number of words (elements) used in the array
  81
  82   // Used only for assert:
  83   private long numBits;
  84
  85   /** Constructs an OpenBitSet large enough to hold numBits.
  86    *
  87    * @param numBits
  88    */
  89   public OpenBitSet(long numBits) {
  90     this.numBits = numBits;
  91     bits = new long[bits2words(numBits)];
  92     wlen = bits.length;
  93   }
  94
  95   public OpenBitSet() {
  96     this(64);
  97   }
  98
  99   /** Constructs an OpenBitSet from an existing long[].
 100    * <br/>
 101    * The first 64 bits are in long[0],
 102    * with bit index 0 at the least significant bit, and bit index 63 at the most significant.
 103    * Given a bit index,
 104    * the word containing it is long[index/64], and it is at bit number index%64 within that word.
 105    * <p>
 106    * numWords are the number of elements in the array that contain
 107    * set bits (non-zero longs).
 108    * numWords should be &lt= bits.length, and
 109    * any existing words in the array at position &gt= numWords should be zero.
 110    *
 111    */
 112   public OpenBitSet(long[] bits, int numWords) {
 113     this.bits = bits;
 114     this.wlen = numWords;
 115     this.numBits = wlen * 64;
 116   }
 117
 118   @Override
 119   public DocIdSetIterator iterator() {
 120     return new OpenBitSetIterator(bits, wlen);
 121   }
 122
 123   /** This DocIdSet implementation is cacheable. */
 124   @Override
 125   public boolean isCacheable() {
 126     return true;
 127   }
 128
 129   /** Returns the current capacity in bits (1 greater than the index of the last bit) */
 130   public long capacity() { return bits.length << 6; }
 131
 132  /**
 133   * Returns the current capacity of this set.  Included for
 134   * compatibility.  This is *not* equal to {@link #cardinality}
 135   */
 136   public long size() {
 137       return capacity();
 138   }
 139
 140   public int length() {
 141     return bits.length << 6;
 142   }
 143
 144   /** Returns true if there are no set bits */
 145   public boolean isEmpty() { return cardinality()==0; }
 146
 147   /** Expert: returns the long[] storing the bits */
 148   public long[] getBits() { return bits; }
 149
 150   /** Expert: sets a new long[] to use as the bit storage */
 151   public void setBits(long[] bits) { this.bits = bits; }
 152
 153   /** Expert: gets the number of longs in the array that are in use */
 154   public int getNumWords() { return wlen; }
 155
 156   /** Expert: sets the number of longs in the array that are in use */
 157   public void setNumWords(int nWords) { this.wlen=nWords; }
 158
 159
 160
 161   /** Returns true or false for the specified bit index. */
 162   public boolean get(int index) {
 163     int i = index >> 6;               // div 64
 164     // signed shift will keep a negative index and force an
 165     // array-index-out-of-bounds-exception, removing the need for an explicit check.
 166     if (i>=bits.length) return false;
 167
 168     int bit = index & 0x3f;           // mod 64
 169     long bitmask = 1L << bit;
 170     return (bits[i] & bitmask) != 0;
 171   }
 172
 173
 174  /** Returns true or false for the specified bit index.
 175    * The index should be less than the OpenBitSet size
 176    */
 177   public boolean fastGet(int index) {
 178     assert index >= 0 && index < numBits;
 179     int i = index >> 6;               // div 64
 180     // signed shift will keep a negative index and force an
 181     // array-index-out-of-bounds-exception, removing the need for an explicit check.
 182     int bit = index & 0x3f;           // mod 64
 183     long bitmask = 1L << bit;
 184     return (bits[i] & bitmask) != 0;
 185   }
 186
 187
 188
 189  /** Returns true or false for the specified bit index
 190   */
 191   public boolean get(long index) {
 192     int i = (int)(index >> 6);             // div 64
 193     if (i>=bits.length) return false;
 194     int bit = (int)index & 0x3f;           // mod 64
 195     long bitmask = 1L << bit;
 196     return (bits[i] & bitmask) != 0;
 197   }
 198
 199   /** Returns true or false for the specified bit index.
 200    * The index should be less than the OpenBitSet size.
 201    */
 202   public boolean fastGet(long index) {
 203     assert index >= 0 && index < numBits;
 204     int i = (int)(index >> 6);               // div 64
 205     int bit = (int)index & 0x3f;           // mod 64
 206     long bitmask = 1L << bit;
 207     return (bits[i] & bitmask) != 0;
 208   }
 209
 210   /*
 211   // alternate implementation of get()
 212   public boolean get1(int index) {
 213     int i = index >> 6;                // div 64
 214     int bit = index & 0x3f;            // mod 64
 215     return ((bits[i]>>>bit) & 0x01) != 0;
 216     // this does a long shift and a bittest (on x86) vs
 217     // a long shift, and a long AND, (the test for zero is prob a no-op)
 218     // testing on a P4 indicates this is slower than (bits[i] & bitmask) != 0;
 219   }
 220   */
 221
 222
 223   /** returns 1 if the bit is set, 0 if not.
 224    * The index should be less than the OpenBitSet size
 225    */
 226   public int getBit(int index) {
 227     assert index >= 0 && index < numBits;
 228     int i = index >> 6;                // div 64
 229     int bit = index & 0x3f;            // mod 64
 230     return ((int)(bits[i]>>>bit)) & 0x01;
 231   }
 232
 233
 234   /*
 235   public boolean get2(int index) {
 236     int word = index >> 6;            // div 64
 237     int bit = index & 0x0000003f;     // mod 64
 238     return (bits[word] << bit) < 0;   // hmmm, this would work if bit order were reversed
 239     // we could right shift and check for parity bit, if it was available to us.
 240   }
 241   */
 242
 243   /** sets a bit, expanding the set size if necessary */
 244   public void set(long index) {
 245     int wordNum = expandingWordNum(index);
 246     int bit = (int)index & 0x3f;
 247     long bitmask = 1L << bit;
 248     bits[wordNum] |= bitmask;
 249   }
 250
 251
 252  /** Sets the bit at the specified index.
 253   * The index should be less than the OpenBitSet size.
 254   */
 255   public void fastSet(int index) {
 256     assert index >= 0 && index < numBits;
 257     int wordNum = index >> 6;      // div 64
 258     int bit = index & 0x3f;     // mod 64
 259     long bitmask = 1L << bit;
 260     bits[wordNum] |= bitmask;
 261   }
 262
 263  /** Sets the bit at the specified index.
 264   * The index should be less than the OpenBitSet size.
 265   */
 266   public void fastSet(long index) {
 267     assert index >= 0 && index < numBits;
 268     int wordNum = (int)(index >> 6);
 269     int bit = (int)index & 0x3f;
 270     long bitmask = 1L << bit;
 271     bits[wordNum] |= bitmask;
 272   }
 273
 274   /** Sets a range of bits, expanding the set size if necessary
 275    *
 276    * @param startIndex lower index
 277    * @param endIndex one-past the last bit to set
 278    */
 279   public void set(long startIndex, long endIndex) {
 280     if (endIndex <= startIndex) return;
 281
 282     int startWord = (int)(startIndex>>6);
 283
 284     // since endIndex is one past the end, this is index of the last
 285     // word to be changed.
 286     int endWord   = expandingWordNum(endIndex-1);
 287
 288     long startmask = -1L << startIndex;
 289     long endmask = -1L >>> -endIndex;  // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
 290
 291     if (startWord == endWord) {
 292       bits[startWord] |= (startmask & endmask);
 293       return;
 294     }
 295
 296     bits[startWord] |= startmask;
 297     Arrays.fill(bits, startWord+1, endWord, -1L);
 298     bits[endWord] |= endmask;
 299   }
 300
 301
 302
 303   protected int expandingWordNum(long index) {
 304     int wordNum = (int)(index >> 6);
 305     if (wordNum>=wlen) {
 306       ensureCapacity(index+1);
 307       wlen = wordNum+1;
 308     }
 309     assert (numBits = Math.max(numBits, index+1)) >= 0;
 310     return wordNum;
 311   }
 312
 313
 314   /** clears a bit.
 315    * The index should be less than the OpenBitSet size.
 316    */
 317   public void fastClear(int index) {
 318     assert index >= 0 && index < numBits;
 319     int wordNum = index >> 6;
 320     int bit = index & 0x03f;
 321     long bitmask = 1L << bit;
 322     bits[wordNum] &= ~bitmask;
 323     // hmmm, it takes one more instruction to clear than it does to set... any
 324     // way to work around this?  If there were only 63 bits per word, we could
 325     // use a right shift of 10111111...111 in binary to position the 0 in the
 326     // correct place (using sign extension).
 327     // Could also use Long.rotateRight() or rotateLeft() *if* they were converted
 328     // by the JVM into a native instruction.
 329     // bits[word] &= Long.rotateLeft(0xfffffffe,bit);
 330   }
 331
 332   /** clears a bit.
 333    * The index should be less than the OpenBitSet size.
 334    */
 335   public void fastClear(long index) {
 336     assert index >= 0 && index < numBits;
 337     int wordNum = (int)(index >> 6); // div 64
 338     int bit = (int)index & 0x3f;     // mod 64
 339     long bitmask = 1L << bit;
 340     bits[wordNum] &= ~bitmask;
 341   }
 342
 343   /** clears a bit, allowing access beyond the current set size without changing the size.*/
 344   public void clear(long index) {
 345     int wordNum = (int)(index >> 6); // div 64
 346     if (wordNum>=wlen) return;
 347     int bit = (int)index & 0x3f;     // mod 64
 348     long bitmask = 1L << bit;
 349     bits[wordNum] &= ~bitmask;
 350   }
 351
 352   /** Clears a range of bits.  Clearing past the end does not change the size of the set.
 353    *
 354    * @param startIndex lower index
 355    * @param endIndex one-past the last bit to clear
 356    */
 357   public void clear(int startIndex, int endIndex) {
 358     if (endIndex <= startIndex) return;
 359
 360     int startWord = (startIndex>>6);
 361     if (startWord >= wlen) return;
 362
 363     // since endIndex is one past the end, this is index of the last
 364     // word to be changed.
 365     int endWord   = ((endIndex-1)>>6);
 366
 367     long startmask = -1L << startIndex;
 368     long endmask = -1L >>> -endIndex;  // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
 369
 370     // invert masks since we are clearing
 371     startmask = ~startmask;
 372     endmask = ~endmask;
 373
 374     if (startWord == endWord) {
 375       bits[startWord] &= (startmask | endmask);
 376       return;
 377     }
 378
 379     bits[startWord] &= startmask;
 380
 381     int middle = Math.min(wlen, endWord);
 382     Arrays.fill(bits, startWord+1, middle, 0L);
 383     if (endWord < wlen) {
 384       bits[endWord] &= endmask;
 385     }
 386   }
 387
 388
 389   /** Clears a range of bits.  Clearing past the end does not change the size of the set.
 390    *
 391    * @param startIndex lower index
 392    * @param endIndex one-past the last bit to clear
 393    */
 394   public void clear(long startIndex, long endIndex) {
 395     if (endIndex <= startIndex) return;
 396
 397     int startWord = (int)(startIndex>>6);
 398     if (startWord >= wlen) return;
 399
 400     // since endIndex is one past the end, this is index of the last
 401     // word to be changed.
 402     int endWord   = (int)((endIndex-1)>>6);
 403
 404     long startmask = -1L << startIndex;
 405     long endmask = -1L >>> -endIndex;  // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
 406
 407     // invert masks since we are clearing
 408     startmask = ~startmask;
 409     endmask = ~endmask;
 410
 411     if (startWord == endWord) {
 412       bits[startWord] &= (startmask | endmask);
 413       return;
 414     }
 415
 416     bits[startWord] &= startmask;
 417
 418     int middle = Math.min(wlen, endWord);
 419     Arrays.fill(bits, startWord+1, middle, 0L);
 420     if (endWord < wlen) {
 421       bits[endWord] &= endmask;
 422     }
 423   }
 424
 425
 426
 427   /** Sets a bit and returns the previous value.
 428    * The index should be less than the OpenBitSet size.
 429    */
 430   public boolean getAndSet(int index) {
 431     assert index >= 0 && index < numBits;
 432     int wordNum = index >> 6;      // div 64
 433     int bit = index & 0x3f;     // mod 64
 434     long bitmask = 1L << bit;
 435     boolean val = (bits[wordNum] & bitmask) != 0;
 436     bits[wordNum] |= bitmask;
 437     return val;
 438   }
 439
 440   /** Sets a bit and returns the previous value.
 441    * The index should be less than the OpenBitSet size.
 442    */
 443   public boolean getAndSet(long index) {
 444     assert index >= 0 && index < numBits;
 445     int wordNum = (int)(index >> 6);      // div 64
 446     int bit = (int)index & 0x3f;     // mod 64
 447     long bitmask = 1L << bit;
 448     boolean val = (bits[wordNum] & bitmask) != 0;
 449     bits[wordNum] |= bitmask;
 450     return val;
 451   }
 452
 453   /** flips a bit.
 454    * The index should be less than the OpenBitSet size.
 455    */
 456   public void fastFlip(int index) {
 457     assert index >= 0 && index < numBits;
 458     int wordNum = index >> 6;      // div 64
 459     int bit = index & 0x3f;     // mod 64
 460     long bitmask = 1L << bit;
 461     bits[wordNum] ^= bitmask;
 462   }
 463
 464   /** flips a bit.
 465    * The index should be less than the OpenBitSet size.
 466    */
 467   public void fastFlip(long index) {
 468     assert index >= 0 && index < numBits;
 469     int wordNum = (int)(index >> 6);   // div 64
 470     int bit = (int)index & 0x3f;       // mod 64
 471     long bitmask = 1L << bit;
 472     bits[wordNum] ^= bitmask;
 473   }
 474
 475   /** flips a bit, expanding the set size if necessary */
 476   public void flip(long index) {
 477     int wordNum = expandingWordNum(index);
 478     int bit = (int)index & 0x3f;       // mod 64
 479     long bitmask = 1L << bit;
 480     bits[wordNum] ^= bitmask;
 481   }
 482
 483   /** flips a bit and returns the resulting bit value.
 484    * The index should be less than the OpenBitSet size.
 485    */
 486   public boolean flipAndGet(int index) {
 487     assert index >= 0 && index < numBits;
 488     int wordNum = index >> 6;      // div 64
 489     int bit = index & 0x3f;     // mod 64
 490     long bitmask = 1L << bit;
 491     bits[wordNum] ^= bitmask;
 492     return (bits[wordNum] & bitmask) != 0;
 493   }
 494
 495   /** flips a bit and returns the resulting bit value.
 496    * The index should be less than the OpenBitSet size.
 497    */
 498   public boolean flipAndGet(long index) {
 499     assert index >= 0 && index < numBits;
 500     int wordNum = (int)(index >> 6);   // div 64
 501     int bit = (int)index & 0x3f;       // mod 64
 502     long bitmask = 1L << bit;
 503     bits[wordNum] ^= bitmask;
 504     return (bits[wordNum] & bitmask) != 0;
 505   }
 506
 507   /** Flips a range of bits, expanding the set size if necessary
 508    *
 509    * @param startIndex lower index
 510    * @param endIndex one-past the last bit to flip
 511    */
 512   public void flip(long startIndex, long endIndex) {
 513     if (endIndex <= startIndex) return;
 514     int startWord = (int)(startIndex>>6);
 515
 516     // since endIndex is one past the end, this is index of the last
 517     // word to be changed.
 518     int endWord   = expandingWordNum(endIndex-1);
 519
 520     /*** Grrr, java shifting wraps around so -1L>>>64 == -1
 521      * for that reason, make sure not to use endmask if the bits to flip will
 522      * be zero in the last word (redefine endWord to be the last changed...)
 523     long startmask = -1L << (startIndex & 0x3f);     // example: 11111...111000
 524     long endmask = -1L >>> (64-(endIndex & 0x3f));   // example: 00111...111111
 525     ***/
 526
 527     long startmask = -1L << startIndex;
 528     long endmask = -1L >>> -endIndex;  // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
 529
 530     if (startWord == endWord) {
 531       bits[startWord] ^= (startmask & endmask);
 532       return;
 533     }
 534
 535     bits[startWord] ^= startmask;
 536
 537     for (int i=startWord+1; i<endWord; i++) {
 538       bits[i] = ~bits[i];
 539     }
 540
 541     bits[endWord] ^= endmask;
 542   }
 543
 544
 545   /*
 546   public static int pop(long v0, long v1, long v2, long v3) {
 547     // derived from pop_array by setting last four elems to 0.
 548     // exchanges one pop() call for 10 elementary operations
 549     // saving about 7 instructions... is there a better way?
 550       long twosA=v0 & v1;
 551       long ones=v0^v1;
 552
 553       long u2=ones^v2;
 554       long twosB =(ones&v2)|(u2&v3);
 555       ones=u2^v3;
 556
 557       long fours=(twosA&twosB);
 558       long twos=twosA^twosB;
 559
 560       return (pop(fours)<<2)
 561              + (pop(twos)<<1)
 562              + pop(ones);
 563
 564   }
 565   */
 566
 567
 568   /** @return the number of set bits */
 569   public long cardinality() {
 570     return BitUtil.pop_array(bits,0,wlen);
 571   }
 572
 573  /** Returns the popcount or cardinality of the intersection of the two sets.
 574    * Neither set is modified.
 575    */
 576   public static long intersectionCount(OpenBitSet a, OpenBitSet b) {
 577     return BitUtil.pop_intersect(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
 578  }
 579
 580   /** Returns the popcount or cardinality of the union of the two sets.
 581     * Neither set is modified.
 582     */
 583   public static long unionCount(OpenBitSet a, OpenBitSet b) {
 584     long tot = BitUtil.pop_union(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
 585     if (a.wlen < b.wlen) {
 586       tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen-a.wlen);
 587     } else if (a.wlen > b.wlen) {
 588       tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen);
 589     }
 590     return tot;
 591   }
 592
 593   /** Returns the popcount or cardinality of "a and not b"
 594    * or "intersection(a, not(b))".
 595    * Neither set is modified.
 596    */
 597   public static long andNotCount(OpenBitSet a, OpenBitSet b) {
 598     long tot = BitUtil.pop_andnot(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
 599     if (a.wlen > b.wlen) {
 600       tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen);
 601     }
 602     return tot;
 603   }
 604
 605  /** Returns the popcount or cardinality of the exclusive-or of the two sets.
 606   * Neither set is modified.
 607   */
 608   public static long xorCount(OpenBitSet a, OpenBitSet b) {
 609     long tot = BitUtil.pop_xor(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
 610     if (a.wlen < b.wlen) {
 611       tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen-a.wlen);
 612     } else if (a.wlen > b.wlen) {
 613       tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen);
 614     }
 615     return tot;
 616   }
 617
 618
 619   /** Returns the index of the first set bit starting at the index specified.
 620    *  -1 is returned if there are no more set bits.
 621    */
 622   public int nextSetBit(int index) {
 623     int i = index>>6;
 624     if (i>=wlen) return -1;
 625     int subIndex = index & 0x3f;      // index within the word
 626     long word = bits[i] >> subIndex;  // skip all the bits to the right of index
 627
 628     if (word!=0) {
 629       return (i<<6) + subIndex + BitUtil.ntz(word);
 630     }
 631
 632     while(++i < wlen) {
 633       word = bits[i];
 634       if (word!=0) return (i<<6) + BitUtil.ntz(word);
 635     }
 636
 637     return -1;
 638   }
 639
 640   /** Returns the index of the first set bit starting at the index specified.
 641    *  -1 is returned if there are no more set bits.
 642    */
 643   public long nextSetBit(long index) {
 644     int i = (int)(index>>>6);
 645     if (i>=wlen) return -1;
 646     int subIndex = (int)index & 0x3f; // index within the word
 647     long word = bits[i] >>> subIndex;  // skip all the bits to the right of index
 648
 649     if (word!=0) {
 650       return (((long)i)<<6) + (subIndex + BitUtil.ntz(word));
 651     }
 652
 653     while(++i < wlen) {
 654       word = bits[i];
 655       if (word!=0) return (((long)i)<<6) + BitUtil.ntz(word);
 656     }
 657
 658     return -1;
 659   }
 660
 661
 662   /** Returns the index of the first set bit starting downwards at
 663    *  the index specified.
 664    *  -1 is returned if there are no more set bits.
 665    */
 666   public int prevSetBit(int index) {
 667     int i = index >> 6;
 668     final int subIndex;
 669     long word;
 670     if (i >= wlen) {
 671       i = wlen - 1;
 672       if (i < 0) return -1;
 673       subIndex = 63;  // last possible bit
 674       word = bits[i];
 675     } else {
 676       if (i < 0) return -1;
 677       subIndex = index & 0x3f;  // index within the word
 678       word = (bits[i] << (63-subIndex));  // skip all the bits to the left of index
 679     }
 680
 681     if (word != 0) {
 682       return (i << 6) + subIndex - Long.numberOfLeadingZeros(word); // See LUCENE-3197
 683     }
 684
 685     while (--i >= 0) {
 686       word = bits[i];
 687       if (word !=0 ) {
 688         return (i << 6) + 63 - Long.numberOfLeadingZeros(word);
 689       }
 690     }
 691
 692     return -1;
 693   }
 694
 695   /** Returns the index of the first set bit starting downwards at
 696    *  the index specified.
 697    *  -1 is returned if there are no more set bits.
 698    */
 699   public long prevSetBit(long index) {
 700     int i = (int) (index >> 6);
 701     final int subIndex;
 702     long word;
 703     if (i >= wlen) {
 704       i = wlen - 1;
 705       if (i < 0) return -1;
 706       subIndex = 63;  // last possible bit
 707       word = bits[i];
 708     } else {
 709       if (i < 0) return -1;
 710       subIndex = (int)index & 0x3f;  // index within the word
 711       word = (bits[i] << (63-subIndex));  // skip all the bits to the left of index
 712     }
 713
 714     if (word != 0) {
 715       return (((long)i)<<6) + subIndex - Long.numberOfLeadingZeros(word); // See LUCENE-3197
 716     }
 717
 718     while (--i >= 0) {
 719       word = bits[i];
 720       if (word !=0 ) {
 721         return (((long)i)<<6) + 63 - Long.numberOfLeadingZeros(word);
 722       }
 723     }
 724
 725     return -1;
 726   }
 727
 728   @Override
 729   public Object clone() {
 730     try {
 731       OpenBitSet obs = (OpenBitSet)super.clone();
 732       obs.bits = obs.bits.clone();  // hopefully an array clone is as fast(er) than arraycopy
 733       return obs;
 734     } catch (CloneNotSupportedException e) {
 735       throw new RuntimeException(e);
 736     }
 737   }
 738
 739   /** this = this AND other */
 740   public void intersect(OpenBitSet other) {
 741     int newLen= Math.min(this.wlen,other.wlen);
 742     long[] thisArr = this.bits;
 743     long[] otherArr = other.bits;
 744     // testing against zero can be more efficient
 745     int pos=newLen;
 746     while(--pos>=0) {
 747       thisArr[pos] &= otherArr[pos];
 748     }
 749     if (this.wlen > newLen) {
 750       // fill zeros from the new shorter length to the old length
 751       Arrays.fill(bits,newLen,this.wlen,0);
 752     }
 753     this.wlen = newLen;
 754   }
 755
 756   /** this = this OR other */
 757   public void union(OpenBitSet other) {
 758     int newLen = Math.max(wlen,other.wlen);
 759     ensureCapacityWords(newLen);
 760     assert (numBits = Math.max(other.numBits, numBits)) >= 0;
 761
 762     long[] thisArr = this.bits;
 763     long[] otherArr = other.bits;
 764     int pos=Math.min(wlen,other.wlen);
 765     while(--pos>=0) {
 766       thisArr[pos] |= otherArr[pos];
 767     }
 768     if (this.wlen < newLen) {
 769       System.arraycopy(otherArr, this.wlen, thisArr, this.wlen, newLen-this.wlen);
 770     }
 771     this.wlen = newLen;
 772   }
 773
 774
 775   /** Remove all elements set in other. this = this AND_NOT other */
 776   public void remove(OpenBitSet other) {
 777     int idx = Math.min(wlen,other.wlen);
 778     long[] thisArr = this.bits;
 779     long[] otherArr = other.bits;
 780     while(--idx>=0) {
 781       thisArr[idx] &= ~otherArr[idx];
 782     }
 783   }
 784
 785   /** this = this XOR other */
 786   public void xor(OpenBitSet other) {
 787     int newLen = Math.max(wlen,other.wlen);
 788     ensureCapacityWords(newLen);
 789     assert (numBits = Math.max(other.numBits, numBits)) >= 0;
 790
 791     long[] thisArr = this.bits;
 792     long[] otherArr = other.bits;
 793     int pos=Math.min(wlen,other.wlen);
 794     while(--pos>=0) {
 795       thisArr[pos] ^= otherArr[pos];
 796     }
 797     if (this.wlen < newLen) {
 798       System.arraycopy(otherArr, this.wlen, thisArr, this.wlen, newLen-this.wlen);
 799     }
 800     this.wlen = newLen;
 801   }
 802
 803
 804   // some BitSet compatability methods
 805
 806   //** see {@link intersect} */
 807   public void and(OpenBitSet other) {
 808     intersect(other);
 809   }
 810
 811   //** see {@link union} */
 812   public void or(OpenBitSet other) {
 813     union(other);
 814   }
 815
 816   //** see {@link andNot} */
 817   public void andNot(OpenBitSet other) {
 818     remove(other);
 819   }
 820
 821   /** returns true if the sets have any elements in common */
 822   public boolean intersects(OpenBitSet other) {
 823     int pos = Math.min(this.wlen, other.wlen);
 824     long[] thisArr = this.bits;
 825     long[] otherArr = other.bits;
 826     while (--pos>=0) {
 827       if ((thisArr[pos] & otherArr[pos])!=0) return true;
 828     }
 829     return false;
 830   }
 831
 832
 833
 834   /** Expand the long[] with the size given as a number of words (64 bit longs).
 835    * getNumWords() is unchanged by this call.
 836    */
 837   public void ensureCapacityWords(int numWords) {
 838     if (bits.length < numWords) {
 839       bits = ArrayUtil.grow(bits, numWords);
 840     }
 841   }
 842
 843   /** Ensure that the long[] is big enough to hold numBits, expanding it if necessary.
 844    * getNumWords() is unchanged by this call.
 845    */
 846   public void ensureCapacity(long numBits) {
 847     ensureCapacityWords(bits2words(numBits));
 848   }
 849
 850   /** Lowers numWords, the number of words in use,
 851    * by checking for trailing zero words.
 852    */
 853   public void trimTrailingZeros() {
 854     int idx = wlen-1;
 855     while (idx>=0 && bits[idx]==0) idx--;
 856     wlen = idx+1;
 857   }
 858
 859   /** returns the number of 64 bit words it would take to hold numBits */
 860   public static int bits2words(long numBits) {
 861    return (int)(((numBits-1)>>>6)+1);
 862   }
 863
 864
 865   /** returns true if both sets have the same bits set */
 866   @Override
 867   public boolean equals(Object o) {
 868     if (this == o) return true;
 869     if (!(o instanceof OpenBitSet)) return false;
 870     OpenBitSet a;
 871     OpenBitSet b = (OpenBitSet)o;
 872     // make a the larger set.
 873     if (b.wlen > this.wlen) {
 874       a = b; b=this;
 875     } else {
 876       a=this;
 877     }
 878
 879     // check for any set bits out of the range of b
 880     for (int i=a.wlen-1; i>=b.wlen; i--) {
 881       if (a.bits[i]!=0) return false;
 882     }
 883
 884     for (int i=b.wlen-1; i>=0; i--) {
 885       if (a.bits[i] != b.bits[i]) return false;
 886     }
 887
 888     return true;
 889   }
 890
 891
 892   @Override
 893   public int hashCode() {
 894     // Start with a zero hash and use a mix that results in zero if the input is zero.
 895     // This effectively truncates trailing zeros without an explicit check.
 896     long h = 0;
 897     for (int i = bits.length; --i>=0;) {
 898       h ^= bits[i];
 899       h = (h << 1) | (h >>> 63); // rotate left
 900     }
 901     // fold leftmost bits into right and add a constant to prevent
 902     // empty sets from returning 0, which is too common.
 903     return (int)((h>>32) ^ h) + 0x98761234;
 904   }
 905
 906 }
 907
 908