Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/balanced_structures/skiplist/skiplist_trail.h
Go to the documentation of this file.
00001 #ifndef H_BALANCED_STRUCTURES_SKIPLIST_SKIPLIST_TRAIL
00002 #define H_BALANCED_STRUCTURES_SKIPLIST_SKIPLIST_TRAIL
00003 
00004 #include "skiplist_node.h"
00005 #include "utils/macros/unused.h"
00006 
00007 namespace balanced_structures {
00008 namespace skiplist {
00009 namespace trail {
00010 
00011 typedef size_t SizeType;
00012 
00032 template <typename T>
00033 struct Trail {
00034   Node<T>* node[MAXLEVEL];
00035   SizeType position[MAXLEVEL];
00036 };
00037 
00046 template <typename T>
00047 class TrailFunction {
00048  public:
00057   virtual bool goFurther(const Node<T>* node, SizeType position)=0;
00058 
00062   virtual ~TrailFunction(){};
00063 };
00064 
00072 template <typename T>
00073 class LowerBoundTrailFunction : public TrailFunction<T> {
00074 public:
00078   LowerBoundTrailFunction(const T& value_):value(value_) { 
00079   }
00080 
00085   virtual bool goFurther(const Node<T>* node, SizeType UNUSED(position)) {
00086     return node->value < value;
00087   }
00088 
00089  private:
00093   T value;
00094 };
00095 
00096 template <typename T>
00097 class UpperBoundTrailFunction : public TrailFunction<T> {
00098 public:
00099   UpperBoundTrailFunction(const T& value_):value(value_) { 
00100   }
00101 
00105   virtual bool goFurther(const Node<T>* node, SizeType UNUSED(position)) {
00106     return node->value <= value;
00107   }
00108 
00109  private:
00113   T value;
00114 };
00115 
00119 template <typename T>
00120 class KthTrailFunction : public TrailFunction<T> {
00121  public:
00125   KthTrailFunction(SizeType pos_):pos(pos_) { 
00126   }
00127 
00131   virtual bool goFurther(const Node<T>* UNUSED(node), SizeType position) {
00132     return position <= pos;
00133   }
00134 
00135  private:
00139   SizeType pos;
00140 };
00141 
00142 } // trail
00143 } // skiplist
00144 } // balanced_structures
00145 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines