Integer Sets ( int_set )

Definition

An instance S of the data type int_set is a subset of a fixed interval [a..b] of the integers, called the range of S.

#include < LEDA/core/int_set.h >

Creation

int_set	S(int a, int b)	creates an instance S of type int_set for elements from [a..b] and initializes it to the empty set.
int_set	S(int n)	creates an instance S of type int_set for elements from [0..n - 1] and initializes it to the empty set.

Operations

void	S.insert(int x)	adds x to S. Precondition a < = x < = b.
void	S.del(int x)	deletes x from S. Precondition a < = x < = b.
bool	S.member(int x)	returns true if x in S, false otherwise. Precondition a < = x < = b.
int	S.min()	returns the minimal integer in the range of of S.
int	S.max()	returns the maximal integer in the range of of S.
void	S.clear()	makes S the empty set.

In any binary operation below, S and T must have the same range:

int_set&	S.join(const int_set& T)	replaces S by S $\cup$ T and returns it.
int_set&	S.intersect(const int_set& T)
~	~	replaces S by S $\cap$ T and returns it.
int_set&	S.diff(const int_set& T)	replaces S by S $\setminus$ T and returns it.
int_set&	S.symdiff(const int_set& T)
~	~	replaces S by (S $\setminus$ T) $\cup$ (T $\setminus$ S) and returns it.
int_set&	S.complement()	replaces S by [a..b] $\setminus$ S and returns it.
int_set	S | const int_set& T	returns the union of S and T.
int_set	S & const int_set& T	returns the intersection of S and T.
int_set	S - const int_set& T	returns the set difference of S and T.
int_set	S	~
int_set	~S	returns the complement of S, i.e. [a..b] $\setminus$ S.

Implementation

Integer sets are implemented by bit vectors. Operations insert, delete, member, min and max take constant time. All other operations take time O(b - a + 1).