home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / set.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  1.7 KB  |  68 lines
  1. {\magonebf 3.8 Sets  (set)}
  2.  
  3. An instance $S$ of the data type $set$ is a collection of elements of a 
  4. linearly ordered type $U$, called the element type of $S$. The size of 
  5. $S$ is the number of elements in $S$, a set of size zero is called the 
  6. empty set.
  7.  
  8.  
  9. \bigskip
  10. {\bf 1. Declaration of a set type}
  11.  
  12. \decl set U 
  13.  
  14. introduces a new data type with name \name\ consisting of all sets with
  15. element type $U$. \precond $U$ is linearly ordered.
  16.  
  17.  
  18.  
  19. \bigskip
  20. {\bf 2. Creation of a set}
  21.  
  22.  
  23. \create S {} 
  24.  
  25. creates an instance \var\ of type \name\ and initializes it to the empty set.
  26.  
  27. \bigskip
  28. {\bf 3. \operations}
  29.  
  30. \+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
  31. \+\op void insert  {U\ x} 
  32.                          {adds $x$ to \var}
  33. \smallskip
  34. \+\op void del     {U\ x} 
  35.                          {deletes $x$ from \var}
  36. \smallskip
  37. \+\op bool member  {U\ x} 
  38.                          {returns true if $x$ in \var, false otherwise}
  39. \smallskip
  40. \+\op U    choose  {}    
  41.                          {returns an element of \var\ (error if \var\ is empty)}
  42. \+\nop                   {\precond{\var\ is not empty}.}
  43. \smallskip
  44. \+\op bool empty   {}    
  45.                          {returns true if \var\ is empty, false otherwise}
  46. \smallskip
  47. \+\op int  size    {}    
  48.                          {returns the size of \var}
  49. \smallskip
  50. \+\op void clear   {}    
  51.                          {makes \var\ the empty set}
  52.  
  53.  
  54. \bigskip
  55. {\bf 4. Iteration}
  56.  
  57.  
  58. {\bf forall}($x,S$) 
  59. $\{$  ``the elements of $S$ are successively assigned to $x$''  $\}$
  60.  
  61. \bigskip
  62. {\bf 5. Implementation}
  63.  
  64. Sets are implemented by red black trees. Operations insert, del, member
  65. take time $O(\log n)$, empty, size take time $O(1)$, and clear takes time 
  66. $O(n)$, where $n$ is the current size of the set.
  67.  
  68.