1 #include "gtest/gtest.h"
2 #include "chre/util/heap.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, std::greater<int>());
44
45 for (size_t i = 0; i < s; ++i) {
46 chre::pop_heap(v, comp);
47 EXPECT_EQ(array_sorted[i], v[v.size() - 1]);
48 v.erase(v.size() - 1);
49 }
50 }
51 }
52
TEST(HeapDeathTest,RemoveHeapWithInvalidIndex)53 TEST(HeapDeathTest, RemoveHeapWithInvalidIndex) {
54 DynamicVector<int> v;
55 std::less<int> comp;
56
57 v.push_back(0);
58 chre::push_heap(v, comp);
59 EXPECT_DEATH(chre::remove_heap(v, 1, comp), "");
60 }
61
TEST(HeapTest,NestedRemoveHeap)62 TEST(HeapTest, NestedRemoveHeap) {
63 DynamicVector<int> v;
64 std::less<int> comp;
65
66 // generate random test data
67 const size_t MaxSize = 1000;
68 std::array<int, MaxSize> array;
69 std::array<int, MaxSize> array_sorted;
70 std::srand(0xcafe);
71 for (size_t i = 0; i < MaxSize; ++i) {
72 array[i] = std::rand();
73 array_sorted[i] = array[i];
74 }
75
76 for (size_t s = 1; s < MaxSize + 1; ++s) {
77 for (size_t i = 0; i < s; ++i) {
78 v.push_back(array[i]);
79 chre::push_heap(v, comp);
80 }
81
82 std::sort(array_sorted.begin(), array_sorted.begin() + s, std::greater<int>());
83
84 // randomly remove one
85 chre::remove_heap(v, std::rand() % s, comp);
86 int data = v[v.size() - 1];
87 v.erase(v.size() - 1);
88
89 for (size_t i = 0; i < s; ++i) {
90 if (array_sorted[i] == data) {
91 continue;
92 }
93
94 chre::pop_heap(v, comp);
95 EXPECT_EQ(array_sorted[i], v[v.size() - 1]);
96 v.erase(v.size() - 1);
97 }
98 }
99 }
100
TEST(HeapTest,FixedSizeVectorMinHeap)101 TEST(HeapTest, FixedSizeVectorMinHeap) {
102 FixedSizeVector<int, 16> v;
103
104 for (size_t i = 0; i < 5; ++i) {
105 v.push_back(i);
106 chre::push_heap(v, std::greater<int>());
107 }
108
109 for (size_t i = 0; i < 5; ++i) {
110 chre::pop_heap(v, std::greater<int>());
111 EXPECT_EQ(i, v[v.size() - 1]);
112 v.erase(v.size() - 1);
113 }
114 }
115