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
|
#include <library/cpp/yt/small_containers/compact_heap.h>
#include <library/cpp/testing/gtest/gtest.h>
#include <random>
namespace NYT {
namespace {
////////////////////////////////////////////////////////////////////////////////
TEST(CompactHeapTest, Simple)
{
TCompactHeap<int, 2> heap;
heap.push(3);
heap.push(1);
heap.push(2);
EXPECT_EQ(3u, heap.size());
EXPECT_EQ(1, heap.extract_min());
EXPECT_EQ(2, heap.get_min());
EXPECT_EQ(2, heap.extract_min());
EXPECT_EQ(3, heap.extract_min());
EXPECT_TRUE(heap.empty());
}
TEST(CompactHeapTest, SimpleComparator)
{
TCompactHeap<int, 2, std::greater<int>> heap;
heap.push(3);
heap.push(1);
heap.push(2);
EXPECT_EQ(3u, heap.size());
EXPECT_EQ(3, heap.extract_min());
EXPECT_EQ(2, heap.get_min());
EXPECT_EQ(2, heap.extract_min());
EXPECT_EQ(1, heap.extract_min());
EXPECT_TRUE(heap.empty());
}
TEST(CompactHeapTest, Capacity)
{
TCompactHeap<int, 2> heap;
EXPECT_EQ(2u, heap.capacity());
EXPECT_EQ(0u, heap.size());
for (int i = 0; i < 100; ++i) {
heap.push(i);
}
EXPECT_LE(100u, heap.capacity());
EXPECT_EQ(100u, heap.size());
for (int i = 0; i < 99; ++i) {
heap.pop();
}
EXPECT_LE(100u, heap.capacity());
EXPECT_EQ(1u, heap.size());
heap.shrink_to_small();
EXPECT_EQ(2u, heap.capacity());
EXPECT_EQ(1u, heap.size());
}
TEST(CompactHeapTest, Stress)
{
TCompactHeap<int, 3, std::greater<int>> heap;
std::vector<int> values;
std::mt19937 rng(42);
for (int iteration = 0; iteration < 1000; ++iteration) {
EXPECT_EQ(values.size(), heap.size());
EXPECT_EQ(values.empty(), heap.empty());
{
std::vector<int> content(heap.begin(), heap.end());
std::sort(content.rbegin(), content.rend());
EXPECT_EQ(values, content);
}
if (!values.empty()) {
EXPECT_EQ(values[0], heap.get_min());
}
if (values.empty() || rng() % 2 == 0) {
int x = rng() % 100;
heap.push(x);
values.push_back(x);
std::sort(values.rbegin(), values.rend());
} else {
if (rng() % 2 == 0) {
EXPECT_EQ(values[0], heap.extract_min());
} else {
heap.pop();
}
values.erase(values.begin());
}
}
}
////////////////////////////////////////////////////////////////////////////////
} // namespace
} // namespace NYT
|
