Persistent Dictionaries

The data type p_dictionary is a variant of the data type Dictionary. It can be used to store objects of an arbitrary type I together with an associated key of a linearly ordered type K (int, string, …). The elements of a persistent dictionary are of type p_dic_item.

Persistent Dictionaries are also closely related to Partially Persistent Dictionaries.

Remark: The interface of Persistent Dictionaries is a little different from Dictionaries and Partially Persistent Dictionaries. The update operations of Persistent Dictionaries return a new dictionary while the corresponding operations of Dictionaries and Partially Persistent Dictionaries return an item, respectively void.

Basic Idea

You want to store objects with associated keys of a linearly ordered type in a dictionary, but you also want to save the history of updates. You want to ask, for example, if object obj was contained in version xyz of your dictionary.

Every update operation gives you a new version of the Persistent Dictionary. You just need to store the versions you want to keep. The advantage is that Persistent Dictionary does not copy the whole data structure, but manages the different versions in a more efficient way, that is, the p_dictionary that is returned by an update operation depends on the original p_dictionary.

In contrast to Partially Persistent Dictionaries, you can change all copies of your original Persistent Dictionary independently. Imagine a tree of Dictionaries with a common root that can branch out during the program.

Complete Example of Persistent Dictionaries ...

Applications

Tip

Use Persistent Dictionaries if you need to access and change previous versions of a dictionary. If you only need to change the newest copy consider using the more efficient Partially Persistent Dictionary.

See also:

Dictionaries

Partially Persistent Dictionaries

Manual Entries:

Manual Page Persistent Dictionaries

User Defined Parameter Types

LEDA Item Concept

Linear Orders