Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <skiplist.h>
Public Types | |
typedef skiplist::ConstIterator< T > | iterator |
Public Member Functions | |
Skiplist (Rand rand_) | |
~Skiplist () | |
iterator | begin () const |
iterator | end () const |
TrailType | generic_trail (trail::TrailFunction< T > *function) const |
iterator | lower_bound (const T &value) const |
iterator | upper_bound (const T &value) const |
iterator | find (const T &value) const |
iterator | insert (const T &value) |
SizeType | nodePosition (const NodeType *node) const |
SizeType | xth (iterator it) const |
void | erase (iterator it) |
iterator | kth (SizeType k) const |
SizeType | size () const |
Private Types | |
typedef Node< T > | NodeType |
typedef size_t | SizeType |
typedef short | LevelType |
typedef trail::Trail< T > | TrailType |
Private Member Functions | |
DISALLOW_EVIL_CONSTRUCTORS (Skiplist) | |
Private Attributes | |
NodeType * | head |
NodeType * | tail |
SizeType | size_ |
Rand | rand |
Skiplist is sorted range container with following operations
xth() find position of current element in expected O(log N)
Nodes: level: 3 1 4 2 1 3 4
# -----(3)---> # -------(4)------> # # -> # --(2)-> # ----(3)----> # -> # # -> # --(2)-> # -> # --(2)-> # -> # # -> # -> # -> # -> # -> # -> # -> # HEAD 1 2 7 14 19 26 TAIL
typedef skiplist::ConstIterator<T> balanced_structures::skiplist::Skiplist< T >::iterator |
Type of the iterator
typedef short balanced_structures::skiplist::Skiplist< T >::LevelType [private] |
typedef Node<T> balanced_structures::skiplist::Skiplist< T >::NodeType [private] |
Type of the node
typedef size_t balanced_structures::skiplist::Skiplist< T >::SizeType [private] |
Type of lengths
typedef trail::Trail<T> balanced_structures::skiplist::Skiplist< T >::TrailType [private] |
Current TrailType type
balanced_structures::skiplist::Skiplist< T >::Skiplist | ( | Rand | rand_ | ) | [inline] |
Constructor, creates empty skiplist
balanced_structures::skiplist::Skiplist< T >::~Skiplist | ( | ) | [inline] |
Destructor
iterator balanced_structures::skiplist::Skiplist< T >::begin | ( | ) | const [inline] |
Iterator to the first element
balanced_structures::skiplist::Skiplist< T >::DISALLOW_EVIL_CONSTRUCTORS | ( | Skiplist< T > | ) | [private] |
iterator balanced_structures::skiplist::Skiplist< T >::end | ( | ) | const [inline] |
Iterator to the element after the last element
void balanced_structures::skiplist::Skiplist< T >::erase | ( | iterator | it | ) | [inline] |
Remove element from skiplist
it | iterator |
iterator balanced_structures::skiplist::Skiplist< T >::find | ( | const T & | value | ) | const [inline] |
TrailType balanced_structures::skiplist::Skiplist< T >::generic_trail | ( | trail::TrailFunction< T > * | function | ) | const [inline] |
iterator balanced_structures::skiplist::Skiplist< T >::insert | ( | const T & | value | ) | [inline] |
inserts a new element into a skiplist
iterator balanced_structures::skiplist::Skiplist< T >::kth | ( | SizeType | k | ) | const [inline] |
Returns iterator to the k-th element of the skiplist
iterator balanced_structures::skiplist::Skiplist< T >::lower_bound | ( | const T & | value | ) | const [inline] |
returns iterator to last node which is < value
SizeType balanced_structures::skiplist::Skiplist< T >::nodePosition | ( | const NodeType * | node | ) | const [inline] |
SizeType balanced_structures::skiplist::Skiplist< T >::size | ( | ) | const [inline] |
iterator balanced_structures::skiplist::Skiplist< T >::upper_bound | ( | const T & | value | ) | const [inline] |
returns iterator to first node which is > value
SizeType balanced_structures::skiplist::Skiplist< T >::xth | ( | iterator | it | ) | const [inline] |
NodeType* balanced_structures::skiplist::Skiplist< T >::head [private] |
Head of the skiplist, does not contain data
Rand balanced_structures::skiplist::Skiplist< T >::rand [private] |
Random generator used for node level generation
SizeType balanced_structures::skiplist::Skiplist< T >::size_ [private] |
size of the skiplist
NodeType* balanced_structures::skiplist::Skiplist< T >::tail [private] |
Tail of the skiplist, does not contain data