Partially Persistent Dictionaries ( pp_dictionary )

Definition

A partially persistent dictionary stores the history of a set of items < k, i > (type pp_dic_item). Here k is a key from a linearly ordered type K, and i is an information from the data type I. An instance D of the parameterized data type pp_dictionary<K,I,CMP> references a version of the set in the history.
An update operation may only be performed on an instance D containing the newest version v. The operation changes the set of items and creates a new version v' which represents the new state of the set. After the operation, D references version v', and all other instances which have referenced version v remain unchanged. An access operation may be applied to any instance D. Let v denote the version referenced by D. Then the operation is carried out on the set which existed when v was created.
The main advantage of a partially persistent dictionary compared to a dictionary is that copy and assignment operations use only constant time and space, because only the versions and not the whole sets are assigned.

The linear order for the data type K is given by a compare object of type CMP. It must provide a function call operator which has the same syntax and semantics as a LEDA compare function (see Section User Defined Parameter Types). The data type pp_dictionary may be instantitiated without specifying the third template argument, i.e. as type pp$\_$dictionary < K, I >. This data type uses the linear order which is defined by the compare function for the type K.

#include < LEDA/core/pp_dictionary.h >

Creation

pp_dictionary<K,I,CMP>

D(const CMP& cmp=CMP())

creates an instance D of type pp_dictionary<K,I,CMP> and initializes D to an empty persistent dictionary. When the argument cmp is provided, the object is used as compare function object which defines the linear order for the data type K.

Operations

3.1 Update operations

pp_dic_item	D.insert(const K& k, const I& i)
		associates the information i with the key k. If there is an item < k, j > in the set then it is deleted. A new item < k, i > is added and returned.
void	D.del(const K& k)	deletes the item with key k from the set (null operation, if no such item exists).
void	D.del_item(pp_dic_item it)
		removes item it from the set. Precondition it is an item in the set.
pp_dic_item	D.change_inf(pp_dic_item it, const I& i)
		makes i the information of item it. This may create a new item; the item < key(it), i > in the new set is returned. Precondition it is an item in the set.
void	D.clear()	makes D the empty dictionary.

3.2 Access operations

const K&	D.key(pp_dic_item it)	returns the key of item it. Precondition it $\in$ D.
const I&	D.inf(pp_dic_item it)	returns the information of item it. Precondition it $\in$ D.
pp_dic_item	D.lookup(const K& k)	returns the item with key k (nil if no such item exists in D).
pp_dic_item	D.locate_succ(const K& k)	returns the item x in D so that key(x) = min{key(y)| y $\in$ D  $\wedge$  key(y) > = k}.
pp_dic_item	D.locate_pred(const K& k)	returns the item x in D so that key(x) = max{key(y)| y $\in$ D  $\wedge$  key(y) < = k}.
int	D.size()	returns the size of D.
bool	D.empty()	returns true if D is empty, false otherwise.

Implementation

Partially persistent dictionaries are implemented by leaf oriented partially persistent red-black trees. Operations insert, del, del_item and lookup take expected time O(log n), the expected time for key, inf, empty, size and change_inf is O(1), and clear takes expected time O(n). Here n is the number of items in the version of the dictionary to which the operation is applied. The expected space requirement is O(1) for each update operation.