Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
00001 #ifndef H_INTERVAL_TREES_UTILS_HEAP 00002 #define H_INTERVAL_TREES_UTILS_HEAP 00003 00017 #include <stdint.h> 00018 #include <limits> 00019 #include "utils/preconditions/preconditions.h" 00020 00021 namespace heap { 00027 template <typename T> 00028 inline T left(T x) { 00029 Preconditions::check(x > 0); 00030 if (x > std::numeric_limits<T>::max() / 2) { 00031 throw std::overflow_error(""); 00032 } 00033 return x * 2; 00034 }; 00035 00041 template <typename T> 00042 inline T right(T x) { 00043 Preconditions::check(x > 0); 00044 if (x > std::numeric_limits<T>::max() / 2) { 00045 throw std::overflow_error(""); 00046 } 00047 return x * 2 + 1; 00048 }; 00049 00055 template <typename T> 00056 inline T parent(T x) { 00057 Preconditions::check(x > 1, "Node does not have a parent"); 00058 return x / 2; 00059 }; 00060 00064 template <typename T> 00065 inline bool isLeftChild(T x) { 00066 Preconditions::check(x > 1); 00067 return (x % 2) == 0; 00068 } 00072 template <typename T> 00073 inline bool isRightChild(T x) { 00074 Preconditions::check(x > 1); 00075 return (x % 2) == 1; 00076 } 00077 00081 template <typename T> 00082 inline T sibling(T x) { 00083 Preconditions::check(x > 1); 00084 return x ^ 1; 00085 } 00086 00094 template <typename T> 00095 T nextPowerOfTwo(T x) { 00096 Preconditions::check(x > 0, "Argument should be positive!"); 00097 00098 if (x > 1 + std::numeric_limits<T>::max() / 2) { 00099 throw std::overflow_error("Next power of two overflows."); 00100 } 00101 00102 size_t tmp = x - 1; 00103 int n = 1; 00104 // LogLog N implementation. 00105 while (n < std::numeric_limits<T>::digits) { 00106 tmp |= (tmp >> n); 00107 n *= 2; 00108 } 00109 return tmp + 1; 00110 } 00111 00112 } 00113 00114 #endif