Many of the advanced data types in LEDA (dictionaries, priority queues, graphs, ...), are defined in terms of so-called items. An item is a container which can hold an object relevant for the data type. For example, in the case of dictionaries a dic_item contains a pair consisting of a key and an information. A general definition of items is given at the end of this section.
We now discuss the role of items for the dictionary example in some detail. A popular specification of dictionaries defines a dictionary as a partial function from some type K to some other type I, or alternatively, as a set of pairs from K x I, i.e., as the graph of the function. In an implementation each pair (k, i) in the dictionary is stored in some location of the memory. Efficiency dictates that the pair (k, i) cannot only be accessed through the key k but sometimes also through the location where it is stored, e.g., we might want to lookup the information i associated with key k (this involves a search in the data structure), then compute with the value i a new value i', and finally associate the new value with k. This either involves another search in the data structure or, if the lookup returned the location where the pair (k, i) is stored, can be done by direct access. Of course, the second solution is more efficient and we therefore wanted to provide it in LEDA.
In LEDA items play the role of positions or locations in data structures. Thus an object of type dictionary<K,I>, where K and I are types, is defined as a collection of items (type dic_item) where each item contains a pair in K x I. We use <k, i> to denote an item with key k and information i and require that for each k in K there is at most one i in I such that <k, i> is in the dictionary. In mathematical terms this definition may be rephrased as follows: A dictionary d is a partial function from the set dic_item to the set K x I. Moreover, for each k in K there is at most one i in I such that the pair (k, i) is in d.
The functionality of the operations
dic_item D.lookup(K k) I D.inf(dic_item it) void D.change_inf(dic_item it, I i')
is now as follows:
D.lookup(K k) returns an item it with contents (k, i),
D.inf(it) extracts i from it, and a new value i' can be associated
with k by
D.change
inf(it, i').
Let us have a look at the insert operation for dictionaries next:
dic_item D.insert(K k, I i)
There are two cases to consider. If D contains an item it with contents (k, i') then i' is replaced by i and it is returned. If D contains no such item, then a new item, i.e., an item which is not contained in any dictionary, is added to D, this item is made to contain (k, i) and is returned. In this manual (cf. section Dictionaries) all of this is abbreviated to
| dic_item | D.insert(K k, I i) | associates the information i with the key k. If there is an item <k, j> in D then j is replaced by i, else a new item <k, i> is added to D. In both cases the item is returned. |
We now turn to a general discussion. With some LEDA types XYZ there is an associated type XYZ_item of items. Nothing is known about the objects of type XYZ_item except that there are infinitely many of them. The only operations available on XYZ_items besides the one defined in the specification of type XYZ is the equality predicate ``=='' and the assignment operator ``='' . The objects of type XYZ are defined as sets or sequences of XYZ_items containing objects of some other type Z. In this situation an XYZ_item containing an object z in Z is denoted by <z>. A new or unused XYZ_item is any XYZ_item which is not part of any object of type XYZ.
Remark: For some readers it may be useful to interpret a dic_item as a pointer to a variable of type K x I. The differences are that the assignment to the variable contained in a dic_item is restricted, e.g., the K-component cannot be changed, and that in return for this restriction the access to dic_items is more flexible than for ordinary variables, e.g., access through the value of the K-component is possible.