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
|
#include <gtest/gtest.h>
#include <algorithm>
#include <vector>
#include "veb.h"
using namespace std;
namespace {
class VEBTest : public ::testing::Test {
protected:
void VEBSortTester(vector<int> values, int max_value) {
shared_ptr<VEB> veb = VEB::Create(max_value);
for (int value: values) {
veb->Insert(value);
}
sort(values.begin(), values.end());
EXPECT_EQ(values.front(), veb->GetMinimum());
EXPECT_EQ(values.back(), veb->GetMaximum());
for (size_t i = 0; i + 1 < values.size(); ++i) {
EXPECT_EQ(values[i + 1], veb->GetSuccessor(values[i]));
}
EXPECT_EQ(-1, veb->GetSuccessor(values.back()));
}
};
TEST_F(VEBTest, SmallRange) {
vector<int> values{8, 13, 5, 1, 4, 15, 2, 10, 6, 7};
VEBSortTester(values, 16);
}
TEST_F(VEBTest, MediumRange) {
vector<int> values{167, 243, 88, 12, 137, 199, 212, 45, 150, 189};
VEBSortTester(values, 255);
}
TEST_F(VEBTest, LargeRangeSparse) {
vector<int> values;
for (size_t i = 0; i < 100; ++i) {
values.push_back(i * 1000000);
}
VEBSortTester(values, 100000000);
}
TEST_F(VEBTest, LargeRangeDense) {
vector<int> values;
for (size_t i = 0; i < 1000000; ++i) {
values.push_back(i);
}
VEBSortTester(values, 1000000);
}
} // namespace
|
