Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/balanced_structures/skiplist/skiplist_node.h
Go to the documentation of this file.
00001 #ifndef H_BALANCED_STRUCTURES_SKIPLIST_SKIPLIST_NODE
00002 #define H_BALANCED_STRUCTURES_SKIPLIST_SKIPLIST_NODE
00003 
00008 #include "skiplist_utils.h"
00009 
00010 namespace balanced_structures {
00011 namespace skiplist {
00012 
00013 typedef short LevelType;
00014 
00023 static const int LEVELUP_PROB = 100 / 4; // 25%
00024 
00032 static const LevelType MAXLEVEL = 15;
00033 
00037 template<typename T>
00038 class Node {
00040   typedef int SizeType;
00041 
00043   typedef Node<T> Self;
00044 
00045  public:
00046 
00047   Node(SizeType level_):value(),level(level_),
00048       previous(NULL) {
00049     Preconditions::check(level >= 1);
00050     Preconditions::check(level <= MAXLEVEL);
00051     forward = new Self*[level];
00052     forward_length = new SizeType[level];
00053     for (LevelType i = 0; i < level; i++) {
00054       forward[i] = NULL;
00055       forward_length[i] = 1;
00056     }
00057   }
00058 
00067   Self* next() const {
00068     return forward[0];
00069   }
00070 
00079   Self* prev() const {
00080     return previous;
00081   }
00082 
00086   ~Node() {
00087     delete forward;
00088     delete forward_length;
00089   }
00090 
00094   T value;
00095 
00101   LevelType level;
00102 
00106   Self** forward;
00107 
00111   SizeType* forward_length;
00112 
00116   Self* previous;
00117 };
00118 
00119 } // namespace skiplist
00120 } // namespace balanced_structures
00121 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines