\manpage {d\_array} {I,E} {Dictionary Arrays}
 
\definition
An instance $A$ of the parameterized data type \name\ (dictionary
array) is an injective mapping from the linearly ordered data type $I$, called
the index type of $A$, to the set of variables of data type $E$, called the
element type of $A$. We use $A(i)$ to denote the variable with index $i$.
 
\creation A 
 
\create {(E\ x)}
   {
creates an injective function $a$ from $I$ to the set of unused variables of
type $E$, assigns $x$ to all variables in the range of $a$ and initializes $A$
with $a$. }
 
 
\operations 2 4 
 
\arrop E\&  {I\ i}
         {  returns the variable $A(i)$. }
 
 
\op  bool defined {(I\ i)}
           {  returns true if $i \in dom(A)$, false otherwise; here
             $dom(A)$ is the set of all $i\in I$ for which $A[i]$ has
             already been executed. }
 
 
     
\bigskip
{\bf Iteration} 
 

{\bf forall\_defined}($i,A$) 
$\{$ ``the elements from $dom(A)$ are successively assigned to $i$'' $\}$ 
 
\implementation
Dictionary arrays are implemented by randomized search trees \cite{AS89}. 
Access operations $A[i]$ take time $O(\log dom(A))$.
The space requirement is $O(dom(A))$.
 
\example

{\bf Program 1}:
We use a dictionary array to count the number of occurrences of the elements in a 
sequence of strings.


\begingroup
\ttbig
{\obeyspaces\gdef {\ }}
\ttverbatim

#include <LEDA/d_array.h>

main()
{ 
  d_array<string,int> N(0);
  string s;

  while (cin >> s) N[s]++;

  forall_defined(s,N) cout << s << "  " << N[s] << endl;

}
\endgroup


\bigskip
{\bf Program 2}:
We use a $d\_array\<string,string\>$ to realize an english/german dictionary.
\begingroup
\ttbig
{\obeyspaces\gdef {\ }}
\ttverbatim

#include <LEDA/d_array.h>

main()
{ 
  d_array<string,string> dic;

  dic["hello"] = "hallo";
  dic["world"] = "Welt";
  dic["book"]  = "Buch";
  dic["key"]   = "Schluessel";
  
  string s;
  forall_defined(s,dic) cout << s << "  " << dic[s] << endl;

}
\endgroup



 
