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 
10 TEST(HeapDeathTest, PushHeapWhenEmpty) {
11   DynamicVector<int> v;
12   std::less<int> comp;
13   EXPECT_DEATH(chre::push_heap(v, comp), "");
14 }
15 
16 TEST(HeapDeathTest, PopHeapWhenEmpty) {
17   DynamicVector<int> v;
18   std::less<int> comp;
19   EXPECT_DEATH(chre::pop_heap(v, comp), "");
20 }
21 
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 
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 
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 
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