9. Implementations
9.1 List of data structures
This section lists the data structures for dictionaries, dictionary arrays, priority queues, and geometric data types currently contained in LEDA. For each of the data structures its name and type, the list of LEDA data types it can implement, and a literature reference are given. Before using a data structures xyz the corresponding header file LEDA/impl/xyz.h has to be included (cf. section 1.2 for an example).
9.1.1 Dictionaries .5em2.7truecm & .5em4.5truecm & .5em6truecm & ab$\_tree$ &a-b tree &dictionary, d_array, sortseq&[BC72] avl$\_tree$ &AVL tree &dictionary, d_array &[AVL62] bb$\_tree$ &BB[α] tree &dictionary, d_array, sortseq &[BM80] ch$\_hashing$ &hashing with chaining &dictionary, d_array &[M84] dp$\_hashing$ &dyn. perf. hashing &h_array &[DKMMRT88,W92] pers$\_tree$ &persistent tree &p_dictionary &[DSST89] rb$\_tree$ &red-black tree &dictionary, d_array, sortseq &[GS78] rs$\_tree$ &rand. search tree &dictionary, d_array, sortseq &[AS89] skiplist &skip lists &dictionary, d_array, sortseq &[Pu90]
9.1.2 Priority Queues


f$\_heap$ &Fibonnacci heap &priority_queue &[FT87] p$\_heap$ &pairing heap &priority_queue &[SV87] k$\_heap$ &k-nary heap &priority_queue &[M84] m$\_heap$ &monotonic heap &priority_queue &[M84] eb$\_tree$ &Emde-Boas tree &priority_queue &[EKZ77,W92]
9.1.3 Geometry


range$\_tree$ &range tree &d2_dictionary, point_set&[Wi85,Lu78] seg$\_tree$ &segment tree &seg_set &[B79,Ed82] ps$\_tree$ &priority search tree & — &[MC81] iv$\_tree$ &interval tree &interval_set &[MC80,Ed82] delaunay$\_tree$ &delaunay tree &point_set &[De92]


9.2 User Implementations
In addition to the data structures listed in the previous section user-defined data structures can also be used as actual implementation parameters provided they fulfill certain requirements.


9.2.1 Dictionaries

Any class dic$\_impl$ that provides the following operations can be used as actual implementation parameter for the $\_dictionary$K, I, dic$\_impl$ and the $\_d$$\_array$I, E, dic$\_impl$ data types (cf. sections 4.3 and 4.4).
`=̀
typedef ... dic_impl_item;
class dic_impl
virtual int cmp(GenPtr, GenPtr) const = 0; virtual int int_type() const = 0; virtual void clear_key(GenPtr&) const = 0; virtual void clear_inf(GenPtr&) const = 0; virtual void copy_key(GenPtr&) const = 0; virtual void copy_inf(GenPtr&) const = 0;
public:
dic_impl(); dic_impl(const dic_impl&); virtual dic_impl();
dic_impl& operator=(const dic_impl&);
GenPtr key(dic_impl_item) const; GenPtr inf(dic_impl_item) const;
dic_impl_item insert(GenPtr,GenPtr); dic_impl_item lookup(GenPtr) const; dic_impl_item first_item() const; dic_impl_item next_item(dic_impl_item) const;
dic_impl_item item(void* p) const return dic_impl_item(p);
void change_inf(dic_impl_item,GenPtr); void del_item(dic_impl_item); void del(GenPtr); void clear();
int size() const; ;


9.2.2 Priority Queues

Any class prio$\_impl$ that provides the following operations can be used as actual implementation parameter for the $\_priority$$\_queue$K, I, prio$\_impl$ data type (cf. section 4.1).
`=̀
typedef ... prio_impl_item;
class prio_impl
virtual int cmp(GenPtr, GenPtr) const = 0; virtual int int_type() const = 0; virtual void clear_key(GenPtr&) const = 0; virtual void clear_inf(GenPtr&) const = 0; virtual void copy_key(GenPtr&) const = 0; virtual void copy_inf(GenPtr&) const = 0;
public:
prio_impl(); prio_impl(int); prio_impl(int,int); prio_impl(const prio_impl&); virtual prio_impl();
prio_impl& operator=(const prio_impl&);
prio_impl_item insert(GenPtr,GenPtr); prio_impl_item find_min() const; prio_impl_item first_item() const; prio_impl_item next_item(prio_impl_item) const;
prio_impl_item item(void* p) const return prio_impl_item(p);
GenPtr key(prio_impl_item) const; GenPtr inf(prio_impl_item) const;
void del_min(); void del_item(prio_impl_item); void decrease_key(prio_impl_item,GenPtr); void change_inf(prio_impl_item,GenPtr); void clear();
int size() const; ;


9.2.3 Sorted Sequences

Any class seq$\_impl$ that provides the following operations can be used as actual implementation parameter for the $\_sortseq$K, I, seq$\_impl$ data type (cf. section 4.6).
`=̀
typedef ... seq_impl_item;
class seq_impl
virtual int cmp(GenPtr, GenPtr) const = 0; virtual int int_type() const = 0; virtual void clear_key(GenPtr&) const = 0; virtual void clear_inf(GenPtr&) const = 0; virtual void copy_key(GenPtr&) const = 0; virtual void copy_inf(GenPtr&) const = 0;
public:
seq_impl(); seq_impl(const seq_impl&); virtual seq_impl();
seq_impl& operator=(const seq_impl&); seq_impl& conc(seq_impl&);
seq_impl_item insert(GenPtr,GenPtr); seq_impl_item insert_at_item(seq_impl_item,GenPtr,GenPtr); seq_impl_item lookup(GenPtr) const; seq_impl_item locate(GenPtr) const; seq_impl_item locate_pred(GenPtr) const; seq_impl_item succ(seq_impl_item) const; seq_impl_item pred(seq_impl_item) const; seq_impl_item item(void* p) const return seq_impl_item(p);
GenPtr key(seq_impl_item) const; GenPtr inf(seq_impl_item) const;
void del(GenPtr); void del_item(seq_impl_item); void change_inf(seq_impl_item,GenPtr); void split_at_item(seq_impl_item,seq_impl&,seq_impl&); void reverse_items(seq_impl_item,seq_impl_item); void clear();
int size() const; ;


10cm