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. If K is a user-defined type, you have to provide a compare function (see Section User Defined Parameter Types).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/core/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(const K& k)	returns the item with key k (nil if no such item exists in D).
p_dictionary<K,I>	D.del(const 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(const K& k, const I& i)
		returns D.del(k) $\cup$ { < k, i > }.
p_dictionary<K,I>	D.change_inf(p_dic_item it, const 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.