Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/interval_trees/array/interval_array.h
Go to the documentation of this file.
00001 #ifndef H_INTERVAL_TREES_ARRAY_INTERVAL_ARRAY
00002 #define H_INTERVAL_TREES_ARRAY_INTERVAL_ARRAY
00003 
00010 #include <vector>
00011 #include <algorithm>
00012 
00013 #pragma GCC diagnostic ignored "-Wtype-limits"
00014 
00021 template<typename ValueType>
00022 class IntervalSumArray {
00023   typedef typename std::vector<ValueType>::size_type SizeType;
00024  public:
00028     void initialize(SizeType size) {
00029       Preconditions::check(size > 0);
00030       data.clear();
00031       data.resize(size);
00032     }
00033 
00037     void increment(SizeType start, SizeType end, ValueType value) {
00038       Preconditions::checkRange(start, end);
00039       Preconditions::check(end <= data.size());
00040       for (SizeType i = start; i < end; i++) {
00041         data[i] += value;
00042       }
00043     }
00044 
00048     ValueType get_sum(SizeType start, SizeType end) {
00049       Preconditions::check(start >= 0);
00050       Preconditions::check(start <= end);
00051       Preconditions::check(end <= data.size());
00052 
00053       ValueType result = ValueType();
00054       for (SizeType i = start; i < end; i++) {
00055           result += data[i];
00056       }
00057       return result;
00058     }
00059 
00060  private:
00061     std::vector<ValueType> data;
00062 };
00063 
00070 template<typename ValueType>
00071 class IntervalMaxArray {
00072   typedef typename std::vector<ValueType>::size_type SizeType;
00073  public:
00074     void initialize(SizeType size) {
00075         data.clear();
00076         data.resize(size);
00077     }
00078 
00082     void set(SizeType start, SizeType end, ValueType value) {
00083       Preconditions::checkRange(start, end);
00084       Preconditions::check(end <= data.size());
00085 
00086       for (SizeType i = start; i < end; i++) {
00087         data[i] = value;
00088       }
00089     }
00090 
00094     void update(SizeType start, SizeType end, ValueType value) {
00095       Preconditions::checkRange(start, end);
00096       Preconditions::check(end <= data.size());
00097 
00098       for (SizeType i = start; i < end; i++) {
00099         data[i] = std::max(data[i], value);
00100       }
00101     }
00102 
00103 
00107     ValueType get_max(SizeType start, SizeType end) {
00108       Preconditions::check(start >= 0);
00109       Preconditions::check(start <= end);
00110       Preconditions::check(end <= data.size());
00111 
00112       ValueType result = ValueType();
00113       for (SizeType i = start; i < end; i++) {
00114         result = std::max(result, data[i]);
00115       }
00116       return result;
00117     }
00118 
00119  private:
00120     std::vector<ValueType> data;
00121 };
00122 
00123 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines