\manpage {list} {E} {Linear Lists}
 
\definition
An instance $L$ of the parameterized data type \name\ is a sequence of items
($list\_item$). Each item in $L$ contains an element of data type $E$, called
the element type of $L$. The number of items in $L$ is called the length of $L$.
If $L$ has length zero it is called the empty list. In the sequel $\<x\>$ is 
used to denote a list item containing the element $x$ and $L[i]$ is used to 
denote the contents of list item $i$ in $L$.
 
\creation L  
 
\create { }
   { creates an instance \var\ of type \name\ and initializes it to
            the empty list. }
 
 
\operations 2 5 
 

\medskip
{\bf 3.1 Access Operations}
\medskip 
 
\op  int length {()}
           {  returns the length of $L$. }
 
 
\op  int size {()}
           {  returns $L$.length(). }
 
 
\op  bool empty {()}
           {  returns true if $L$ is empty, false otherwise. }
 
 
\op  list\_item first {()}
           {  returns the first item of $L$. }
 
 
\op  list\_item last {()}
           {  returns the last item of $L$. }
 
 
\op  list\_item succ {(list\_item\ it)}
           {  returns the successor item of item $it$, nil if
	     $it=L$.last().\\
	     \precond $it$ is an item in $L$. }
 
 
\op  list\_item pred {(list\_item\ it)}
           {  returns the predecessor item of item $it$, nil if
	     $it=L$.first().\\
	     \precond $it$ is an item in $L$. }
 
 
\op  list\_item cyclic\_succ {(list\_item\ it)}
           {  returns the cyclic successor of item $it$, i.e.,
	     $L$.first() if $it = L$.last(), $L$.succ($it$) otherwise. }
 
 
\op  list\_item cyclic\_pred {(list\_item\ it)}
           {  returns the cyclic predecessor of item $it$, i.e,
             $L$.last() if $it = L$.first(), $L$.pred($it$) otherwise. }
 
 
\op  list\_item search {(E\ x)}
           {  returns the first item of $L$ that contains $x$,
	     nil if $x$ is not an element of $L$. } 
 
 
\op  E contents {(list\_item\ it)}
           {  returns the contents $L[it]$ of item $it$.\\
	     \precond $it$ is an item in $L$. }
 
 
\op  E inf {(list\_item\ it)}
           {  returns $L$.contents($it$). }
 
 
\op  E  head {()}
           {  returns the first element of $L$, i.e. the contents
	     of $L$.first().\\
	     \precond $L$ is not empty. }
 
 
\op  E  tail {()}
           {  returns the last element of $L$, i.e. the contents
	     of $L$.last().\\
	     \precond $L$ is not empty. }
 
 
\op  int rank {(E\ x)}
           {  returns the rank of $x$ in $L$, i.e. its first
	     position in $L$ as an integer from [1\dots $|L|$]
	     (0 if $x$ is not in $L$).  }
 
 

\medskip
{\bf 3.2 Update Operations}
\medskip 
 
\op  list\_item push {(E\ x)}
           {  adds a new item $\<x\>$ at the front of $L$ and
	     returns it ( $L$.insert($x,L$.first$(),before$) ). }
 
 
\op  list\_item append {(E\ x)}
           {  appends a new item $\<x\>$ to $L$ and returns
             it ( $L$.insert($x,L$.last$(),after$) ). }
 
 
\opl list\_item insert {(E\ a, \ list\_item\ l, \ int\ dir=0)}
           {  inserts a new item $\<x\>$ after (if $dir=after$)
	     or before (if $dir=before$) 
	     item $it$ into $L$ and
	     returns it
	     (here $after$ and $before$
	     are predefined $int$ constants).\\ 
	     \precond $it$ is an item in $L$. }
 
 
\op  E  pop {()}
           {  deletes the first item from $L$ and returns its
  	     contents.\\
	     \precond $L$ is not empty. }
 
 
\op  E  Pop {()}
           {  deletes the last item from $L$ and returns its
	     contents.\\
	     \precond $L$ is not empty. }
 
 
\op  E del\_item {(list\_item\ it)}
           {  deletes the item $it$ from $L$ and returns its
	     contents $L[it]$.\\
	     \precond $it$ is an item in $L$. }
 
 
\op  void assign {(list\_item\ it, E\ x)}
           {  makes $x$ the contents of item $it$.\\
	     \precond $it$ is an item in $L$. }
 
 
\op  void conc {(list\<E\>\&\ L1)}
           {  appends list $L1$ to list $L$ and makes $L1$ the
	     empty list.\\
	     \precond: $L \ne L1$ }
 
 
\opl void split {(list\_item\ it, \ list\<E\>\&\ L1, \ list\<E\>\&\ L2)}
           {  splits $L$ at item $it$ into lists $L1$ and $L2$.
	     More precisely
	     if $L = x_1,\dots,x_{k-1},it,x_{k+1},\dots,x_n$ then
	     $L1 = x_1,\dots,x_{k-1}$ and $L2 = it,x_{k+1},\dots,x_n$.\\
	     \precond $it$ is an item in $L$. If $L \ne L1$ and $L \ne L2$
	     $L$ is assigned the empty list. }
 
 
\opl void sort {(int\ (*cmp)(const\ E\&,const\ E\&))}
           {  sorts the items of $L$ using the ordering defined
	     by the compare function $cmp : E\times E \longrightarrow int$,
	     with\\
 	     $$cmp(a,b)\ \ \cases{< 0,  &if $a < b$\cr
		                  = 0,  &if $a = b$\cr
		                  > 0,  &if $a > b$\cr}$$
	     More precisely, if $(in_1,\dots,in_n)$ and 
	     $(out_1,\dots,out_n))$ denote the values of $L$
	     before and after the call of sort, then
	     $cmp(L[out_j],L[out_{j+1}]) \le 0$ for
	     $1\le j<n$ and there is a
	     permutation
	     $\pi$ of $[1..n]$ such that $out_i = in_{\pi_i}$ for
	     $1 \le i \le n$
	     . }
 
 
\op  void  sort {()}
           {  sorts the items of $L$ using the default ordering of type $E$,
             i.e., the linear order defined by function 
             $int$ compare$(const\ E\&,\ const\ E\&)$.  }
 
 
\op  list\_item min {()}
           {  returns the item with the minimal contents with respect
             to the default linear order of type $E$.  }
 
 
\opl list\_item min {(int\ (*cmp)(const\ E\&,const\ E\&))}
           {  returns the item with the minimal contents with respect
             to the linear order defined by compare function $cmp$.  }
 
 
\op  list\_item max {()}
           {  returns the item with the maximal contents with respect
             to the default linear order of type $E$.  }
 
 
\opl list\_item max {(int\ (*cmp)(const\ E\&,const\ E\&))}
           {  returns the item with the maximal contents with respect
             to the linear order defined by compare function $cmp$.  }
 
 
\op  void apply {(void\ (*f)(E\&\ x))}
           {  for all items $\<x\>$ in $L$ function $f$ is
	     called with argument $x$ (passed by reference). }
 
 
\opl void bucket\_sort {(int\ i,\ int\ j,\ int\ (*f)(const\ E\&))}
           {  sorts the items of $L$ using bucket sort,
	     where $f : E \longrightarrow int$ with $f(x) \in [i..j]$ for
	     all elements $x$ of $L$. The sort is stable,
	     i.e., if $f(x)=f(y)$ and $\<x\>$ is before $\<y\>$ in
	     $L$ then $\<x\>$ is before $\<y\>$ after the sort. }
 
 
\op  void permute {()}
           {  the items of $L$ are randomly permuted. }
 
 
\op  void clear {()}
           {  makes $L$ the empty list.  }
 
 

\bigskip
{\bf 3.3 Input and Output} 
 
\opl void read {(istream\&\ I, \ char\ delim\ ='\n')}
           {  reads a sequence of objects of type $E$ terminated
	     by the delimiter $delim$ from the input stream $I$
	     using the overloaded $Read$ function 
	     (section \ref{Overloading}).
	     $L$ is made a list of appropriate length and the
	     sequence is stored in $L$. }
 
 
\op  void read {(char\ delim\ =\ '\n')}
           {  calls $L$.read($cin$, $delim$) to read $L$ from
	     the standard input stream $cin$. }
 
 
\opl void read {(string\ s, char\ delim='\n')}
           {  As above, but uses string $s$ as a prompt. }
 
 
\opl void print {(ostream\&\ O, \ char\ space='\ ')}
           {  prints the contents of list $L$ to the output
	     stream $O$ using the overload $Print$ function
	     (cf.~section \ref{Overloading}) to print each element. The 
	     elements are separated by the character $space$. }
 
 
\op  void print {(char\ space='\ ')}
           {  calls $L$.print($cout$, $space$) to print $L$ on
	     the standard output stream $cout$. }
 
 
\opl void print {(string\ s, char\ space='\ ')}
           {  As above, but uses string $s$ as a header. }
 
 

\medskip
{\bf 3.4 Iterators }

Each list $L$ has a special item called the iterator of $L$. There 
are operations to read the current value or the contents of this iterator,
to move it (setting it to its successor or predecessor) and to test whether 
the end (head or tail) of the list is reached. If the iterator contains a 
$list\_item \neq nil$ we call this item the position of the iterator. 
Iterators are used to implement iteration statements on lists. 
 
\op  void set\_iterator {(list\_item\ it)}
           {  assigns item $it$ to the iterator\\
	     \precond $it$ is in $L$ or $it$ = nil.  }
 
 
\op  void init\_iterator {()}
           {  assigns nil to the iterator. }
 
 
\op  list\_item get\_iterator {()}
           {  returns the current value of the iterator. }
 
 
\opl list\_item move\_iterator {(direction\ dir)}
           {  moves the iterator to its successor (predecessor)
	     if $dir=forward$ ($backward$) and to the first 
	     (last) item if the iterator is undefined (= nil), returns
	     the iterator. }
 
 
\op  bool current\_element {(E\&\ x)}
           {  if the iterator is defined ($\neq$ nil) its contents is
             assigned to $x$ and true is returned else false
	     is returned. }
 
 
\op  bool next\_element {(E\&\ x)}
           {  calls $L$.move\_iterator($forward$) and then
	     returns $L$.current\_element($x$).  }
 
 
\op  bool prev\_element {(E\&\ x)}
           {  calls $L$.move\_iterator($backward$) and then
	     returns $L$.current\_element($x$).  }
 
 

\bigskip
{\bf 3.5 Operators} 
 
\binop list\<E\>\& = {L1}
         {  The assignment operator makes $L$ a copy of
	     list $L_1$. More precisely if $L_1$ is the sequence
	     of items $x_1, x_2, \dots x_n$ then $L$ is made a
	     sequence of items $y_1, y_2, \dots y_n$ with
	     $L[y_i] = L_1[x_i]$ for $1 \le i \le n$. }
 
 
\arrop E\&  {list\_item\ it}
         {  returns a reference to the contents of $it$. }
 
 

\bigskip
{\bf 3.6 Iterations Macros}

{\bf forall\_items}($it,L$)       
$\{$ ``the items of $L$ are successively assigned to $it$'' $\}$

{\bf forall}($x,L$)       
$\{$ ``the elements of $L$ are successively assigned to $x$'' $\}$ 
 
\implementation
The data type list is realized by doubly linked linear lists. All operations
take constant time except for the following operations: search and rank take 
linear time $O(n)$, bucket\_sort takes time $O(n + j - i)$ and sort takes time 
$O(n\cdot c\cdot\log n$) where $c$ is the time complexity of the compare
function. $n$ is always the current length of the list.
 
