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 K there is at most one item < k, i > 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 D creates an instance D of type p_dictionary and initializes D to an empty persistent dictionary.

Operations

 K D.key(p_dic_item it) returns the key of item it. Precondition it D. I D.inf(p_dic_item it) returns the information of item it. Precondition it 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 D.del(const K& k) returns {x D| key(x)! = k}. p_dictionary D.del_item(p_dic_item it) returns {x D| x! = it}. p_dictionary D.insert(const K& k, const I& i) returns D.del(k) { < k, i > }. p_dictionary D.change_inf(p_dic_item it, const I& i) returns D.del_item(it) { < k, i > }, where k = key(it). Precondition it 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: Partially Persistent Dictionaries ( Up: Dictionary Types Previous: Two-Dimensional Maps ( map2   Contents   Index
root 2008-01-09