Open
Graph Drawing
Framework

 v. 2022.02 (Dogwood)
 

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 50 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 ( item)
inline

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

Definition at line 104 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 154 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 139 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 132 of file Skiplist.h.

◆ end()

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

returns an invalid iterator

Definition at line 157 of file Skiplist.h.

◆ grow()

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

Definition at line 171 of file Skiplist.h.

◆ isElement()

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

◆ random_height()

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

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

Friends And Related Function Documentation

◆ Element

template<class X >
friend class Element
friend

Definition at line 52 of file Skiplist.h.

◆ SkiplistIterator< X >

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

Definition at line 51 of file Skiplist.h.

Member Data Documentation

◆ m_height

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

Definition at line 162 of file Skiplist.h.

◆ m_lSize

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

Definition at line 160 of file Skiplist.h.

◆ m_realheight

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

Definition at line 163 of file Skiplist.h.

◆ m_start

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

Definition at line 161 of file Skiplist.h.


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