Dynamic Integer Sets ( d_int_set )

Definition

An instance S of the data type d_int_set is a subset of the integers.

#include < LEDA/d _int _set.h >

Creation

d_int_set

S

creates an instance S of type d_int_set initializes it to the empty set.

Operations

void	S.insert(int x)	adds x to S. As the sets range is expanding dynamically during insertion for the range [S.min(),S.max()] inserting the extrema early saves repeated reallocation time.
void	S.del(int x)	deletes x from S.
bool	S.member(int x)	returns true if x in S, false otherwise.
int	S.choose()	returns a random element of S. Precondition S is not empty.
bool	S.empty()	returns true if S is empty, false otherwise.
int	S.size()	returns the size of S.
void	S.clear()	makes S the empty set.
d_int_set	S.join(d_int_set T)	returns S $\cup$ T.
d_int_set	S.intersect(d_int_set T)	returns S $\cap$ T.
d_int_set	S.diff(d_int_set T)	returns S - T.
d_int_set	S.symdiff(d_int_set T)	returns the symmectric difference of S and T.
d_int_set	S + T	returns the union S.join(T).
d_int_set	S - T	returns the difference S.diff(T).
d_int_set	S & T	returns the intersection of S and T.
d_int_set	S | T	returns the union S.join(T).
d_int_set	S
d_int_set&	S += T	assigns S.join(T) to S and returns S.
d_int_set&	S -= T	assigns S.diff(T) to S and returns S.
d_int_set&	S &= T	assigns S.intersect(T) to S and returns S.
d_int_set&	S |= T	assigns S.join(T) to S and returns S.
d_int_set&	S
bool	S != T	returns true if S! = T, false otherwise.
bool	S == T	returns true if S = T, false otherwise.
bool	S >= T	returns true if T $\subseteq$ S, false otherwise.
bool	S <= T	returns true if S $\subseteq$ T, false otherwise.
bool	S < T	returns true if S $\subset$ T, false otherwise.
bool	S > T	returns true if T $\subset$ S, false otherwise.
void	S.get_element_list(list<int>& L)
		fills L with all elements stored in the set in increasing order.

Implementation

Integer sets are implemented by bit vectors. Operations insert, delete, member, empty, and size take constant time. clear, intersection, union and complement take time O(b - a + 1).