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/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.
int	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.
int_set&	S = S1	assignment.
int_set	S | S1	returns the union of S and S1.
int_set	S & S1	returns the intersection of S and S1.
int_set	S	returns the complement of S.

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).