\manpage {int\_set} {} {Integer Sets}
 
\definition
An instance $S$ of the data type $int\_set$ is a subset of a fixed interval
$[a..b]$ of the integers.
 
\creation S 
 
\create {(int\ a,\ int\ b)}
   { creates an instance \var\ of type $int\_set$ for elements from
            $[a..b]$ and initializes it to the empty set. }
 
 
\create {(int\ n)}
   { creates an instance \var\ of type $int\_set$ for elements from
            $[0..n-1]$ and initializes it to the empty set. }
 
 
\operations 1.8 5 
 
\op  void insert {(int\ x)}
           {  adds $x$ to \var.\\
	     \precond $a\le x\le b$. }
 
 
\op  void del {(int\ x)}
           {  deletes $x$ from \var.\\
            \precond $a\le x\le b$. }
 
 
\op  int member {(int\ x)}
           {  returns true if $x$ in \var, false otherwise.\\
	     \precond $a\le x\le b$. }
 
 
\op  void clear {()}
           {  makes \var\ the empty set. }
 
 
\binop int\_set\& = {S1}
         {  assignment. }
 
 
\binop int\_set | {S1}
         {  returns the union of $S$ and $S1$ }
 
 
\binop int\_set \& {S1}
         {  returns the intersection of $S$ and $S1$ }
 
 
\unop int\_set  \tilde {}
         {  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)$.
 
