ogdf::Skiplist< X > Class Template Reference

A randomized skiplist. More...

#include <ogdf/basic/Skiplist.h>

List of all members.

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.
	~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

---

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

---

Constructor & Destructor Documentation

template<class X >

ogdf::Skiplist< X >::Skiplist

(

)

[inline]

Construct an initially empty skiplist.

Definition at line 99 of file Skiplist.h.

template<class X >

ogdf::Skiplist< X >::~Skiplist

(

)

[inline]

Definition at line 107 of file Skiplist.h.

---

Member Function Documentation

template<class X >

void ogdf::Skiplist< X >::add

(

X

item

)

[inline]

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

Definition at line 125 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 176 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 160 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 153 of file Skiplist.h.

template<class X >

void ogdf::Skiplist< X >::grow

(

int

newheight

)

[inline, private]

Definition at line 190 of file Skiplist.h.

template<class X >

bool ogdf::Skiplist< X >::isElement

(

X

item

)

const [inline]

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

Definition at line 113 of file Skiplist.h.

template<class X >

int ogdf::Skiplist< X >::random_height

(

)

[inline, private]

Definition at line 184 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 150 of file Skiplist.h.

---

Friends And Related Function Documentation

template<class X >

friend class Element [friend]

Definition at line 73 of file Skiplist.h.

template<class X >

friend class SkiplistIterator< X > [friend]

Definition at line 72 of file Skiplist.h.

---

Member Data Documentation

template<class X >

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

Definition at line 181 of file Skiplist.h.

template<class X >

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

Definition at line 179 of file Skiplist.h.

template<class X >

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

Definition at line 182 of file Skiplist.h.

template<class X >

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

Definition at line 180 of file Skiplist.h.

---

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

• ogdf/basic/Skiplist.h