home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / sortseq.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  6.7 KB  |  159 lines
  1. {\magonebf 4.6 Sorted Sequences  (sortseq)}
  2.  
  3. An instance $S$ of the data type $sortseq$ is a sequence of items ($seq\_item$).
  4. Every item contains a key from a linearly ordered data type $K$ , called the 
  5. key type of $S$, and an information from a data type $I$, called the information
  6. type  of $S$. The number of items in $S$ is called the size of $S$. A sorted 
  7. sequence of size zero is called empty. We use $<k,i>$ to denote a $seq\_item$ 
  8. with key $k$ and information $i$ (called the information associated with key 
  9. $k$). For each $k \in K$ there is at most one item $<k,i> \in S$. 
  10.  
  11. The linear order on $K$ may be time-dependent, e.g., in an algorithm that
  12. sweeps an arrangement of lines by a vertical sweep line we may want to order
  13. the lines by the y-coordinates of their intersections with the sweep line. 
  14. However, whenever an operation (except of reverse\_items) is applied to a 
  15. sorted sequence $S$, the keys of $S$ must form an increasing sequence according
  16. to the currently valid linear order on $K$. For operation reverse\_items this 
  17. must hold after the execution of the operation.
  18.  
  19.  
  20.  
  21. \bigskip
  22. {\bf 1. Declaration of a sorted sequence type}
  23.  
  24.  
  25. \decltwo sortseq K I 
  26.  
  27. introduces a new data type with name \name\ consisting of all 
  28. sorted sequences with key type $K$ and information type $I$.
  29.  
  30.  
  31. \bigskip
  32. {\bf 2. Creation of a sorted sequence }
  33.  
  34.  
  35. \create S {}
  36.  
  37. creates an instance \var\ of type \name\ and initializes it to the empty 
  38. sorted sequence.
  39.  
  40.  
  41. \bigskip
  42. {\bf 3. \operations}
  43.  
  44. \+\cleartabs & \hskip 1.8truecm & \hskip 6truecm &\cr
  45. \smallskip
  46. \+\op K         key         {seq\_item\ it}     
  47.                                {returns the key of item $it$}
  48. \+\nop                         {\precond $it$ is an item in \var.}
  49. \smallskip
  50. \+\op I         inf         {seq\_item\ it}     
  51.                                {returns the information of item $it$}
  52. \+\nop                         {\precond $it$ is an item in \var.}
  53. \smallskip
  54. \+\op seq\_item lookup      {K\ k}    
  55.                                {returns the item with key $k$ }
  56. \+\nop                         {( nil if no such item exists in \var\ )}
  57. \smallskip
  58. \+\op seq\_item insert      {K\ k, I\ i}
  59.                                {associates information $i$ with key $k$: If}
  60. \+\nop                         {there is an item $<k,j>$ in \var\ then $j$ is}
  61. \+\nop                         {replaced by $i$, else a new item $<k,i>$ is}
  62. \+\nop                         {added to \var. In both cases the item is }
  63. \+\nop                         {returned.}
  64. \smallskip
  65. \+\op seq\_item insert\_at\_item  {seq\_item\ it,\ K\ k, I\ i} {}
  66. \+\nop                         {Like insert($k,i$), the item $it$ gives the}
  67. \+\nop                         {position of the item $<k,i>$ in the sequence}
  68. \+\nop                         {\precond $it$ is an item in $S$ with either}
  69. \+\nop                         {key($it$) is maximal with key($it) < k$ or}
  70. \+\nop                         {key($it$) is minimal with key$(it) > k$}
  71. \smallskip
  72. \+\op seq\_item locate      {K\ k}    
  73.                                {returns the item $<k\',i>$ in \var\ such that}
  74. \+\nop                         {$k\'$ is minimal with $k\' >= k$ ( nil if no }
  75. \+\nop                         {such item exists).}
  76. \smallskip
  77. \+\op seq\_item succ        {seq\_item\ it}      
  78.                               {returns the successor item of it, i.e., the }
  79. \+\nop                        {item $<k,i>$ in \var\ such that $k$ is minimal}
  80. \+\nop                        {with $k > key(it)$ (nil if no such item exists).}
  81. \+\nop                        {\precond $it$ is an item in \var.}
  82. \smallskip 
  83. \+\op seq\_item pred        {seq\_item\ it}      
  84.                               {returns the predecessor item of $it$, i.e., the}
  85. \+\nop                        {item $<k,i>$ in \var\ such that $k$ is maximal }
  86. \+\nop                        {with $k < key(it)$ (nil if no such item exists).}
  87. \+\nop                        {\precond $it$ is an item in \var.}
  88. \smallskip
  89. \+\op seq\_item max         {}       
  90.                                {returns the item with maximal key}
  91. \+\nop                         {(nil if \var\ is empty).}
  92. \smallskip
  93. \+\op seq\_item min         {}       
  94.                                {returns the item with minimal key}
  95. \+\nop                         {(nil if \var\ is empty).}
  96. \smallskip
  97. \+\op void      del\_item   {seq\_item\ it}    
  98.                                {removes the item $it$ from \var.}
  99. \+\nop                         {\precond $it$ is an item in \var.}
  100. \smallskip
  101. \+\op void      del         {K\ k}    
  102.                                {removes the item with key $k$ from \var}
  103. \+\nop                         {(null operation if no such item exists).}
  104. \smallskip
  105. \+\op void      change\_inf {seq\_item\ it,\ I\ i} 
  106.                                {makes $i$ the information of item $it$.}
  107. \+\nop                         {\precond $it$ is an item in \var.}
  108. \smallskip
  109. \+\op void      reverse\_items {seq\_item\ a,\ seq\_item\ b}  {}
  110. \+\nop                     {the subsequence of $S$ from $a$ to $b$ is reversed.}
  111. \+\nop                     {\precond $a$ appears before $b$ in $S$.}
  112. \smallskip
  113. \+\op void      split {seq\_item\ it,\ sortseq\&\ S_1,\ sortseq\&\ S_2}  {}
  114. \+\nop                {splits $S$ at item $it$ into sequences $S_1$ and $S_2$}
  115. \+\nop                {and makes $S$ empty. More precisely, if}
  116. \+\nop                {$S = x_1,\dots,x_{k-1},it,x_{k+1},\dots,x_n$ then}
  117. \+\nop                {$S1 = x_1,\dots,x_{k-1},it$ and $S2 = x_{k+1},\dots,x_n$}
  118. \+\nop                {\precond $it$ is an item in $S$. }
  119. \smallskip
  120. \+\op sortseq\& conc {sortseq\&\ S_1} 
  121.                      {appends $S_1$ to $S$, makes $S_1$ empty and} 
  122. \+\nop               {returns $S$. \precond }
  123. \+\nop               {$S$.key($S$.max()) $\le$ $S_1$.key($S_1$.min()).}
  124. \smallskip
  125. \+\op void      clear       {}       
  126.                                {makes \var\ the empty sorted sequence.}
  127. \smallskip
  128. \+\op int       size        {}       
  129.                                {returns the size of \var.}
  130. \smallskip
  131. \+\op bool      empty       {}       
  132.                               {returns true if \var\ is empty, false otherwise.}
  133.  
  134. \bigskip
  135. {\bf 4. Iteration}
  136.  
  137.  
  138. {\bf forall\_seq\_items}($i,S$) 
  139. $\{$  ``the items of $S$ are successively assigned to $i$''  $\}$
  140.  
  141.  
  142.  
  143. \bigskip
  144. {\bf 5. Implementation}
  145. \medskip
  146. Sorted sequences are implemented by (2,4)-trees. Operations lookup, locate, 
  147. insert, del, split, conc take time $O(\log n)$, operations succ, pred, max, 
  148. min, key, inf, insert\_at\_item and del\_item take time $O(1)$. Clear takes 
  149. time $O(n)$ and reverse\_items $O(\ell)$, where $\ell$ is the length of the 
  150. reversed subsequence. The space requirement is $O(n)$. Here $n$ is the current 
  151. size of the sequence.
  152.  
  153.  
  154. \bigskip
  155. {\bf 6. Example }
  156. \medskip
  157. \input prog/sortseq.prog
  158.  
  159.