|Persistent dictionaries (classes |
|Two-dimensional maps (class |
In addition, LEDA offers two classes for persistent
dictionaries, the classes
are dictionaries that do not forget their “creation
history” so that one can go back and access an older
state of the dictionary at any time.
p_dictionary, an insertion or
deletion of a key-value pair leads to a new dictionary being
created. This new dictionary contains the modification; the old
dictionary is unchanged and is returned by the operation. It
then can be caught in an assignment of the form
D_old = D.insert(k,v);
and is thus further available. This assignment takes only constant
time in contrast to ordinary dictionaries because no deep copy in the
sense of LEDA rule “Copy of a value”
is made. Even if
D is changed now,
D_old does not change, and nevertheless the
implementation of this data type is so efficient that search and
modification operations are very fast. This structure is used in the
planar_subdivision, for example.
pp_dictionary, only the
dictionary created last may be changed; all
previous ones can be accessed only by searches. Such a
dictionary is called partially
persistent. The main benefit of a
pp_dictionary, when compared to a
p_dictionary, is that an even faster
implementation of the search and modification operations is
possible, due to the restriction that only the latest dictionary
may be modified.
All container types introduced in this chapter are one-dimensional in the sense that the keys must originate from a one-dimensional universe; they cannot be pairs of keys, so the set of keys cannot be (a subset of) a cross-product of partial key sets. Put differently: The key always consists of only one component.
As an extension of the one-dimensional container type
map to two-dimensional
key sets, LEDA offers the class
map2. In this
structure, a value v can be stored, associated to a
pair (s1,s2) of two
components of partial keys s1 and s2. So the structure manages
containers of the form (s1,s2,v), in which v can be accessed via
a full key pair (s1, s2).
This class has the same interface as
map and the same implementation by
hashing with chaining and table doubling.
Further information on
map2 can be found
on the corresponding manual