\manpage {array} {E} {One Dimensional Arrays} 
 
\definition
    An instance $A$ of the parameterized data type \name\ is a mapping from 
    an interval $I =[a..b]$ of integers, the index set of $A$, to the set of 
    variables of data type $E$, the element type of $A$. $A(i)$ is called the 
    element at position $i$.  
 
\creation A
 
\create {(int\ a,\ int\ b)}
   { creates an instance \var\ of type \name\ with index set $[a..b]$.  }
 
 
\create {(int\ n)}
   { creates an instance \var\ of type \name\ with index set $[0..n-1]$.  }
 
 
\create { }
   { creates an instance \var\ of type \name\ with empty index set. }
 
 
\operations 1.2 5 
 
\arrop E\&  {int\ x}
         {  returns $A(x)$.\\
               \precond $a\le x\le b$.   }
 
 
\op  int low {()}
           {  returns the minimal index $a$.  }
 
 
\op  int high {()}
           {  returns the maximal index $b$.  }
 
 
\opl void sort {(int\ (*cmp)(const\ E\&,\ const\ E\&))}
           {  sorts the elements of \var, using function $cmp$
	      to compare two elements, i.e., if $(in_a,\dots,in_b)$
	      and $(out_a,\dots,out_b)$ denote the values of the
	      variables $(A(a),\dots,A(b))$ before and after the
	      call of sort, then $cmp(out_i,out_j) \le 0$ for $i\le j$
	      and there is a permutation $\pi$ of $[a..b]$ such that
	      $out_i=in_{\pi(i)}$ for $a \le i \le b$. }
 
 
\op  void sort {()}
           {  sorts the elements of \var\ according to the linear order
              of the element type $E$.\\
	      \precond A linear order on $E$
              must have been defined by $compare(const E\&, const E\&)$.  }
 
 
\opl void sort {(int\ (*cmp)(const\ E\&,const\ E\&),\ int\ l,\ int\ h)}
           {  sorts sub-array \var$[l..h]$ using compare function $cmp$. }
 
 
\op  void sort {(int\ l, \ int\ h)}
           {  sorts sub-array \var$[l..h]$ using the linear order on $E$. }
 
 
\op  void permute {()}
           {  the elemens of \var\ are randomly permuted. }
 
 
\op  void permute {(int\ l, \ int\ h)}
           {  the elements of \var$[l..h]$ are randomly permuted. }
 
 
\opl int binary\_search {(int\ (*cmp)(const\ E\&,const\ E\&),\ E\ x)}
           {  performs a binary search for $x$. Returns $i$
	      with $A[i] = x$ if $x$ in $A$, $A$.low$()-1$
	      otherwise. Function $cmp$ is used to compare
	      two elements.\\
	      \precond $A$ must be sorted
	      according to $cmp$. }
 
 
\op  int binary\_search {(E\ x)}
           {  performs a binary search for $x$ using the default
              linear order on $E$.\\
	      \precond $A$ must be sorted. }
 
 
\op  void read {(istream\ I)}
           {  reads $b-a+1$ objects of type $E$ from the
	      input stream $I$ into the array $A$ using the
	      overloaded $Read$ function (cf.~section \ref{Overloading}). }
 
 
\op  void read {()}
           {  calls $A$.read($cin$) to read $A$ from the
	      standard input stream $cin$. }
 
 
\op  void read {(string\ s)}
           {  As above, uses string $s$ as prompt. }
 
 
\opl void print {(ostream\ O, char\ space\ ='\ ')}
           {  prints the contents of array $A$ to the output
	      stream $O$ using the overloaded $Print$ function
	      (cf.~section \ref{Overloading}) to print each element. The
	      elements are separated by the character $space$. }
 
 
\op  void print {(char\ space\ =\ '\ ')}
           {  calls $A$.print($cout$, $space$) to print $A$ on
	      the standard output stream $cout$. }
 
 
\opl void print {(string\ s, char\ space\ =\ '\ ')}
           {  As above, uses string $s$ as header. }
 
 
\implementation
Arrays are implemented by \CC vectors. The access operation takes time
$O(1)$, the sorting is realized by quicksort (time $O(n \log n)$) and
the binary\_search operation takes time $O(\log n)$, where $n = b-a+1$.
The space requirement is $O(|I|* sizeof(E))$.
 
