Open
Graph Drawing
Framework

 v.2007.11
 

ogdf::Skiplist< X > Class Template Reference

A randomized skiplist. More...

#include <Skiplist.h>

List of all members.

Public Member Functions

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

Private Member Functions

int random_height ()
void grow (int newheight)

Private Attributes

int lSize
Element ** start
int height
int realheight

Friends

class SkiplistIterator< X >
class Element

Classes

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


Detailed Description

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

A randomized skiplist.

The elements hight 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 69 of file Skiplist.h.


Constructor & Destructor Documentation

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

Construct an initially empty skiplist.

Definition at line 97 of file Skiplist.h.

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

Definition at line 105 of file Skiplist.h.


Member Function Documentation

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 111 of file Skiplist.h.

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

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

Definition at line 123 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 148 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 151 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 158 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 174 of file Skiplist.h.

template<class X>
int ogdf::Skiplist< X >::random_height (  )  [inline, private]

Definition at line 182 of file Skiplist.h.

template<class X>
void ogdf::Skiplist< X >::grow ( int  newheight  )  [inline, private]

Definition at line 188 of file Skiplist.h.


Friends And Related Function Documentation

template<class X>
friend class SkiplistIterator< X > [friend]

Definition at line 70 of file Skiplist.h.

template<class X>
friend class Element [friend]

Definition at line 71 of file Skiplist.h.


Member Data Documentation

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

Definition at line 177 of file Skiplist.h.

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

Definition at line 178 of file Skiplist.h.

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

Definition at line 179 of file Skiplist.h.

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

Definition at line 180 of file Skiplist.h.


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

© 1999-2007 by oreas GmbH, © 2005-2007 by University Dortmund and University Cologne.

Generated on Thu Nov 22 19:40:08 2007 by doxygen 1.5.4.