2362N/A * Copyright (c) 1995, 2007, Oracle and/or its affiliates. All rights reserved. 0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 0N/A * This code is free software; you can redistribute it and/or modify it 0N/A * under the terms of the GNU General Public License version 2 only, as 2362N/A * published by the Free Software Foundation. Oracle designates this 0N/A * particular file as subject to the "Classpath" exception as provided 2362N/A * by Oracle in the LICENSE file that accompanied this code. 0N/A * This code is distributed in the hope that it will be useful, but WITHOUT 0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 0N/A * version 2 for more details (a copy is included in the LICENSE file that 0N/A * accompanied this code). 0N/A * You should have received a copy of the GNU General Public License version 0N/A * 2 along with this work; if not, write to the Free Software Foundation, 0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2362N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2362N/A * or visit www.oracle.com if you need additional information or have any 0N/A * This class implements a vector of bits that grows as needed. Each 0N/A * component of the bit set has a {@code boolean} value. The 0N/A * bits of a {@code BitSet} are indexed by nonnegative integers. 0N/A * Individual indexed bits can be examined, set, or cleared. One 0N/A * {@code BitSet} may be used to modify the contents of another 0N/A * {@code BitSet} through logical AND, logical inclusive OR, and 0N/A * logical exclusive OR operations. 0N/A * <p>By default, all bits in the set initially have the value 0N/A * <p>Every bit set has a current size, which is the number of bits 0N/A * of space currently in use by the bit set. Note that the size is 0N/A * related to the implementation of a bit set, so it may change with 0N/A * implementation. The length of a bit set relates to logical length 0N/A * of a bit set and is defined independently of implementation. 0N/A * <p>Unless otherwise noted, passing a null parameter to any of the 0N/A * methods in a {@code BitSet} will result in a 0N/A * {@code NullPointerException}. 0N/A * <p>A {@code BitSet} is not safe for multithreaded use without 0N/A * external synchronization. 0N/A * @author Arthur van Hoff 0N/A * @author Michael McCloskey 0N/A * @author Martin Buchholz 0N/A * BitSets are packed into arrays of "words." Currently a word is 0N/A * a long, which consists of 64 bits, requiring 6 address bits. 0N/A * The choice of word size is determined purely by performance concerns. 0N/A /* Used to shift left or right for a partial word mask */ 0N/A * @serialField bits long[] 0N/A * The bits in this BitSet. The ith bit is stored in bits[i/64] at 0N/A * bit position i % 64 (where bit position 0 refers to the least 0N/A * significant bit and 63 refers to the most significant bit). 0N/A * The internal field corresponding to the serialField "bits". 0N/A * The number of words in the logical size of this BitSet. 0N/A * Whether the size of "words" is user-specified. If so, we assume 0N/A * the user knows what he's doing and try harder to preserve it. 0N/A /* use serialVersionUID from JDK 1.0.2 for interoperability */ 0N/A * Given a bit index, return word index containing it. 0N/A * Every public method must preserve these invariants. 0N/A * Sets the field wordsInUse to the logical size in words of the bit set. 0N/A * WARNING:This method assumes that the number of words actually in use is 0N/A * less than or equal to the current value of wordsInUse! 0N/A // Traverse the bitset until a used word is found 0N/A * Creates a new bit set. All bits are initially {@code false}. 0N/A * Creates a bit set whose initial size is large enough to explicitly 0N/A * represent bits with indices in the range {@code 0} through 0N/A * {@code nbits-1}. All bits are initially {@code false}. 0N/A * @param nbits the initial size of the bit set 0N/A * @throws NegativeArraySizeException if the specified initial size 0N/A // nbits can't be negative; size 0 is OK 0N/A * Creates a bit set using words as the internal representation. 0N/A * The last word (if there is one) must be non-zero. 0N/A * Returns a new bit set containing all the bits in the given long array. 0N/A * <p>More precisely, 0N/A * <br>{@code BitSet.valueOf(longs).get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)} 0N/A * <br>for all {@code n < 64 * longs.length}. 0N/A * <p>This method is equivalent to 0N/A * {@code BitSet.valueOf(LongBuffer.wrap(longs))}. 0N/A * @param longs a long array containing a little-endian representation 0N/A * of a sequence of bits to be used as the initial bits of the 0N/A * Returns a new bit set containing all the bits in the given long 0N/A * buffer between its position and limit. 0N/A * <p>More precisely, 0N/A * <br>{@code BitSet.valueOf(lb).get(n) == ((lb.get(lb.position()+n/64) & (1L<<(n%64))) != 0)} 0N/A * <br>for all {@code n < 64 * lb.remaining()}. 0N/A * <p>The long buffer is not modified by this method, and no 0N/A * reference to the buffer is retained by the bit set. 0N/A * @param lb a long buffer containing a little-endian representation 0N/A * of a sequence of bits between its position and limit, to be 0N/A * used as the initial bits of the new bit set 0N/A * Returns a new bit set containing all the bits in the given byte array. 0N/A * <p>More precisely, 0N/A * <br>{@code BitSet.valueOf(bytes).get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)} 0N/A * <br>for all {@code n < 8 * bytes.length}. 0N/A * <p>This method is equivalent to 0N/A * {@code BitSet.valueOf(ByteBuffer.wrap(bytes))}. 0N/A * @param bytes a byte array containing a little-endian 0N/A * representation of a sequence of bits to be used as the 0N/A * initial bits of the new bit set 0N/A * Returns a new bit set containing all the bits in the given byte 0N/A * buffer between its position and limit. 0N/A * <p>More precisely, 0N/A * <br>{@code BitSet.valueOf(bb).get(n) == ((bb.get(bb.position()+n/8) & (1<<(n%8))) != 0)} 0N/A * <br>for all {@code n < 8 * bb.remaining()}. 0N/A * <p>The byte buffer is not modified by this method, and no 0N/A * reference to the buffer is retained by the bit set. 0N/A * @param bb a byte buffer containing a little-endian representation 0N/A * of a sequence of bits between its position and limit, to be 0N/A * used as the initial bits of the new bit set 0N/A * Returns a new byte array containing all the bits in this bit set. 0N/A * <p>More precisely, if 0N/A * <br>{@code byte[] bytes = s.toByteArray();} 0N/A * <br>then {@code bytes.length == (s.length()+7)/8} and 0N/A * <br>{@code s.get(n) == ((bytes[n/8] & (1<<(n%8))) != 0)} 0N/A * <br>for all {@code n < 8 * bytes.length}. 0N/A * @return a byte array containing a little-endian representation 0N/A * of all the bits in this bit set 0N/A for (
long x =
words[n -
1]; x !=
0; x >>>=
8)
0N/A for (
int i =
0; i < n -
1; i++)
0N/A for (
long x =
words[n -
1]; x !=
0; x >>>=
8)
0N/A * Returns a new long array containing all the bits in this bit set. 0N/A * <p>More precisely, if 0N/A * <br>{@code long[] longs = s.toLongArray();} 0N/A * <br>then {@code longs.length == (s.length()+63)/64} and 0N/A * <br>{@code s.get(n) == ((longs[n/64] & (1L<<(n%64))) != 0)} 0N/A * <br>for all {@code n < 64 * longs.length}. 0N/A * @return a long array containing a little-endian representation 0N/A * of all the bits in this bit set 0N/A * Ensures that the BitSet can hold enough words. 0N/A * @param wordsRequired the minimum acceptable number of words. 0N/A // Allocate larger of doubled size or required size 0N/A * Ensures that the BitSet can accommodate a given wordIndex, 0N/A * temporarily violating the invariants. The caller must 0N/A * restore the invariants before returning to the user, 0N/A * possibly using recalculateWordsInUse(). 0N/A * @param wordIndex the index to be accommodated. 0N/A * Checks that fromIndex ... toIndex is a valid range of bit indices. 0N/A * Sets the bit at the specified index to the complement of its 0N/A * @param bitIndex the index of the bit to flip 0N/A * @throws IndexOutOfBoundsException if the specified index is negative 0N/A * Sets each bit from the specified {@code fromIndex} (inclusive) to the 0N/A * specified {@code toIndex} (exclusive) to the complement of its current 0N/A * @param fromIndex index of the first bit to flip 0N/A * @param toIndex index after the last bit to flip 0N/A * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, 0N/A * or {@code toIndex} is negative, or {@code fromIndex} is 0N/A * larger than {@code toIndex} 0N/A // Case 2: Multiple words 0N/A // Handle first word 0N/A // Handle intermediate words, if any 0N/A * Sets the bit at the specified index to {@code true}. 0N/A * @param bitIndex a bit index 0N/A * @throws IndexOutOfBoundsException if the specified index is negative 0N/A * Sets the bit at the specified index to the specified value. 0N/A * @param bitIndex a bit index 0N/A * @param value a boolean value to set 0N/A * @throws IndexOutOfBoundsException if the specified index is negative 0N/A * Sets the bits from the specified {@code fromIndex} (inclusive) to the 0N/A * specified {@code toIndex} (exclusive) to {@code true}. 0N/A * @param fromIndex index of the first bit to be set 0N/A * @param toIndex index after the last bit to be set 0N/A * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, 0N/A * or {@code toIndex} is negative, or {@code fromIndex} is 0N/A * larger than {@code toIndex} 0N/A // Increase capacity if necessary 0N/A // Case 2: Multiple words 0N/A // Handle first word 0N/A // Handle intermediate words, if any 0N/A // Handle last word (restores invariants) 0N/A * Sets the bits from the specified {@code fromIndex} (inclusive) to the 0N/A * specified {@code toIndex} (exclusive) to the specified value. 0N/A * @param fromIndex index of the first bit to be set 0N/A * @param toIndex index after the last bit to be set 0N/A * @param value value to set the selected bits to 0N/A * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, 0N/A * or {@code toIndex} is negative, or {@code fromIndex} is 0N/A * larger than {@code toIndex} 0N/A * Sets the bit specified by the index to {@code false}. 0N/A * @param bitIndex the index of the bit to be cleared 0N/A * @throws IndexOutOfBoundsException if the specified index is negative 0N/A * Sets the bits from the specified {@code fromIndex} (inclusive) to the 0N/A * specified {@code toIndex} (exclusive) to {@code false}. 0N/A * @param fromIndex index of the first bit to be cleared 0N/A * @param toIndex index after the last bit to be cleared 0N/A * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, 0N/A * or {@code toIndex} is negative, or {@code fromIndex} is 0N/A * larger than {@code toIndex} 0N/A // Case 2: Multiple words 0N/A // Handle first word 0N/A // Handle intermediate words, if any 0N/A * Sets all of the bits in this BitSet to {@code false}. 0N/A * Returns the value of the bit with the specified index. The value 0N/A * is {@code true} if the bit with the index {@code bitIndex} 0N/A * is currently set in this {@code BitSet}; otherwise, the result 0N/A * @param bitIndex the bit index 0N/A * @return the value of the bit with the specified index 0N/A * @throws IndexOutOfBoundsException if the specified index is negative 0N/A * Returns a new {@code BitSet} composed of bits from this {@code BitSet} 0N/A * from {@code fromIndex} (inclusive) to {@code toIndex} (exclusive). 0N/A * @param fromIndex index of the first bit to include 0N/A * @param toIndex index after the last bit to include 0N/A * @return a new {@code BitSet} from a range of this {@code BitSet} 0N/A * @throws IndexOutOfBoundsException if {@code fromIndex} is negative, 0N/A * or {@code toIndex} is negative, or {@code fromIndex} is 0N/A * larger than {@code toIndex} 0N/A // If no set bits in range return empty bitset 0N/A // Process all words but the last word 0N/A // Process the last word 0N/A ?
/* straddles source words */ 0N/A // Set wordsInUse correctly 0N/A * Returns the index of the first bit that is set to {@code true} 0N/A * that occurs on or after the specified starting index. If no such 0N/A * bit exists then {@code -1} is returned. 0N/A * <p>To iterate over the {@code true} bits in a {@code BitSet}, 0N/A * use the following loop: 0N/A * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i+1)) { 0N/A * // operate on index i here 0N/A * @param fromIndex the index to start checking from (inclusive) 0N/A * @return the index of the next set bit, or {@code -1} if there 0N/A * @throws IndexOutOfBoundsException if the specified index is negative 0N/A * Returns the index of the first bit that is set to {@code false} 0N/A * that occurs on or after the specified starting index. 0N/A * @param fromIndex the index to start checking from (inclusive) 0N/A * @return the index of the next clear bit 0N/A * @throws IndexOutOfBoundsException if the specified index is negative 0N/A // Neither spec nor implementation handle bitsets of maximal length. 0N/A * Returns the index of the nearest bit that is set to {@code true} 0N/A * that occurs on or before the specified starting index. 0N/A * If no such bit exists, or if {@code -1} is given as the 0N/A * starting index, then {@code -1} is returned. 0N/A * <p>To iterate over the {@code true} bits in a {@code BitSet}, 0N/A * use the following loop: 0N/A * for (int i = bs.length(); (i = bs.previousSetBit(i-1)) >= 0; ) { 0N/A * // operate on index i here 0N/A * @param fromIndex the index to start checking from (inclusive) 0N/A * @return the index of the previous set bit, or {@code -1} if there 0N/A * @throws IndexOutOfBoundsException if the specified index is less 0N/A * Returns the index of the nearest bit that is set to {@code false} 0N/A * that occurs on or before the specified starting index. 0N/A * If no such bit exists, or if {@code -1} is given as the 0N/A * starting index, then {@code -1} is returned. 0N/A * @param fromIndex the index to start checking from (inclusive) 0N/A * @return the index of the previous clear bit, or {@code -1} if there 0N/A * @throws IndexOutOfBoundsException if the specified index is less 0N/A * Returns the "logical size" of this {@code BitSet}: the index of 0N/A * the highest set bit in the {@code BitSet} plus one. Returns zero 0N/A * if the {@code BitSet} contains no set bits. 0N/A * @return the logical size of this {@code BitSet} 0N/A * Returns true if this {@code BitSet} contains no bits that are set 0N/A * @return boolean indicating whether this {@code BitSet} is empty 0N/A * Returns true if the specified {@code BitSet} has any bits set to 0N/A * {@code true} that are also set to {@code true} in this {@code BitSet}. 0N/A * @param set {@code BitSet} to intersect with 0N/A * @return boolean indicating whether this {@code BitSet} intersects 0N/A * the specified {@code BitSet} 0N/A * Returns the number of bits set to {@code true} in this {@code BitSet}. 0N/A * @return the number of bits set to {@code true} in this {@code BitSet} 0N/A * Performs a logical <b>AND</b> of this target bit set with the 0N/A * argument bit set. This bit set is modified so that each bit in it 0N/A * has the value {@code true} if and only if it both initially 0N/A * had the value {@code true} and the corresponding bit in the 0N/A * bit set argument also had the value {@code true}. 0N/A * @param set a bit set 0N/A // Perform logical AND on words in common 0N/A * Performs a logical <b>OR</b> of this bit set with the bit set 0N/A * argument. This bit set is modified so that a bit in it has the 0N/A * value {@code true} if and only if it either already had the 0N/A * value {@code true} or the corresponding bit in the bit set 0N/A * argument has the value {@code true}. 0N/A * @param set a bit set 0N/A // Perform logical OR on words in common 0N/A // Copy any remaining words 0N/A // recalculateWordsInUse() is unnecessary 0N/A * Performs a logical <b>XOR</b> of this bit set with the bit set 0N/A * argument. This bit set is modified so that a bit in it has the 0N/A * value {@code true} if and only if one of the following 0N/A * <li>The bit initially has the value {@code true}, and the 0N/A * corresponding bit in the argument has the value {@code false}. 0N/A * <li>The bit initially has the value {@code false}, and the 0N/A * corresponding bit in the argument has the value {@code true}. 0N/A * @param set a bit set 0N/A // Perform logical XOR on words in common 0N/A // Copy any remaining words 0N/A * Clears all of the bits in this {@code BitSet} whose corresponding 0N/A * bit is set in the specified {@code BitSet}. 0N/A * @param set the {@code BitSet} with which to mask this 0N/A // Perform logical (a & !b) on words in common 0N/A * Returns the hash code value for this bit set. The hash code depends 0N/A * only on which bits are set within this {@code BitSet}. 0N/A * <p>The hash code is defined to be the result of the following 0N/A * public int hashCode() { 0N/A * long[] words = toLongArray(); 0N/A * for (int i = words.length; --i >= 0; ) 0N/A * h ^= words[i] * (i + 1); 0N/A * return (int)((h >> 32) ^ h); 0N/A * Note that the hash code changes if the set of bits is altered. 0N/A * @return the hash code value for this bit set 0N/A return (
int)((h >>
32) ^ h);
0N/A * Returns the number of bits of space actually in use by this 0N/A * {@code BitSet} to represent bit values. 0N/A * The maximum element in the set is the size - 1st element. 0N/A * @return the number of bits currently in this bit set 0N/A * Compares this object against the specified object. 0N/A * The result is {@code true} if and only if the argument is 0N/A * not {@code null} and is a {@code Bitset} object that has 0N/A * exactly the same set of bits set to {@code true} as this bit 0N/A * set. That is, for every nonnegative {@code int} index {@code k}, 0N/A * <pre>((BitSet)obj).get(k) == this.get(k)</pre> 0N/A * must be true. The current sizes of the two bit sets are not compared. 0N/A * @param obj the object to compare with 0N/A * @return {@code true} if the objects are the same; 0N/A * {@code false} otherwise 0N/A // Check words in use by both BitSets 0N/A * Cloning this {@code BitSet} produces a new {@code BitSet} 0N/A * that is equal to it. 0N/A * The clone of the bit set is another bit set that has exactly the 0N/A * same bits set to {@code true} as this bit set. 0N/A * @return a clone of this bit set 0N/A * Attempts to reduce internal storage used for the bits in this bit set. 0N/A * Calling this method may, but is not required to, affect the value 0N/A * returned by a subsequent call to the {@link #size()} method. 0N/A * Save the state of the {@code BitSet} instance to a stream (i.e., 0N/A * Reconstitute the {@code BitSet} instance from a stream (i.e., 0N/A // Assume maximum length then find real length 0N/A // because recalculateWordsInUse assumes maintenance 0N/A // or reduction in logical size 0N/A * Returns a string representation of this bit set. For every index 0N/A * for which this {@code BitSet} contains a bit in the set 0N/A * state, the decimal representation of that index is included in 0N/A * the result. Such indices are listed in order from lowest to 0N/A * highest, separated by ", " (a comma and a space) and 0N/A * surrounded by braces, resulting in the usual mathematical 0N/A * notation for a set of integers. 0N/A * BitSet drPepper = new BitSet();</pre> 0N/A * Now {@code drPepper.toString()} returns "{@code {}}".<p> 0N/A * drPepper.set(2);</pre> 0N/A * Now {@code drPepper.toString()} returns "{@code {2}}".<p> 0N/A * drPepper.set(10);</pre> 0N/A * Now {@code drPepper.toString()} returns "{@code {2, 4, 10}}". 0N/A * @return a string representation of this bit set