Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/balanced_structures/skiplist/skiplist.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines