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