| 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> </td> <td>1.04</td> <td> </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> </td> <td>1.00</td> <td> </td> <td>1.02</td>
74 </tr>
75 </table>
76
77 * @version $Id$
78 */
79
80 public class OpenBitSet extends DocIdSet implements Cloneable, Serializable {
81 protected long[] bits;
82 protected int wlen; // number of words (elements) used in the array
83
84 /** Constructs an OpenBitSet large enough to hold numBits.
85 *
86 * @param numBits
87 */
88 public OpenBitSet(long numBits) {
89 bits = new long[bits2words(numBits)];
90 wlen = bits.length;
91 }
92
93 public OpenBitSet() {
94 this(64);
95 }
96
97 /** Constructs an OpenBitSet from an existing long[].
98 * <br/>
99 * The first 64 bits are in long[0],
100 * with bit index 0 at the least significant bit, and bit index 63 at the most significant.
101 * Given a bit index,
102 * the word containing it is long[index/64], and it is at bit number index%64 within that word.
103 * <p>
104 * numWords are the number of elements in the array that contain
105 * set bits (non-zero longs).
106 * numWords should be <= bits.length, and
107 * any existing words in the array at position >= numWords should be zero.
108 *
109 */
110 public OpenBitSet(long[] bits, int numWords) {
111 this.bits = bits;
112 this.wlen = numWords;
113 }
114
115 public DocIdSetIterator iterator() {
116 return new OpenBitSetIterator(bits, wlen);
117 }
118
119 /** Returns the current capacity in bits (1 greater than the index of the last bit) */
120 public long capacity() { return bits.length << 6; }
121
122 /**
123 * Returns the current capacity of this set. Included for
124 * compatibility. This is *not* equal to {@link #cardinality}
125 */
126 public long size() {
127 return capacity();
128 }
129
130 /** Returns true if there are no set bits */
131 public boolean isEmpty() { return cardinality()==0; }
132
133 /** Expert: returns the long[] storing the bits */
134 public long[] getBits() { return bits; }
135
136 /** Expert: sets a new long[] to use as the bit storage */
137 public void setBits(long[] bits) { this.bits = bits; }
138
139 /** Expert: gets the number of longs in the array that are in use */
140 public int getNumWords() { return wlen; }
141
142 /** Expert: sets the number of longs in the array that are in use */
143 public void setNumWords(int nWords) { this.wlen=nWords; }
144
145
146
147 /** Returns true or false for the specified bit index. */
148 public boolean get(int index) {
149 int i = index >> 6; // div 64
150 // signed shift will keep a negative index and force an
151 // array-index-out-of-bounds-exception, removing the need for an explicit check.
152 if (i>=bits.length) return false;
153
154 int bit = index & 0x3f; // mod 64
155 long bitmask = 1L << bit;
156 return (bits[i] & bitmask) != 0;
157 }
158
159
160 /** Returns true or false for the specified bit index.
161 * The index should be less than the OpenBitSet size
162 */
163 public boolean fastGet(int index) {
164 int i = index >> 6; // div 64
165 // signed shift will keep a negative index and force an
166 // array-index-out-of-bounds-exception, removing the need for an explicit check.
167 int bit = index & 0x3f; // mod 64
168 long bitmask = 1L << bit;
169 return (bits[i] & bitmask) != 0;
170 }
171
172
173
174 /** Returns true or false for the specified bit index
175 */
176 public boolean get(long index) {
177 int i = (int)(index >> 6); // div 64
178 if (i>=bits.length) return false;
179 int bit = (int)index & 0x3f; // mod 64
180 long bitmask = 1L << bit;
181 return (bits[i] & bitmask) != 0;
182 }
183
184 /** Returns true or false for the specified bit index.
185 * The index should be less than the OpenBitSet size.
186 */
187 public boolean fastGet(long index) {
188 int i = (int)(index >> 6); // div 64
189 int bit = (int)index & 0x3f; // mod 64
190 long bitmask = 1L << bit;
191 return (bits[i] & bitmask) != 0;
192 }
193
194 /*
195 // alternate implementation of get()
196 public boolean get1(int index) {
197 int i = index >> 6; // div 64
198 int bit = index & 0x3f; // mod 64
199 return ((bits[i]>>>bit) & 0x01) != 0;
200 // this does a long shift and a bittest (on x86) vs
201 // a long shift, and a long AND, (the test for zero is prob a no-op)
202 // testing on a P4 indicates this is slower than (bits[i] & bitmask) != 0;
203 }
204 */
205
206
207 /** returns 1 if the bit is set, 0 if not.
208 * The index should be less than the OpenBitSet size
209 */
210 public int getBit(int index) {
211 int i = index >> 6; // div 64
212 int bit = index & 0x3f; // mod 64
213 return ((int)(bits[i]>>>bit)) & 0x01;
214 }
215
216
217 /*
218 public boolean get2(int index) {
219 int word = index >> 6; // div 64
220 int bit = index & 0x0000003f; // mod 64
221 return (bits[word] << bit) < 0; // hmmm, this would work if bit order were reversed
222 // we could right shift and check for parity bit, if it was available to us.
223 }
224 */
225
226 /** sets a bit, expanding the set size if necessary */
227 public void set(long index) {
228 int wordNum = expandingWordNum(index);
229 int bit = (int)index & 0x3f;
230 long bitmask = 1L << bit;
231 bits[wordNum] |= bitmask;
232 }
233
234
235 /** Sets the bit at the specified index.
236 * The index should be less than the OpenBitSet size.
237 */
238 public void fastSet(int index) {
239 int wordNum = index >> 6; // div 64
240 int bit = index & 0x3f; // mod 64
241 long bitmask = 1L << bit;
242 bits[wordNum] |= bitmask;
243 }
244
245 /** Sets the bit at the specified index.
246 * The index should be less than the OpenBitSet size.
247 */
248 public void fastSet(long index) {
249 int wordNum = (int)(index >> 6);
250 int bit = (int)index & 0x3f;
251 long bitmask = 1L << bit;
252 bits[wordNum] |= bitmask;
253 }
254
255 /** Sets a range of bits, expanding the set size if necessary
256 *
257 * @param startIndex lower index
258 * @param endIndex one-past the last bit to set
259 */
260 public void set(long startIndex, long endIndex) {
261 if (endIndex <= startIndex) return;
262
263 int startWord = (int)(startIndex>>6);
264
265 // since endIndex is one past the end, this is index of the last
266 // word to be changed.
267 int endWord = expandingWordNum(endIndex-1);
268
269 long startmask = -1L << startIndex;
270 long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
271
272 if (startWord == endWord) {
273 bits[startWord] |= (startmask & endmask);
274 return;
275 }
276
277 bits[startWord] |= startmask;
278 Arrays.fill(bits, startWord+1, endWord, -1L);
279 bits[endWord] |= endmask;
280 }
281
282
283
284 protected int expandingWordNum(long index) {
285 int wordNum = (int)(index >> 6);
286 if (wordNum>=wlen) {
287 ensureCapacity(index+1);
288 wlen = wordNum+1;
289 }
290 return wordNum;
291 }
292
293
294 /** clears a bit.
295 * The index should be less than the OpenBitSet size.
296 */
297 public void fastClear(int index) {
298 int wordNum = index >> 6;
299 int bit = index & 0x03f;
300 long bitmask = 1L << bit;
301 bits[wordNum] &= ~bitmask;
302 // hmmm, it takes one more instruction to clear than it does to set... any
303 // way to work around this? If there were only 63 bits per word, we could
304 // use a right shift of 10111111...111 in binary to position the 0 in the
305 // correct place (using sign extension).
306 // Could also use Long.rotateRight() or rotateLeft() *if* they were converted
307 // by the JVM into a native instruction.
308 // bits[word] &= Long.rotateLeft(0xfffffffe,bit);
309 }
310
311 /** clears a bit.
312 * The index should be less than the OpenBitSet size.
313 */
314 public void fastClear(long index) {
315 int wordNum = (int)(index >> 6); // div 64
316 int bit = (int)index & 0x3f; // mod 64
317 long bitmask = 1L << bit;
318 bits[wordNum] &= ~bitmask;
319 }
320
321 /** clears a bit, allowing access beyond the current set size without changing the size.*/
322 public void clear(long index) {
323 int wordNum = (int)(index >> 6); // div 64
324 if (wordNum>=wlen) return;
325 int bit = (int)index & 0x3f; // mod 64
326 long bitmask = 1L << bit;
327 bits[wordNum] &= ~bitmask;
328 }
329
330 /** Clears a range of bits. Clearing past the end does not change the size of the set.
331 *
332 * @param startIndex lower index
333 * @param endIndex one-past the last bit to clear
334 */
335 public void clear(long startIndex, long endIndex) {
336 if (endIndex <= startIndex) return;
337
338 int startWord = (int)(startIndex>>6);
339 if (startWord >= wlen) return;
340
341 // since endIndex is one past the end, this is index of the last
342 // word to be changed.
343 int endWord = (int)((endIndex-1)>>6);
344
345 long startmask = -1L << startIndex;
346 long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
347
348 // invert masks since we are clearing
349 startmask = ~startmask;
350 endmask = ~endmask;
351
352 if (startWord == endWord) {
353 bits[startWord] &= (startmask | endmask);
354 return;
355 }
356
357 bits[startWord] &= startmask;
358
359 int middle = Math.min(wlen, endWord);
360 Arrays.fill(bits, startWord+1, middle, 0L);
361 if (endWord < wlen) {
362 bits[endWord] &= endmask;
363 }
364 }
365
366
367
368 /** Sets a bit and returns the previous value.
369 * The index should be less than the OpenBitSet size.
370 */
371 public boolean getAndSet(int index) {
372 int wordNum = index >> 6; // div 64
373 int bit = index & 0x3f; // mod 64
374 long bitmask = 1L << bit;
375 boolean val = (bits[wordNum] & bitmask) != 0;
376 bits[wordNum] |= bitmask;
377 return val;
378 }
379
380 /** Sets a bit and returns the previous value.
381 * The index should be less than the OpenBitSet size.
382 */
383 public boolean getAndSet(long index) {
384 int wordNum = (int)(index >> 6); // div 64
385 int bit = (int)index & 0x3f; // mod 64
386 long bitmask = 1L << bit;
387 boolean val = (bits[wordNum] & bitmask) != 0;
388 bits[wordNum] |= bitmask;
389 return val;
390 }
391
392 /** flips a bit.
393 * The index should be less than the OpenBitSet size.
394 */
395 public void fastFlip(int index) {
396 int wordNum = index >> 6; // div 64
397 int bit = index & 0x3f; // mod 64
398 long bitmask = 1L << bit;
399 bits[wordNum] ^= bitmask;
400 }
401
402 /** flips a bit.
403 * The index should be less than the OpenBitSet size.
404 */
405 public void fastFlip(long index) {
406 int wordNum = (int)(index >> 6); // div 64
407 int bit = (int)index & 0x3f; // mod 64
408 long bitmask = 1L << bit;
409 bits[wordNum] ^= bitmask;
410 }
411
412 /** flips a bit, expanding the set size if necessary */
413 public void flip(long index) {
414 int wordNum = expandingWordNum(index);
415 int bit = (int)index & 0x3f; // mod 64
416 long bitmask = 1L << bit;
417 bits[wordNum] ^= bitmask;
418 }
419
420 /** flips a bit and returns the resulting bit value.
421 * The index should be less than the OpenBitSet size.
422 */
423 public boolean flipAndGet(int index) {
424 int wordNum = index >> 6; // div 64
425 int bit = index & 0x3f; // mod 64
426 long bitmask = 1L << bit;
427 bits[wordNum] ^= bitmask;
428 return (bits[wordNum] & bitmask) != 0;
429 }
430
431 /** flips a bit and returns the resulting bit value.
432 * The index should be less than the OpenBitSet size.
433 */
434 public boolean flipAndGet(long index) {
435 int wordNum = (int)(index >> 6); // div 64
436 int bit = (int)index & 0x3f; // mod 64
437 long bitmask = 1L << bit;
438 bits[wordNum] ^= bitmask;
439 return (bits[wordNum] & bitmask) != 0;
440 }
441
442 /** Flips a range of bits, expanding the set size if necessary
443 *
444 * @param startIndex lower index
445 * @param endIndex one-past the last bit to flip
446 */
447 public void flip(long startIndex, long endIndex) {
448 if (endIndex <= startIndex) return;
449 int oldlen = wlen;
450 int startWord = (int)(startIndex>>6);
451
452 // since endIndex is one past the end, this is index of the last
453 // word to be changed.
454 int endWord = expandingWordNum(endIndex-1);
455
456 /*** Grrr, java shifting wraps around so -1L>>>64 == -1
457 * for that reason, make sure not to use endmask if the bits to flip will
458 * be zero in the last word (redefine endWord to be the last changed...)
459 long startmask = -1L << (startIndex & 0x3f); // example: 11111...111000
460 long endmask = -1L >>> (64-(endIndex & 0x3f)); // example: 00111...111111
461 ***/
462
463 long startmask = -1L << startIndex;
464 long endmask = -1L >>> -endIndex; // 64-(endIndex&0x3f) is the same as -endIndex due to wrap
465
466 if (startWord == endWord) {
467 bits[startWord] ^= (startmask & endmask);
468 return;
469 }
470
471 bits[startWord] ^= startmask;
472
473 for (int i=startWord+1; i<endWord; i++) {
474 bits[i] = ~bits[i];
475 }
476
477 bits[endWord] ^= endmask;
478 }
479
480
481 /*
482 public static int pop(long v0, long v1, long v2, long v3) {
483 // derived from pop_array by setting last four elems to 0.
484 // exchanges one pop() call for 10 elementary operations
485 // saving about 7 instructions... is there a better way?
486 long twosA=v0 & v1;
487 long ones=v0^v1;
488
489 long u2=ones^v2;
490 long twosB =(ones&v2)|(u2&v3);
491 ones=u2^v3;
492
493 long fours=(twosA&twosB);
494 long twos=twosA^twosB;
495
496 return (pop(fours)<<2)
497 + (pop(twos)<<1)
498 + pop(ones);
499
500 }
501 */
502
503
504 /** @return the number of set bits */
505 public long cardinality() {
506 return BitUtil.pop_array(bits,0,wlen);
507 }
508
509 /** Returns the popcount or cardinality of the intersection of the two sets.
510 * Neither set is modified.
511 */
512 public static long intersectionCount(OpenBitSet a, OpenBitSet b) {
513 return BitUtil.pop_intersect(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
514 }
515
516 /** Returns the popcount or cardinality of the union of the two sets.
517 * Neither set is modified.
518 */
519 public static long unionCount(OpenBitSet a, OpenBitSet b) {
520 long tot = BitUtil.pop_union(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
521 if (a.wlen < b.wlen) {
522 tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen-a.wlen);
523 } else if (a.wlen > b.wlen) {
524 tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen);
525 }
526 return tot;
527 }
528
529 /** Returns the popcount or cardinality of "a and not b"
530 * or "intersection(a, not(b))".
531 * Neither set is modified.
532 */
533 public static long andNotCount(OpenBitSet a, OpenBitSet b) {
534 long tot = BitUtil.pop_andnot(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
535 if (a.wlen > b.wlen) {
536 tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen);
537 }
538 return tot;
539 }
540
541 /** Returns the popcount or cardinality of the exclusive-or of the two sets.
542 * Neither set is modified.
543 */
544 public static long xorCount(OpenBitSet a, OpenBitSet b) {
545 long tot = BitUtil.pop_xor(a.bits, b.bits, 0, Math.min(a.wlen, b.wlen));
546 if (a.wlen < b.wlen) {
547 tot += BitUtil.pop_array(b.bits, a.wlen, b.wlen-a.wlen);
548 } else if (a.wlen > b.wlen) {
549 tot += BitUtil.pop_array(a.bits, b.wlen, a.wlen-b.wlen);
550 }
551 return tot;
552 }
553
554
555 /** Returns the index of the first set bit starting at the index specified.
556 * -1 is returned if there are no more set bits.
557 */
558 public int nextSetBit(int index) {
559 int i = index>>6;
560 if (i>=wlen) return -1;
561 int subIndex = index & 0x3f; // index within the word
562 long word = bits[i] >> subIndex; // skip all the bits to the right of index
563
564 if (word!=0) {
565 return (i<<6) + subIndex + BitUtil.ntz(word);
566 }
567
568 while(++i < wlen) {
569 word = bits[i];
570 if (word!=0) return (i<<6) + BitUtil.ntz(word);
571 }
572
573 return -1;
574 }
575
576 /** Returns the index of the first set bit starting at the index specified.
577 * -1 is returned if there are no more set bits.
578 */
579 public long nextSetBit(long index) {
580 int i = (int)(index>>>6);
581 if (i>=wlen) return -1;
582 int subIndex = (int)index & 0x3f; // index within the word
583 long word = bits[i] >>> subIndex; // skip all the bits to the right of index
584
585 if (word!=0) {
586 return (((long)i)<<6) + (subIndex + BitUtil.ntz(word));
587 }
588
589 while(++i < wlen) {
590 word = bits[i];
591 if (word!=0) return (((long)i)<<6) + BitUtil.ntz(word);
592 }
593
594 return -1;
595 }
596
597
598
599
600 public Object clone() {
601 try {
602 OpenBitSet obs = (OpenBitSet)super.clone();
603 obs.bits = (long[]) obs.bits.clone(); // hopefully an array clone is as fast(er) than arraycopy
604 return obs;
605 } catch (CloneNotSupportedException e) {
606 throw new RuntimeException(e);
607 }
608 }
609
610 /** this = this AND other */
611 public void intersect(OpenBitSet other) {
612 int newLen= Math.min(this.wlen,other.wlen);
613 long[] thisArr = this.bits;
614 long[] otherArr = other.bits;
615 // testing against zero can be more efficient
616 int pos=newLen;
617 while(--pos>=0) {
618 thisArr[pos] &= otherArr[pos];
619 }
620 if (this.wlen > newLen) {
621 // fill zeros from the new shorter length to the old length
622 Arrays.fill(bits,newLen,this.wlen,0);
623 }
624 this.wlen = newLen;
625 }
626
627 /** this = this OR other */
628 public void union(OpenBitSet other) {
629 int newLen = Math.max(wlen,other.wlen);
630 ensureCapacityWords(newLen);
631
632 long[] thisArr = this.bits;
633 long[] otherArr = other.bits;
634 int pos=Math.min(wlen,other.wlen);
635 while(--pos>=0) {
636 thisArr[pos] |= otherArr[pos];
637 }
638 if (this.wlen < newLen) {
639 System.arraycopy(otherArr, this.wlen, thisArr, this.wlen, newLen-this.wlen);
640 }
641 this.wlen = newLen;
642 }
643
644
645 /** Remove all elements set in other. this = this AND_NOT other */
646 public void remove(OpenBitSet other) {
647 int idx = Math.min(wlen,other.wlen);
648 long[] thisArr = this.bits;
649 long[] otherArr = other.bits;
650 while(--idx>=0) {
651 thisArr[idx] &= ~otherArr[idx];
652 }
653 }
654
655 /** this = this XOR other */
656 public void xor(OpenBitSet other) {
657 int newLen = Math.max(wlen,other.wlen);
658 ensureCapacityWords(newLen);
659
660 long[] thisArr = this.bits;
661 long[] otherArr = other.bits;
662 int pos=Math.min(wlen,other.wlen);
663 while(--pos>=0) {
664 thisArr[pos] ^= otherArr[pos];
665 }
666 if (this.wlen < newLen) {
667 System.arraycopy(otherArr, this.wlen, thisArr, this.wlen, newLen-this.wlen);
668 }
669 this.wlen = newLen;
670 }
671
672
673 // some BitSet compatability methods
674
675 //** see {@link intersect} */
676 public void and(OpenBitSet other) {
677 intersect(other);
678 }
679
680 //** see {@link union} */
681 public void or(OpenBitSet other) {
682 union(other);
683 }
684
685 //** see {@link andNot} */
686 public void andNot(OpenBitSet other) {
687 remove(other);
688 }
689
690 /** returns true if the sets have any elements in common */
691 public boolean intersects(OpenBitSet other) {
692 int pos = Math.min(this.wlen, other.wlen);
693 long[] thisArr = this.bits;
694 long[] otherArr = other.bits;
695 while (--pos>=0) {
696 if ((thisArr[pos] & otherArr[pos])!=0) return true;
697 }
698 return false;
699 }
700
701
702
703 /** Expand the long[] with the size given as a number of words (64 bit longs).
704 * getNumWords() is unchanged by this call.
705 */
706 public void ensureCapacityWords(int numWords) {
707 if (bits.length < numWords) {
708 long[] newBits = new long[numWords];
709 System.arraycopy(bits,0,newBits,0,wlen);
710 bits = newBits;
711 }
712 }
713
714 /** Ensure that the long[] is big enough to hold numBits, expanding it if necessary.
715 * getNumWords() is unchanged by this call.
716 */
717 public void ensureCapacity(long numBits) {
718 ensureCapacityWords(bits2words(numBits));
719 }
720
721 /** Lowers numWords, the number of words in use,
722 * by checking for trailing zero words.
723 */
724 public void trimTrailingZeros() {
725 int idx = wlen-1;
726 while (idx>=0 && bits[idx]==0) idx--;
727 wlen = idx+1;
728 }
729
730 /** returns the number of 64 bit words it would take to hold numBits */
731 public static int bits2words(long numBits) {
732 return (int)(((numBits-1)>>>6)+1);
733 }
734
735
736 /** returns true if both sets have the same bits set */
737 public boolean equals(Object o) {
738 if (this == o) return true;
739 if (!(o instanceof OpenBitSet)) return false;
740 OpenBitSet a;
741 OpenBitSet b = (OpenBitSet)o;
742 // make a the larger set.
743 if (b.wlen > this.wlen) {
744 a = b; b=this;
745 } else {
746 a=this;
747 }
748
749 // check for any set bits out of the range of b
750 for (int i=a.wlen-1; i>=b.wlen; i--) {
751 if (a.bits[i]!=0) return false;
752 }
753
754 for (int i=b.wlen-1; i>=0; i--) {
755 if (a.bits[i] != b.bits[i]) return false;
756 }
757
758 return true;
759 }
760
761
762 public int hashCode() {
763 long h = 0x98761234; // something non-zero for length==0
764 for (int i = bits.length; --i>=0;) {
765 h ^= bits[i];
766 h = (h << 1) | (h >>> 63); // rotate left
767 }
768 return (int)((h>>32) ^ h); // fold leftmost bits into right
769 }
770
771 }
772
773
774 | OpenBitSet.java |