Partially Persistent Dictionaries

Partially Persistent Dictionaries are also closely related to 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 your 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, obj was contained in version xyz of your dictionary.

You can use Partially Persistent Dictionaries in exactly the same way as Dictionaries. If you want to store a version you simply define another pp_dictionary and assign the current pp_dictionary. The advantage is that pp_dictionary does not copy the whole data structure, but manages the different versions in a more efficient way. In effect, the assignment is done in constant time and not in time proportional to the size of the dictionary.

If one of the two pp_dictionaries is changed after the assignment, the other is frozen at the current state, that is, it cannot be changed anymore.

Complete Example of Partially Persistent Dictionaries ...

Applications

Tip

Use a Partially Persistent Dictionaries if you only need to access, but not change, previous versions. If you need to change more than the newest copy use the data type Persistent Dictionary.

See also:

Dictionaries.

Persistent Dictionaries

Manual Entries:

Manual Page Partially Persistent Dictionaries

User Defined Parameter Types

LEDA Item Concept

Linear Orders