\manpage {p\_dictionary} {K,I} {Persistent Dictionaries}
 
\definition

An instance $D$ of the parameterized data type \name\ is a set
of items (type $p\_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 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 empty.
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 item $\<k,i\> \in D$.

The difference between dictionaries (cf. section \ref{Dictionaries}) and 
persistent dictionaries lies in the fact that update operations performed
on a persistent dictionary $D$ do not change $D$ but create and return a
new dictionary $D\'$. For example, $D$.del($k$) returns the dictionary $D\'$
containing all items $it$ of $D$ with key($it$) $\ne$ $k$. Also, an assignment
$ D1 = D2 $ does not assign a copy of $D2$ (with new items) to $D1$ but the
value of $D2$ itself.

 
\creation D 
 
\create { }
   { creates an instance \var\ of type \name\ and initializes \var\ to an
    empty persistent dictionary. }
 
 
\operations 3.8 4
 
\op  K key {(p\_dic\_item\ p)}
           {  returns the key of item $it$.\\
               \precond $it$ $\in$ \var. }
 
 
\op  I inf {(p\_dic\_item\ p)}
           {  returns the information of item $it$.\\
	       \precond $it$ $\in$ \var. }
 
 
\op  p\_dic\_item lookup {(K\ k)}
           {  returns the item with key $k$ (nil if no such
	       item exists in \var). }
 
 
\op  p\_dictionary\<K,I\> del {(K\ k)}
           {  returns $\{\ x \in \var\ |\ key(x) \ne k\ \}$. }
 
 
\opl p\_dictionary\<K,I\> del\_item {(p\_dic\_item\ it)}
           {  returns $\{\ x \in \var\ |\ x \ne it\ \}$. }
 
 
\op  p\_dictionary\<K,I\> insert {(K\ k, \ I\ i)}
           {  returns \var.del($k$) $\cup$ $\{\<k,i\>\}$. }
 
 
\opl p\_dictionary\<K,I\> change\_inf {(p\_dic\_item\ it, \ I\ i)}
           {  Let $k = key(it)$, returns \var.del\_item($it$) $\cup$
               $\{\<k,i\>\}$. \precond $it$ $\in$ \var. }
 
 
\op  int   size {()}
           {  returns the size of \var. }
 
 
\op  bool   empty {()}
           {  returns true if \var\ is empty, false otherwise. }
 
 
\implementation
Persistent dictionaries are implemented by leaf oriented 
persistent red black trees.
Operations insert, lookup, del\_item, del take time $O(\log^2 n)$, key, inf, 
empty, size, change\_inf and clear take time $O(1)$. The space requirement is
$O(1)$ for each update operation.
 
