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
&a-b tree &dictionary, d_array, sortseq&[BC72]
avl
&AVL tree &dictionary, d_array &[AVL62]
bb
&BB[α] tree &dictionary, d_array, sortseq &[BM80]
ch
&hashing with chaining &dictionary, d_array &[M84]
dp
&dyn. perf. hashing &h_array &[DKMMRT88,W92]
pers
&persistent tree &p_dictionary &[DSST89]
rb
&red-black tree &dictionary, d_array, sortseq &[GS78]
rs
&rand. search tree &dictionary, d_array, sortseq &[AS89]
skiplist &skip lists &dictionary, d_array, sortseq &[Pu90]
9.1.2 Priority Queues
f
&Fibonnacci heap &priority_queue &[FT87]
p
&pairing heap &priority_queue &[SV87]
k
&k-nary heap &priority_queue &[M84]
m
&monotonic heap &priority_queue &[M84]
eb
&Emde-Boas tree &priority_queue &[EKZ77,W92]
9.1.3 Geometry
range
&range tree &d2_dictionary, point_set&[Wi85,Lu78]
seg
&segment tree &seg_set &[B79,Ed82]
ps
&priority search tree & — &[MC81]
iv
&interval tree &interval_set &[MC80,Ed82]
delaunay
&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
that provides the following operations can be used as
actual implementation parameter for the
K, I, dic
and the

I, E, dic
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
that provides the following operations can be used as
actual implementation parameter for the

K, I, prio
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
that provides the following operations can be used as
actual implementation parameter for the
K, I, seq
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