diff options
Diffstat (limited to 'libjava/java/util/BitSet.java')
| -rw-r--r-- | libjava/java/util/BitSet.java | 569 |
1 files changed, 451 insertions, 118 deletions
diff --git a/libjava/java/util/BitSet.java b/libjava/java/util/BitSet.java index 1da1875..366c005 100644 --- a/libjava/java/util/BitSet.java +++ b/libjava/java/util/BitSet.java @@ -1,6 +1,5 @@ -// BitSet - A vector of bits. - -/* Copyright (C) 1998, 1999, 2000 Free Software Foundation +/* BitSet.java -- A vector of bits. + Copyright (C) 1998, 1999, 2000, 2001 Free Software Foundation, Inc. This file is part of GNU Classpath. @@ -50,22 +49,32 @@ import java.io.Serializable; * while another thread is simultaneously modifying it, the results are * undefined. * - * @specnote Historically, there has been some confusion as to whether or not - * this class should be synchronized. From an efficiency perspective, - * it is very undesirable to synchronize it because multiple locks - * and explicit lock ordering are required to safely synchronize some - * methods. The JCL 1.2 supplement book specifies that as of JDK - * 1.2, the class is no longer synchronized. - * * @author Jochen Hoenicke * @author Tom Tromey <tromey@cygnus.com> - * @date October 23, 1998. - * @status API complete to JDK 1.3. + * @author Eric Blake <ebb9@email.byu.edu> + * @status updated to 1.4 */ public class BitSet implements Cloneable, Serializable { /** - * Create a new empty bit set. + * Compatible with JDK 1.0. + */ + private static final long serialVersionUID = 7997698588986878753L; + + /** + * A common mask. + */ + private static final int LONG_MASK = 0x3f; + + /** + * The actual bits. + * @serial the i'th bit is in bits[i/64] at position i%64 (where position + * 0 is the least significant). + */ + private long[] bits; + + /** + * Create a new empty bit set. All bits are initially false. */ public BitSet() { @@ -75,18 +84,15 @@ public class BitSet implements Cloneable, Serializable /** * Create a new empty bit set, with a given size. This * constructor reserves enough space to represent the integers - * from <code>0</code> to <code>nbits-1</code>. - * @param nbits the initial size of the bit set. - * @throws NegativeArraySizeException if the specified initial - * size is negative. - * @require nbits >= 0 + * from <code>0</code> to <code>nbits-1</code>. + * + * @param nbits the initial size of the bit set + * @throws NegativeArraySizeException if nbits < 0 */ public BitSet(int nbits) { - if (nbits < 0) - throw new NegativeArraySizeException(); - int length = nbits / 64; - if (nbits % 64 != 0) + int length = nbits >>> 6; + if ((nbits & LONG_MASK) != 0) ++length; bits = new long[length]; } @@ -95,8 +101,9 @@ public class BitSet implements Cloneable, Serializable * Performs the logical AND operation on this bit set and the * given <code>set</code>. This means it builds the intersection * of the two sets. The result is stored into this bit set. - * @param set the second bit set. - * @require set != null + * + * @param set the second bit set + * @throws NullPointerException if set is null */ public void and(BitSet bs) { @@ -104,63 +111,143 @@ public class BitSet implements Cloneable, Serializable int i; for (i = 0; i < max; ++i) bits[i] &= bs.bits[i]; - for (; i < bits.length; ++i) - bits[i] = 0; + while (i < bits.length) + bits[i++] = 0; } /** * Performs the logical AND operation on this bit set and the * complement of the given <code>set</code>. This means it * selects every element in the first set, that isn't in the - * second set. The result is stored into this bit set. - * @param set the second bit set. - * @require set != null - * @since JDK1.2 + * second set. The result is stored into this bit set. + * + * @param set the second bit set + * @throws NullPointerException if set is null + * @since 1.2 */ public void andNot(BitSet bs) { - int max = Math.min(bits.length, bs.bits.length); - int i; - for (i = 0; i < max; ++i) + int i = Math.min(bits.length, bs.bits.length); + while (--i >= 0) bits[i] &= ~bs.bits[i]; } /** + * Returns the number of bits set to true. + * + * @return the number of true bits + * @since 1.4 + */ + public int cardinality() + { + int card = 0; + for (int i = bits.length - 1; i >= 0; i--) + { + long a = bits[i]; + // Take care of common cases. + if (a == 0) + continue; + if (a == -1) + { + card += 64; + continue; + } + + // Successively collapse alternating bit groups into a sum. + a = ((a >> 1) & 0x5555555555555555L) + (a & 0x5555555555555555L); + a = ((a >> 2) & 0x3333333333333333L) + (a & 0x3333333333333333L); + int b = (int) ((a >>> 32) + a); + b = ((b >> 4) & 0x0f0f0f0f) + (b & 0x0f0f0f0f); + b = ((b >> 8) & 0x00ff00ff) + (b & 0x00ff00ff); + card += ((b >> 16) & 0x0000ffff) + (b & 0x0000ffff); + } + return card; + } + + /** + * Sets all bits in the set to false. + * + * @since 1.4 + */ + public void clear() + { + Arrays.fill(bits, 0); + } + + /** * Removes the integer <code>bitIndex</code> from this set. That is * the corresponding bit is cleared. If the index is not in the set, * this method does nothing. - * @param bitIndex a non-negative integer. - * @exception ArrayIndexOutOfBoundsException if the specified bit index - * is negative. - * @require bitIndex >= 0 + * + * @param bitIndex a non-negative integer + * @throws IndexOutOfBoundsException if bitIndex < 0 */ public void clear(int pos) { - if (pos < 0) - throw new IndexOutOfBoundsException(); - int bit = pos % 64; - int offset = pos / 64; + int offset = pos >>> 6; ensure(offset); - bits[offset] &= ~(1L << bit); + // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, + // so we'll just let that be our exception. + bits[offset] &= ~(1L << pos); + } + + /** + * Sets the bits between from (inclusive) and to (exclusive) to false. + * + * @param from the start range (inclusive) + * @param to the end range (exclusive) + * @throws IndexOutOfBoundsException if from < 0 || from > to + * @since 1.4 + */ + public void clear(int from, int to) + { + if (from < 0 || from > to) + throw new IndexOutOfBoundsException(); + if (from == to) + return; + int lo_offset = from >>> 6; + int hi_offset = to >>> 6; + ensure(hi_offset); + if (lo_offset == hi_offset) + { + bits[hi_offset] &= ((1L << from) - 1) | (-1L << to); + return; + } + + bits[lo_offset] &= (1L << from) - 1; + bits[hi_offset] &= -1L << to; + for (int i = lo_offset + 1; i < hi_offset; i++) + bits[i] = 0; } /** * Create a clone of this bit set, that is an instance of the same * class and contains the same elements. But it doesn't change when * this bit set changes. + * * @return the clone of this object. */ public Object clone() { - BitSet bs = new BitSet(bits.length * 64); - System.arraycopy(bits, 0, bs.bits, 0, bits.length); - return bs; + try + { + BitSet bs = (BitSet) super.clone(); + bs.bits = (long[]) bits.clone(); + return bs; + } + catch (CloneNotSupportedException e) + { + // Impossible to get here. + return null; + } } /** * Returns true if the <code>obj</code> is a bit set that contains * exactly the same elements as this bit set, otherwise false. - * @return true if obj equals this bit set. + * + * @param obj the object to compare to + * @return true if obj equals this bit set */ public boolean equals(Object obj) { @@ -171,42 +258,124 @@ public class BitSet implements Cloneable, Serializable int i; for (i = 0; i < max; ++i) if (bits[i] != bs.bits[i]) - return false; + return false; // If one is larger, check to make sure all extra bits are 0. for (int j = i; j < bits.length; ++j) if (bits[j] != 0) - return false; + return false; for (int j = i; j < bs.bits.length; ++j) if (bs.bits[j] != 0) - return false; + return false; return true; } /** - * Returns true if the integer <code>bitIndex</code> is in this bit - * set, otherwise false. - * @param bitIndex a non-negative integer - * @return the value of the bit at the specified index. - * @exception ArrayIndexOutOfBoundsException if the specified bit index - * is negative. - * @require bitIndex >= 0 + * Sets the bit at the index to the opposite value. + * + * @param index the index of the bit + * @throws IndexOutOfBoundsException if index is negative + * @since 1.4 */ - public boolean get(int pos) + public void flip(int index) { - if (pos < 0) + int offset = index >>> 6; + ensure(offset); + // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, + // so we'll just let that be our exception. + bits[offset] ^= 1L << index; + } + + /** + * Sets a range of bits to the opposite value. + * + * @param from the low index (inclusive) + * @param to the high index (exclusive) + * @throws IndexOutOfBoundsException if from > to || from < 0 + * @since 1.4 + */ + public void flip(int from, int to) + { + if (from < 0 || from > to) throw new IndexOutOfBoundsException(); + if (from == to) + return; + int lo_offset = from >>> 6; + int hi_offset = to >>> 6; + ensure(hi_offset); + if (lo_offset == hi_offset) + { + bits[hi_offset] ^= (-1L << from) & ((1L << to) - 1); + return; + } - int bit = pos % 64; - int offset = pos / 64; + bits[lo_offset] ^= -1L << from; + bits[hi_offset] ^= (1L << to) - 1; + for (int i = lo_offset + 1; i < hi_offset; i++) + bits[i] ^= -1; + } + /** + * Returns true if the integer <code>bitIndex</code> is in this bit + * set, otherwise false. + * + * @param pos a non-negative integer + * @return the value of the bit at the specified index + * @throws IndexOutOfBoundsException if the index is negative + */ + public boolean get(int pos) + { + int offset = pos >>> 6; if (offset >= bits.length) return false; + // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, + // so we'll just let that be our exception. + return (bits[offset] & (1L << pos)) != 0; + } + + /** + * Returns a new <code>BitSet</code> composed of a range of bits from + * this one. + * + * @param from the low index (inclusive) + * @param to the high index (exclusive) + * @throws IndexOutOfBoundsException if from > to || from < 0 + * @since 1.4 + */ + public BitSet get(int from, int to) + { + if (from < 0 || from > to) + throw new IndexOutOfBoundsException(); + BitSet bs = new BitSet(to - from); + int lo_offset = from >>> 6; + if (lo_offset >= bits.length) + return bs; + + int lo_bit = from & LONG_MASK; + int hi_offset = to >>> 6; + if (lo_bit == 0) + { + int len = Math.min(hi_offset - lo_offset + 1, bits.length - lo_offset); + System.arraycopy(bits, lo_offset, bs.bits, 0, len); + if (hi_offset < bits.length) + bs.bits[hi_offset - lo_offset] &= (1L << to) - 1; + return bs; + } - return (bits[offset] & (1L << bit)) == 0 ? false : true; + int len = Math.min(hi_offset, bits.length - 1); + int reverse = ~lo_bit; + int i; + for (i = 0; lo_offset < len; lo_offset++, i++) + bs.bits[i] = ((bits[lo_offset] >>> lo_bit) + | (bits[lo_offset + 1] << reverse)); + if ((to & LONG_MASK) > lo_bit) + bs.bits[i++] = bits[lo_offset] >>> lo_bit; + if (hi_offset < bits.length) + bs.bits[i - 1] &= (1L << (to - from)) - 1; + return bs; } /** - * Returns a hash code value for this bit set. The hash code of + * Returns a hash code value for this bit set. The hash code of * two bit sets containing the same integers is identical. The algorithm * used to compute it is as follows: * @@ -233,21 +402,55 @@ public class BitSet implements Cloneable, Serializable * </pre> * * Note that the hash code values changes, if the set is changed. + * * @return the hash code value for this bit set. */ public int hashCode() { long h = 1234; - for (int i = bits.length - 1; i >= 0; --i) - h ^= bits[i] * (i + 1); + for (int i = bits.length; i > 0; ) + h ^= i * bits[--i]; return (int) ((h >> 32) ^ h); } /** + * Returns true if the specified BitSet and this one share at least one + * common true bit. + * + * @param set the set to check for intersection + * @return true if the sets intersect + * @throws NullPointerException if set is null + * @since 1.4 + */ + public boolean intersects(BitSet set) + { + int i = Math.min(bits.length, set.bits.length); + while (--i >= 0) + if ((bits[i] & set.bits[i]) != 0) + return true; + return false; + } + + /** + * Returns true if this set contains no true bits. + * + * @return true if all bits are false + * @since 1.4 + */ + public boolean isEmpty() + { + for (int i = bits.length - 1; i >= 0; i--) + if (bits[i] != 0) + return false; + return true; + } + + /** * Returns the logical number of bits actually used by this bit * set. It returns the index of the highest set bit plus one. * Note that this method doesn't return the number of set bits. - * @return the index of the highest set bit plus one. + * + * @return the index of the highest set bit plus one. */ public int length() { @@ -266,54 +469,186 @@ public class BitSet implements Cloneable, Serializable // b >= 0 checks if the highest bit is zero. while (b >= 0) { - --len; - b <<= 1; + --len; + b <<= 1; } return len; } /** + * Returns the index of the next false bit, from the specified bit + * (inclusive). + * + * @param from the start location + * @return the first false bit + * @throws IndexOutOfBoundsException if from is negative + * @since 1.4 + */ + public int nextClearBit(int from) + { + int offset = from >>> 6; + long mask = 1L << from; + while (offset < bits.length) + { + // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, + // so we'll just let that be our exception. + long h = bits[offset]; + do + { + if ((h & mask) == 0) + return from; + mask <<= 1; + from++; + } + while (mask != 0); + mask = 1; + offset++; + } + return from; + } + + /** + * Returns the index of the next true bit, from the specified bit + * (inclusive). If there is none, -1 is returned. You can iterate over + * all true bits with this loop:<br> + * <pre> + * for (int i = bs.nextSetBit(0); i >= 0; i = bs.nextSetBit(i + 1)) + * { // operate on i here } + * </pre> + * + * @param from the start location + * @return the first true bit, or -1 + * @throws IndexOutOfBoundsException if from is negative + * @since 1.4 + */ + public int nextSetBit(int from) + { + int offset = from >>> 6; + long mask = 1L << from; + while (offset < bits.length) + { + // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, + // so we'll just let that be our exception. + long h = bits[offset]; + do + { + if ((h & mask) != 0) + return from; + mask <<= 1; + from++; + } + while (mask != 0); + mask = 1; + offset++; + } + return -1; + } + + /** * Performs the logical OR operation on this bit set and the * given <code>set</code>. This means it builds the union * of the two sets. The result is stored into this bit set, which * grows as necessary. - * @param set the second bit set. - * @exception OutOfMemoryError if the current set can't grow. - * @require set != null + * + * @param bs the second bit set + * @throws NullPointerException if bs is null */ public void or(BitSet bs) { ensure(bs.bits.length - 1); - int i; - for (i = 0; i < bs.bits.length; ++i) + for (int i = bs.bits.length - 1; i >= 0; i--) bits[i] |= bs.bits[i]; } /** - * Add the integer <code>bitIndex</code> to this set. That is + * Add the integer <code>bitIndex</code> to this set. That is * the corresponding bit is set to true. If the index was already in * the set, this method does nothing. The size of this structure * is automatically increased as necessary. - * @param bitIndex a non-negative integer. - * @exception ArrayIndexOutOfBoundsException if the specified bit index - * is negative. - * @require bitIndex >= 0 + * + * @param pos a non-negative integer. + * @throws IndexOutOfBoundsException if pos is negative */ public void set(int pos) { - if (pos < 0) - throw new IndexOutOfBoundsException(); - int bit = pos % 64; - int offset = pos / 64; + int offset = pos >>> 6; ensure(offset); - bits[offset] |= 1L << bit; + // ArrayIndexOutOfBoundsException subclasses IndexOutOfBoundsException, + // so we'll just let that be our exception. + bits[offset] |= 1L << pos; + } + + /** + * Sets the bit at the given index to the specified value. The size of + * this structure is automatically increased as necessary. + * + * @param index the position to set + * @param value the value to set it to + * @throws IndexOutOfBoundsException if index is negative + * @since 1.4 + */ + public void set(int index, boolean value) + { + if (value) + set(index); + else + clear(index); + } + + /** + * Sets the bits between from (inclusive) and to (exclusive) to true. + * + * @param from the start range (inclusive) + * @param to the end range (exclusive) + * @throws IndexOutOfBoundsException if from < 0 || from > to + * @since 1.4 + */ + public void set(int from, int to) + { + if (from < 0 || from > to) + throw new IndexOutOfBoundsException(); + if (from == to) + return; + int lo_offset = from >>> 6; + int hi_offset = to >>> 6; + ensure(hi_offset); + if (lo_offset == hi_offset) + { + bits[hi_offset] |= (-1L << from) & ((1L << to) - 1); + return; + } + + bits[lo_offset] |= -1L << from; + bits[hi_offset] |= (1L << to) - 1; + for (int i = lo_offset + 1; i < hi_offset; i++) + bits[i] = -1; + } + + /** + * Sets the bits between from (inclusive) and to (exclusive) to the + * specified value. + * + * @param from the start range (inclusive) + * @param to the end range (exclusive) + * @param value the value to set it to + * @throws IndexOutOfBoundsException if from < 0 || from > to + * @since 1.4 + */ + public void set(int from, int to, boolean value) + { + if (value) + set(from, to); + else + clear(from, to); } /** * Returns the number of bits actually used by this bit set. Note - * that this method doesn't return the number of set bits. - * @returns the number of bits currently used. + * that this method doesn't return the number of set bits, and that + * future requests for larger bits will make this automatically grow. + * + * @return the number of bits currently used. */ public int size() { @@ -324,32 +659,32 @@ public class BitSet implements Cloneable, Serializable * Returns the string representation of this bit set. This * consists of a comma separated list of the integers in this set * surrounded by curly braces. There is a space after each comma. + * A sample string is thus "{1, 3, 53}". * @return the string representation. */ public String toString() { - String r = "{"; + StringBuffer r = new StringBuffer("{"); boolean first = true; for (int i = 0; i < bits.length; ++i) { - long bit = 1; - long word = bits[i]; - if (word == 0) - continue; - for (int j = 0; j < 64; ++j) - { - if ((word & bit) != 0) - { - if (!first) - r += ", "; - r += Integer.toString(64 * i + j); - first = false; - } - bit <<= 1; - } + long bit = 1; + long word = bits[i]; + if (word == 0) + continue; + for (int j = 0; j < 64; ++j) + { + if ((word & bit) != 0) + { + if (! first) + r.append(", "); + r.append(64 * i + j); + first = false; + } + bit <<= 1; + } } - - return r += "}"; + return r.append("}").toString(); } /** @@ -357,32 +692,30 @@ public class BitSet implements Cloneable, Serializable * given <code>set</code>. This means it builds the symmetric * remainder of the two sets (the elements that are in one set, * but not in the other). The result is stored into this bit set, - * which grows as necessary. - * @param set the second bit set. - * @exception OutOfMemoryError if the current set can't grow. - * @require set != null + * which grows as necessary. + * + * @param bs the second bit set + * @throws NullPointerException if bs is null */ public void xor(BitSet bs) { ensure(bs.bits.length - 1); - int i; - for (i = 0; i < bs.bits.length; ++i) + for (int i = bs.bits.length - 1; i >= 0; i--) bits[i] ^= bs.bits[i]; } - // Make sure the vector is big enough. + /** + * Make sure the vector is big enough. + * + * @param lastElt the size needed for the bits array + */ private final void ensure(int lastElt) { - if (lastElt + 1 > bits.length) + if (lastElt >= bits.length) { - long[] nd = new long[lastElt + 1]; - System.arraycopy(bits, 0, nd, 0, bits.length); - bits = nd; + long[] nd = new long[lastElt + 1]; + System.arraycopy(bits, 0, nd, 0, bits.length); + bits = nd; } } - - // The actual bits. - long[] bits; - - private static final long serialVersionUID = 7997698588986878753L; } |