2 * Copyright 1995-2007 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Sun designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Sun in the LICENSE file that accompanied this code.
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 * CA 95054 USA or visit www.sun.com if you need additional information or
28 import javajs.api.JSONEncodable;
34 * a fast 32-bit BitSet optimized for Java2Script -- about 25 times faster than
37 * @author Bob Hanson hansonr@stolaf.edu
39 * Additions by Bob Hanson to allow for JavaScript mix of int/long Note
40 * that Firefox (Sept 2012) does not really treat "Int32Array" as such,
41 * because any element can be pushed into being a 64-bit number, which
42 * really isn't because the last 8 bits are not usable.
44 * This class implements a vector of bits that grows as needed. Each
45 * component of the bit set has a {@code boolean} value. The bits of a
46 * {@code BitSet} are indexed by nonnegative integers. Individual
47 * indexed bits can be examined, set, or cleared. One {@code BitSet} may
48 * be used to modify the contents of another {@code BitSet} through
49 * logical AND, logical inclusive OR, and logical exclusive OR
53 * By default, all bits in the set initially have the value {@code
57 * Every bit set has a current size, which is the number of bits of
58 * space currently in use by the bit set. Note that the size is related
59 * to the implementation of a bit set, so it may change with
60 * implementation. The length of a bit set relates to logical length of
61 * a bit set and is defined independently of implementation.
64 * Unless otherwise noted, passing a null parameter to any of the
65 * methods in a {@code BitSet} will result in a {@code
66 * NullPointerException}.
69 * A {@code BitSet} is not safe for multithreaded use without external
72 * @author Arthur van Hoff
73 * @author Michael McCloskey
74 * @author Martin Buchholz
77 public class BS implements Cloneable, JSONEncodable {
79 * BitSets are packed into arrays of "words."
81 * An int, which consists of 32 bits, requiring 5 address bits, is used for
82 * the JavaScript port.
84 private final static int ADDRESS_BITS_PER_WORD = 5;
85 private final static int BITS_PER_WORD = 1 << ADDRESS_BITS_PER_WORD;
87 /* Used to shift left or right for a partial word mask */
88 private static final int WORD_MASK = 0xffffffff;
92 * The internal field corresponding to the serialField "bits".
97 * The number of words in the logical size of this BitSet.
99 private transient int wordsInUse = 0;
102 * Whether the size of "words" is user-specified. If so, we assume the user
103 * knows what he's doing and try harder to preserve it.
105 private transient boolean sizeIsSticky = false;
107 /* use serialVersionUID from JDK 1.0.2 for interoperability */
108 //private static final long serialVersionUID = 7997698588986878753L;
111 * Given a bit index, return word index containing it.
115 private static int wordIndex(int bitIndex) {
116 return bitIndex >> ADDRESS_BITS_PER_WORD;
120 * Sets the field wordsInUse to the logical size in words of the bit set.
121 * WARNING:This method assumes that the number of words actually in use is
122 * less than or equal to the current value of wordsInUse!
124 private void recalculateWordsInUse() {
125 // Traverse the bitset until a used word is found
127 for (i = wordsInUse - 1; i >= 0; i--)
131 wordsInUse = i + 1; // The new logical size
135 * Creates a new bit set. All bits are initially {@code false}.
138 initWords(BITS_PER_WORD);
139 sizeIsSticky = false;
143 * Creates a bit set whose initial size is large enough to explicitly
144 * represent bits with indices in the range {@code 0} through {@code nbits-1}.
145 * All bits are initially {@code false}.
148 * the initial size of the bit set
150 * @throws NegativeArraySizeException
151 * if the specified initial size is negative
153 public static BS newN(int nbits) {
159 private void init(int nbits) {
160 // nbits can't be negative; size 0 is OK
162 throw new NegativeArraySizeException("nbits < 0: " + nbits);
167 private void initWords(int nbits) {
168 words = new int[wordIndex(nbits - 1) + 1];
172 * Ensures that the BitSet can hold enough words.
174 * @param wordsRequired
175 * the minimum acceptable number of words.
177 private void ensureCapacity(int wordsRequired) {
178 if (words.length < wordsRequired) {
179 // Allocate larger of doubled size or required size
180 int request = Math.max(2 * words.length, wordsRequired);
182 sizeIsSticky = false;
187 * Ensures that the BitSet can accommodate a given wordIndex, temporarily
188 * violating the invariants. The caller must restore the invariants before
189 * returning to the user, possibly using recalculateWordsInUse().
192 * the index to be accommodated.
194 private void expandTo(int wordIndex) {
195 int wordsRequired = wordIndex + 1;
196 if (wordsInUse < wordsRequired) {
197 ensureCapacity(wordsRequired);
198 wordsInUse = wordsRequired;
204 * Sets the bit at the specified index to {@code true}.
208 * @throws IndexOutOfBoundsException
209 * if the specified index is negative
212 public void set(int bitIndex) {
214 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
216 int wordIndex = wordIndex(bitIndex);
219 words[wordIndex] |= (1 << bitIndex); // Restores invariants
224 * Sets the bit at the specified index to the specified value.
229 * a boolean value to set
230 * @throws IndexOutOfBoundsException
231 * if the specified index is negative
234 public void setBitTo(int bitIndex, boolean value) {
242 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
243 * specified {@code toIndex} (exclusive) to {@code true}.
246 * index of the first bit to be set
248 * index after the last bit to be set
249 * @throws IndexOutOfBoundsException
250 * if {@code fromIndex} is negative, or {@code toIndex} is negative,
251 * or {@code fromIndex} is larger than {@code toIndex}
254 public void setBits(int fromIndex, int toIndex) {
256 if (fromIndex == toIndex)
259 // Increase capacity if necessary
260 int startWordIndex = wordIndex(fromIndex);
261 int endWordIndex = wordIndex(toIndex - 1);
262 expandTo(endWordIndex);
264 int firstWordMask = WORD_MASK << fromIndex;
265 int lastWordMask = WORD_MASK >>> -toIndex;
266 if (startWordIndex == endWordIndex) {
268 words[startWordIndex] |= (firstWordMask & lastWordMask);
270 // Case 2: Multiple words
272 words[startWordIndex] |= firstWordMask;
274 // Handle intermediate words, if any
275 for (int i = startWordIndex + 1; i < endWordIndex; i++)
276 words[i] = WORD_MASK;
278 // Handle last word (restores invariants)
279 words[endWordIndex] |= lastWordMask;
284 * Sets the bit specified by the index to {@code false}.
287 * the index of the bit to be cleared
288 * @throws IndexOutOfBoundsException
289 * if the specified index is negative
292 public void clear(int bitIndex) {
294 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
296 int wordIndex = wordIndex(bitIndex);
297 if (wordIndex >= wordsInUse)
300 words[wordIndex] &= ~(1 << bitIndex);
302 recalculateWordsInUse();
306 * Sets the bits from the specified {@code fromIndex} (inclusive) to the
307 * specified {@code toIndex} (exclusive) to {@code false}.
310 * index of the first bit to be cleared
312 * index after the last bit to be cleared
313 * @throws IndexOutOfBoundsException
314 * if {@code fromIndex} is negative, or {@code toIndex} is negative,
315 * or {@code fromIndex} is larger than {@code toIndex}
318 public void clearBits(int fromIndex, int toIndex) {
319 if (fromIndex == toIndex)
322 int startWordIndex = wordIndex(fromIndex);
323 if (startWordIndex >= wordsInUse)
326 int endWordIndex = wordIndex(toIndex - 1);
327 if (endWordIndex >= wordsInUse) {
329 endWordIndex = wordsInUse - 1;
332 int firstWordMask = WORD_MASK << fromIndex;
333 int lastWordMask = WORD_MASK >>> -toIndex;
334 if (startWordIndex == endWordIndex) {
336 words[startWordIndex] &= ~(firstWordMask & lastWordMask);
338 // Case 2: Multiple words
340 words[startWordIndex] &= ~firstWordMask;
342 // Handle intermediate words, if any
343 for (int i = startWordIndex + 1; i < endWordIndex; i++)
347 words[endWordIndex] &= ~lastWordMask;
350 recalculateWordsInUse();
354 * Sets all of the bits in this BitSet to {@code false}.
358 public void clearAll() {
359 while (wordsInUse > 0)
360 words[--wordsInUse] = 0;
364 * Returns the value of the bit with the specified index. The value is {@code
365 * true} if the bit with the index {@code bitIndex} is currently set in this
366 * {@code BitSet}; otherwise, the result is {@code false}.
370 * @return the value of the bit with the specified index
371 * @throws IndexOutOfBoundsException
372 * if the specified index is negative
374 public boolean get(int bitIndex) {
376 throw new IndexOutOfBoundsException("bitIndex < 0: " + bitIndex);
378 int wordIndex = wordIndex(bitIndex);
379 return (wordIndex < wordsInUse)
380 && ((words[wordIndex] & (1 << bitIndex)) != 0);
384 * Returns the index of the first bit that is set to {@code true} that occurs
385 * on or after the specified starting index. If no such bit exists then
386 * {@code -1} is returned.
389 * To iterate over the {@code true} bits in a {@code BitSet}, use the
394 * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) {
395 * // operate on index i here
400 * the index to start checking from (inclusive)
401 * @return the index of the next set bit, or {@code -1} if there is no such
403 * @throws IndexOutOfBoundsException
404 * if the specified index is negative
407 public int nextSetBit(int fromIndex) {
409 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
411 int u = wordIndex(fromIndex);
415 int word = words[u] & (WORD_MASK << fromIndex);
419 return (u * BITS_PER_WORD) + Integer.numberOfTrailingZeros(word);
420 if (++u == wordsInUse)
427 * Returns the index of the first bit that is set to {@code false} that occurs
428 * on or after the specified starting index.
431 * the index to start checking from (inclusive)
432 * @return the index of the next clear bit
433 * @throws IndexOutOfBoundsException
434 * if the specified index is negative
437 public int nextClearBit(int fromIndex) {
438 // Neither spec nor implementation handle bitsets of maximal length.
441 throw new IndexOutOfBoundsException("fromIndex < 0: " + fromIndex);
443 int u = wordIndex(fromIndex);
447 int word = ~words[u] & (WORD_MASK << fromIndex);
451 return (u * BITS_PER_WORD) + Integer.numberOfTrailingZeros(word);
452 if (++u == wordsInUse)
453 return wordsInUse * BITS_PER_WORD;
459 * Returns the "logical size" of this {@code BitSet}: the index of the highest
460 * set bit in the {@code BitSet} plus one. Returns zero if the {@code BitSet}
461 * contains no set bits.
463 * @return the logical size of this {@code BitSet}
466 public int length() {
470 return BITS_PER_WORD * (wordsInUse - 1)
471 + (BITS_PER_WORD - Integer.numberOfLeadingZeros(words[wordsInUse - 1]));
475 * Returns true if this {@code BitSet} contains no bits that are set to
478 * @return boolean indicating whether this {@code BitSet} is empty
481 public boolean isEmpty() {
482 return wordsInUse == 0;
486 * Returns true if the specified {@code BitSet} has any bits set to {@code
487 * true} that are also set to {@code true} in this {@code BitSet}.
490 * {@code BitSet} to intersect with
491 * @return boolean indicating whether this {@code BitSet} intersects the
492 * specified {@code BitSet}
495 public boolean intersects(BS set) {
496 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
497 if ((words[i] & set.words[i]) != 0)
503 * Returns the number of bits set to {@code true} in this {@code BitSet}.
505 * @return the number of bits set to {@code true} in this {@code BitSet}
508 public int cardinality() {
510 for (int i = 0; i < wordsInUse; i++)
511 sum += Integer.bitCount(words[i]);
516 * Performs a logical <b>AND</b> of this target bit set with the argument bit
517 * set. This bit set is modified so that each bit in it has the value {@code
518 * true} if and only if it both initially had the value {@code true} and the
519 * corresponding bit in the bit set argument also had the value {@code true}.
524 public void and(BS set) {
528 while (wordsInUse > set.wordsInUse)
529 words[--wordsInUse] = 0;
531 // Perform logical AND on words in common
532 for (int i = 0; i < wordsInUse; i++)
533 words[i] &= set.words[i];
535 recalculateWordsInUse();
539 * Performs a logical <b>OR</b> of this bit set with the bit set argument.
540 * This bit set is modified so that a bit in it has the value {@code true} if
541 * and only if it either already had the value {@code true} or the
542 * corresponding bit in the bit set argument has the value {@code true}.
547 public void or(BS set) {
551 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
553 if (wordsInUse < set.wordsInUse) {
554 ensureCapacity(set.wordsInUse);
555 wordsInUse = set.wordsInUse;
558 // Perform logical OR on words in common
559 for (int i = 0; i < wordsInCommon; i++)
560 words[i] |= set.words[i];
562 // Copy any remaining words
563 if (wordsInCommon < set.wordsInUse)
564 System.arraycopy(set.words, wordsInCommon, words, wordsInCommon,
565 wordsInUse - wordsInCommon);
570 * Performs a logical <b>XOR</b> of this bit set with the bit set argument.
571 * This bit set is modified so that a bit in it has the value {@code true} if
572 * and only if one of the following statements holds:
574 * <li>The bit initially has the value {@code true}, and the corresponding bit
575 * in the argument has the value {@code false}.
576 * <li>The bit initially has the value {@code false}, and the corresponding
577 * bit in the argument has the value {@code true}.
583 public void xor(BS set) {
584 int wordsInCommon = Math.min(wordsInUse, set.wordsInUse);
586 if (wordsInUse < set.wordsInUse) {
587 ensureCapacity(set.wordsInUse);
588 wordsInUse = set.wordsInUse;
591 // Perform logical XOR on words in common
592 for (int i = 0; i < wordsInCommon; i++)
593 words[i] ^= set.words[i];
595 // Copy any remaining words
596 if (wordsInCommon < set.wordsInUse)
597 System.arraycopy(set.words, wordsInCommon, words, wordsInCommon,
598 set.wordsInUse - wordsInCommon);
600 recalculateWordsInUse();
604 * Clears all of the bits in this {@code BitSet} whose corresponding bit is
605 * set in the specified {@code BitSet}.
608 * the {@code BitSet} with which to mask this {@code BitSet}
611 public void andNot(BS set) {
612 // Perform logical (a & !b) on words in common
613 for (int i = Math.min(wordsInUse, set.wordsInUse) - 1; i >= 0; i--)
614 words[i] &= ~set.words[i];
616 recalculateWordsInUse();
620 * Returns a hash code value for this bit set. The hash code depends only on
621 * which bits have been set within this <code>BitSet</code>. The algorithm
622 * used to compute it may be described as follows.
624 * Suppose the bits in the <code>BitSet</code> were to be stored in an array
625 * of <code>long</code> integers called, say, <code>words</code>, in such a
626 * manner that bit <code>k</code> is set in the <code>BitSet</code> (for
627 * nonnegative values of <code>k</code>) if and only if the expression
630 * ((k >> 6) < words.length) && ((words[k >> 6] & (1 << (bit & 0x3F))) != 0)
633 * is true. Then the following definition of the <code>hashCode</code> method
634 * would be a correct implementation of the actual algorithm:
637 * public int hashCode() {
639 * for (int i = words.length; --i >= 0;) {
640 * h ˆ= words[i] * (i + 1);
642 * return (int) ((h >> 32) ˆ h);
646 * Note that the hash code values change if the set of bits is altered.
648 * Overrides the <code>hashCode</code> method of <code>Object</code>.
650 * @return a hash code value for this bit set.
653 public int hashCode() {
655 for (int i = wordsInUse; --i >= 0;)
656 h ^= words[i] * (i + 1);
658 return (int) ((h >> 32) ^ h);
662 * Returns the number of bits of space actually in use by this {@code BitSet}
663 * to represent bit values. The maximum element in the set is the size - 1st
666 * @return the number of bits currently in this bit set
669 return words.length * BITS_PER_WORD;
673 * Compares this object against the specified object. The result is {@code
674 * true} if and only if the argument is not {@code null} and is a {@code
675 * Bitset} object that has exactly the same set of bits set to {@code true} as
676 * this bit set. That is, for every nonnegative {@code int} index {@code k},
679 * ((BitSet) obj).get(k) == this.get(k)
682 * must be true. The current sizes of the two bit sets are not compared.
685 * the object to compare with
686 * @return {@code true} if the objects are the same; {@code false} otherwise
690 public boolean equals(Object obj) {
691 if (!(obj instanceof BS))
698 if (wordsInUse != set.wordsInUse)
701 // Check words in use by both BitSets
702 for (int i = 0; i < wordsInUse; i++)
703 if (words[i] != set.words[i])
710 * Cloning this {@code BitSet} produces a new {@code BitSet} that is equal to
711 * it. The clone of the bit set is another bit set that has exactly the same
712 * bits set to {@code true} as this bit set.
714 * @return a clone of this bit set
718 public Object clone() {
719 if (!sizeIsSticky && wordsInUse != words.length)
720 setLength(wordsInUse);
725 * Attempts to reduce internal storage used for the bits in this bit set.
726 * Calling this method may, but is not required to, affect the value returned
727 * by a subsequent call to the {@link #size()} method.
730 private void setLength(int n) {
731 int[] a = new int[n];
732 System.arraycopy(words, 0, a, 0, Math.min(wordsInUse, n));
737 * Returns a string representation of this bit set. For every index for which
738 * this {@code BitSet} contains a bit in the set state, the decimal
739 * representation of that index is included in the result. Such indices are
740 * listed in order from lowest to highest, separated by ", " (a comma and
741 * a space) and surrounded by braces, resulting in the usual mathematical
742 * notation for a set of integers.
748 * BitSet drPepper = new BitSet();
751 * Now {@code drPepper.toString()} returns "{}".
758 * Now {@code drPepper.toString()} returns "{2}".
766 * Now {@code drPepper.toString()} returns "{2, 4, 10}".
768 * @return a string representation of this bit set
771 public String toString() {
772 return escape(this, '{', '}');
775 private final static int[] emptyBitmap = new int[0];
780 * @param bitsetToCopy
783 public static BS copy(BS bitsetToCopy) {
786 * Clazz.clone will copy wordsInUse and sizeIsSticky,
787 * but just a pointer to the words array.
791 * bs = Clazz.clone(bitsetToCopy);
797 int wordCount = bitsetToCopy.wordsInUse;
798 if (wordCount == 0) {
799 bs.words = emptyBitmap;
801 bs.words = new int[bs.wordsInUse = wordCount];
802 System.arraycopy(bitsetToCopy.words, 0, bs.words, 0, wordCount);
810 * @return n bits below max
812 public int cardinalityN(int max) {
813 int n = cardinality();
814 for (int i = length(); --i >= max;)
821 public String toJSON() {
823 int numBits = (wordsInUse > 128) ? cardinality() : wordsInUse
825 SB b = SB.newN(6 * numBits + 2);
828 int i = nextSetBit(0);
831 for (i = nextSetBit(i + 1); i >= 0; i = nextSetBit(i + 1)) {
832 int endOfRun = nextClearBit(i);
834 b.append(", ").appendI(i);
835 } while (++i < endOfRun);
843 public static String escape(BS bs, char chOpen, char chClose) {
845 return chOpen + "{}" + chClose;
847 s.append(chOpen + "{");
848 int imax = bs.length();
852 while (++i <= imax) {
853 boolean isSet = bs.get(i);
854 if (i == imax || iLast >= 0 && !isSet) {
855 if (iLast >= 0 && iFirst != iLast)
856 s.append((iFirst == iLast - 1 ? " " : ":") + iLast);
863 s.append((iFirst == -2 ? "" : " ") + i);
869 s.append("}").appendC(chClose);
873 public static BS unescape(String str) {
876 if (str == null || (len = (str = str.trim()).length()) < 4
877 || str.equalsIgnoreCase("({null})")
878 || (ch = str.charAt(0)) != '(' && ch != '['
879 || str.charAt(len - 1) != (ch == '(' ? ')' : ']')
880 || str.charAt(1) != '{' || str.indexOf('}') != len - 2)
883 for (int i = len; --i >= 2;)
884 if (!PT.isDigit(ch = str.charAt(i)) && ch != ' ' && ch != '\t'
888 while (PT.isDigit(str.charAt(--lastN))) {
895 lastN = Integer.parseInt(str.substring(lastN, len));
896 } catch (NumberFormatException e) {
899 BS bs = BS.newN(lastN);
903 for (int i = 2; i <= len; i++) {
904 switch (ch = str.charAt(i)) {
915 bs.setBits(iPrev, iThis + 1);
920 iPrev = lastN = iThis;
924 if (PT.isDigit(ch)) {
927 iThis = (iThis * 10) + (ch - 48);
931 return (iPrev >= 0 ? null : bs);