Math.h

Go to the documentation of this file.

 
#pragma once
 
#include <ogdf/basic/Array.h>
#include <ogdf/basic/ArrayBuffer.h>
#include <ogdf/basic/basic.h>
 
#include <cmath>
#include <numeric>
#include <type_traits>
#include <utility>
 
namespace ogdf {
namespace Math {
namespace internal {
 
template<typename T, int size>
inline typename std::enable_if<size == 1, T>::type nextPower2(T x) {
    return x;
}
 
template<typename T, int size>
inline typename std::enable_if<size != 1, T>::type nextPower2(T x) {
    x = nextPower2<T, size / 2>(x);
    return x | (x >> size / 2);
}
 
}
 
constexpr double pi = 3.14159265358979323846;
 
constexpr double pi_2 = 1.57079632679489661923;
 
constexpr double pi_180 = 0.01745329251994329576;
 
constexpr double one_rad = 57.29577951308232087679;
 
const double log_of_4 = log(4.0);
 
constexpr double gamma = 0.57721566490153286061;
 
template<typename T>
inline T nextPower2(T x) {
    return internal::nextPower2<T, sizeof(T) * 8>(x - 1) + 1;
}
 
template<typename T, typename... Args>
inline static T nextPower2(T arg1, T arg2, Args... args) {
    return nextPower2(std::max(arg1, arg2, args...));
}
 
template<typename T>
inline void updateMax(T& max, const T& newValue) {
    if (max < newValue) {
        max = newValue;
    }
}
 
template<typename T>
inline void updateMin(T& min, const T& newValue) {
    if (min > newValue) {
        min = newValue;
    }
}
 
template<typename T>
OGDF_DEPRECATED("Use std::log2(x).")
inline T log2(T x) {
    OGDF_ASSERT(x > 0);
    return std::log2(x);
}
 
inline double log4(double x) {
    OGDF_ASSERT(x > 0);
    return log(x) / log_of_4;
}
 
template<typename T>
inline int sgn(T val) {
    return (T(0) < val) - (val < T(0));
}
 
inline double degreesToRadians(const double& angleInDegrees) {
    return angleInDegrees * Math::pi_180;
}
 
inline double radiansToDegrees(const double& angleInRadians) {
    return angleInRadians * Math::one_rad;
}
 
OGDF_EXPORT int binomial(int n, int k);
 
OGDF_EXPORT double binomial_d(int n, int k);
 
OGDF_DEPRECATED("Use std::tgamma(n+1).")
 
inline int factorial(int n) { return (int)std::tgamma(n + 1); }
 
OGDF_DEPRECATED("Use std::tgamma(n+1).")
 
inline double factorial_d(int n) { return std::tgamma(n + 1); }
 
OGDF_EXPORT double harmonic(unsigned n);
 
OGDF_DEPRECATED("Use std::ilogb(v).")
 
inline int floorLog2(int v) {
    if (v <= 0) {
        return -1;
    } else {
        return std::ilogb(v);
    }
}
 
template<typename T>
inline T gcd(T a, T b) {
    // If b > a, they will be swapped in the first iteration.
    do {
        T c = a % b;
        a = b;
        b = c;
    } while (b > 0);
    return a;
}
 
template<class T, class INDEX = int>
inline T gcd(const Array<T, INDEX>& numbers) {
    T current_gcd = numbers[numbers.low()];
    for (INDEX i = numbers.low() + 1; i <= numbers.high(); i++) {
        current_gcd = gcd(current_gcd, numbers[i]);
    }
    return current_gcd;
}
 
template<typename T>
inline T lcm(T a, T b) {
    T g = gcd(a, b);
    OGDF_ASSERT(g != 0);
    return (a / g) * b;
}
 
inline void getFraction(double d, int& num, int& denom, const double epsilon = 5e-10,
        const int count = 10) {
    ArrayBuffer<int> continuedFrac;
 
    // build continued fraction
    int z((int)d);
    continuedFrac.push(z);
    d = d - z;
    int i = 0;
    while (d > epsilon && i++ < count) {
        d = 1 / d;
        z = (int)d;
        continuedFrac.push(z);
        d = d - z;
    }
 
    // simplify continued fraction to simple fraction
    num = 1;
    denom = 0;
    while (!continuedFrac.empty()) {
        int last = continuedFrac.popRet();
        std::swap(num, denom);
        num += last * denom;
    }
}
 
template<class Container>
inline typename Container::value_type minValue(const Container& values) {
    OGDF_ASSERT(!values.empty());
    return *std::min_element(values.begin(), values.end());
}
 
template<class Container>
inline typename Container::value_type maxValue(const Container& values) {
    OGDF_ASSERT(!values.empty());
    return *std::max_element(values.begin(), values.end());
}
 
template<class Container>
inline typename Container::value_type sum(const Container& values) {
    return std::accumulate(values.begin(), values.end(),
            static_cast<typename Container::value_type>(0));
}
 
template<class Container>
inline double mean(const Container& values) {
    OGDF_ASSERT(!values.empty());
    return sum(values) / static_cast<double>(values.size());
}
 
template<class Container>
inline double standardDeviation(const Container& values, double mean) {
    OGDF_ASSERT(!values.empty());
    double sum = 0;
    for (auto value : values) {
        double d = value - mean;
        sum += d * d;
    }
    return sqrt(sum / values.size());
}
 
template<class Container>
inline double standardDeviation(const Container& values) {
    return standardDeviation(values, mean(values));
}
 
}
}