structure
Class BitSet

java.lang.Object
  structure.BitSet

public class BitSet
extends java.lang.Object

A simple class implementing a set of numbered bits.

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.

Postcondition:

constructs an empty set of small integers

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.

Postcondition:

constructs an empty set with count potential elements

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.

Returns:

True iff bit i is in the set.

Precondition:

i >= 0

Postcondition:

returns true iff i in 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 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.

Postcondition:

constructs a copy of the set

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.

Precondition:

other is non-null

Postcondition:

constructs set w/elements from this and other

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.

Precondition:

other is not null

Postcondition:

constructs set w/elements in this and other

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.

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.

Returns:

The difference between this and other.

Precondition:

other is not null

Postcondition:

returns true iff elements of this are all in other

isEmpty

public boolean isEmpty()

Determine if a set is empty.

Returns:

True iff this set is empty.

Postcondition:

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.

Precondition:

o is not null

Postcondition:

returns true iff this and o have same elements

indexOf

protected int indexOf(int b)

Determine the int index associated with a bit number.

Returns:

the index in array of bit b.

Precondition:

bit >= 0

Postcondition:

returns index of integer containing 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.

Precondition:

bit >= 0

Postcondition:

returns bit position of bit in 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.

Returns:

True if index of bit is within array.

Precondition:

bit >= 0

Postcondition:

Returns rue if set is large enough to contain bit

toString

public java.lang.String toString()

Constructs string representing set.

Overrides:

toString in class java.lang.Object

Returns:

String representing bitset.

Postcondition:

returns string representation of set