Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
balanced_structures::skiplist::Skiplist< T > Class Template Reference

#include <skiplist.h>

Collaboration diagram for balanced_structures::skiplist::Skiplist< T >:

List of all members.

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

NodeTypehead
NodeTypetail
SizeType size_
Rand rand

Detailed Description

template<typename T>
class balanced_structures::skiplist::Skiplist< T >

Skiplist is sorted range container with following operations

  • insert() in expected O(log N)
  • erase() in expected O(log N)
  • find() element by value in expected O(log N)
  • kth() element in expected O(log N)
  • xth() find position of current element in expected O(log N)

    Skiplist:

     Nodes:
     level: 3    1    4    2    1    3    4
       # -----(3)---> # -------(4)------> #
       # -> # --(2)-> # ----(3)----> # -> #
       # -> # --(2)-> # -> # --(2)-> # -> #
       # -> # -> # -> # -> # -> # -> # -> #
     HEAD   1    2    7   14   19   26   TAIL
     

Member Typedef Documentation

Type of the iterator

template<typename T >
typedef short balanced_structures::skiplist::Skiplist< T >::LevelType [private]
template<typename T >
typedef Node<T> balanced_structures::skiplist::Skiplist< T >::NodeType [private]

Type of the node

template<typename T >
typedef size_t balanced_structures::skiplist::Skiplist< T >::SizeType [private]

Type of lengths

template<typename T >
typedef trail::Trail<T> balanced_structures::skiplist::Skiplist< T >::TrailType [private]

Current TrailType type


Constructor & Destructor Documentation

template<typename T >
balanced_structures::skiplist::Skiplist< T >::Skiplist ( Rand  rand_) [inline]

Constructor, creates empty skiplist

template<typename T >
balanced_structures::skiplist::Skiplist< T >::~Skiplist ( ) [inline]

Destructor


Member Function Documentation

template<typename T >
iterator balanced_structures::skiplist::Skiplist< T >::begin ( ) const [inline]

Iterator to the first element

template<typename T >
balanced_structures::skiplist::Skiplist< T >::DISALLOW_EVIL_CONSTRUCTORS ( Skiplist< T >  ) [private]
template<typename T >
iterator balanced_structures::skiplist::Skiplist< T >::end ( ) const [inline]

Iterator to the element after the last element

template<typename T >
void balanced_structures::skiplist::Skiplist< T >::erase ( iterator  it) [inline]

Remove element from skiplist

Precondition:
  • it should be a valid iterator
Postcondition:
only iterators pointing to the deleted element will be invalidated
Parameters:
ititerator
template<typename T >
iterator balanced_structures::skiplist::Skiplist< T >::find ( const T &  value) const [inline]
Returns:
iterator to first element equals to value or end() if not found
template<typename T >
TrailType balanced_structures::skiplist::Skiplist< T >::generic_trail ( trail::TrailFunction< T > *  function) const [inline]
Returns:
trail to element determined by a TrailFunction<T>
template<typename T >
iterator balanced_structures::skiplist::Skiplist< T >::insert ( const T &  value) [inline]

inserts a new element into a skiplist

Returns:
iterator to newly inserted element
template<typename T >
iterator balanced_structures::skiplist::Skiplist< T >::kth ( SizeType  k) const [inline]

Returns iterator to the k-th element of the skiplist

Precondition:
template<typename T >
iterator balanced_structures::skiplist::Skiplist< T >::lower_bound ( const T &  value) const [inline]

returns iterator to last node which is < value

template<typename T >
SizeType balanced_structures::skiplist::Skiplist< T >::nodePosition ( const NodeType node) const [inline]
Returns:
distance of the node from the start
template<typename T >
SizeType balanced_structures::skiplist::Skiplist< T >::size ( ) const [inline]
Returns:
number of elements in the skiplist
template<typename T >
iterator balanced_structures::skiplist::Skiplist< T >::upper_bound ( const T &  value) const [inline]

returns iterator to first node which is > value

template<typename T >
SizeType balanced_structures::skiplist::Skiplist< T >::xth ( iterator  it) const [inline]
Returns:
distance of the iterator from the start of the list

Member Data Documentation

template<typename T >
NodeType* balanced_structures::skiplist::Skiplist< T >::head [private]

Head of the skiplist, does not contain data

template<typename T >
Rand balanced_structures::skiplist::Skiplist< T >::rand [private]

Random generator used for node level generation

template<typename T >
SizeType balanced_structures::skiplist::Skiplist< T >::size_ [private]

size of the skiplist

template<typename T >
NodeType* balanced_structures::skiplist::Skiplist< T >::tail [private]

Tail of the skiplist, does not contain data


The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines