|
|||
|
|
|
|||
|
|
#include <Skiplist.h>
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... | |
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.
Definition at line 69 of file Skiplist.h.
| ogdf::Skiplist< X >::Skiplist | ( | ) | [inline] |
| ogdf::Skiplist< X >::~Skiplist | ( | ) | [inline] |
Definition at line 105 of file Skiplist.h.
| 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 111 of file Skiplist.h.
| void ogdf::Skiplist< X >::add | ( | X | item | ) | [inline] |
| 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.
| int ogdf::Skiplist< X >::empty | ( | ) | const [inline] |
| 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.
| const SkiplistIterator<X> ogdf::Skiplist< X >::begin | ( | ) | const [inline] |
| int ogdf::Skiplist< X >::random_height | ( | ) | [inline, private] |
Definition at line 182 of file Skiplist.h.
| void ogdf::Skiplist< X >::grow | ( | int | newheight | ) | [inline, private] |
Definition at line 188 of file Skiplist.h.
friend class SkiplistIterator< X > [friend] |
Definition at line 70 of file Skiplist.h.
friend class Element [friend] |
Definition at line 71 of file Skiplist.h.
int ogdf::Skiplist< X >::lSize [private] |
Definition at line 177 of file Skiplist.h.
Element** ogdf::Skiplist< X >::start [private] |
Definition at line 178 of file Skiplist.h.
int ogdf::Skiplist< X >::height [private] |
Definition at line 179 of file Skiplist.h.
int ogdf::Skiplist< X >::realheight [private] |
Definition at line 180 of file Skiplist.h.
