1 #include "gtest/gtest.h"
2 #include "chre/util/priority_queue.h"
3 
4 using chre::PriorityQueue;
5 
6 namespace {
7 class DummyElement {
8  public:
DummyElement()9   DummyElement() {};
DummyElement(int index,int value)10   DummyElement(int index, int value) {
11     mValue = value;
12     mIndex = index;
13   };
~DummyElement()14   ~DummyElement() {};
setValue(int value)15   void setValue(int value) {
16     mValue = value;
17   }
getValue() const18   int getValue() const {
19     return mValue;
20   }
getIndex() const21   int getIndex() const {
22     return mIndex;
23   }
24 
25  private:
26   int mIndex = -1;
27   int mValue = -1;
28 };
29 
compareFunction(const DummyElement & left,const DummyElement & right)30 bool compareFunction(const DummyElement& left, const DummyElement& right) {
31   return left.getValue() > right.getValue();
32 };
33 
34 class CompareClass {
35  public:
operator ()(const DummyElement & left,const DummyElement & right) const36   bool operator() (const DummyElement& left, const DummyElement& right) const {
37     return left.getValue() > right.getValue();
38   }
39 };
40 }  // namespace
41 
TEST(PriorityQueueTest,IsEmptyInitially)42 TEST(PriorityQueueTest, IsEmptyInitially) {
43   PriorityQueue<int> q;
44   EXPECT_TRUE(q.empty());
45   EXPECT_EQ(0, q.size());
46   EXPECT_EQ(0, q.capacity());
47 }
48 
TEST(PriorityQueueTest,SimplePushPop)49 TEST(PriorityQueueTest, SimplePushPop) {
50   PriorityQueue<int> q;
51 
52   EXPECT_TRUE(q.push(0));
53   EXPECT_TRUE(q.push(2));
54   EXPECT_TRUE(q.push(3));
55   EXPECT_TRUE(q.push(1));
56   q.pop();
57   EXPECT_TRUE(q.push(4));
58 }
59 
TEST(PriorityQueueTest,TestSize)60 TEST(PriorityQueueTest, TestSize) {
61   PriorityQueue<int> q;
62 
63   q.push(1);
64   EXPECT_EQ(1, q.size());
65   q.push(2);
66   EXPECT_EQ(2, q.size());
67   q.pop();
68   EXPECT_EQ(1, q.size());
69 }
70 
TEST(PriorityQueueTest,TestEmpty)71 TEST(PriorityQueueTest, TestEmpty) {
72   PriorityQueue<int> q;
73 
74   q.push(1);
75   EXPECT_FALSE(q.empty());
76   q.push(2);
77   EXPECT_FALSE(q.empty());
78   q.pop();
79   EXPECT_FALSE(q.empty());
80   q.pop();
81   EXPECT_TRUE(q.empty());
82 }
83 
TEST(PriorityQueueTest,TestCapacity)84 TEST(PriorityQueueTest, TestCapacity) {
85   PriorityQueue<int> q;
86 
87   q.push(1);
88   EXPECT_EQ(1, q.capacity());
89   q.push(2);
90   EXPECT_EQ(2, q.capacity());
91   q.push(3);
92   EXPECT_EQ(4, q.capacity());
93 }
94 
TEST(PriorityQueueTest,PopWhenEmpty)95 TEST(PriorityQueueTest, PopWhenEmpty) {
96   PriorityQueue<int> q;
97   q.pop();
98   EXPECT_EQ(0, q.size());
99 }
100 
TEST(PriorityQueueDeathTest,TopWhenEmpty)101 TEST(PriorityQueueDeathTest, TopWhenEmpty) {
102   PriorityQueue<int> q;
103   EXPECT_DEATH(q.top(), "");
104 }
105 
TEST(PriorityQueueTest,TestTop)106 TEST(PriorityQueueTest, TestTop) {
107   PriorityQueue<int> q;
108   q.push(1);
109   EXPECT_EQ(1, q.top());
110   q.push(2);
111   q.push(3);
112   EXPECT_EQ(3, q.top());
113   q.pop();
114   EXPECT_EQ(2, q.top());
115   q.pop();
116   EXPECT_EQ(1, q.top());
117 }
118 
TEST(PriorityQueueDeathTest,InvalidSubscript)119 TEST(PriorityQueueDeathTest, InvalidSubscript) {
120   PriorityQueue<int> q;
121   EXPECT_DEATH(q[0], "");
122 }
123 
TEST(PriorityQueueTest,Subscript)124 TEST(PriorityQueueTest, Subscript) {
125   PriorityQueue<int> q;
126   q.push(1);
127   q.push(2);
128   EXPECT_EQ(2, q[0]);
129   EXPECT_EQ(1, q[1]);
130 
131   q.pop();
132   EXPECT_EQ(1, q[0]);
133 }
134 
TEST(PriorityQueueDeathTest,RemoveWithInvalidIndex)135 TEST(PriorityQueueDeathTest, RemoveWithInvalidIndex) {
136   PriorityQueue<int> q;
137   EXPECT_DEATH(q.remove(0), "");
138   EXPECT_EQ(0, q.size());
139 }
140 
TEST(PriorityQueueTest,RemoveWithIndex)141 TEST(PriorityQueueTest, RemoveWithIndex) {
142   PriorityQueue<int> q;
143   q.push(1);
144   q.push(2);
145   q.remove(0);
146   EXPECT_EQ(1, q.top());
147   EXPECT_EQ(1, q.size());
148 
149   q.push(3);
150   q.remove(1);
151   EXPECT_EQ(3, q.top());
152   EXPECT_EQ(1, q.size());
153 }
154 
TEST(PriorityQueueTest,CompareGreater)155 TEST(PriorityQueueTest, CompareGreater) {
156   PriorityQueue<int, std::greater<int>> q;
157 
158   EXPECT_TRUE(q.push(0));
159   EXPECT_TRUE(q.push(2));
160   EXPECT_TRUE(q.push(3));
161   EXPECT_TRUE(q.push(1));
162 
163   for (size_t i = 0; i < 4; i++) {
164     EXPECT_EQ(i, q.top());
165     q.pop();
166   }
167 }
168 
TEST(PriorityQueueTest,EmplaceCompareLambda)169 TEST(PriorityQueueTest, EmplaceCompareLambda) {
170   auto cmp = [](const DummyElement& left, const DummyElement& right) {
171     return left.getValue() > right.getValue();
172   };
173   PriorityQueue<DummyElement, decltype(cmp)> q(cmp);
174 
175   EXPECT_TRUE(q.emplace(0, 0));
176   EXPECT_TRUE(q.emplace(1, 2));
177   EXPECT_TRUE(q.emplace(2, 1));
178   EXPECT_EQ(3, q.size());
179 
180   EXPECT_EQ(0, q.top().getValue());
181   EXPECT_EQ(0, q.top().getIndex());
182 
183   q.pop();
184   EXPECT_EQ(1, q.top().getValue());
185   EXPECT_EQ(2, q.top().getIndex());
186 
187   q.pop();
188   EXPECT_EQ(2, q.top().getValue());
189   EXPECT_EQ(1, q.top().getIndex());
190 }
191 
TEST(PriorityQueueTest,EmplaceCompareFunction)192 TEST(PriorityQueueTest, EmplaceCompareFunction) {
193   PriorityQueue<DummyElement,
194                 std::function<bool(const DummyElement&, const DummyElement&)>>
195       q(compareFunction);
196 
197   EXPECT_TRUE(q.emplace(0, 0));
198   EXPECT_TRUE(q.emplace(1, 2));
199   EXPECT_TRUE(q.emplace(2, 1));
200   EXPECT_EQ(3, q.size());
201 
202   EXPECT_EQ(0, q.top().getValue());
203   EXPECT_EQ(0, q.top().getIndex());
204 
205   q.pop();
206   EXPECT_EQ(1, q.top().getValue());
207   EXPECT_EQ(2, q.top().getIndex());
208 
209   q.pop();
210   EXPECT_EQ(2, q.top().getValue());
211   EXPECT_EQ(1, q.top().getIndex());
212 }
213 
TEST(PriorityQueueTest,EmplaceCompareClass)214 TEST(PriorityQueueTest, EmplaceCompareClass) {
215   PriorityQueue<DummyElement, CompareClass> q;
216 
217   EXPECT_TRUE(q.emplace(0, 0));
218   EXPECT_TRUE(q.emplace(1, 2));
219   EXPECT_TRUE(q.emplace(2, 1));
220   EXPECT_EQ(3, q.size());
221 
222   EXPECT_EQ(0, q.top().getValue());
223   EXPECT_EQ(0, q.top().getIndex());
224 
225   q.pop();
226   EXPECT_EQ(1, q.top().getValue());
227   EXPECT_EQ(2, q.top().getIndex());
228 
229   q.pop();
230   EXPECT_EQ(2, q.top().getValue());
231   EXPECT_EQ(1, q.top().getIndex());
232 }
233 
TEST(PriorityQueuetest,Iterator)234 TEST(PriorityQueuetest, Iterator) {
235   PriorityQueue<int> q;
236   q.push(0);
237   q.push(1);
238   q.push(2);
239 
240   PriorityQueue<int>::iterator it = q.begin();
241   EXPECT_EQ(q[0], *it);
242 
243   it += q.size();
244   EXPECT_TRUE(it == q.end());
245 }
246 
TEST(PriorityQueuetest,ConstIterator)247 TEST(PriorityQueuetest, ConstIterator) {
248   PriorityQueue<int> q;
249   q.push(0);
250   q.push(1);
251   q.push(2);
252 
253   PriorityQueue<int>::const_iterator cit = q.cbegin();
254   EXPECT_EQ(q[0], *cit);
255 
256   cit += q.size();
257   EXPECT_TRUE(cit == q.cend());
258 }
259