Key Sets ( KeySet )

Definition

An instance S of the data type KeySet is a collection of elements of the data type AgdKey with an associated keymapper mapper. All keys stored in S must be allocated by mapper.

#include < AGD/KeySet.h >

Creation

KeySet	S	creates an instances S of type KeySet initialized to the empty set. Sets the associated keymapper to the default keymapper of AGD.
KeySet	S(const Keymapper& M)	creates an instances S of type KeySet with associated keymapper M initialized to the empty set.
KeySet	S(const KeySet& T)	creates an instances S of type KeySet initialized to a copy of T.

Operations

const Keymapper *

S.get_keymapper()

returns the associated keymapper.

a) Common Set Operations

void	S.insert(const AgdKey& k)	adds k to S.
void	S.del(const AgdKey& k)	deletes k from S.
bool	S.member(const AgdKey& k)	returns true iff k $\in$ S.
KeySet	S.join(const KeySet& T)	returns S $\cup$ T.
KeySet	S.diff(const KeySet& T)	returns S $\setminus$ T.
KeySet	S.intersect(const KeySet& T)
		returns S $\cap$ T.
KeySet	S.symdiff(const KeySet& T)
		returns (S $\cup$ T) $\setminus$ (S $\cap$ T).
bool	S.empty()	returns true iff S = $\emptyset$.
void	S.clear()	makes S the empty set.

b) Operators The following operators return a new key set instead of changing S.

KeySet	S + const KeySet& T	returns S.join(T).
KeySet	S - const KeySet& T	returns S.diff(T).
KeySet	S & const KeySet& T	returns S.intersect(T).
KeySet	S

The following operators manipulate S directly.

KeySet&	S += const KeySet& T	assigns S.join(T) to S and returns S.
KeySet&	S -= const KeySet& T	assigns S.diff(T) to S and returns S.
KeySet&	S &= const KeySet& T	assigns S.intersect(T) to S and returns S.
KeySet&	S
KeySet&	S << const AgdKey& k	inserts k into S and returns S.

Relational and assignment operators:

bool	S == const KeySet& T	return true iff S = T.
bool	S != const KeySet& T	return true iff S! = T.
bool	S <= const KeySet& T	returns true iff S $\subseteq$ T.
bool	S >= const KeySet& T	returns true iff S $\supseteq$ T.
KeySet&	S = const KeySet& T	assigns T to S. Returns S.

c) Iteration The following functions return iterators of type KeySet::const_iterator.

const_iterator	S.begin()	returns an iterator pointing to first element in S.
const_iterator	S.end()	returns an iterator pointing to one-past-last element in S.
const_iterator	S.rbegin()	returns an iterator pointing to last element in S.
const_iterator	S.rend()	returns an iterator pointing to one-before-first element in S.

d) Input and Output

void	S.read(istream& is, int delim = EOF)
		reads a sequence of strings s1,..., sk terminated by delim from the input stream is, and assigns the set $\left\{\vphantom{ <s_1>,\ldots,<s_k>}\right.$ < s1 > ,..., < sk > $\left.\vphantom{ <s_1>,\ldots,<s_k>}\right\}$ to S.
void	S.read(char delim = ' \n')	calls S.read(cin,delim) to read S from the standard input stream cin.
void	S.print(ostream& os, char space = ', ')
		prints the string representations of the elements of S to the output stream os. The elements are separated by space.
void	S.print(char space = ' ')	calls S.print(cout,space) to print S to the standard output stream cout.
istream&	istream& is >> KeySet& S	reads the key set S from the input stream is.
ostream&	ostream& os << const KeySet& S
		writes the key set S to the output stream os.

Implementation

Key sets are implemented by bit vectors using an internal numbering of keys. All keys stored in a key set must be allocated by the same keymapper.