Source code: joelib/util/BitSet14.java
1 /*
2 * @(#)BitSet14.java 1.54 01/12/03
3 *
4 * Copyright 2002 Sun Microsystems, Inc. All rights reserved.
5 * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6 */
7 package joelib.util;
8
9 import java.io.IOException;
10
11
12 /**
13 * This class implements a vector of bits that grows as needed. Each
14 * component of the bit set has a <code>boolean</code> value. The
15 * bits of a <code>BitSet14</code> are indexed by nonnegative integers.
16 * Individual indexed bits can be examined, set, or cleared. One
17 * <code>BitSet14</code> may be used to modify the contents of another
18 * <code>BitSet14</code> through logical AND, logical inclusive OR, and
19 * logical exclusive OR operations.
20 * <p>
21 * By default, all bits in the set initially have the value
22 * <code>false</code>.
23 * <p>
24 * Every bit set has a current size, which is the number of bits
25 * of space currently in use by the bit set. Note that the size is
26 * related to the implementation of a bit set, so it may change with
27 * implementation. The length of a bit set relates to logical length
28 * of a bit set and is defined independently of implementation.
29 * <p>
30 * Unless otherwise noted, passing a null parameter to any of the
31 * methods in a <code>BitSet14</code> will result in a
32 * <code>NullPointerException</code>.
33 *
34 * A <code>BitSet14</code> is not safe for multithreaded use without
35 * external synchronization.
36 *
37 * @author Arthur van Hoff
38 * @author Michael McCloskey
39 * @version 1.54, 12/03/01
40 * @since JDK1.0
41 */
42 public class BitSet14 implements Cloneable, java.io.Serializable
43 {
44 //~ Static fields/initializers /////////////////////////////////////////////
45
46 /*
47 * BitSet14s are packed into arrays of "units." Currently a unit is a long,
48 * which consists of 64 bits, requiring 6 address bits. The choice of unit
49 * is determined purely by performance concerns.
50 */
51 private final static int ADDRESS_BITS_PER_UNIT = 6;
52 private final static int BITS_PER_UNIT = 1 << ADDRESS_BITS_PER_UNIT;
53 private final static int BIT_INDEX_MASK = BITS_PER_UNIT - 1;
54
55 /* Used to shift left or right for a partial word mask */
56 private static final long WORD_MASK = 0xffffffffffffffffL;
57
58 /* use serialVersionUID from JDK 1.0.2 for interoperability */
59 private static final long serialVersionUID = 7997698588986878753L;
60
61 /*
62 * trailingZeroTable[i] is the number of trailing zero bits in the binary
63 * representaion of i.
64 */
65 private final static byte[] trailingZeroTable =
66 {
67 -25, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
68 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
69 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 6, 0, 1, 0, 2, 0, 1, 0,
70 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
71 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
72 3, 0, 1, 0, 2, 0, 1, 0, 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
73 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0,
74 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
75 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0, 4, 0, 1, 0, 2, 0, 1, 0,
76 3, 0, 1, 0, 2, 0, 1, 0, 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
77 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
78 };
79
80 //~ Instance fields ////////////////////////////////////////////////////////
81
82 /**
83 * The bits in this BitSet14. The ith bit is stored in bits[i/64] at
84 * bit position i % 64 (where bit position 0 refers to the least
85 * significant bit and 63 refers to the most significant bit).
86 * INVARIANT: The words in bits[] above unitInUse-1 are zero.
87 *
88 * @serial
89 */
90 private long[] bits; // this should be called unit[]
91
92 /**
93 * The number of units in the logical size of this BitSet14.
94 * INVARIANT: unitsInUse is nonnegative.
95 * INVARIANT: bits[unitsInUse-1] is nonzero unless unitsInUse is zero.
96 */
97 private transient int unitsInUse = 0;
98
99 //~ Constructors ///////////////////////////////////////////////////////////
100
101 /**
102 * Creates a new bit set. All bits are initially <code>false</code>.
103 */
104 public BitSet14()
105 {
106 this(BITS_PER_UNIT);
107 }
108
109 /**
110 * Creates a bit set whose initial size is large enough to explicitly
111 * represent bits with indices in the range <code>0</code> through
112 * <code>nbits-1</code>. All bits are initially <code>false</code>.
113 *
114 * @param nbits the initial size of the bit set.
115 * @exception NegativeArraySizeException if the specified initial size
116 * is negative.
117 */
118 public BitSet14(int nbits)
119 {
120 // nbits can't be negative; size 0 is OK
121 if (nbits < 0)
122 {
123 throw new NegativeArraySizeException("nbits < 0: " + nbits);
124 }
125
126 bits = new long[(unitIndex(nbits - 1) + 1)];
127 }
128
129 //~ Methods ////////////////////////////////////////////////////////////////
130
131 /**
132 * Returns true if this <code>BitSet14</code> contains no bits that are set
133 * to <code>true</code>.
134 *
135 * @return boolean indicating whether this <code>BitSet14</code> is empty.
136 * @since 1.4
137 */
138 public boolean isEmpty()
139 {
140 return (unitsInUse == 0);
141 }
142
143 /**
144 * Performs a logical <b>AND</b> of this target bit set with the
145 * argument bit set. This bit set is modified so that each bit in it
146 * has the value <code>true</code> if and only if it both initially
147 * had the value <code>true</code> and the corresponding bit in the
148 * bit set argument also had the value <code>true</code>.
149 *
150 * @param set a bit set.
151 */
152 public void and(BitSet14 set)
153 {
154 if (this == set)
155 {
156 return;
157 }
158
159 // Perform logical AND on bits in common
160 int oldUnitsInUse = unitsInUse;
161 unitsInUse = Math.min(unitsInUse, set.unitsInUse);
162
163 int i;
164
165 for (i = 0; i < unitsInUse; i++)
166 {
167 bits[i] &= set.bits[i];
168 }
169
170 // Clear out units no longer used
171 for (; i < oldUnitsInUse; i++)
172 {
173 bits[i] = 0;
174 }
175
176 // Recalculate units in use if necessary
177 if ((unitsInUse > 0) && (bits[unitsInUse - 1] == 0))
178 {
179 recalculateUnitsInUse();
180 }
181 }
182
183 /**
184 * Clears all of the bits in this <code>BitSet14</code> whose corresponding
185 * bit is set in the specified <code>BitSet14</code>.
186 *
187 * @param set the <code>BitSet14</code> with which to mask this
188 * <code>BitSet14</code>.
189 * @since JDK1.2
190 */
191 public void andNot(BitSet14 set)
192 {
193 int unitsInCommon = Math.min(unitsInUse, set.unitsInUse);
194
195 // Perform logical (a & !b) on bits in common
196 for (int i = 0; i < unitsInCommon; i++)
197 {
198 bits[i] &= ~set.bits[i];
199 }
200
201 recalculateUnitsInUse();
202 }
203
204 /**
205 * Returns the number of bits set to <tt>true</tt> in this
206 * <code>BitSet14</code>.
207 *
208 * @return the number of bits set to <tt>true</tt> in this
209 * <code>BitSet14</code>.
210 * @since 1.4
211 */
212 public int cardinality()
213 {
214 int sum = 0;
215
216 for (int i = 0; i < unitsInUse; i++)
217 {
218 sum += bitCount(bits[i]);
219 }
220
221 return sum;
222 }
223
224 /**
225 * Sets the bit specified by the index to <code>false</code>.
226 *
227 * @param bitIndex the index of the bit to be cleared.
228 * @exception IndexOutOfBoundsException if the specified index is negative.
229 * @since JDK1.0
230 */
231 public void clear(int bitIndex)
232 {
233 if (bitIndex < 0)
234 {
235 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
236 }
237
238 int unitIndex = unitIndex(bitIndex);
239
240 if (unitIndex >= unitsInUse)
241 {
242 return;
243 }
244
245 bits[unitIndex] &= ~bit(bitIndex);
246
247 if (bits[unitsInUse - 1] == 0)
248 {
249 recalculateUnitsInUse();
250 }
251 }
252
253 /**
254 * Sets the bits from the specified fromIndex(inclusive) to the
255 * specified toIndex(exclusive) to <code>false</code>.
256 *
257 * @param fromIndex index of the first bit to be cleared.
258 * @param toIndex index after the last bit to be cleared.
259 * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
260 * or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
261 * larger than <tt>toIndex</tt>.
262 * @since 1.4
263 */
264 public void clear(int fromIndex, int toIndex)
265 {
266 if (fromIndex < 0)
267 {
268 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
269 }
270
271 if (toIndex < 0)
272 {
273 throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
274 }
275
276 if (fromIndex > toIndex)
277 {
278 throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
279 " > toIndex: " + toIndex);
280 }
281
282 int startUnitIndex = unitIndex(fromIndex);
283
284 if (startUnitIndex >= unitsInUse)
285 {
286 return;
287 }
288
289 int endUnitIndex = unitIndex(toIndex);
290
291 long bitMask = 0;
292
293 if (startUnitIndex == endUnitIndex)
294 {
295 // Case 1: One word
296 bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
297 (1L << (fromIndex & BIT_INDEX_MASK));
298 bits[startUnitIndex] &= ~bitMask;
299
300 if (bits[unitsInUse - 1] == 0)
301 {
302 recalculateUnitsInUse();
303 }
304
305 return;
306 }
307
308 // Case 2: Multiple words
309 // Handle first word
310 bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
311 bits[startUnitIndex] &= ~bitMask;
312
313 // Handle intermediate words, if any
314 if ((endUnitIndex - startUnitIndex) > 1)
315 {
316 for (int i = startUnitIndex + 1; i < endUnitIndex; i++)
317 {
318 if (i < unitsInUse)
319 {
320 bits[i] = 0;
321 }
322 }
323 }
324
325 // Handle last word
326 if (endUnitIndex < unitsInUse)
327 {
328 bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
329 bits[endUnitIndex] &= ~bitMask;
330 }
331
332 if (bits[unitsInUse - 1] == 0)
333 {
334 recalculateUnitsInUse();
335 }
336 }
337
338 /**
339 * Sets all of the bits in this BitSet14 to <code>false</code>.
340 *
341 * @since 1.4
342 */
343 public void clear()
344 {
345 while (unitsInUse > 0)
346 {
347 bits[--unitsInUse] = 0;
348 }
349 }
350
351 /**
352 * Cloning this <code>BitSet14</code> produces a new <code>BitSet14</code>
353 * that is equal to it.
354 * The clone of the bit set is another bit set that has exactly the
355 * same bits set to <code>true</code> as this bit set and the same
356 * current size.
357 * <p>Overrides the <code>clone</code> method of <code>Object</code>.
358 *
359 * @return a clone of this bit set.
360 * @see #size()
361 */
362 public Object clone()
363 {
364 BitSet14 result = null;
365
366 try
367 {
368 result = (BitSet14) super.clone();
369 }
370 catch (CloneNotSupportedException e)
371 {
372 throw new InternalError();
373 }
374
375 result.bits = new long[bits.length];
376 System.arraycopy(bits, 0, result.bits, 0, unitsInUse);
377
378 return result;
379 }
380
381 /**
382 * Compares this object against the specified object.
383 * The result is <code>true</code> if and only if the argument is
384 * not <code>null</code> and is a <code>Bitset</code> object that has
385 * exactly the same set of bits set to <code>true</code> as this bit
386 * set. That is, for every nonnegative <code>int</code> index <code>k</code>,
387 * <pre>((BitSet14)obj).get(k) == this.get(k)</pre>
388 * must be true. The current sizes of the two bit sets are not compared.
389 * <p>Overrides the <code>equals</code> method of <code>Object</code>.
390 *
391 * @param obj the object to compare with.
392 * @return <code>true</code> if the objects are the same;
393 * <code>false</code> otherwise.
394 * @see #size()
395 */
396 public boolean equals(Object obj)
397 {
398 if (!(obj instanceof BitSet14))
399 {
400 return false;
401 }
402
403 if (this == obj)
404 {
405 return true;
406 }
407
408 BitSet14 set = (BitSet14) obj;
409 int minUnitsInUse = Math.min(unitsInUse, set.unitsInUse);
410
411 // Check units in use by both BitSet14s
412 for (int i = 0; i < minUnitsInUse; i++)
413 {
414 if (bits[i] != set.bits[i])
415 {
416 return false;
417 }
418 }
419
420 // Check any units in use by only one BitSet14 (must be 0 in other)
421 if (unitsInUse > minUnitsInUse)
422 {
423 for (int i = minUnitsInUse; i < unitsInUse; i++)
424 {
425 if (bits[i] != 0)
426 {
427 return false;
428 }
429 }
430 }
431 else
432 {
433 for (int i = minUnitsInUse; i < set.unitsInUse; i++)
434 {
435 if (set.bits[i] != 0)
436 {
437 return false;
438 }
439 }
440 }
441
442 return true;
443 }
444
445 /**
446 * Sets the bit at the specified index to to the complement of its
447 * current value.
448 *
449 * @param bitIndex the index of the bit to flip.
450 * @exception IndexOutOfBoundsException if the specified index is negative.
451 * @since 1.4
452 */
453 public void flip(int bitIndex)
454 {
455 if (bitIndex < 0)
456 {
457 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
458 }
459
460 int unitIndex = unitIndex(bitIndex);
461 int unitsRequired = unitIndex + 1;
462
463 if (unitsInUse < unitsRequired)
464 {
465 ensureCapacity(unitsRequired);
466 bits[unitIndex] ^= bit(bitIndex);
467 unitsInUse = unitsRequired;
468 }
469 else
470 {
471 bits[unitIndex] ^= bit(bitIndex);
472
473 if (bits[unitsInUse - 1] == 0)
474 {
475 recalculateUnitsInUse();
476 }
477 }
478 }
479
480 /**
481 * Sets each bit from the specified fromIndex(inclusive) to the
482 * specified toIndex(exclusive) to the complement of its current
483 * value.
484 *
485 * @param fromIndex index of the first bit to flip.
486 * @param toIndex index after the last bit to flip.
487 * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
488 * or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
489 * larger than <tt>toIndex</tt>.
490 * @since 1.4
491 */
492 public void flip(int fromIndex, int toIndex)
493 {
494 if (fromIndex < 0)
495 {
496 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
497 }
498
499 if (toIndex < 0)
500 {
501 throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
502 }
503
504 if (fromIndex > toIndex)
505 {
506 throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
507 " > toIndex: " + toIndex);
508 }
509
510 // Increase capacity if necessary
511 int endUnitIndex = unitIndex(toIndex);
512 int unitsRequired = endUnitIndex + 1;
513
514 if (unitsInUse < unitsRequired)
515 {
516 ensureCapacity(unitsRequired);
517 unitsInUse = unitsRequired;
518 }
519
520 int startUnitIndex = unitIndex(fromIndex);
521 long bitMask = 0;
522
523 if (startUnitIndex == endUnitIndex)
524 {
525 // Case 1: One word
526 bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
527 (1L << (fromIndex & BIT_INDEX_MASK));
528 bits[startUnitIndex] ^= bitMask;
529
530 if (bits[unitsInUse - 1] == 0)
531 {
532 recalculateUnitsInUse();
533 }
534
535 return;
536 }
537
538 // Case 2: Multiple words
539 // Handle first word
540 bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
541 bits[startUnitIndex] ^= bitMask;
542
543 // Handle intermediate words, if any
544 if ((endUnitIndex - startUnitIndex) > 1)
545 {
546 for (int i = startUnitIndex + 1; i < endUnitIndex; i++)
547 {
548 bits[i] ^= WORD_MASK;
549 }
550 }
551
552 // Handle last word
553 bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
554 bits[endUnitIndex] ^= bitMask;
555
556 // Check to see if we reduced size
557 if (bits[unitsInUse - 1] == 0)
558 {
559 recalculateUnitsInUse();
560 }
561 }
562
563 /**
564 * Returns the value of the bit with the specified index. The value
565 * is <code>true</code> if the bit with the index <code>bitIndex</code>
566 * is currently set in this <code>BitSet14</code>; otherwise, the result
567 * is <code>false</code>.
568 *
569 * @param bitIndex the bit index.
570 * @return the value of the bit with the specified index.
571 * @exception IndexOutOfBoundsException if the specified index is negative.
572 */
573 public boolean get(int bitIndex)
574 {
575 if (bitIndex < 0)
576 {
577 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
578 }
579
580 boolean result = false;
581 int unitIndex = unitIndex(bitIndex);
582
583 if (unitIndex < unitsInUse)
584 {
585 result = ((bits[unitIndex] & bit(bitIndex)) != 0);
586 }
587
588 return result;
589 }
590
591 /**
592 * Returns a new <tt>BitSet14</tt> composed of bits from this <tt>BitSet14</tt>
593 * from <tt>fromIndex</tt>(inclusive) to <tt>toIndex</tt>(exclusive).
594 *
595 * @param fromIndex index of the first bit to include.
596 * @param toIndex index after the last bit to include.
597 * @return a new <tt>BitSet14</tt> from a range of this <tt>BitSet14</tt>.
598 * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
599 * or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
600 * larger than <tt>toIndex</tt>.
601 * @since 1.4
602 */
603 public BitSet14 get(int fromIndex, int toIndex)
604 {
605 if (fromIndex < 0)
606 {
607 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
608 }
609
610 if (toIndex < 0)
611 {
612 throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
613 }
614
615 if (fromIndex > toIndex)
616 {
617 throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
618 " > toIndex: " + toIndex);
619 }
620
621 // If no set bits in range return empty bitset
622 if ((length() <= fromIndex) || (fromIndex == toIndex))
623 {
624 return new BitSet14(0);
625 }
626
627 // An optimization
628 if (length() < toIndex)
629 {
630 toIndex = length();
631 }
632
633 BitSet14 result = new BitSet14(toIndex - fromIndex);
634 int startBitIndex = fromIndex & BIT_INDEX_MASK;
635 int endBitIndex = toIndex & BIT_INDEX_MASK;
636 int targetWords = (toIndex - fromIndex + 63) / 64;
637 int sourceWords = unitIndex(toIndex) - unitIndex(fromIndex) + 1;
638 int inverseIndex = 64 - startBitIndex;
639 int targetIndex = 0;
640 int sourceIndex = unitIndex(fromIndex);
641
642 // Process all words but the last word
643 while (targetIndex < (targetWords - 1))
644 {
645 result.bits[targetIndex++] = (bits[sourceIndex++] >>> startBitIndex) |
646 ((inverseIndex == 64) ? 0 : (bits[sourceIndex] << inverseIndex));
647 }
648
649 // Process the last word
650 result.bits[targetIndex] = ((sourceWords == targetWords)
651 ? (bits[sourceIndex] & bitsRightOf(endBitIndex)) >>> startBitIndex
652 : ((bits[sourceIndex++] >>> startBitIndex) |
653 ((inverseIndex == 64) ? 0
654 : ((getBits(sourceIndex) &
655 bitsRightOf(endBitIndex)) << inverseIndex))));
656
657 // Set unitsInUse correctly
658 result.unitsInUse = targetWords;
659 result.recalculateUnitsInUse();
660
661 return result;
662 }
663
664 /**
665 * Returns a hash code value for this bit set. The has code
666 * depends only on which bits have been set within this
667 * <code>BitSet14</code>. The algorithm used to compute it may
668 * be described as follows.<p>
669 * Suppose the bits in the <code>BitSet14</code> were to be stored
670 * in an array of <code>long</code> integers called, say,
671 * <code>bits</code>, in such a manner that bit <code>k</code> is
672 * set in the <code>BitSet14</code> (for nonnegative values of
673 * <code>k</code>) if and only if the expression
674 * <pre>((k>>6) < bits.length) && ((bits[k>>6] & (1L << (bit & 0x3F))) != 0)</pre>
675 * is true. Then the following definition of the <code>hashCode</code>
676 * method would be a correct implementation of the actual algorithm:
677 * <pre>
678 * public int hashCode() {
679 * long h = 1234;
680 * for (int i = bits.length; --i >= 0; ) {
681 * h ^= bits[i] * (i + 1);
682 * }
683 * return (int)((h >> 32) ^ h);
684 * }</pre>
685 * Note that the hash code values change if the set of bits is altered.
686 * <p>Overrides the <code>hashCode</code> method of <code>Object</code>.
687 *
688 * @return a hash code value for this bit set.
689 */
690 public int hashCode()
691 {
692 long h = 1234;
693
694 for (int i = bits.length; --i >= 0;)
695 {
696 h ^= (bits[i] * (i + 1));
697 }
698
699 return (int) ((h >> 32) ^ h);
700 }
701
702 /**
703 * Returns true if the specified <code>BitSet14</code> has any bits set to
704 * <code>true</code> that are also set to <code>true</code> in this
705 * <code>BitSet14</code>.
706 *
707 * @param set <code>BitSet14</code> to intersect with
708 * @return boolean indicating whether this <code>BitSet14</code> intersects
709 * the specified <code>BitSet14</code>.
710 * @since 1.4
711 */
712 public boolean intersects(BitSet14 set)
713 {
714 for (int i = Math.min(unitsInUse, set.unitsInUse) - 1; i >= 0; i--)
715 {
716 if ((bits[i] & set.bits[i]) != 0)
717 {
718 return true;
719 }
720 }
721
722 return false;
723 }
724
725 /**
726 * Returns the "logical size" of this <code>BitSet14</code>: the index of
727 * the highest set bit in the <code>BitSet14</code> plus one. Returns zero
728 * if the <code>BitSet14</code> contains no set bits.
729 *
730 * @return the logical size of this <code>BitSet14</code>.
731 * @since 1.2
732 */
733 public int length()
734 {
735 if (unitsInUse == 0)
736 {
737 return 0;
738 }
739
740 long highestUnit = bits[unitsInUse - 1];
741 int highPart = (int) (highestUnit >>> 32);
742
743 return (64 * (unitsInUse - 1)) +
744 ((highPart == 0) ? bitLen((int) highestUnit) : (32 +
745 bitLen((int) highPart)));
746 }
747
748 /**
749 * Returns the index of the first bit that is set to <code>false</code>
750 * that occurs on or after the specified starting index.
751 *
752 * @param fromIndex the index to start checking from (inclusive).
753 * @return the index of the next clear bit.
754 * @throws IndexOutOfBoundsException if the specified index is negative.
755 * @since 1.4
756 */
757 public int nextClearBit(int fromIndex)
758 {
759 if (fromIndex < 0)
760 {
761 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
762 }
763
764 int u = unitIndex(fromIndex);
765
766 if (u >= unitsInUse)
767 {
768 return fromIndex;
769 }
770
771 int testIndex = (fromIndex & BIT_INDEX_MASK);
772 long unit = bits[u] >> testIndex;
773
774 if (unit == (WORD_MASK >> testIndex))
775 {
776 testIndex = 0;
777 }
778
779 while ((unit == WORD_MASK) && (u < (unitsInUse - 1)))
780 {
781 unit = bits[++u];
782 }
783
784 if (unit == WORD_MASK)
785 {
786 return length();
787 }
788
789 if (unit == 0)
790 {
791 return (u * BITS_PER_UNIT) + testIndex;
792 }
793
794 testIndex += trailingZeroCnt(~unit);
795
796 return ((u * BITS_PER_UNIT) + testIndex);
797 }
798
799 /**
800 * Returns the index of the first bit that is set to <code>true</code>
801 * that occurs on or after the specified starting index. If no such
802 * bit exists then -1 is returned.
803 *
804 * To iterate over the <code>true</code> bits in a <code>BitSet14</code>,
805 * use the following loop:
806 *
807 * for(int i=bs.nextSetBit(0); i>=0; i=bs.nextSetBit(i+1)) {
808 * // operate on index i here
809 * }
810 *
811 * @param fromIndex the index to start checking from (inclusive).
812 * @return the index of the next set bit.
813 * @throws IndexOutOfBoundsException if the specified index is negative.
814 * @since 1.4
815 */
816 public int nextSetBit(int fromIndex)
817 {
818 if (fromIndex < 0)
819 {
820 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
821 }
822
823 int u = unitIndex(fromIndex);
824
825 if (u >= unitsInUse)
826 {
827 return -1;
828 }
829
830 int testIndex = (fromIndex & BIT_INDEX_MASK);
831 long unit = bits[u] >> testIndex;
832
833 if (unit == 0)
834 {
835 testIndex = 0;
836 }
837
838 while ((unit == 0) && (u < (unitsInUse - 1)))
839 {
840 unit = bits[++u];
841 }
842
843 if (unit == 0)
844 {
845 return -1;
846 }
847
848 testIndex += trailingZeroCnt(unit);
849
850 return ((u * BITS_PER_UNIT) + testIndex);
851 }
852
853 /**
854 * Performs a logical <b>OR</b> of this bit set with the bit set
855 * argument. This bit set is modified so that a bit in it has the
856 * value <code>true</code> if and only if it either already had the
857 * value <code>true</code> or the corresponding bit in the bit set
858 * argument has the value <code>true</code>.
859 *
860 * @param set a bit set.
861 */
862 public void or(BitSet14 set)
863 {
864 if (this == set)
865 {
866 return;
867 }
868
869 ensureCapacity(set.unitsInUse);
870
871 // Perform logical OR on bits in common
872 int unitsInCommon = Math.min(unitsInUse, set.unitsInUse);
873 int i;
874
875 for (i = 0; i < unitsInCommon; i++)
876 {
877 bits[i] |= set.bits[i];
878 }
879
880 // Copy any remaining bits
881 for (; i < set.unitsInUse; i++)
882 {
883 bits[i] = set.bits[i];
884 }
885
886 if (unitsInUse < set.unitsInUse)
887 {
888 unitsInUse = set.unitsInUse;
889 }
890 }
891
892 /**
893 * Sets the bit at the specified index to <code>true</code>.
894 *
895 * @param bitIndex a bit index.
896 * @exception IndexOutOfBoundsException if the specified index is negative.
897 * @since JDK1.0
898 */
899 public void set(int bitIndex)
900 {
901 if (bitIndex < 0)
902 {
903 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
904 }
905
906 int unitIndex = unitIndex(bitIndex);
907 int unitsRequired = unitIndex + 1;
908
909 if (unitsInUse < unitsRequired)
910 {
911 ensureCapacity(unitsRequired);
912 bits[unitIndex] |= bit(bitIndex);
913 unitsInUse = unitsRequired;
914 }
915 else
916 {
917 bits[unitIndex] |= bit(bitIndex);
918 }
919 }
920
921 /**
922 * Sets the bit at the specified index to the specified value.
923 *
924 * @param bitIndex a bit index.
925 * @param value a boolean value to set.
926 * @exception IndexOutOfBoundsException if the specified index is negative.
927 * @since 1.4
928 */
929 public void set(int bitIndex, boolean value)
930 {
931 if (value)
932 {
933 set(bitIndex);
934 }
935 else
936 {
937 clear(bitIndex);
938 }
939 }
940
941 /**
942 * Sets the bits from the specified fromIndex(inclusive) to the
943 * specified toIndex(exclusive) to <code>true</code>.
944 *
945 * @param fromIndex index of the first bit to be set.
946 * @param toIndex index after the last bit to be set.
947 * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
948 * or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
949 * larger than <tt>toIndex</tt>.
950 * @since 1.4
951 */
952 public void set(int fromIndex, int toIndex)
953 {
954 if (fromIndex < 0)
955 {
956 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
957 }
958
959 if (toIndex < 0)
960 {
961 throw new IndexOutOfBoundsException("toIndex < 0: " + toIndex);
962 }
963
964 if (fromIndex > toIndex)
965 {
966 throw new IndexOutOfBoundsException("fromIndex: " + fromIndex +
967 " > toIndex: " + toIndex);
968 }
969
970 // Increase capacity if necessary
971 int endUnitIndex = unitIndex(toIndex);
972 int unitsRequired = endUnitIndex + 1;
973
974 if (unitsInUse < unitsRequired)
975 {
976 ensureCapacity(unitsRequired);
977 unitsInUse = unitsRequired;
978 }
979
980 int startUnitIndex = unitIndex(fromIndex);
981 long bitMask = 0;
982
983 if (startUnitIndex == endUnitIndex)
984 {
985 // Case 1: One word
986 bitMask = (1L << (toIndex & BIT_INDEX_MASK)) -
987 (1L << (fromIndex & BIT_INDEX_MASK));
988 bits[startUnitIndex] |= bitMask;
989
990 return;
991 }
992
993 // Case 2: Multiple words
994 // Handle first word
995 bitMask = bitsLeftOf(fromIndex & BIT_INDEX_MASK);
996 bits[startUnitIndex] |= bitMask;
997
998 // Handle intermediate words, if any
999 if ((endUnitIndex - startUnitIndex) > 1)
1000 {
1001 for (int i = startUnitIndex + 1; i < endUnitIndex; i++)
1002 {
1003 bits[i] |= WORD_MASK;
1004 }
1005 }
1006
1007 // Handle last word
1008 bitMask = bitsRightOf(toIndex & BIT_INDEX_MASK);
1009 bits[endUnitIndex] |= bitMask;
1010 }
1011
1012 /**
1013 * Sets the bits from the specified fromIndex(inclusive) to the
1014 * specified toIndex(exclusive) to the specified value.
1015 *
1016 * @param fromIndex index of the first bit to be set.
1017 * @param toIndex index after the last bit to be set
1018 * @param value value to set the selected bits to
1019 * @exception IndexOutOfBoundsException if <tt>fromIndex</tt> is negative,
1020 * or <tt>toIndex</tt> is negative, or <tt>fromIndex</tt> is
1021 * larger than <tt>toIndex</tt>.
1022 * @since 1.4
1023 */
1024 public void set(int fromIndex, int toIndex, boolean value)
1025 {
1026 if (value)
1027 {
1028 set(fromIndex, toIndex);
1029 }
1030 else
1031 {
1032 clear(fromIndex, toIndex);
1033 }
1034 }
1035
1036 /**
1037 * Returns the number of bits of space actually in use by this
1038 * <code>BitSet14</code> to represent bit values.
1039 * The maximum element in the set is the size - 1st element.
1040 *
1041 * @return the number of bits currently in this bit set.
1042 */
1043 public int size()
1044 {
1045 return bits.length << ADDRESS_BITS_PER_UNIT;
1046 }
1047
1048 /**
1049 * Returns a string representation of this bit set. For every index
1050 * for which this <code>BitSet14</code> contains a bit in the set
1051 * state, the decimal representation of that index is included in
1052 * the result. Such indices are listed in order from lowest to
1053 * highest, separated by ", " (a comma and a space) and
1054 * surrounded by braces, resulting in the usual mathematical
1055 * notation for a set of integers.<p>
1056 * Overrides the <code>toString</code> method of <code>Object</code>.
1057 * <p>Example:
1058 * <pre>
1059 * BitSet14 drPepper = new BitSet14();</pre>
1060 * Now <code>drPepper.toString()</code> returns "<code>{}</code>".<p>
1061 * <pre>
1062 * drPepper.set(2);</pre>
1063 * Now <code>drPepper.toString()</code> returns "<code>{2}</code>".<p>
1064 * <pre>
1065 * drPepper.set(4);
1066 * drPepper.set(10);</pre>
1067 * Now <code>drPepper.toString()</code> returns "<code>{2, 4, 10}</code>".
1068 *
1069 * @return a string representation of this bit set.
1070 */
1071 public String toString()
1072 {
1073 int numBits = unitsInUse << ADDRESS_BITS_PER_UNIT;
1074 StringBuffer buffer = new StringBuffer((8 * numBits) + 2);
1075 String separator = "";
1076 buffer.append('{');
1077
1078 for (int i = 0; i < numBits; i++)
1079 {
1080 if (get(i))
1081 {
1082 buffer.append(separator);
1083 separator = ", ";
1084 buffer.append(i);
1085 }
1086 }
1087
1088 buffer.append('}');
1089
1090 return buffer.toString();
1091 }
1092
1093 /**
1094 * Performs a logical <b>XOR</b> of this bit set with the bit set
1095 * argument. This bit set is modified so that a bit in it has the
1096 * value <code>true</code> if and only if one of the following
1097 * statements holds:
1098 * <ul>
1099 * <li>The bit initially has the value <code>true</code>, and the
1100 * corresponding bit in the argument has the value <code>false</code>.
1101 * <li>The bit initially has the value <code>false</code>, and the
1102 * corresponding bit in the argument has the value <code>true</code>.
1103 * </ul>
1104 *
1105 * @param set a bit set.
1106 */
1107 public void xor(BitSet14 set)
1108 {
1109 int unitsInCommon;
1110
1111 if (unitsInUse >= set.unitsInUse)
1112 {
1113 unitsInCommon = set.unitsInUse;
1114 }
1115 else
1116 {
1117 unitsInCommon = unitsInUse;
1118
1119 int newUnitsInUse = set.unitsInUse;
1120 ensureCapacity(newUnitsInUse);
1121 unitsInUse = newUnitsInUse;
1122 }
1123
1124 // Perform logical XOR on bits in common
1125 int i;
1126
1127 for (i = 0; i < unitsInCommon; i++)
1128 {
1129 bits[i] ^= set.bits[i];
1130 }
1131
1132 // Copy any remaining bits
1133 for (; i < set.unitsInUse; i++)
1134 {
1135 bits[i] = set.bits[i];
1136 }
1137
1138 recalculateUnitsInUse();
1139 }
1140
1141 /**
1142 * Given a bit index, return a unit that masks that bit in its unit.
1143 */
1144 private static long bit(int bitIndex)
1145 {
1146 return 1L << (bitIndex & BIT_INDEX_MASK);
1147 }
1148
1149 /**
1150 * Returns the number of bits set in val.
1151 * For a derivation of this algorithm, see
1152 * "Algorithms and data structures with applications to
1153 * graphics and geometry", by Jurg Nievergelt and Klaus Hinrichs,
1154 * Prentice Hall, 1993.
1155 */
1156 private static int bitCount(long val)
1157 {
1158 val -= (val & 0xaaaaaaaaaaaaaaaaL) >>> 1;
1159 val = (val & 0x3333333333333333L) +
1160 ((val >>> 2) & 0x3333333333333333L);
1161 val = (val + (val >>> 4)) & 0x0f0f0f0f0f0f0f0fL;
1162 val += val >>> 8;
1163 val += val >>> 16;
1164
1165 return ((int) (val) + (int) (val >>> 32)) & 0xff;
1166 }
1167
1168 /**
1169 * bitLen(val) is the number of bits in val.
1170 */
1171 private static int bitLen(int w)
1172 {
1173 // Binary search - decision tree (5 tests, rarely 6)
1174 return ((w < (1 << 15))
1175 ? ((w < (1 << 7))
1176 ? ((w < (1 << 3))
1177 ? ((w < (1 << 1)) ? ((w < (1 << 0)) ? ((w < 0) ? 32 : 0) : 1)
1178 : ((w < (1 << 2)) ? 2 : 3))
1179 : ((w < (1 << 5)) ? ((w < (1 << 4)) ? 4 : 5) : ((w < (1 << 6)) ? 6 : 7)))
1180 : ((w < (1 << 11))
1181 ? ((w < (1 << 9)) ? ((w < (1 << 8)) ? 8 : 9) : ((w < (1 << 10)) ? 10 : 11))
1182 : ((w < (1 << 13)) ? ((w < (1 << 12)) ? 12 : 13)
1183 : ((w < (1 << 14)) ? 14 : 15))))
1184 : ((w < (1 << 23))
1185 ? ((w < (1 << 19))
1186 ? ((w < (1 << 17)) ? ((w < (1 << 16)) ? 16 : 17)
1187 : ((w < (1 << 18)) ? 18 : 19))
1188 : ((w < (1 << 21)) ? ((w < (1 << 20)) ? 20 : 21)
1189 : ((w < (1 << 22)) ? 22 : 23)))
1190 : ((w < (1 << 27))
1191 ? ((w < (1 << 25)) ? ((w < (1 << 24)) ? 24 : 25)
1192 : ((w < (1 << 26)) ? 26 : 27))
1193 : ((w < (1 << 29)) ? ((w < (1 << 28)) ? 28 : 29)
1194 : ((w < (1 << 30)) ? 30 : 31)))));
1195 }
1196
1197 /**
1198 * Returns a long that has all the bits that are more significant
1199 * than or equal to the specified index set to 1. All other bits are 0.
1200 */
1201 private static long bitsLeftOf(int x)
1202 {
1203 return WORD_MASK << x;
1204 }
1205
1206 /**
1207 * Returns a long that has all bits that are less significant
1208 * than the specified index set to 1. All other bits are 0.
1209 */
1210 private static long bitsRightOf(int x)
1211 {
1212 return ((x == 0) ? 0 : WORD_MASK >>> (64 - x));
1213 }
1214
1215 private static int trailingZeroCnt(long val)
1216 {
1217 // Loop unrolled for performance
1218 int byteVal = (int) val & 0xff;
1219
1220 if (byteVal != 0)
1221 {
1222 return trailingZeroTable[byteVal];
1223 }
1224
1225 byteVal = (int) (val >>> 8) & 0xff;
1226
1227 if (byteVal != 0)
1228 {
1229 return trailingZeroTable[byteVal] + 8;
1230 }
1231
1232 byteVal = (int) (val >>> 16) & 0xff;
1233
1234 if (byteVal != 0)
1235 {
1236 return trailingZeroTable[byteVal] + 16;
1237 }
1238
1239 byteVal = (int) (val >>> 24) & 0xff;
1240
1241 if (byteVal != 0)
1242 {
1243 return trailingZeroTable[byteVal] + 24;
1244 }
1245
1246 byteVal = (int) (val >>> 32) & 0xff;
1247
1248 if (byteVal != 0)
1249 {
1250 return trailingZeroTable[byteVal] + 32;
1251 }
1252
1253 byteVal = (int) (val >>> 40) & 0xff;
1254
1255 if (byteVal != 0)
1256 {
1257 return trailingZeroTable[byteVal] + 40;
1258 }
1259
1260 byteVal = (int) (val >>> 48) & 0xff;
1261
1262 if (byteVal != 0)
1263 {
1264 return trailingZeroTable[byteVal] + 48;
1265 }
1266
1267 byteVal = (int) (val >>> 56) & 0xff;
1268
1269 return trailingZeroTable[byteVal] + 56;
1270 }
1271
1272 /**
1273 * Given a bit index return unit index containing it.
1274 */
1275 private static int unitIndex(int bitIndex)
1276 {
1277 return bitIndex >> ADDRESS_BITS_PER_UNIT;
1278 }
1279
1280 /**
1281 * Returns the unit of this bitset at index j as if this bitset had an
1282 * infinite amount of storage.
1283 */
1284 private long getBits(int j)
1285 {
1286 return (j < unitsInUse) ? bits[j] : 0;
1287 }
1288
1289 /**
1290 * Ensures that the BitSet14 can hold enough units.
1291 * @param unitsRequired the minimum acceptable number of units.
1292 */
1293 private void ensureCapacity(int unitsRequired)
1294 {
1295 if (bits.length < unitsRequired)
1296 {
1297 // Allocate larger of doubled size or required size
1298 int request = Math.max(2 * bits.length, unitsRequired);
1299 long[] newBits = new long[request];
1300 System.arraycopy(bits, 0, newBits, 0, unitsInUse);
1301 bits = newBits;
1302 }
1303 }
1304
1305 /**
1306 * This override of readObject makes sure unitsInUse is set properly
1307 * when deserializing a bitset
1308 *
1309 */
1310 private void readObject(java.io.ObjectInputStream in)
1311 throws IOException, ClassNotFoundException
1312 {
1313 in.defaultReadObject();
1314
1315 // Assume maximum length then find real length
1316 // because recalculateUnitsInUse assumes maintenance
1317 // or reduction in logical size
1318 unitsInUse = bits.length;
1319 recalculateUnitsInUse();
1320 }
1321
1322 /**
1323 * Set the field unitsInUse with the logical size in units of the bit
1324 * set. WARNING:This methodName assumes that the number of units actually
1325 * in use is less than or equal to the current value of unitsInUse!
1326 */
1327 private void recalculateUnitsInUse()
1328 {
1329 // Traverse the bitset until a used unit is found
1330 int i;
1331
1332 for (i = unitsInUse - 1; i >= 0; i--)
1333 {
1334 if (bits[i] != 0)
1335 {
1336 break;
1337 }
1338 }
1339
1340 unitsInUse = i + 1; // The new logical size
1341 }
1342}
1343///////////////////////////////////////////////////////////////////////////////
1344// END OF FILE.
1345///////////////////////////////////////////////////////////////////////////////