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...
bool	empty () const
	Returns true if the skiplist contains no elements. More...
const SkiplistIterator< X >	end () const
	returns an invalid iterator 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	m_height
int	m_lSize
int	m_realheight
Element **	m_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 54 of file Skiplist.h.

Constructor & Destructor Documentation

Skiplist()

template<class X >

ogdf::Skiplist< X >::Skiplist ( )

inline

Construct an initially empty skiplist.

Definition at line 78 of file Skiplist.h.

~Skiplist()

template<class X >

ogdf::Skiplist< X >::~Skiplist ( )

inline

Definition at line 86 of file Skiplist.h.

Member Function Documentation

add()

template<class X >

void ogdf::Skiplist< X >::add ( X  item )

inline

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

Definition at line 105 of file Skiplist.h.

begin()

template<class X >

const SkiplistIterator<X> ogdf::Skiplist< X >::begin ( ) const

inline

returns an (forward) iterator for the skiplist

Definition at line 158 of file Skiplist.h.

clear()

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

empty()

template<class X >

bool ogdf::Skiplist< X >::empty ( ) const

inline

Returns true if the skiplist contains no elements.

Definition at line 135 of file Skiplist.h.

end()

template<class X >

const SkiplistIterator<X> ogdf::Skiplist< X >::end ( ) const

inline

returns an invalid iterator

Definition at line 161 of file Skiplist.h.

grow()

template<class X >

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

inlineprivate

Definition at line 177 of file Skiplist.h.

isElement()

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

random_height()

template<class X >

int ogdf::Skiplist< X >::random_height ( )

inlineprivate

Definition at line 169 of file Skiplist.h.

size()

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

Friends And Related Function Documentation

Element

template<class X >

friend class Element

friend

Definition at line 56 of file Skiplist.h.

SkiplistIterator< X >

template<class X >

friend class SkiplistIterator< X >

friend

Definition at line 55 of file Skiplist.h.

Member Data Documentation

m_height

template<class X >

int ogdf::Skiplist< X >::m_height

private

Definition at line 166 of file Skiplist.h.

m_lSize

template<class X >

int ogdf::Skiplist< X >::m_lSize

private

Definition at line 164 of file Skiplist.h.

m_realheight

template<class X >

int ogdf::Skiplist< X >::m_realheight

private

Definition at line 167 of file Skiplist.h.

m_start

template<class X >

Element** ogdf::Skiplist< X >::m_start

private

Definition at line 165 of file Skiplist.h.

---

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

• include/ogdf/basic/Skiplist.h