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/core/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

int	S.min()	returns the smallest element in S. Precondition S is not empty.
int	S.max()	returns the largest element in S. Precondition S is not empty.
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(const d_int_set& T)
		returns S $\cup$ T.
d_int_set	S.intersect(const d_int_set& T)
		returns S $\cap$ T.
d_int_set	S.diff(const d_int_set& T)
		returns S - T.
d_int_set	S.symdiff(const d_int_set& T)
		returns the symmectric difference of S and T.
d_int_set	S + const d_int_set& T	returns the union S.join(T).
d_int_set	S - const d_int_set& T	returns the difference S.diff(T).
d_int_set	S & const d_int_set& T	returns the intersection of S and T.
d_int_set	S | const d_int_set& T	returns the union S.join(T).
d_int_set	S
d_int_set&	S += const d_int_set& T	assigns S.join(T) to S and returns S.
d_int_set&	S -= const d_int_set& T	assigns S.diff(T) to S and returns S.
d_int_set&	S &= const d_int_set& T	assigns S.intersect(T) to S and returns S.
d_int_set&	S |= const d_int_set& T	assigns S.join(T) to S and returns S.
d_int_set&	S
bool	S != const d_int_set& T	returns true if S! = T, false otherwise.
bool	S == const d_int_set& T	returns true if S = T, false otherwise.
bool	S >= const d_int_set& T	returns true if T $\subseteq$ S, false otherwise.
bool	S <= const d_int_set& T	returns true if S $\subseteq$ T, false otherwise.
bool	S < const d_int_set& T	returns true if S $\subset$ T, false otherwise.
bool	S > const d_int_set& 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.

Iteration

forall_elements(x,S) { ``the elements of S are successively assigned to x'' }

Implementation

Dynamic integer sets are implemented by (dynamic) bit vectors. Operations member, empty, size, min and max take constant time. The operations clear, intersection, union and complement take time O(b - a + 1), where a = max() and b = min(). The operations insert and del also take time O(b - a + 1), if the bit vector has to be reallocated. Otherwise they take constant time. Iterating over all elements (with the iteration macro) requires time O(b - a + 1) plus the time spent in the body of the loop.