\manpage {set} {E} {Sets}
 
\definition
An instance $S$ of the parameterized data type \name\ is a collection of
elements of the linearly ordered type $E$, called the element type of $S$. The
size of $S$ is the number of elements in $S$, a set of size zero is called the
empty set.
 
\creation S 
 
\create { }
   { creates an instance \var\ of type \name\ and initializes it to
            the empty set. }
 
 
\operations 1.8 5
 
\op  void insert {(E\ x)}
           {  adds $x$ to \var. }
 
 
\op  void del {(E\ x)}
           {  deletes $x$ from \var. }
 
 
\op  bool member {(E\ x)}
           {  returns true if $x$ in \var, false otherwise. }
 
 
\op  E choose {()}
           {  returns an element of \var.\\
               \precond \var\ is not empty. }
 
 
\op  bool empty {()}
           {  returns true if \var\ is empty, false otherwise. }
 
 
\op  int size {()}
           {  returns the size of \var. }
 
 
\op  void clear {()}
           {  makes \var\ the empty set. }
 
 

\bigskip
{\bf Iteration}

\medskip
{\bf forall}($x,S$) 
$\{$  ``the elements of $S$ are successively assigned to $x$''  $\}$ 
 
\implementation
Sets are implemented by randomized search trees \cite{AS89}. Operations insert,
del, member take time $O(\log n)$, empty, size take time $O(1)$, and clear 
takes time $O(n)$, where $n$ is the current size of the set.
 
