structure
Class BitSet

java.lang.Object
  |
  +--structure.BitSet

public class BitSet
extends java.lang.Object

Implementation of a set of numbered bits. This class's interface differs from the Set, java.util.Bitset, and Set interfaces, so care must be taken to invoke the proper methods.

See Also:
CharSet, BitSet

Field Summary
protected  int allocated
          The current number of integers allocated.
protected  int bitsPerInt
          The number of bits contained in a single integer.
protected  int[] data
          The array of integers that contains the set's bits
protected  int initialCapacity
          The initial capacity of the set, by default.
 
Constructor Summary
BitSet()
          Constructs an empty bitset.
BitSet(int count)
          Constructs an empty bitset with potential to hold values between 0..count-1.
 
Method Summary
 void add(int i)
          Adds a bit to the bitset, if not already there.
 void clear()
          Remove all bits from the set.
 void clear(int count)
          Remove bits from set; set size to count.
 java.lang.Object clone()
          Returns a copy of the set.
 boolean contains(int i)
          Determine if a bit is a member of the set.
 java.lang.Object difference(BitSet other)
          Computes the difference between this set and the other.
 boolean equals(java.lang.Object o)
          Return true iff this set and o contain the same elements.
protected  void extend(int bit)
          Ensures that bit "bit" is within capacity of set.
protected  int indexOf(int b)
          Determine the int index associated with a bit number.
 java.lang.Object intersection(BitSet other)
          Return the intersection of this set and the other.
 boolean isEmpty()
          Determine if a set is empty.
protected  int offsetOf(int bit)
          Return the bit index within the associated int of bit "bit"
protected  boolean probe(int bit)
          Determines if bit is within capacity of set.
 void remove(int i)
          Remove bit i from the bitset.
 boolean subset(BitSet other)
          Returns true iff this set is a subset of the other.
 java.lang.String toString()
          Constructs string representing set.
 java.lang.Object union(BitSet other)
          Compute a new set that is the union of this set and other.
 
Methods inherited from class java.lang.Object
finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 

Field Detail

bitsPerInt

protected final int bitsPerInt
The number of bits contained in a single integer.

See Also:
Constant Field Values

initialCapacity

protected final int initialCapacity
The initial capacity of the set, by default.

See Also:
Constant Field Values

data

protected int[] data
The array of integers that contains the set's bits


allocated

protected int allocated
The current number of integers allocated.

Constructor Detail

BitSet

public BitSet()
Constructs an empty bitset.


BitSet

public BitSet(int count)
Constructs an empty bitset with potential to hold values between 0..count-1.

Parameters:
count - The number of distinct values possibly in set.
Method Detail

add

public void add(int i)
Adds a bit to the bitset, if not already there. Set is potentially extended.

Parameters:
i - The number of the bit to be added.

remove

public void remove(int i)
Remove bit i from the bitset.

Parameters:
i - The index of the bit to be removed.

contains

public boolean contains(int i)
Determine if a bit is a member of the set.

Parameters:
i - The bit index of potential bit.
Returns:
True iff bit i is in the set.

clear

public void clear()
Remove all bits from the set.


clear

public void clear(int count)
Remove bits from set; set size to count.

Parameters:
count - The new capacity of the newly empty set.

clone

public java.lang.Object clone()
Returns a copy of the set.

Overrides:
clone in class java.lang.Object
Returns:
A new BitSet with the same values as this.

union

public java.lang.Object union(BitSet other)
Compute a new set that is the union of this set and other. Elements of the new set appear in at least one of the two sets.

Parameters:
other - The set to be unioned with this.
Returns:
The union of the two sets.

intersection

public java.lang.Object intersection(BitSet other)
Return the intersection of this set and the other. A bit is in the result if it is in this set and other.

Parameters:
other - The other set to be intersected with this.

difference

public java.lang.Object difference(BitSet other)
Computes the difference between this set and the other. An element is in the difference if it is in this, but not in other.

Parameters:
other - The difference between this set and other.

subset

public boolean subset(BitSet other)
Returns true iff this set is a subset of the other. A set is a subset of another if its elements are elements of the other.

Parameters:
other - The potential superset.
Returns:
The difference between this and other.

isEmpty

public boolean isEmpty()
Determine if a set is empty.

Returns:
True iff this set is empty.

equals

public boolean equals(java.lang.Object o)
Return true iff this set and o contain the same elements.

Overrides:
equals in class java.lang.Object
Parameters:
o - Another non-null bitset.
Returns:
True iff this set has the same elements as o.

indexOf

protected int indexOf(int b)
Determine the int index associated with a bit number.

Returns:
the index in array of bit b.

offsetOf

protected int offsetOf(int bit)
Return the bit index within the associated int of bit "bit"

Parameters:
bit - The index of the bit in set.
Returns:
The index of the bit desired, within the word.

extend

protected void extend(int bit)
Ensures that bit "bit" is within capacity of set.


probe

protected boolean probe(int bit)
Determines if bit is within capacity of set.

Parameters:
bit - The index of desired bit.
Returns:
True if index of bit is within array.

toString

public java.lang.String toString()
Constructs string representing set.

Overrides:
toString in class java.lang.Object
Returns:
String representing bitset.