The LEDA Manual Page (the type specification)

In general the specification of a LEDA data type consists of four parts: a definition of the set of objects comprising the (parameterized) abstract 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 four parts appear under the headers definition, creation, operations, and implementation respectively. Sometimes there is also a fifth part showing an example.

• Definition
  This part of the specification defines the objects (also called instances or elements) comprising the data type using standard mathematical concepts and notation.

  Example

  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.

• Creation
  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,

  
  h_array<string,int> A(0);
  

  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.

• Operations
  In this section the operations of the data types are described. For each operation the description consists of two parts
  1. The interface of the operation is defined using the C++ function declaration syntax. In this syntax the result type of the operation (void if there is no result) is followed by the operation name and an argument list specifying the type of each argument. For example,

     
     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.

  2. The effect of the operation is defined. Often the arguments have to fulfill certain preconditions. If such a condition is violated the effect of the operation is undefined. Some, but not all, of these cases result in error messages and abnormal termination of the program (see also section Error Handling). For the insert operation on lists this definition reads:

     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).

• Implementation
  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 ([2]). Access operations A[x] take time O(log dom(A)). The space requirement is O(dom(A)).