home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / man / list.tex < prev    next >
Encoding:
Text File  |  1991-11-15  |  11.9 KB  |  278 lines
  1. {\magonebf 3.7 Linear Lists  (list) }
  2.  
  3. An instance $L$ of the data type $list$ is a sequence of items ($list\_item$). 
  4. Each item in $L$ contains an element of a data type $E$, called the element 
  5. type of $L$. The number of items in $L$ is called the length of $L$. If $L$ has
  6. length zero it is called the empty list. In the sequel $<x>$ is used to 
  7. denote a list item containing the element $x$ and $L[i]$ is used to denote 
  8. the contents of list item $i$ in $L$.
  9.  
  10.  
  11. \bigskip
  12. {\bf 1. Declaration of a list type}
  13.  
  14.  
  15. \decl list E
  16.  
  17. introduces a new data type with name \name\ consisting of all lists with 
  18. element type $E$.
  19.  
  20.  
  21.  
  22. \bigskip
  23. {\bf 2. Creation of list}
  24.  
  25.  
  26. \create L {}
  27.    
  28. creates  an instance \var\ of type \name\ and initializes it to the empty list.
  29.  
  30.  
  31. \bigskip
  32. {\bf 3. \operations }
  33.  
  34. \+\cleartabs & \hskip 2truecm & \hskip 5.5truecm &\cr
  35.  
  36. {\bf a) Access Operations}
  37. \medskip
  38. \+\op int        length {}                
  39.                                {returns the length of $L$.}
  40. \smallskip
  41. \+\op int        size {}                
  42.                                {returns $L$.length().}
  43. \smallskip
  44. \+\op bool       empty {}                 
  45.                                {returns true if $L$ is empty, false otherwise.}
  46. \smallskip
  47. \+\op list\_item first {}                 
  48.                                {returns the first item of $L$.}
  49. \smallskip
  50. \+\op list\_item last {}                  
  51.                                {returns the last item of $L$.}
  52. \smallskip
  53. \+\op list\_item succ {list\_item\ it}        
  54.                                 {returns the successor item of item $it$, nil}
  55. \+\nop                          {if $it = L$.last().}
  56. \+\nop                          {\precond $it$ is an item in $L$.}
  57. \smallskip
  58. \+\op list\_item pred {list\_item\ it}        
  59.                                {returns the predecessor item of item $it$, nil}
  60. \+\nop                         {if $it = L$.first().}
  61. \+\nop                         {\precond $it$ is an item in $L$.}
  62. \smallskip
  63. \+\op list\_item cyclic\_succ {list\_item\ it} 
  64.                     {returns the cyclic successor of item $it$, i.e.,}
  65. \+\nop              {$L$.first() if $it = L$.last(), $L$.succ($it$) otherwise.}
  66. \smallskip
  67. \+\op list\_item cyclic\_pred {list\_item\ it} 
  68.                     {returns the cyclic predecessor of item $it$, i.e,}
  69. \+\nop              {$L$.last() if $it = L$.first(), $L$.pred($it$) otherwise.}
  70. \smallskip
  71. \+\op list\_item search {E\ x}                  
  72.                            {returns the first item of $L$ that contains $x$,}
  73. \+\nop                     {nil if $x$ is not an element of $L$}
  74. \smallskip
  75. \+\op E          contents {list\_item\ it}    
  76.                                    {returns the contents $L[it]$ of item $it$ }
  77. \+\nop                             {\precond $it$ is an item in $L$.}
  78. \smallskip
  79. \+\op E          inf {list\_item\ it}    
  80.                                    {returns $L$.contents($it$).}
  81. \smallskip
  82. \+\op E          head {}                  
  83.                           {returns the first element of $L$, i.e. the contents}
  84. \+\nop                    {of $L$.first().} 
  85. \+\nop                    {\precond $L$ is not empty.}
  86. \smallskip
  87. \+\op E          tail {}                  
  88.                           {returns the last element of $L$, i.e. the contents}
  89. \+\nop                    { of $L$.last().}
  90. \+\nop                    {\precond $L$ is not empty.}
  91. \smallskip
  92. \+\op int        rank {E\ x}
  93.                           {returns the rank of $x$ in $L$, i.e. its first}
  94. \+\nop                    {position in $L$ as an integer from [1\dots $|L|$]}
  95. \+\nop                    {(0 if $x$ is not in $L$). }
  96.  
  97.  
  98. \medskip
  99. {\bf b) Update Operations}
  100. \medskip
  101. \+\op list\_item insert {E\ x, list\_item\ it,\ direction\ dir=after}    {}
  102. \+\nop                     {inserts a new item $<x>$ after (if $dir=after$)}
  103. \+\nop                     {or before (if $dir=before$) item $it$ into $L$ and}
  104. \+\nop                     {returns it. \precond $it$ is an item in $L$.}
  105. \smallskip
  106. \+\op list\_item push {E\ x}          
  107.                              {adds a new item $<x>$ at the front of $L$ and}
  108. \+\nop                       {returns it ( $L$.insert($x,L$.first$(),before$) )}
  109. \smallskip
  110. \+\op list\_item append {E\ x}        
  111.                               {appends a new item $<x>$ to $L$ and returns}
  112. \+\nop                        {it ( $L$.insert($x,L$.last$(),after$) )}
  113. \smallskip
  114. \+\op E          del\_item {list\_item\ it}      
  115.                           {deletes the item $it$ from $L$ and returns its }
  116. \+\nop                    {contents $L[it]$.}
  117. \+\nop                    {\precond $it$ is an item in $L$.}
  118. \smallskip
  119. \+\op E          pop {}                   
  120.                           {deletes the first item from $L$ and returns its }
  121. \+\nop                    {contents.}
  122. \+\nop                    {\precond $L$ is not empty.}
  123. \smallskip
  124. \+\op E          Pop {}                   
  125.                           {deletes the last item from $L$ and returns its }
  126. \+\nop                    {contents.}
  127. \+\nop                    {\precond $L$ is not empty.}
  128. \smallskip
  129. \+\op void       assign {list\_item\ it,\ E\ x}
  130.                            {makes $x$ the contents of item $it$.}
  131. \+\nop                     {\precond $it$ is an item in $L$.}
  132. \smallskip
  133. \+\op void       conc {list\&\ L1}          
  134.                               {appends list $L1$ to list $L$ and makes $L1$ the}
  135. \+\nop                        {empty list}
  136. \smallskip
  137. \+\op void       split {list\_item\ it, list\&\ L1,\ L2}           {}
  138. \+\nop                {splits $L$ at item $it$ into lists $L1$ and $L2$}
  139. \+\nop                {and makes $L$ the empty list. More precisely,}
  140. \+\nop                {if $L = x_1,\dots,x_{k-1},it,x_{k+1},\dots,x_n$ then}
  141. \+\nop                {$L1 = x_1,\dots,x_{k-1}$ and $L2 = it,x_{k+1},\dots,x_n$}
  142. \+\nop                {\precond $it$ is an item in $L$. }
  143. \smallskip
  144. \+\op void       apply {void\ (*f)(E\&)}  
  145.                               {for all items $<x>$ in $L$ function $f$ is}
  146. \+\nop                        {called with argument $x$ (passed by reference).}
  147. \smallskip
  148. \+\op void       sort {int\ (*cmp)(E\&,E\&)}   
  149.                 {sorts the items of $L$ using the ordering defined}
  150. \+\nop          {by the compare function $cmp : E\times E \longrightarrow int$,}
  151. \+\nop          {\phantom{with $cmp(a,b)$} $ < 0$,  if $a < b$ }
  152. \+\nop          {with $cmp(a,b)$           $ = 0$,  if $a = b$ }
  153. \+\nop          {\phantom{with $cmp(a,b)$} $ < 0$,  if $a > b$ }
  154. \+\nop          {More precisely, if $L = (x_1,\dots,x_n)$ before the sort}
  155. \+\nop          {then $L = (x_{\pi(1)},\dots,x_{\pi(n)})$ for some permutation}
  156. \+\nop          {$\pi$ of $[1..n]$ and $cmp(L[x_j],L[x_{j+1}]) \le 0$ for}
  157. \+\nop          {$1\le j<n$ after the sort.}
  158.  
  159. \smallskip
  160. \+\op void       bucket\_sort {int\ i,\ int\ j,\ int\ (*f)(E\&)}  {}
  161. \+\nop            {sorts the items of $L$ using bucket sort, }
  162. \+\nop            {where $f : E \longrightarrow int$ with $f(x) \in [i..j]$ for}
  163. \+\nop            {all elements $x$ of $L$. The sort is stable, }
  164. \+\nop            {i.e., if $f(x)=f(y)$ and $<x>$ is before $<y>$ in}
  165. \+\nop            {$L$ then $<x>$ is before $<y>$ after the sort.}
  166. \smallskip
  167. \+\op void       permute {}                    
  168.                                 {the items of $L$ are randomly permuted.}
  169. \smallskip
  170. \+\op void       clear {}                      
  171.                                     {makes $L$ the empty list }
  172. \medskip
  173.  
  174. \bigskip
  175. {\bf Input and Output}
  176. \smallskip
  177. \+\op void       read {istream\ I,\ char\ delim = '\backslash n'}     {}
  178. \+\nop                      {reads a sequence of objects of type $E$ terminated}
  179. \+\nop                      {by the delimiter $delim$ from the input stream $I$}
  180. \+\nop                      {using the overloaded $Read$ function (section 1.5)}
  181. \+\nop                      {$L$ is made a list of appropriate length and the}
  182. \+\nop                      {sequence is stored in $L$.}
  183. \smallskip
  184. \+\op void       read {char\ delim = '\backslash n'}
  185.                             {Calls $L$.read($cin$, $delim$) to read $L$ from}
  186. \+\nop                      {the standard input stream $cin$.}
  187. \smallskip
  188. \+\op void       read {string\ s,\ char\ delim = '\backslash n'}     {}
  189. \+\nop                      {As above, but uses string $s$ as a prompt.}
  190. \smallskip
  191. \+\op void       print {ostream\ O,\ char\ space = '\ '}    {} 
  192. \+\nop                      {Prints the contents of list $L$ to the output}
  193. \+\nop                      {stream $O$ using the overload $Print$ function}
  194. \+\nop                      {(cf. section 1.5) to print each element. The}
  195. \+\nop                      {elements are separated by the character $space$.}
  196. \smallskip
  197. \+\op void       print {char\ space = '\ '}
  198.                             {Calls $L$.print($cout$, $space$) to print $L$ on}
  199. \+\nop                      {the standard output stream $cout$.}
  200. \smallskip
  201. \+\op void       print {string\ s,\ char\ space = '\ '}    {} 
  202. \+\nop                      {As above, but uses string $s$ as a header.}
  203.  
  204.  
  205.  
  206. \medskip
  207. {\bf d) Iterators }
  208. \medskip
  209. Each list $L$ has a special item called the iterator of $L$. There 
  210. are operations to read the current value or the contents of this iterator,
  211. to move it (setting it to its successor or predecessor) and to test whether 
  212. the end (head or tail) of the list is reached. If the iterator contains a 
  213. $list\_item \neq nil$ we call this item the position of the iterator. 
  214. Iterators are used to implement iteration statements on lists.
  215. \bigskip
  216. \+\op void       set\_iterator {list\_item\ it}          
  217.                             {assigns item $it$ to the iterator}
  218. \+\nop                      {\precond $it$ is in $L$ or $it$ = nil. }
  219. \smallskip
  220. \+\op void       init\_iterator {}         
  221.                             {assigns nil to the iterator}
  222. \smallskip
  223. \+\op list\_item get\_iterator {}          
  224.                             {returns the current value of the iterator}
  225. \smallskip
  226. \+\op list\_item move\_iterator {direction\ dir=forward}    {}
  227. \+\nop                      {moves the iterator to its successor (predecessor)}
  228. \+\nop                      {if $dir=forward$ ($backward$) and to the first}
  229. \+\nop                      {(last) item if it is undefined (= nil), returns}
  230. \+\nop                      {the iterator.}
  231. \smallskip
  232. \+\op bool       current\_element {E\&\ x} 
  233.                        {if the iterator is defined ($\neq$ nil) its contents is}
  234. \+\nop                 {assigned to $x$ and true is returned else false}
  235. \+\nop                 {is returned}
  236. \smallskip
  237. \+\op bool       next\_element {E\&\ x} 
  238.                             { $L$.move\_iterator($forward$) $+$}
  239. \+\nop                      { return $L$.current\_element($x$) }
  240. \smallskip
  241. \+\op bool       prev\_element {E\&\ x} 
  242.                             { $L$.move\_iterator($backward$) $+$}
  243. \+\nop                      { return $L$.current\_element($x$)  }
  244.  
  245. \bigskip
  246. {\bf e) Operators}
  247. \medskip
  248. \+\opa E\&  {list\_item\ it}  
  249.                            {returns a reference to the contents of $it$.}
  250. \medskip
  251. \+\opb list(E)\& =  L_1   
  252.                            {The assignment operator makes $L$ a copy of}
  253. \+\nop                     {list $L_1$. More precisely if $L_1$ is the sequence}
  254. \+\nop                     {of items $x_1, x_2, \dots x_n$ then $L$ is made a}
  255. \+\nop                     {sequence of items $y_1, y_2, \dots y_n$ with}
  256. \+\nop                     {$L[y_i] = L_1[x_i]$ for $1 \le i \le n$.}
  257.  
  258. \vfill\eject
  259.  
  260. \bigskip
  261. {\bf 5. Iteration}
  262.  
  263. {\bf forall\_list\_items}($it,L$)       
  264. $\{$ ``the items of $L$ are successively assigned to $it$'' $\}$
  265.  
  266. {\bf forall}($x,L$)       
  267. $\{$ ``the elements of $L$ are successively assigned to $x$'' $\}$
  268.  
  269. \bigskip
  270. {\bf 6. Implementation}
  271.  
  272. The data type list is realized by doubly linked linear lists. All operations
  273. take constant time except for the following operations. Search and rank take 
  274. linear time $O(n)$, bucket\_sort takes time $O(n + j - i)$ and sort takes time 
  275. $O(n\cdot c\cdot\log n$) where $c$ is the time complexity of the compare
  276. function. $n$ is always the current length of the list.
  277.  
  278.