1/** \file
2 * \brief Tests for Math.h
3 *
4 * \author Ivo Hedtke
5 *
6 * \par License:
7 * This file is part of the Open Graph Drawing Framework (OGDF).
8 *
9 * \par
10 * Copyright (C)<br>
11 * See README.md in the OGDF root directory for details.
12 *
13 * \par
14 * This program is free software; you can redistribute it and/or
15 * modify it under the terms of the GNU General Public License
16 * Version 2 or 3 as published by the Free Software Foundation;
17 * see the file LICENSE.txt included in the packaging of this file
18 * for details.
19 *
20 * \par
21 * This program is distributed in the hope that it will be useful,
22 * but WITHOUT ANY WARRANTY; without even the implied warranty of
23 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
24 * GNU General Public License for more details.
25 *
26 * \par
27 * You should have received a copy of the GNU General Public
28 * License along with this program; if not, see
29 * http://www.gnu.org/copyleft/gpl.html
30 */
31
32#include <typeinfo>
33
34#include <ogdf/basic/Math.h>
35#include <ogdf/basic/EpsilonTest.h>
36
37#include <testing.h>
38
39template<typename T>
40static void testGcdAndLcm(const char *type)
41{
42 it("computes gcd of large numbers of type " + string(type), [] {
43 T big = std::numeric_limits<T>::max();
44 AssertThat(Math::gcd(big, big), Equals(big));
45 });
46 it("computes lcm of large numbers of type " + string(type), [] {
47 T big = std::numeric_limits<T>::max();
48 AssertThat(Math::lcm(big, big), Equals(big));
49 });
50}
51
52static void testHarmonic()
53{
54 it("computes harmonic numbers correctly", []() {
55 EpsilonTest eps;
56 AssertThat(eps.equal(Math::harmonic(0), 1.0), IsTrue());
57 AssertThat(eps.equal(Math::harmonic(1), 1.0), IsTrue());
58 AssertThat(eps.equal(Math::harmonic(2), 1.5), IsTrue());
59 AssertThat(eps.equal(Math::harmonic(3), 1.5 + 1/3.0), IsTrue());
60 AssertThat(Math::harmonic(10), IsLessThan(3));
61 AssertThat(Math::harmonic(11), IsGreaterThan(3));
62 AssertThat(Math::harmonic(30), IsLessThan(4));
63 AssertThat(Math::harmonic(31), IsGreaterThan(4));
64 AssertThat(Math::harmonic(82), IsLessThan(5));
65 AssertThat(Math::harmonic(83), IsGreaterThan(5));
66 AssertThat(Math::harmonic(12366), IsLessThan(10));
67 AssertThat(Math::harmonic(12367), IsGreaterThan(10));
68 });
69 it("computes huge harmonic numbers correctly", []() {
70 unsigned i = 2012783313;
71 double result;
72 while ((result = Math::harmonic(i)) < 22.0) {
73 i++;
74 }
75 AssertThat(i, Equals(2012783315u));
76 });
77}
78
79namespace next_power_2 {
80
81template<typename T>
82void testSingle(T input, T expected) {
83 AssertThat(Math::nextPower2(input), Equals(expected));
84}
85
86template<typename T>
87void testJump(int exponent) {
88 const T value = static_cast<T>(1) << exponent;
89
90 testSingle<T>(value - 1, value);
91 testSingle<T>(value, value);
92 testSingle<T>(value + 1, value * 2);
93}
94
95template<typename T>
96void test(const string &name, int maxExponent = sizeof(T)*8 - 1) {
97 it("works with " + name, [&] {
98 testSingle<T>(0, 0);
99 testSingle<T>(1, 1);
100 testSingle<T>(2, 2);
101
102 for (int i = 2; i < maxExponent; i++) {
103 testJump<T>(i);
104 }
105 });
106}
107
108template<typename T>
109void testUnSigned(string name) {
110 test<typename std::make_signed<T>::type>(name, sizeof(T)* 8 - 2);
111 test<typename std::make_unsigned<T>::type>("unsigned " + name);
112}
113
114}
115
116go_bandit([]() {
117 describe("Math.h", []() {
118 it("computes gcd with two arguments", []() {
119 AssertThat(Math::gcd(5,7), Equals(1));
120 AssertThat(Math::gcd(5,15), Equals(5));
121 AssertThat(Math::gcd(6,9), Equals(3));
122 });
123 it("computes gcd with array of arguments", []() {
124 AssertThat(Math::gcd(Array<int>({5,7,11})), Equals(1));
125 AssertThat(Math::gcd(Array<int>({6,12,45})), Equals(3));
126 });
127 testGcdAndLcm<int>("int");
128 testGcdAndLcm<unsigned int>("unsigned int");
129 testGcdAndLcm<long>("long");
130 testGcdAndLcm<unsigned long>("unsigned long");
131 testGcdAndLcm<long long>("long long");
132 testGcdAndLcm<unsigned long long>("unsigned long long");
133
134 testHarmonic();
135
136 describe("nextPower2", [] {
137 next_power_2::test<char>("char");
138 next_power_2::testUnSigned<short>("short");
139 next_power_2::testUnSigned<int>("int");
140 next_power_2::testUnSigned<long>("long");
141 next_power_2::testUnSigned<long long>("long long");
142 });
143 });
144});
145