1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
|
#include <numeric>
#include "HCheckConfig.h"
#include "catch.hpp"
#include "util/HighsHash.h"
#include "util/HighsHashTree.h"
TEST_CASE("Highs_log2i", "[util]") {
// test 32 bit and 64 bit values whoes log2 value should be floored
uint32_t x = 12345;
uint64_t y = 1234567891011;
REQUIRE(HighsHashHelpers::log2i(x) == 13);
REQUIRE(HighsHashHelpers::log2i(y) == 40);
// test 2^13 and 2^40 which should yield the same result
x = 8192;
y = 1099511627776;
REQUIRE(HighsHashHelpers::log2i(x) == 13);
REQUIRE(HighsHashHelpers::log2i(y) == 40);
}
TEST_CASE("Highs_HashTree", "[util]") {
// test 32 bit and 64 bit values whoes log2 value should be floored
HighsHashTree<int> htree;
htree.insert(1);
htree.insert(2);
htree.insert(3);
REQUIRE(!htree.contains(4));
REQUIRE(htree.contains(1));
REQUIRE(htree.contains(2));
REQUIRE(htree.contains(3));
htree.erase(2);
REQUIRE(htree.contains(1));
REQUIRE(!htree.contains(2));
REQUIRE(htree.contains(3));
REQUIRE(!htree.insert(1));
REQUIRE(!htree.insert(3));
constexpr int NUM_CHECK = 10000;
for (int i = 0; i < NUM_CHECK; ++i) {
htree.insert(i);
}
std::vector<int> test;
std::vector<int> testReference;
testReference.resize(NUM_CHECK);
std::iota(testReference.begin(), testReference.end(), 0);
htree.for_each([&](const HighsHashTableEntry<int>& entry) {
test.push_back(entry.key());
return false;
});
REQUIRE(test.size() == NUM_CHECK);
std::sort(test.begin(), test.end());
REQUIRE(std::equal(test.begin(), test.end(), testReference.begin()));
for (int i = 0; i < NUM_CHECK; ++i) {
REQUIRE(htree.contains(i));
}
testReference.clear();
for (int i = 0; i < NUM_CHECK; ++i) {
if ((i % 7) == 0) {
REQUIRE(htree.contains(i));
htree.erase(i);
REQUIRE(!htree.contains(i));
} else {
testReference.push_back(i);
}
}
test.clear();
htree.for_each([&](const HighsHashTableEntry<int>& entry) {
test.push_back(entry.key());
return false;
});
REQUIRE(test.size() == testReference.size());
std::sort(test.begin(), test.end());
REQUIRE(std::equal(test.begin(), test.end(), testReference.begin()));
HighsHashTree<int> htree2;
for (int i = 0; i < NUM_CHECK; ++i) {
if (htree.contains(i)) {
REQUIRE((i % 7) != 0);
} else {
REQUIRE((i % 7) == 0);
htree2.insert(i);
}
}
const auto* commonElement = htree.find_common(htree2);
REQUIRE(commonElement == nullptr);
for (int i = 0; i < NUM_CHECK; ++i) {
if (i % 7 != 0) {
htree2.insert(i);
commonElement = htree.find_common(htree2);
REQUIRE(commonElement != nullptr);
REQUIRE(commonElement->key() == i);
htree.erase(i);
commonElement = htree.find_common(htree2);
REQUIRE(commonElement == nullptr);
}
}
HighsHashTree<int> htree3 = htree2;
for (int i = 0; i < NUM_CHECK; ++i) {
const int* a = htree2.find(i);
const int* b = htree3.find(i);
if (a == b) {
REQUIRE(a == nullptr);
} else {
REQUIRE(*a == *b);
}
}
}
|
