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 ([70]), 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.