Persistent Dictionaries ( p_dictionary )

Definition

An instance D of the parameterized data type p_dictionary<K,I> 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 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) ! = k. Also, an assignment D1 = D2 does not assign a copy of D2 (with new items) to D1 but the value of D2 itself.

#include < LEDA/p _dictionary.h >

Creation

p_dictionary<K,I>

D

creates an instance D of type p_dictionary<K,I> and initializes D to an empty persistent dictionary.

Operations

K	D.key(p_dic_item it)	returns the key of item it. Precondition it $\in$ D.
I	D.inf(p_dic_item it)	returns the information of item it. Precondition it $\in$ D.
p_dic_item	D.locate(K k)	returns the item with key k (nil if no such item exists in D).
p_dictionary<K,I>	D.del(K k)	returns {x $\in$ D| key(x)! = k}.
p_dictionary<K,I>	D.del_item(p_dic_item it)	returns {x $\in$ D| x! = it}.
p_dictionary<K,I>	D.insert(K k, I i)	returns D.del(k) $\cup$ { < k, i > }.
p_dictionary<K,I>	D.change_inf(p_dic_item it, I i)
		returns D.del_item(it) $\cup$ { < k, i > }, where k = key(it). Precondition it $\in$ D.
int	D.size()	returns the size of D.
bool	D.empty()	returns true if D 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²n), key, inf, empty, size and change_inf take time O(1). The space requirement is O(1) for each update operation.