User Defined Parameter Types

If a user defined class type T shall be used as actual type parameter in a container class, it has to provide the following operations:

a) a constructor taking no arguments	T : : T()
b) a copy constructor	T : : T(constT&)
c) an assignment operator	T& T : : operator = (constT&)
and if required by the parameterized data type
d) an input operator	istream& operator > > (istream&, T&)
e) an output operator	ostream& operator < < (ostream&, const T&)
f) a compare function	int compare(const T&, const T&)
g) a hash function	int Hash(const T&)

In the following two subsections we explain the background of the required compare and hash function. Section Implementation Parameters concerns a very special parameter type, namely implementation parameters.

Linear Orders

Many data types, such as dictionaries, priority queues, and sorted sequences require linearly ordered parameter types. Whenever a type T is used in such a situation, e.g. in dictionary<T,...> the function

int   compare(const T&, const T&)

must be declared and must define a linear order on the data type T.

A binary relation rel on a set T is called a linear order on T if for all x,y,z in T:

1) x rel x
2) x rel y and y rel z implies x rel z
3) x rel y or y rel x
4) x rel y and y rel x implies x = y

A function int compare(const T&, const T&) defines the linear order rel on T if

$$\mathrm{compare}(x,y)\ \ \cases{ < 0, &if $x$\ {\it rel} $y... ... &if $x = y$\cr > 0, &if $y$\ {\it rel} $x$\ and $x \ne y$}$$

For each of the data types char, short, int, long, float, double, integer, rational, bigfloat, real, string, and point a function compare is predefined and defines the so-called default ordering on that type. The default ordering is the usual $\le$ - order for the built-in numerical types, the lexicographic ordering for string, and for point the lexicographic ordering of the cartesian coordinates. For all other types T there is no default ordering, and the user has to provide a compare function whenever a linear order on T is required.

Example: Suppose pairs of real numbers shall be used as keys in a dictionary with the lexicographic order of their components. First we declare class pair as the type of pairs of real numbers, then we define the I/O operations operator>> and operator<< and the lexicographic order on pair by writing an appropriate compare function.

class pair {
  double  x;
  double  y;

public:
 pair() { x = y = 0; }
 pair(const pair& p) { x = p.x; y = p.y; }


 friend istream& operator>> (istream& is, pair& p) 
 { is >> p.x >> p.y; return is; }
 friend ostream& operator<< (ostream& os, const pair& p) 
 { os << p.x << " " << p.y; return os; }

 friend int compare(const pair&, const pair&);

};

int compare(const pair& p, const pair& q)
{
  if (p.x < q.x) return  -1;
  if (p.x > q.x) return   1; 
  if (p.y < q.y) return  -1;
  if (p.y > q.y) return   1;
  return 0;
}

Now we can use dictionaries with key type pair, e.g.,

dictionary<pair,int> D;

Sometimes, a user may need additional linear orders on a data type T which are different from the order defined by compare. In The following example a user wants to order points in the plane by the lexicographic ordering of their cartesian coordinates and by their polar coordinates. The former ordering is the default ordering for points. The user can introduce an alternative ordering on the data type point (cf. section Basic Data Types for Two-Dimensional Geometry) by defining an appropriate comparing function

int   pol_cmp(const point& x, const point& y)
{ /* lexicographic ordering on polar coordinates */ }

Now she has several possibilities:

1. First he can call the macro

   
   DEFINE_LINEAR_ORDER(point, pol_cmp, pol_point)
   

   After this call pol_point is a new data type which is equivalent to the data type point, with the only exception that if pol_point is used as an actual parameter e.g. in dictionary< pol_point,...>, the resulting data type is based on the linear order defined by pol_cmp. Now, dictionaries based on either ordering can be used.

   
   dictionary<point,int>     D0; // default ordering
   dictionary<pol_point,int> D1; // polar ordering
   

   In general the macro call

   
   DEFINE_LINEAR_ORDER(T, cmp, T1)
   

   introduces a new type T1 equivalent to type T with the linear order defined by the compare function cmp.

2. As a new feature all order based data types like dictionaries, priority queues, and sorted sequences offer a constructor which allows a user to set the internally used ordering at construction time.

   
   dictionary<point,int> D0;          // default ordering
   dictionary<point,int> D1(pol_cmp); // polar ordering
   

   This alternative handles the cases where two or more different orderings are needed more elegantly.

3. Instead of passing a compare function cmp(const T&, const T&) to the sorted type one can also pass an object (a so-called compare object) of a class that is derived from the class leda$\_$cmp$\_$base and that overloads the function-call operator int operator()(const T&, const T&) to define a linear order for T.

   This variant is helpful when the compare function depends on a global parameter. We give an example. More examples can be found in several sections of the LEDA book [58]. Assume that we want to compare edges of a graph GRAPH < point, int > (in this type every node has an associated point in the plane; the point associated with a node v is accessed as G[v]) according to the distance of their endpoints. We write

   
   class cmp_edges_by_length: public leda_cmp_base<edge> { 
     const GRAPH<point,int>& G;
   public:
     cmp_edges_by_length(const GRAPH<point,int>& g): G(g){}
   
     int operator()(const edge& e, const edge& f) const
     { point pe = G[G.source(e)]; point qe = G[G.target(e)];
       point pf = G[G.source(f)]; point qf = G[G.target(f)];
       return compare(pe.sqr_dist(qe),pf.sqr_dist(qf));
     } 
   };
    
   main(){
     GRAPH<point,int> G;
     cmp_edges_by_length cmp(G);
     list<edge> E = G.all_edges();
     E.sort(cmp);
   }
   

   The class cmp$\_$edges$\_$by$\_$length has a function operator that takes two edges e and f of a graph G and compares them according to their length. The graph G is a parameter of the constructor. In the main program we define cmp(G) as an instance of cmp$\_$edges$\_$by$\_$length and then pass cmp as the compare object to the sort function of list < edge >. In the implementation of the sort function a comparison between two edges is made by writing cmp(e, f ), i.e., for the body of the sort function there is no difference whether a function or a compare object is passed to it.

Hashed Types

LEDA also contains parameterized data types requiring a hash function and an equality test (operator==) for the actual type parameters. Examples are dictionaries implemented by hashing with chaining ( _dictionary<K,I, ch_hashing>) or hashing arrays ( h_array<I,E>). Whenever a type T is used in such a context, e.g., in h_array<T,...> there must be defined

1. a hash function int Hash(const T&)
2. the equality test bool operator = = (const T&, constT&)

Hash maps the elements of type T to integers. It is not required that Hash is a perfect hash function, i.e., it has not to be injective. However, the performance of the underlying implementations very strongly depends on the ability of the function to keep different elements of T apart by assigning them different integers. Typically, a search operation in a hashing implementation takes time linear in the maximal size of any subset whose elements are assigned the same hash value. For each of the simple numerical data types char, short, int, long there is a predefined Hash function: the identity function.

We demonstrate the use of Hash and a data type based on hashing by extending the example from the previous section. Suppose we want to associate information with values of the pair class by using a hashing array h_array<pair,int> A. We first define a hash function that assigns each pair (x, y) the integral part of the first component x

int  Hash(const pair& p) { return int(p.x); }

and then can use a hashing array with index type pair

h_array<pair, int>  A;

Implementation Parameters

For many of the parameterized data types (in the current version: dictionary, priority queue, d_array, and sortseq) there exist variants taking an additional data structure parameter for choosing a particular implementation (cf. chapter Dictionaries with Implementation Parameter, Sorted Sequences with Implementation Parameter, Dictionary Arrays with Implementation Parameter and Priority Queues with Implementation Parameter). Since C++ does not allow to overload templates we had to use different names: the variants with an additional implementation parameters start with an underscore, e.g., _d_array<I,E,impl>. We can easily modify the example program from section A First Example to use a dictionary array implemented by a particular data structure, e.g., skip lists ([]), instead of the default data structure (cf. section List of data structures).

#include <LEDA/_d_array.h>
#include <LEDA/impl/skiplist.h>

main()
{
  _d_array<string, int, skiplist>  N(0);
  string s;

  while (cin >> s) N[s]++;
  
  forall_defined(s,N) 
    cout << s << " " << N[s] << endl;
}

Any type _XYZ<T1, ... ,Tk, xyz_impl> is derived from the corresponding ``normal" parameterized type XYZ<T1, ...,Tk>, i.e., an instance of type _XYZ<T1, ...,Tk, xyz_impl> can be passed as argument to functions with a formal parameter of type XYZ<T1, ...,Tk>&. This provides a mechanism for choosing implementations of data types in pre-compiled algorithms. See ``prog/graph/dijkstra.c" for an example.

LEDA offers several implementations for each of the data types. For instance, skip lists, randomized search trees, and red-black trees for dictionary arrays. Users can also provide their own implementation. A data structure xyz_impl can be used as actual implementation parameter for a data type _XYZ if it provides a certain set of operations and uses certain virtual functions for type dependent operations (e.g. compare, initialize, copy, ...). Chapter Implementations lists all data structures contained in the current version and gives the exact requirements for implementations of dictionaries, priority_queues, sorted sequences and dictionary arrays. A detailed description of the mechanism for parameterized data types and implementation parameters used in LEDA will be published soon.