Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/interval_trees/fenwick/fenwick.h
Go to the documentation of this file.
00001 #ifndef H_INTERVAL_TREES_FENWICK_FENWICK
00002 #define H_INTERVAL_TREES_FENWICK_FENWICK
00003 
00009 #include <unistd.h>
00010 #include <vector>
00011 #include <algorithm>
00012 #include "utils/preconditions/preconditions.h"
00013 #include <functional>
00014 #include "debug/ppdebug.h"
00015 
00016 namespace interval_trees {
00017 namespace fenwick {
00018 
00023 enum FenwickDirection {
00024   TO_ZERO, // can query interval [0..pos]
00025   TO_INFTY, // can query interval [pos..size)
00026 };
00027 
00040 template<typename ValueType, class Operation>
00041 class FenwickTree {
00042  public:
00043   typedef size_t SizeType;
00044 
00048   void initialize(FenwickDirection type_, size_t size,
00049      const ValueType& initial) {
00050     Preconditions::check(size > 0, "size shoud be positive");
00051     data.clear();
00052     data.resize(size, initial);
00053     type = type_;
00054   }
00055 
00060   void update(SizeType pos, ValueType value) {
00061     Preconditions::checkRange(pos, data.size());
00062     pos++;
00063     while (pos > 0 && pos <= data.size()) {
00064       data[pos-1] = Operation::operation(data[pos-1], value);
00065       pos = _advance(pos, TO_ZERO);
00066     }
00067   }
00068 
00073   ValueType get_on_interval(SizeType pos) {
00074     Preconditions::checkRange(pos, data.size());
00075     ValueType result = data[pos];
00076     pos = _advance(pos + 1, TO_INFTY);
00077     while (pos > 0 && pos <= data.size()) {
00078       result = Operation::operation(result, data[pos-1]);
00079       pos = _advance(pos, TO_INFTY);
00080     }
00081     return result;
00082   }
00083 
00084  private:
00088   inline SizeType _advance(SizeType pos, FenwickDirection direction) {
00089     if (type == direction) {
00090       return pos + last_one(pos);
00091     } else {
00092       return pos - last_one(pos);
00093     }
00094   }
00095 
00099   SizeType last_one(SizeType x) {
00100     return x ^ (x & (x - 1));
00101   }
00102 
00103   std::vector<ValueType> data;
00104   FenwickDirection type;
00105 };
00106 
00107 
00111 template <typename T>
00112 struct BinaryPlus {
00113     static T operation(const T& x, const T& y) {
00114       return x + y;
00115     }
00116 };
00117 
00118 template<typename T>
00119 class FenwickSumTree {
00123   typedef class FenwickTree<T, BinaryPlus<T> > FenwickType;
00124 
00128   typedef typename FenwickType::SizeType SizeType;
00129 
00130  public:
00131 
00132   void initialize(SizeType size) {
00133     fenwick.initialize(TO_ZERO, size, 0);
00134   }
00135 
00136   void increment(SizeType pos, T value) {
00137     fenwick.update(pos, value);
00138   }
00139 
00140   T get_prefix_sum(SizeType pos) {
00141     return fenwick.get_on_interval(pos);
00142   }
00143 
00144  private:
00148   FenwickType fenwick;
00149 };
00150 
00151 template <typename T>
00152 struct BinaryMax  {
00153     static T operation(const T& x, const T& y) {
00154       return std::max(x, y);
00155     }
00156 };
00157 
00158 template<typename T>
00159 class FenwickMaxTree {
00160  public:
00161   void initialize(FenwickDirection type, size_t size) {
00162     T initial = T(); // zero
00163 
00164     fenwick.initialize(type, size, initial);
00165   }
00166 
00167   void update(int pos, T value) {
00168     fenwick.update(pos, value);
00169   }
00170 
00171   T get_max(int pos) {
00172     return fenwick.get_on_interval(pos);
00173   }
00174 
00175  private:
00176   typedef FenwickTree<T, BinaryMax<T> > FenwickType;
00177   FenwickType fenwick;
00178 };
00179 
00180 } // namespace fenwick
00181 } // namespace interval_trees
00182 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines