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