1 #include "chre/util/heap.h"
2 #include "gtest/gtest.h"
3
4 #include <algorithm>
5 #include <array>
6
7 using chre::DynamicVector;
8 using chre::FixedSizeVector;
9
TEST(HeapDeathTest,PushHeapWhenEmpty)10 TEST(HeapDeathTest, PushHeapWhenEmpty) {
11 DynamicVector<int> v;
12 std::less<int> comp;
13 EXPECT_DEATH(chre::push_heap(v, comp), "");
14 }
15
TEST(HeapDeathTest,PopHeapWhenEmpty)16 TEST(HeapDeathTest, PopHeapWhenEmpty) {
17 DynamicVector<int> v;
18 std::less<int> comp;
19 EXPECT_DEATH(chre::pop_heap(v, comp), "");
20 }
21
TEST(HeapTest,NestedPushPopHeap)22 TEST(HeapTest, NestedPushPopHeap) {
23 DynamicVector<int> v;
24 std::less<int> comp;
25
26 // generate random test data
27 const size_t MaxSize = 1000;
28 std::array<int, MaxSize> array;
29 std::array<int, MaxSize> array_sorted;
30 std::srand(0xcafe);
31 for (size_t i = 0; i < MaxSize; ++i) {
32 array[i] = std::rand();
33 array_sorted[i] = array[i];
34 }
35
36 // make sure the popped data is in the right order of various array sizes.
37 for (size_t s = 1; s < MaxSize + 1; ++s) {
38 for (size_t i = 0; i < s; ++i) {
39 v.push_back(array[i]);
40 chre::push_heap(v, comp);
41 }
42
43 std::sort(array_sorted.begin(), array_sorted.begin() + s,
44 std::greater<int>());
45
46 for (size_t i = 0; i < s; ++i) {
47 chre::pop_heap(v, comp);
48 EXPECT_EQ(array_sorted[i], v[v.size() - 1]);
49 v.erase(v.size() - 1);
50 }
51 }
52 }
53
TEST(HeapDeathTest,RemoveHeapWithInvalidIndex)54 TEST(HeapDeathTest, RemoveHeapWithInvalidIndex) {
55 DynamicVector<int> v;
56 std::less<int> comp;
57
58 v.push_back(0);
59 chre::push_heap(v, comp);
60 EXPECT_DEATH(chre::remove_heap(v, 1, comp), "");
61 }
62
TEST(HeapTest,NestedRemoveHeap)63 TEST(HeapTest, NestedRemoveHeap) {
64 DynamicVector<int> v;
65 std::less<int> comp;
66
67 // generate random test data
68 const size_t MaxSize = 1000;
69 std::array<int, MaxSize> array;
70 std::array<int, MaxSize> array_sorted;
71 std::srand(0xcafe);
72 for (size_t i = 0; i < MaxSize; ++i) {
73 array[i] = std::rand();
74 array_sorted[i] = array[i];
75 }
76
77 for (size_t s = 1; s < MaxSize + 1; ++s) {
78 for (size_t i = 0; i < s; ++i) {
79 v.push_back(array[i]);
80 chre::push_heap(v, comp);
81 }
82
83 std::sort(array_sorted.begin(), array_sorted.begin() + s,
84 std::greater<int>());
85
86 // randomly remove one
87 chre::remove_heap(v, std::rand() % s, comp);
88 int data = v[v.size() - 1];
89 v.erase(v.size() - 1);
90
91 for (size_t i = 0; i < s; ++i) {
92 if (array_sorted[i] == data) {
93 continue;
94 }
95
96 chre::pop_heap(v, comp);
97 EXPECT_EQ(array_sorted[i], v[v.size() - 1]);
98 v.erase(v.size() - 1);
99 }
100 }
101 }
102
TEST(HeapTest,FixedSizeVectorMinHeap)103 TEST(HeapTest, FixedSizeVectorMinHeap) {
104 FixedSizeVector<int, 16> v;
105
106 for (size_t i = 0; i < 5; ++i) {
107 v.push_back(i);
108 chre::push_heap(v, std::greater<int>());
109 }
110
111 for (size_t i = 0; i < 5; ++i) {
112 chre::pop_heap(v, std::greater<int>());
113 EXPECT_EQ(i, v[v.size() - 1]);
114 v.erase(v.size() - 1);
115 }
116 }
117