Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_MATH_BINSEARCH_INT_BINSEARCH 00002 #define H_MATH_BINSEARCH_INT_BINSEARCH 00003 00007 #include "utils/preconditions/preconditions.h" 00008 #include "utils/static_assert/static_assert.h" 00009 #include <stdexcept> 00010 00011 namespace math { 00012 namespace binsearch { 00013 00027 template <typename T> 00028 T range_middle(T left, T right) { 00029 STATIC_ASSERT(std::numeric_limits<T>::is_integer, 00030 "T should be of integral type"); 00031 Preconditions::check(left < right, "Invalid range"); 00032 T len = right - left; 00033 if (len <= 0) { 00034 throw std::overflow_error("Too big range!"); 00035 } 00036 return left + len / 2; 00037 } 00038 00066 template <typename ValueType, typename SizeType> 00067 SizeType lower_bound(ValueType pole[], SizeType left, SizeType right, ValueType value) 00068 { 00069 STATIC_ASSERT(std::numeric_limits<SizeType>::is_integer, 00070 "SizeType should be of integral type"); 00071 Preconditions::check(left <= right, "Invalid range"); 00072 if (left == right) { 00073 return left; 00074 } 00075 if (std::numeric_limits<SizeType>::is_signed) { 00076 // Checks for signed values overflow. 00077 // Note that right - left == 0 could be also caused by overflow! 00078 if (right - left < 0) { 00079 throw std::overflow_error("Too big range!"); 00080 } 00081 } 00082 while (right - left > 0) { 00083 SizeType middle = range_middle(left, right); 00084 if (pole[middle] < value) { 00085 left = middle + 1; 00086 } else { 00087 right = middle; 00088 } 00089 } 00090 return left; 00091 } 00092 00118 template <typename ValueType, typename SizeType> 00119 SizeType upper_bound(ValueType pole[], SizeType left, SizeType right, ValueType value) { 00120 Preconditions::check(left <= right, "Invalid range"); 00121 if (left == right) { 00122 return left; 00123 } 00124 if (std::numeric_limits<SizeType>::is_signed) { 00125 // Checks for signed values overflow. 00126 // Note that right - left == 0 could be also caused by overflow! 00127 if (right - left <= 0) { 00128 throw std::overflow_error("Too big range"); 00129 } 00130 } 00131 while (right - left > 0) { 00132 SizeType middle = range_middle(left, right); 00133 if (value < pole[middle]) { 00134 right = middle; 00135 } else { 00136 left = middle + 1; 00137 } 00138 } 00139 return left; 00140 } 00141 00142 } // namespace binsearch 00143 } // namespace math 00144 #endif