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