Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #include "utils/rand/rand.h" 00002 #include "debug/ppdebug.h" 00012 #include "skiplist_node.h" 00013 #include "skiplist_iterator.h" 00014 #include "skiplist_trail.h" 00015 #include <vector> 00016 #include "utils/macros/unused.h" 00017 #include "utils/macros/evil_constructors.h" 00018 00019 namespace balanced_structures { 00020 namespace skiplist { 00021 00044 template<typename T> 00045 class Skiplist { 00047 typedef Node<T> NodeType; 00048 00050 typedef size_t SizeType; 00051 00052 typedef short LevelType; 00053 00055 typedef trail::Trail<T> TrailType; 00056 00057 public: 00059 typedef skiplist::ConstIterator<T> iterator; 00060 00064 Skiplist(Rand rand_):rand(rand_) { 00065 head = new NodeType(MAXLEVEL); 00066 tail = new NodeType(MAXLEVEL); 00067 size_ = 0; 00068 for (LevelType i = 0; i < MAXLEVEL; i++) { 00069 head->forward[i] = tail; 00070 head->forward_length[i] = 1; 00071 } 00072 tail->previous = head; 00073 } 00074 00078 ~Skiplist() { 00079 NodeType* node = head; 00080 while (node != NULL) { 00081 NodeType* tmp = node->next(); 00082 delete node; 00083 node = tmp; 00084 } 00085 } 00086 00087 00091 iterator begin() const { 00092 return iterator(head->next()); 00093 } 00094 00098 iterator end() const { 00099 return iterator(tail); 00100 } 00101 00102 00106 TrailType generic_trail(trail::TrailFunction<T>* function) const { 00107 TrailType trail; 00108 SizeType position = 0; 00109 NodeType* node = head; 00110 for (LevelType i = MAXLEVEL - 1; i >= 0; i--) { 00111 // invariant: function(current_node, cnt) is true 00112 while ((node->forward[i] != tail) && 00113 (function->goFurther(node->forward[i], 00114 position + node->forward_length[i]))) { 00115 position += node->forward_length[i]; 00116 node = node->forward[i]; 00117 } 00118 trail.node[i] = node; 00119 trail.position[i] = position; 00120 } 00121 return trail; 00122 } 00123 00127 iterator lower_bound(const T& value) const { 00128 trail::LowerBoundTrailFunction<T> funct(value); 00129 TrailType trail = generic_trail(&funct); 00130 return iterator(trail.node[0]->next()); 00131 } 00132 00136 iterator upper_bound(const T& value) const { 00137 trail::UpperBoundTrailFunction<T> funct(value); 00138 TrailType trail = generic_trail(&funct); 00139 return iterator(trail.node[0]->next()); 00140 } 00141 00146 iterator find(const T& value) const { 00147 iterator it = lower_bound(value); 00148 if (*it != value) return end(); 00149 return it; 00150 } 00151 00157 iterator insert(const T& value) { 00158 trail::LowerBoundTrailFunction<T> funct(value); 00159 TrailType trail = generic_trail(&funct); 00160 SizeType pos = trail.position[0]+1; 00161 00162 // create a new node 00163 NodeType* node = new NodeType(node_utils::randomLevel(&rand, LEVELUP_PROB, 00164 MAXLEVEL)); 00165 node->value = value; 00166 node->previous = trail.node[0]; 00167 trail.node[0]->forward[0]->previous = node; 00168 00169 // set forward links of the newly created node 00170 // and insert it into lists 00171 for (LevelType i = 0; i < node->level; i++) { 00172 node->forward[i] = trail.node[i]->forward[i]; 00173 node->forward_length[i] = trail.node[i]->forward_length[i] + 00174 trail.position[i] - pos + 1; 00175 trail.node[i]->forward[i] = node; 00176 trail.node[i]->forward_length[i] = pos - trail.position[i]; 00177 } 00178 // set update forward lengths of higher levels 00179 for (LevelType i = node->level; i < MAXLEVEL; i++) { 00180 trail.node[i]->forward_length[i]++; 00181 } 00182 size_++; 00183 return iterator(node); 00184 } 00185 00189 SizeType nodePosition(const NodeType* node) const { 00190 SizeType distance_end = 0; 00191 while (node != tail) { 00192 assert(node->level > 0); 00193 LevelType top = node->level - 1; 00194 distance_end += node->forward_length[top]; 00195 node = node->forward[top]; 00196 } 00197 return size_ - distance_end; 00198 } 00199 00203 SizeType xth(iterator it) const { 00204 return nodePosition(it.getNode()); 00205 } 00206 00216 void erase(iterator it) { 00217 Preconditions::check(it != end(), "can't delete end()"); 00218 NodeType* node = it.getNode(); 00219 00220 // get the full trail for the node 00221 trail::KthTrailFunction<T> funct(nodePosition(node)); 00222 TrailType trail = generic_trail(&funct); 00223 assert(trail.node[0]->next() == node); 00224 00225 NodeType* prev = trail.node[0]; 00226 NodeType* next = node->next(); 00227 00228 next->previous = prev; 00229 // remove node at levels 00230 for (int i=0; i < node->level; i++) { 00231 trail.node[i]->forward[i] = node->forward[i]; 00232 trail.node[i]->forward_length[i] += node->forward_length[i] - 1; 00233 }; 00234 // update lengths of higher levels 00235 for (int i = node->level; i < MAXLEVEL; i++) { 00236 trail.node[i]->forward_length[i]--; 00237 } 00238 00239 delete node; 00240 size_--; 00241 } 00242 00243 00249 iterator kth(SizeType k) const { 00250 Preconditions::checkRange(k, size()); 00251 trail::KthTrailFunction<T> funct(k); 00252 TrailType trail = generic_trail(&funct); 00253 return iterator(trail.node[0]->next()); 00254 } 00255 00259 SizeType size() const { 00260 return size_; 00261 } 00262 00263 private: 00264 00268 NodeType* head; 00269 00273 NodeType* tail; 00274 00278 SizeType size_; 00279 00283 Rand rand; 00284 00285 DISALLOW_EVIL_CONSTRUCTORS(Skiplist); 00286 }; 00287 00288 00289 } // namespace skiplist 00290 } // namespace balanced_structures