next up previous contents index
Next: Partially Persistent Dictionaries ( Up: Dictionary Types Previous: Two-Dimensional Maps ( map2   Contents   Index


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$ Dkey(x)! = k}.

p_dictionary<K,I> D.del_item(p_dic_item it) returns {x $ \in$ Dx! = 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(log2n), key, inf, empty, size and change_inf take time O(1). The space requirement is O(1) for each update operation.


next up previous contents index
Next: Partially Persistent Dictionaries ( Up: Dictionary Types Previous: Two-Dimensional Maps ( map2   Contents   Index
root 2008-01-09