Bitset(3X) — Subroutines
NAME
Bitset − set of ints/enums/bits package
SYNOPSIS
#include <codelibs/boolean.h>
#include <codelibs/bitset.h>
// a set of ints/enums/bits
class Bitset
{
public:
| Bitset(int, int, ...); | // new element list | ||
| Bitset(int); | // new size | ||
| Bitset(Bitset const &); | // new bitset | ||
| Bitset(); | // new empty set | ||
| ~Bitset(); | // destructor | ||
| Bitset &operator=(Bitset const &); | // assignment - duplicate a set | ||
| Bitset &add(int); | // add element to set | ||
| Bitset &operator+=(int); | // inline for add | ||
| Bitset &remove(int); | // delete element from set | ||
| Bitset &operator-=(int); | // inline for delete | ||
| int size() const; | // number of elements in bitset | ||
| int card() const; | // cardinality (same as above) | ||
| boolean isin(int) const; | // is element in set? | ||
| void clear(); | // clear the set | ||
| unsigned long hash() const; | // return a hash value for a set | ||
| Bitset &operator|=(Bitset const &); | // union with | ||
| Bitset &operator&=(Bitset const &); | // intersect with | ||
| Bitset &operator-=(Bitset const &); | // difference from | ||
| Bitset &operator^=(Bitset const &); | // symmetric difference | ||
| Bitset &operator~(); | // complement self | ||
| int get(int) const; | // get value of element (0 or 1) | ||
| int operator[](int) const; | // array reference - like get() | ||
| boolean operator<=(Bitset const &) const; | // is subset? | ||
| boolean operator>=(Bitset const &) const; | // is superset? | ||
| boolean operator==(Bitset const &) const; | // is equal? | ||
| boolean operator!=(Bitset const &) const; | // is not equal? | ||
| boolean operator<(Bitset const &) const; | // is proper subset? | ||
| boolean operator>(Bitset const &) const; | // is proper superset? |
};
// iterator over a bitset
class Bitsetiter
{
public:
| Bitsetiter(Bitset const &); | // creator - iterate over a set | ||
| ~Bitsetiter(); | // destructor | ||
| int operator()(); | // get next element in set |
};
CC ... -lcodelibs
DESCRIPTION
This package of routines handles simple sets of non-negative integers and enums efficiently. It allows manipulation of an arbitrary number of sets of arbitrary size in a simple manner. It can also be used to handle arbitrary length strings of bits efficiently.
Bitset
constructors
A set may be constructed by list of elements in that set. The list MUST be terminated with a negative value such as -1.
A set may be initialized to hold at least a particular number of elements. This size is only of real importance to set a domain for the complement self operator and must be a positive value greater than or equal to one. In any case, sets will always be grown automatically to accommodate new elements as necessary.
other memfuncs
The other member functions for Bitset are pretty much self-explanatory. The comments in the SYNOPSIS section above should describe what they do.
The hash() function is most useful for creating hash tables of Bitsets using the hashtable(3X) package. The hash value returned is caclulated using only the actual elements currently within the Bitset and is thus independent of its size.
The operators |=,&=,-=, and ~ All modify the Bitset itself rather than returning a new Bitset.
Bitsetiter
This allows arbitrary iteration over a Bitset. The example below shows how it is to be used. The operator() returns the next element in the Bitset. It returns -1 after the last element is returned to mark the end of the iteration.
EXAMPLES
#include <stdio.h>
#include <codelibs/bitset.h>
// initialize with certain elements
Bitset s(1, 2, 13, 17, -1);
s += 16; // add element 16
Bitset s2(40); // room for at least 40 elements
s2.add(34); // add element 34
Bitset t;
t = s;
t |= s2; // t := s union s2
if (s[2]) // is element 2 in s?
printf("2 is in set\n");
if (s < s2) // is s a proper subset of s2
printf("is proper subset\n");
// print out the elements in a set
int e;
Bitsetiter si(s); // si is an iterator over a set s
while ((e = si()) >= 0)
printf("%d ", e);
printf("\n");
SEE ALSO
NOTES
The current implementation does not handle large sparse sets very efficiently, since one bit is allocated for each element. However, it handles generic bit strings very efficiently.
— codelibs — C++