Bitset--Set of Small Integers

A Bitset is a set of small integers (between 0 and 31, inclusive, on most machines). It is similar to the PASCAL SET data type, and is implemented very efficiently using a single word. Each bit of the word indicates if the integer associated with the bit position is an element of the set. Bitsets are particularly useful in conjunction with enum constants. For example, if an enum constant for the days of the week is declared

enum day { Sun,Mon,Tue,Wed,Thu,Fri,Sat };

then these identifiers can be used conveniently with Bitsets:

Bitset workday(Mon,Tue,Wed,Thu,Fri);
Bitset weekend(Sat,Sun);
enum day d;

// ...

if (workday.includes(d))        // test if d is a workday
// ...

Printing such a Bitset will print the values of the enum constants:

cout << weekend;        // prints [0,6]

This can easily be changed by creating a derived class of Bitset which re-defines the virtual function printOn().

CONSTRUCTORS

Bitset(): Constructs an empty Bitset.
Bitset(int i1)
Bitset(int i1, int i2)
Bitset(int i1, int i2, int i3)
Bitset(int i1, int i2, int i3, int i4)
Bitset(int i1, int i2, int i3, int i4, int i5)
Bitset(int i1, int i2, int i3, int i4, int i5, int i6)
Bitset(int i1, int i2, int i3, int i4, int i5, int i6, int i7): Construct a Bitset with the specified bits set. Bits are numbered beginning with 0. Up to 7 bits may be set with these constructors.

SEARCHING

virtual unsigned hash() const: Returns a number suitable for use as a hash table probe.

RELATIONAL OPERATORS

bool operator>(const Bitset&) const

Returns YES if the left Bitset operand is a proper superset of the right Bitset operand; that is, the left operand contains all the integers in the right operand, and the operands are not equal. For example:

Bitset(0,1,2) > Bitset(0,1)     // YES
Bitset(0,1) > Bitset(0,1)       // NO
Bitset(1,2) > Bitset(0,1)       // NO

bool operator<(const Bitset&) const

Returns YES if the left Bitset operand is a proper subset of the right Bitset operand; that is, the right operand contains all the integers in the left operand, and the operands are not equal. For example:

Bitset(0,1) < Bitset(0,1,2)     // YES
Bitset(0,1) < Bitset(0,1)       // NO
Bitset(0,1) < Bitset(1,2)       // NO

bool operator>=(const Bitset&) const

Returns YES if the left Bitset operand is a superset of the right Bitset operand, or if the operands are equal. For example:

Bitset(0,1,2) >= Bitset(0,1)    // YES
Bitset(0,1) >= Bitset(0,1)      // YES
Bitset(1,2) >= Bitset(0,1)      // NO

bool operator<=(const Bitset&) const

Returns YES if the left Bitset operand is a subset of the right Bitset operand, or if the operands are equal. For example:

Bitset(0,1) <= Bitset(0,1,2)    // YES
Bitset(0,1) <= Bitset(0,1)      // YES
Bitset(0,1) <= Bitset(1,2)      // NO

bool operator==(const Bitset&) const

bool operator!=(const Bitset&) const

Returns YES if the left Bitset operand is equal to (or not equal to) the right Bitset operand.

LOGICAL OPERATORS

Bitset operator~() const: Returns a Bitset that contains all elements that are not in this Bitset; for example, on a 32-bit machine, ~Bitset(0,31) is [1,2,3, ... , 30].
Bitset operator-(const Bitset&) const: Returns a Bitset that contains all integers that are in the left Bitset operand and not in the right Bitset operand. For example, Bitset(0,1,2) - Bitset(1,2) is [0].
Bitset operator&(const Bitset&) const: Returns a Bitset containing all integers that are in both the left and right Bitset operands. For example, Bitset(0,1) & Bitset(1,2) is [1].
Bitset operator^(const Bitset&) const: Returns a Bitset containing all integers that are in the left or right Bitset operands, but not in both. For example, Bitset(0,1) ^ Bitset(1,2) is [0,2].
Bitset operator|(const Bitset& n) const: Returns a Bitset containing all integers that are in either the left or right Bitset operands. For example, Bitset(0,1) | Bitset(1,2) is [0,1,2].
void operator-=(const Bitset&)
void operator&=(const Bitset&)
void operator^=(const Bitset&)
void operator|=(const Bitset&): Replaces the left Bitset operand by the result of applying the indicated logical operation to the left and right Bitset operands.

TESTING BITSETS

bool includes(unsigned i) const: Returns YES if this Bitset contains the integer i.
virtual bool isEmpty() const: Returns YES if ths Bitset is empty; that is, it contains no integers.
virtual bool isEqual(const Object& ob) const: Returns YES if ob is of species Bitset and equals this Bitset.

COPYING BITSETS

void operator=(const Bitset&): Assigns the value of the right Bitset operand to the left.
virtual void deepenShallowCopy(): This function is a no-op for class Bitset.

BITSET CAPACITY AND SIZE

virtual unsigned capacity() const: Returns the maximum number of small integers that can be in a Bitset. Since the smallest integer that can be in a Bitset is 0, the largest allowable Bitset integer is capacity() - 1.
virtual unsigned size() const: Returns the number of integers (1 bits) in this Bitset.

BITSET MASKING

static unsigned bit(unsigned i): Returns a mask with the ith bit set to 1.
unsigned asMask() const: Returns an unsigned integer with a 1 in each bit position that corresponds to a small integer that is in this Bitset; for example, Bitset(0,2).asMask() returns 5.

PRINTING BITSETS

virtual void printOn(ostream& strm =cout) const: Prints this Bitset on output stream strm. For example, Bitset(1,10,3).printOn(cout) writes [1,3,10] on cout.