Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
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