Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/math/binsearch/int_binsearch.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines