In general the specification of a LEDA data type consists of five parts: a definition of the set of objects comprising the (parameterized) abstract data type, a list of all local types of the data type, a description of how to create an object of the data type, the definition of the operations available on the objects of the data type, and finally, information about the implementation. The five parts appear under the headers definition, types, creation, operations, and implementation, respectively. Sometimes there is also a fifth part showing an example.
This part of the specification defines the objects (also called instances or elements) comprising the data type using standard mathematical concepts and notation.
The generic data type dictionary array:
An object a of type d_array<I,E> is an injective function from the data type I to the set of variables of data type E. The types I and E are called the index and the element type, respectively. a is called a dictionary array from I to E.
Note that the types I and E are parameters in the definition above. Any built-in, pointer, item, or user-defined class type T can be used as actual type parameter of a parameterized data type. Class types however have to provide several operations listed in Chapter User Defined Parameter Types.
This section gives the list of all local types of the data type. For example,
d_array<I,E>::item the item type.
d_array<I,E>::index_type >the index type.
d_array<I,E>::element_type >the element type.
A variable of a data type is introduced by a C++ variable declaration. For all LEDA data types variables are initialized at the time of declaration. In many cases the user has to provide arguments used for the initialization of the variable. In general a declaration
XYZ<t1, ... ,tk> y(x1, ... ,xt);
introduces a variable y of the data type XYZ< t1, ... ,tk > and uses the arguments x1, ... ,xt to initialize it. For example,
introduces A as a dictionary array from strings to integers, and initializes A as follows: an injective function a from string to the set of unused variables of type int is constructed, and is assigned to A. Moreover, all variables in the range of a are initialized to 0. The reader may wonder how LEDA handles an array of infinite size. The solution is, of course, that only that part of A is explicitly stored which has been accessed already.
For all data types, the assignment operator (=) is available for variables of that type. Note however that assignment is in general not a constant time operation, e.g., if L1 and L2 are variables of type list<T> then the assignment L1 = L2 takes time proportional to the length of the list L2 times the time required for copying an object of type T.
Remark: For most of the complex data types of LEDA, e.g., dictionaries, lists, and priority queues, it is convenient to interpret a variable name as the name for an object of the data type which evolves over time by means of the operations applied to it. This is appropriate, whenever the operations on a data type only ``modify'' the values of variables, e.g., it is more natural to say an operation on a dictionary D modifies D than to say that it takes the old value of D, constructs a new dictionary out of it, and assigns the new value to D. Of course, both interpretations are equivalent. From this more object-oriented point of view, a variable declaration, e.g., dictionary<string,int> D, is creating a new dictionary object with name D rather than introducing a new variable of type dictionary<string,int>; hence the name ``Creation'' for this part of a specification.
In this section the operations of the data types are described. For each operation the description consists of two parts
list_item L.insert (E x, list_item it, int dir = leda::after)
defines the interface of the insert operation on a list L of elements of type E (cf. Section Linear Lists). Insert takes as arguments an element x of type E, a list_item it and an optional relative position argument dir. It returns a list_item as result.
E& A[I x]
defines the interface of the access operation on a dictionary array A. It takes an element x of type I as an argument and returns a variable of type E.
A new item with contents x is inserted after (if dir = leda::after) or before (if dir = leda::before) item it into L. The new item is returned.
Precondition: item it must be in L.
For the access operation on dictionary arrays the definition reads:
returns the variable A(x).
The implementation section lists the (default) data structures used to implement the data type and gives the time bounds for the operations and the space requirement. For example,
Dictionary arrays are implemented by randomized search trees (). Access operations A[x] take time O(log dom(A)). The space requirement is O(dom(A)).