Open
Graph Drawing
Framework

 v.2015.05
 

ogdf::Skiplist< X > Class Template Reference

A randomized skiplist. More...

#include <ogdf/basic/Skiplist.h>

Classes

class  Element
 Internal structure to hold the items and internal forward pointers of the skiplist. More...
 

Public Member Functions

 Skiplist ()
 Construct an initially empty skiplist. More...
 
 ~Skiplist ()
 
void add (X item)
 Adds the item item into the skiplist [O'(log n)]. More...
 
const SkiplistIterator< X > begin () const
 returns an (forward) iterator for the skiplist More...
 
void clear (bool killData=false)
 Clears the current skiplist. More...
 
int empty () const
 Returns true if the skiplist contains no elements. More...
 
bool isElement (X item) const
 Returns true if the item item is contained in the skiplist [O'(log n)]. More...
 
int size () const
 Returns the current size of the skiplist, i.e., the number of elements. More...
 

Private Member Functions

void grow (int newheight)
 
int random_height ()
 

Private Attributes

int height
 
int lSize
 
int realheight
 
Element ** start
 

Friends

class Element
 
class SkiplistIterator< X >
 

Detailed Description

template<class X>
class ogdf::Skiplist< X >

A randomized skiplist.

The elements height is computed using the traditional coin-flip method, using a 50-50 chance to stop growing. The given running times of the methods below are therefore only expected running times.

Warning
The code expects the type X to be a pointer! If X is not a pointer, compiler errors will occur!

Definition at line 62 of file Skiplist.h.

Constructor & Destructor Documentation

template<class X>
ogdf::Skiplist< X >::Skiplist ( )
inline

Construct an initially empty skiplist.

Definition at line 90 of file Skiplist.h.

template<class X>
ogdf::Skiplist< X >::~Skiplist ( )
inline

Definition at line 98 of file Skiplist.h.

Member Function Documentation

template<class X>
void ogdf::Skiplist< X >::add ( item)
inline

Adds the item item into the skiplist [O'(log n)].

Definition at line 116 of file Skiplist.h.

template<class X>
const SkiplistIterator<X> ogdf::Skiplist< X >::begin ( ) const
inline

returns an (forward) iterator for the skiplist

Definition at line 167 of file Skiplist.h.

template<class X>
void ogdf::Skiplist< X >::clear ( bool  killData = false)
inline

Clears the current skiplist.

If killData is true, the items of the Skiplist (which are stored as pointers) are automatically deleted.

Definition at line 151 of file Skiplist.h.

template<class X>
int ogdf::Skiplist< X >::empty ( ) const
inline

Returns true if the skiplist contains no elements.

Definition at line 144 of file Skiplist.h.

template<class X>
void ogdf::Skiplist< X >::grow ( int  newheight)
inlineprivate

Definition at line 181 of file Skiplist.h.

template<class X>
bool ogdf::Skiplist< X >::isElement ( item) const
inline

Returns true if the item item is contained in the skiplist [O'(log n)].

Definition at line 104 of file Skiplist.h.

template<class X>
int ogdf::Skiplist< X >::random_height ( )
inlineprivate

Definition at line 175 of file Skiplist.h.

template<class X>
int ogdf::Skiplist< X >::size ( ) const
inline

Returns the current size of the skiplist, i.e., the number of elements.

Definition at line 141 of file Skiplist.h.

Friends And Related Function Documentation

template<class X>
friend class Element
friend

Definition at line 64 of file Skiplist.h.

template<class X>
friend class SkiplistIterator< X >
friend

Definition at line 63 of file Skiplist.h.

Member Data Documentation

template<class X>
int ogdf::Skiplist< X >::height
private

Definition at line 172 of file Skiplist.h.

template<class X>
int ogdf::Skiplist< X >::lSize
private

Definition at line 170 of file Skiplist.h.

template<class X>
int ogdf::Skiplist< X >::realheight
private

Definition at line 173 of file Skiplist.h.

template<class X>
Element** ogdf::Skiplist< X >::start
private

Definition at line 171 of file Skiplist.h.


The documentation for this class was generated from the following file: