home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / int_set.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  1.5 KB  |  52 lines
  1. {\magonebf 3.9 Integer Sets  (int\_set)}
  2.  
  3. An instance $S$ of the data type $int\_set$ is a subset of a fixed interval 
  4. interval $[a..b]$ of the integers.
  5.  
  6. \def\name{$int\_set$}
  7. \def\type{int\_set}
  8.  
  9. \bigskip
  10. {\bf 1. Creation of an int\_set}
  11.  
  12. \create S (a,b)
  13.  
  14. creates an instance \var\ of type $int\_set$ for elements from $[a..b]$ and 
  15. initializes it to the empty set. 
  16.  
  17. \bigskip
  18. {\bf 2. \operations}
  19. \+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
  20. \+\op void insert  {int\ x} 
  21.                             {adds $x$ to \var}
  22. \+\nop                      {\precond $a\le x\le b$.}
  23. \smallskip
  24. \+\op void del     {int\ x} 
  25.                             {deletes $x$ from \var}
  26. \+\nop                      {\precond $a\le x\le b$.}
  27. \smallskip
  28. \+\op bool member  {int\ x} 
  29.                             {returns true if $x$ in \var, false otherwise}
  30. \+\nop                      {\precond $a\le x\le b$.}
  31. \smallskip
  32. \+\op void clear   {}    
  33.                             {makes \var\ the empty set}
  34. \bigskip
  35. \+&$int\_set$  &$S1\ =\ S2$   &assignment\cr
  36. \smallskip
  37. \+&$int\_set$  &$S1\ |\ S2$   &returns the union of $S1$ and $S2$\cr
  38. \smallskip
  39. \+&$int\_set$  &$S1\ \&\ S2$  &returns the intersection of $S1$ and $S2$\cr
  40. \smallskip
  41. \+&$int\_set$  &$\tilde{}\ S$ &returns the complement of $S$\cr
  42. \smallskip
  43.  
  44.  
  45. \bigskip
  46. {\bf 3. Implementation}
  47.  
  48. Integer sets are implemented by bit vectors. Operations insert, delete,
  49. member,empty, and size take constant time. Clear, intersection, union 
  50. and complement take time $O(b-a+1)$.
  51.  
  52.