Next: Dynamic Integer Sets (
Up: Basic Data Types
Previous: Sets ( set )
~ Contents
~ Index
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 T and returns it.

int_set& 
S.intersect(const int_set& T) 
~ 
~ 
replaces S by
S T and returns it.

int_set& 
S.diff(const int_set& T) 
replaces S by
S T and returns it.

int_set& 
S.symdiff(const int_set& T) 
~ 
~ 
replaces S by
(S T) (T S) and returns it.

int_set& 
S.complement() 
replaces S by
[a..b] 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] 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).
Next: Dynamic Integer Sets (
Up: Basic Data Types
Previous: Sets ( set )
~ Contents
~ Index
root
20080109