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 ppdictionary < 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
3.2 Access operations
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.