structure
Class BitSet

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

public class BitSet

extends 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, java.util.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.
Object	clone() Returns a copy of the set.
boolean	contains(int i) Determine if a bit is a member of the set.
Object	difference(BitSet other) Computes the difference between this set and the other.
boolean	equals(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.
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.
String	toString() Constructs string representing set.
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, registerNatives, wait, wait, wait

Field Detail

bitsPerInt

protected final int bitsPerInt

The number of bits contained in a single integer.

initialCapacity

protected final int initialCapacity

The initial capacity of the set, by default.

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.

Precondition:

i >= 0

Postcondition:

i is added to the set

remove

public void remove(int i)

Remove bit i from the bitset.

Parameters:

i - The index of the bit to be removed.

Precondition:

i >= 0

Postcondition:

removes i from set if present

contains

public boolean contains(int i)

Determine if a bit is a member of the set.

Parameters:

i - The bit index of potential bit.

Precondition:

i >= 0

Postcondition:

returns true iff i in set

Returns:

True iff bit i is in the set.

clear

public void clear()

Remove all bits from the set.

Postcondition:

removes all values from 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.

Postcondition:

removes all values from set, sets set size to count

clone

public Object clone()

Returns a copy of the set.

Overrides:

clone in class Object

Postcondition:

constructs a copy of the set

Returns:

A new BitSet with the same values as this.

union

public 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.

Precondition:

other is non-null

Postcondition:

constructs set w/elements from this and other

Returns:

The union of the two sets.

intersection

public 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.

Precondition:

other is not null

Postcondition:

constructs set w/elements in this and other

difference

public 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.

Precondition:

other is not null

Postcondition:

constructs set w/elements from this but not 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.

Precondition:

other is not null

Postcondition:

returns true iff elements of this are all in other

Returns:

The difference between this and other.

isEmpty

public boolean isEmpty()

Determine if a set is empty.

Postcondition:

returns true iff this set is empty

Returns:

True iff this set is empty.

equals

public boolean equals(Object o)

Return true iff this set and o contain the same elements.

Overrides:

equals in class Object

Parameters:

o - Another non-null bitset.

Precondition:

o is not null

Postcondition:

returns true iff this and o have same elements

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.

Precondition:

bit >= 0

Postcondition:

returns index of integer containing bit b

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.

Precondition:

bit >= 0

Postcondition:

returns bit position of bit in word

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.

Precondition:

bit >= 0

Postcondition:

ensures set is large enough to contain bit

probe

protected boolean probe(int bit)

Determines if bit is within capacity of set.

Parameters:

bit - The index of desired bit.

Precondition:

bit >= 0

Postcondition:

Returns rue if set is large enough to contain bit

Returns:

True if index of bit is within array.

toString

public String toString()

Constructs string representing set.

Overrides:

toString in class Object

Postcondition:

returns string representation of set

Returns:

String representing bitset.