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