\manpage {dictionary} {K,I} {Dictionaries}
 
\definition
An instance $D$ of the parameterized data type \name\ is a collection
of items ($dic\_item$). Every item in $D$ contains a key from the linearly
ordered data type $K$, called the key type of $D$, and an information from the
data type $I$, called the information type  of $D$. The number of items in $D$
is called the size of $D$. A dictionary of size zero is called the empty
dictionary. We use $\<k,i\>$ to denote an item with key $k$ and information
$i$ ($i$ is said to be the information associated with key $k$).  For each
$k \in K$ there is at most one $i \in I$ with $\<k,i\> \in D$.
 
\creation D 
 
\create { }
   { creates an instance \var\ of type \name\ and initializes it with
            the empty dictionary. }
 
 
\operations 2 4.2 
 
\op  K key {(dic\_item\ it)}
           {  returns the key of item $it$.\\
	  \precond $it$ is an item in \var. }
 
 
\op  I inf {(dic\_item\ it)}
           {  returns the information of item $it$.\\
	    \precond $it$ is an item in \var. }
 
 
\op  dic\_item insert {(K\ k, I\ i)}
           {  associates the information $i$ with the key $k$.
             If there is an item $\<k,j\>$ in \var\ then $j$ is
             replaced by $i$, else a new item $\<k,i\>$ is added
       	     to \var. In both cases the item is returned. }
 
 
\op  dic\_item lookup {(K\ k)}
           {  returns the item with key $k$ (nil if no such
	       item exists in \var). }
 
 
\op  I access {(K\ k)}
           {  returns the information associated with key $k$.
              \precond there is an item with key $k$ in \var. }
 
 
\op  void del {(K\ k)}
           {  deletes the item with key $k$ from \var\
              (null operation, if no such item exists). }
 
 
\op  void del\_item {(dic\_item\ it)}
           {  removes item $it$ from \var.\\
              \precond $it$ is an item in \var. }
 
 
\opl void change\_inf {(dic\_item\ it, \ I\ i)}
           {  makes $i$ the information of item $it$.\\
              \precond $it$ is an item in \var. }
 
 
\op  void     clear {()}
           {  makes \var\ the empty dictionary. }
 
 
\op  int      size {()}
           {  returns the size of \var. }
 
 
\op  bool     empty {()}
           {  returns true if \var\ is empty, false otherwise. }
 
 
\implementation
Dictionaries are implemented by randomized search trees \cite{AS89}. Operations 
insert, lookup, del\_item, del take time $O(\log n)$, key, inf, empty, size,
change\_inf take time $O(1)$, and clear takes time $O(n)$. Here $n$ is the 
current size of the dictionary. The space requirement is $O(n)$. 
 
\example
We count the number of occurrences of each string in a sequence of strings.

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

#include <LEDA/dictionary.h>

main()
{ dictionary<string,int> D;
  string s;
  dic_item it;

  while (cin >> s)
  { it = D.lookup(s);
    if (it==nil) D.insert(s,1);
    else D.change_inf(it,D.inf(it)+1);
  }

  forall_items(it,D) cout << D.key(it) << " : " <<  D.inf(it) << endl;

}
\endgroup


 
