skiprope_node< T > Class Template Reference
A skiprope_node is a chunk of a skiprope<T>. Each node is a vector<T> and the number of T's in the vector varies from node to node. The start position of any given node is equal to the sum of the nodes before it. More...
#include <skiprope.h>
Classes | |
| struct | link_info |
Public Types | |
| typedef skiprope_node< T > | self |
Public Member Functions | |
| void | adjust_widths (ptrdiff_t) |
| adjust the width_ members of this node's link info to account for inserts or deletes in data_ | |
| const_iterator | begin () const |
| iterator | begin () |
| const_iterator | end () const |
| iterator | end () |
| void | erase (typename std::vector< T >::iterator b, typename std::vector< T >::iterator e) |
| void | erase (ptrdiff_t o, ptrdiff_t cnt) |
| void | erase (ptrdiff_t o) |
| void | insert (T const *f, T const *l, ptrdiff_t o) |
| void | insert (T const &d, ptrdiff_t o) |
| int | levels () const |
| void | push_back (T const *f, T const *l) |
| ptrdiff_t | size () const |
Static Public Member Functions | |
| static void | discard (self *victim) |
| static self * | new_node (int max_possible_level) |
| allocate a new node which will have a level which is some random number between 1 and max_possible_level, inclusive. Space will be allocated in the returned pointer for the link_ array to be treated as link_[levels_]. | |
Private Types | |
| typedef std::vector< T > ::const_iterator | const_iterator |
| typedef std::vector< T >::iterator | iterator |
Private Member Functions | |
| void | operator delete (void *p) |
| void * | operator new (size_t) |
Private Attributes | |
| std::vector< T > | data_ |
| data stored in this node | |
| int | levels_ |
| number of linkage levels in this node | |
| link_info | link_ [1] |
Friends | |
| class | skiprope< T > |
| class | skiprope_const_iterator< T > |
| class | skiprope_debugger< T > |
| class | skiprope_iterator< T > |
Detailed Description
template<class T>
class cxxtls::skiprope_node< T >
A skiprope_node is a chunk of a skiprope<T>. Each node is a vector<T> and the number of T's in the vector varies from node to node. The start position of any given node is equal to the sum of the nodes before it.
skiprope nodes vary in the size of their data structure. Each node has between 1 and 32 (or 48, or whatever -- the algorithm behaves well regardless of the maximum height -- but it mustn't bee too small or you'll get lots of searching. Too tall and you get lots of wasted space (well, if T is large and the vector chunk size is large you won't) ).
Skiprope nodes appear in multiple linked lists (and they have linkage info for each in which they appear). The linkage is bidirectional and each node level's linkage information contains a width_ member which is the distance from this node, to the next_ node at this level). Here is a picture showing how nodes are linked together in the skiprope and what width_ members contain:
lvl Nodes/levels ---+-------------------------- 3| X 2| X Z 1| X Z H J 0| X A B Z C D E F G H I J Here is a small portion of the linkage data: X[0].next_ = A X[0].width_ = width(X) A[0].prev_ = X A[0].width_ = width(A) B[0].prev_ = A B[0].next_ = Z B[0].width_ = width(B) ... X[1].next_ = Z X[1].width_= width(X) + width(A) + width(B) <A and B have only level 0 info> ... Z[1].next_ = H Z[1].prev_ = X Z[1].width_ = width(Z) + width(D) + width(E) + width(F) + width(G) ... X[2].next_ = Z X[2].width_ = width(X) + width(A) + width(B) Z[2].next_ = H Z[2].prev_ = X Z[2].width_ = width(Z) + width(D) + width(E) + width(F) + width(G) ... X[3].width_ = width(X)
Definition at line 81 of file skiprope.h.
Member Typedef Documentation
typedef std::vector<T>::const_iterator const_iterator [private] |
Definition at line 146 of file skiprope.h.
Definition at line 145 of file skiprope.h.
| typedef skiprope_node<T> self |
Definition at line 171 of file skiprope.h.
Member Function Documentation
| void adjust_widths | ( | ptrdiff_t | amount | ) |
adjust the width_ members of this node's link info to account for inserts or deletes in data_
Definition at line 262 of file skiprope.h.
| const_iterator begin | ( | ) | const |
Definition at line 174 of file skiprope.h.
| iterator begin | ( | ) |
Definition at line 173 of file skiprope.h.
| static void discard | ( | self * | victim | ) | [static] |
| const_iterator end | ( | ) | const |
Definition at line 177 of file skiprope.h.
| iterator end | ( | ) |
Definition at line 176 of file skiprope.h.
| void erase | ( | ptrdiff_t | o, | |
| ptrdiff_t | cnt | |||
| ) |
| void erase | ( | ptrdiff_t | o | ) |
| void insert | ( | T const * | f, | |
| T const * | l, | |||
| ptrdiff_t | o | |||
| ) |
| void insert | ( | T const & | d, | |
| ptrdiff_t | o | |||
| ) |
Definition at line 281 of file skiprope.h.
| int levels | ( | ) | const |
| static self* new_node | ( | int | max_possible_level | ) | [static] |
allocate a new node which will have a level which is some random number between 1 and max_possible_level, inclusive. Space will be allocated in the returned pointer for the link_ array to be treated as link_[levels_].
Definition at line 194 of file skiprope.h.
| void operator delete | ( | void * | p | ) | [private] |
| void* operator new | ( | size_t | ) | [private] |
| void push_back | ( | T const * | f, | |
| T const * | l | |||
| ) |
Definition at line 307 of file skiprope.h.
| ptrdiff_t size | ( | ) | const |
Friends And Related Function Documentation
friend class skiprope< T > [friend] |
Definition at line 151 of file skiprope.h.
friend class skiprope_const_iterator< T > [friend] |
Definition at line 152 of file skiprope.h.
friend class skiprope_debugger< T > [friend] |
Definition at line 155 of file skiprope.h.
friend class skiprope_iterator< T > [friend] |
Definition at line 153 of file skiprope.h.
Member Data Documentation
std::vector<T> data_ [private] |
data stored in this node
Definition at line 143 of file skiprope.h.
int levels_ [private] |
number of linkage levels in this node
Definition at line 141 of file skiprope.h.
Definition at line 255 of file skiprope.h.
The documentation for this class was generated from the following file:
- include/cxxtls/skiprope.h
