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