home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / interval.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  3.7 KB  |  106 lines
  1.  
  2. {\magonebf  6.4 Sets of intervals (interval\_set)}
  3.  
  4. An instance $S$ of the data type $interval\_set$ is a collection of items 
  5. ($is\_item$). Every item in $S$ contains a closed interval of the real numbers
  6. as key and an information from a data type $I$, called the information 
  7. type of $S$. The number of items in $S$ is called the size of $S$. An interval 
  8. set of size zero is said to be empty. We use $<x,y,i>$ to denote the item with 
  9. interval $[x,y]$ and information $i$, $x$ ($y$) is called the left (right)
  10. boundary of the item. For each interval $[x,y] \subset \real$ there is at 
  11. most one item $<x,y,i> \in S$.
  12.  
  13.  
  14. \bigskip
  15. {\bf 1. Declaration of an interval set type}
  16.  
  17. \decl interval\_set I
  18.  
  19. introduces a new data type with name \name\ consisting of all 
  20. interval sets  with information type $I$. 
  21.  
  22.  
  23. \bigskip
  24. {\bf 2. Creation of an interval set}
  25.  
  26.  
  27. \create S {}
  28.  
  29. creates an instance \var\ of type \name\ and initializes \var\ to the 
  30. empty set. 
  31.  
  32.  
  33.  
  34. \bigskip
  35. {\bf 3. \operations}
  36.  
  37. \+\cleartabs & \hskip 2.6truecm & \hskip 5.5truecm &\cr
  38. \+\op real     left {is\_item\ it}  
  39.                             {returns the left boundary of item $it$.}
  40. \+\nop                      {\precond $it$ is an item in \var.}
  41. \smallskip
  42. \+\op real     right {is\_item\ it} 
  43.                                     {returns the right boundary of item $it$.}
  44. \+\nop                              {\precond $it$ is an item in \var.}
  45. \smallskip
  46. \+\op I        inf {is\_item\ it}   
  47.                                     {returns the information of item $it$.}
  48. \+\nop                              {\precond $it$ is an item in \var.}
  49. \smallskip
  50. \+\op is\_item insert {real\ x,\ real\ y,\ I\ i}
  51.                       {associates the information $i$ with interval}
  52. \+\nop                {$[x,y]$. If there is an item $<x,y,j>$ in \var }
  53. \+\nop                {then $j$ is replaced by $i$, else a new item }
  54. \+\nop                {$<x,y,i>$ is added to $S$. In both cases }
  55. \+\nop                {the item is returned.}
  56. \smallskip
  57. \+\op is\_item lookup {real\ x,\ real\ y} 
  58.                       {returns the item with interval $[x,y]$}
  59. \+\nop                {(nil if no such item exists in \var).}
  60. \smallskip
  61. \+\op list(is\_item)  intersection {real\ a,\ real\ b}  {}
  62. \+\nop                {returns all items $<x,y,i>\ \in\ S$ with}
  63. \+\nop                {$[x,y] \cap [a,b] \neq \emptyset$.}
  64. \smallskip
  65. \+\op void del {real\ x,\ real\ y}         
  66.                       {deletes the item with interval $[x,y]$}
  67. \+\nop                {from \var.}
  68. \smallskip
  69. \+\op void del\_item {is\_item\ it}   
  70.                               {removes item $it$ from \var.}
  71. \+\nop                        {\precond $it$ is an item in \var.}
  72. \smallskip
  73. \+\op void change\_inf {is\_item\ it,\ I\ i} 
  74.                               {makes $i$ the information of item $it$.}
  75. \+\nop                        {\precond $it$ is an item in \var.}
  76. \smallskip
  77. \+\op void clear {}           
  78.                               {makes \var\ the empty interval\_set.}
  79. \smallskip 
  80. \+\op bool empty {}           
  81.                               {returns true iff \var\ is empty.}
  82. \smallskip 
  83. \+\op int  size {}            
  84.                               {returns the size of \var.}
  85.  
  86.  
  87.  
  88. \bigskip
  89. {\bf 4. Iteration}
  90.  
  91. {\bf forall\_is\_items}($i,S$) 
  92. $\{$ ``the items of $S$ are successively assigned to $i$ '' $\}$
  93.  
  94.  
  95.  
  96. \bigskip
  97. {\bf 5. Implementation}
  98.  
  99. Interval sets are implemented by two-dimensional range trees.
  100. Operations insert, lookup, del\_item and del take time $O(\log^2 n)$,
  101. intersection takes time $O(k + \log^2 n)$, where $k$ is the size
  102. of the returned list. Operations left, right, inf, empty, and size
  103. take time $O(1)$, and clear $O(n\log n)$. Here $n$ is always the 
  104. current size of the interval set. The space requirement is $O(n\log n)$.
  105.  
  106.