← Back to branch summary

~slub.team/goobi-indexserver/3.x

« back to all changes in this revision

Viewing changes to lucene/src/java/org/apache/lucene/util/OpenBitSet.java

  • Committer: Sebastian Meyer
  • Date: 2012-08-03 09:12:40 UTC
  • Revision ID: sebastian.meyer@slub-dresden.de-20120803091240-x6861b0vabq1xror
https://launchpad.net/bugs/985487
Remove Lucene and Solr source code and add patches instead
Fix Bug #985487: Auto-suggestion for the search interface

Show diffs side-by-side

added added

removed removed

Lines of Context:
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