\manpage {string} {} {Strings} 
 
\definition
An instance $s$ of the data type $string$ is a sequence of characters 
(type $char$).  The number of characters in the sequence is called the 
length of $s$. A string of length zero is called the empty string.
Strings can be used wherever a \CC $char*$ string can be used.

$Strings$ differ from the \CC type $char*$ in several aspects: parameter
passing by value and assignment works properly (i.e., the value is passed
or assigned and not a pointer to the value) and $strings$ offer many additional
operations.

 
\creation s 
 
\create { }
   { introduces a variable $s$ of type $string$. $s$ is initialized
            with the empty string. }
 
 
\create {(char*\ p)}
   { introduces a variable $s$ of type $string$. $s$ is initialized
            with a copy of the \CC string $p$. }
 
 
\create {(char*\ format,\ ...)}
   { introduces a variable $s$ of type $string$. $s$ is initialized
            with the string produced by printf($format$,\dots).  }
 
 
\create {(char\ c)}
   { introduces a variable $s$ of type $string$. $s$ is initialized
            with the one-character string ``$c$''. }
 
 
\operations 2. 4.7 
 
\op  int    length {()}
           {  returns the length of string $s$. }
 
 
\arrop char\&  {int\ i}
         {  returns the character at position $i$.\\
	       \precond{$0 \le i \le s$.length()$-$1.} }
 
 
\funop string  {int\ i, \ int\ j}
         {  returns the substring of $s$ starting at
	      position $\max(0,i)$ and ending at 
              position $\min(j,s$.length()$-1)$.\\
              If $\min(j,s$.length()$-1) < \max(0,i)$
              then the empty string is returned.  
	      }
 
 
\op  string head {(int\ i)}
           {  returns the first $i$ characters of $s$.  }
 
 
\op  string tail {(int\ i)}
           {  returns the last $i$ characters of $s$.  }
 
 
\op  int pos {(string\ s1, int\ i)}
           {  returns the minimum $j$ such that $j \ge i$ and $s_1$
              is a substring of $s$ starting at position $j$
	      (returns -1 if no such $j$ exists). }
 
 
\op  int pos {(string\ s1)}
           {  returns pos$(s1,0)$. }
 
 
\op  string insert {(int\ i\ , \ string\ s1)}
           {  returns $s(0,i-1)$ + $s_1$ + $s(i,s$.length()$-1)$. }
 
 
\opl string replace {( string\ s1, \  string\ s2, \ int\ i=1)}
           {  returns the string created from $s$ by replacing
	      the $i$-th occurrence of $s_1$ in $s$ by $s_2$.  }
 
 
\opl string replace {(int\ i, \ int\ j\ , \  string\ s1)}
           {  returns the string created from $s$ by replacing
	      $s(i,j)$ by $s_1$.  }
 
 
\opl string replace {(int\ i, \  string\ s)}
           {  returns the string created from $s$ by replacing
	      $s[i]$ by $s_1$.  }
 
 
\opl string replace\_all {( string\ s1, \  string\ s2)}
           {  returns the string created from $s$ by replacing
	      all occurrences of $s_1$ in $s$ by $s_2$.\\
              \precond{The occurrences of $s_1$ in $s$ 
               do not overlap (it's hard to say what the function returns
               if the precondition is violated.).}  }
 
 
\opl string del {( string\ s1\ , \ int\ i=1)}
           {  returns $s$.replace($s_1,"",i$).  }
 
 
\op  string del {(int\ i\ , \ int\ j)}
           {  returns $s$.replace($i,j,""$).  }
 
 
\op  string del {(int\ i)}
           {  returns $s$.replace($i,""$).  }
 
 
\op  string del\_all {( string\ s)}
           {  returns $s$.replace\_all($s_1,""$).  }
 
 
\opl void read {(istream\&\ I, \ char\ delim='\ ')}
           {  reads characters from input stream $I$ into $s$
              until the first occurrence of character $delim$. }
 
 
\op  void read {(char\ delim='\ ')}
           {  read($cin$,$delim$).  }
 
 
\op  void read\_line {(istream\&\ I)}
           {  read($I$,'$\backslash$n').  }
 
 
\op  void read\_line {()}
           {  read\_line($cin$).  }
 
 
\binopfunc  string   {x\+ y}
           {  returns the concatenation of $x$ and $y$. }
 
 
\binop string\& += {x}
         {  appends $x$ to $s$ and returns a reference to $s$. }
 
 
\binopfunc  bool   {x\ ==y}
           {  true iff $x$ and $y$ are equal. }
 
 
\binopfunc  bool   {x\ !=y}
           {  true iff $x$ and $y$ are not equal. }
 
 
\binopfunc  bool   {x\ <y}
           {  true iff $x$ is lexicographically smaller than $y$. }
 
 
\binopfunc  bool   {x\ >y}
           {  true iff $x$ is lexicographically greater than $y$. }
 
 
\binopfunc  bool   {x\ <=y}
           {  returns $(x < y)\ ||\ (x == y)$. }
 
 
\binopfunc  bool   {x\ >=y}
           {  returns $(x > y)\ ||\ (x == y)$. }
 
 
\binopfunc  istream\&   {istream\&\ I\ >>\&\ s}
           {  read($I$,'\ ').  }
 
 
\binopfunc  ostream\&   {ostream\&\ O\ <<s}
           {  writes string $s$ to the output stream $O$.  }
 
 
\implementation 
Strings are implemented by \CC character vectors. All operations involving
the search for a pattern $s1$ in a string $s$ take time $O(s.lenght() * s1.length())$, $[\ ]$ takes constant time and all other operations on a 
string $s$ take time $O(s.length())$.
 
