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