next up previous contents index
Next: Partitions ( partition ) Up: Basic Data Types Previous: Integer Sets ( int_set   Contents   Index


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.


next up previous contents index
Next: Partitions ( partition ) Up: Basic Data Types Previous: Integer Sets ( int_set   Contents   Index