Items

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.

**Remark:** Item types are, like all other types, functions,
constants, ..., defined in the `"namespace leda"` in LEDA-4.5.

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.