1 /*
2 * Copyright (C) 2016 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "chre/util/priority_queue.h"
18 #include "gtest/gtest.h"
19
20 using chre::PriorityQueue;
21
22 namespace {
23 class FakeElement {
24 public:
FakeElement()25 FakeElement() {}
FakeElement(int index,int value)26 FakeElement(int index, int value) {
27 mValue = value;
28 mIndex = index;
29 }
30
~FakeElement()31 ~FakeElement() {}
32
setValue(int value)33 void setValue(int value) {
34 mValue = value;
35 }
getValue() const36 int getValue() const {
37 return mValue;
38 }
getIndex() const39 int getIndex() const {
40 return mIndex;
41 }
42
43 private:
44 int mIndex = -1;
45 int mValue = -1;
46 };
47
compareFunction(const FakeElement & left,const FakeElement & right)48 bool compareFunction(const FakeElement &left, const FakeElement &right) {
49 return left.getValue() > right.getValue();
50 }
51
52 class CompareClass {
53 public:
operator ()(const FakeElement & left,const FakeElement & right) const54 bool operator()(const FakeElement &left, const FakeElement &right) const {
55 return left.getValue() > right.getValue();
56 }
57 };
58 } // namespace
59
TEST(PriorityQueueTest,IsEmptyInitially)60 TEST(PriorityQueueTest, IsEmptyInitially) {
61 PriorityQueue<int> q;
62 EXPECT_TRUE(q.empty());
63 EXPECT_EQ(0, q.size());
64 EXPECT_EQ(0, q.capacity());
65 }
66
TEST(PriorityQueueTest,SimplePushPop)67 TEST(PriorityQueueTest, SimplePushPop) {
68 PriorityQueue<int> q;
69
70 EXPECT_TRUE(q.push(0));
71 EXPECT_TRUE(q.push(2));
72 EXPECT_TRUE(q.push(3));
73 EXPECT_TRUE(q.push(1));
74 q.pop();
75 EXPECT_TRUE(q.push(4));
76 }
77
TEST(PriorityQueueTest,TestSize)78 TEST(PriorityQueueTest, TestSize) {
79 PriorityQueue<int> q;
80
81 q.push(1);
82 EXPECT_EQ(1, q.size());
83 q.push(2);
84 EXPECT_EQ(2, q.size());
85 q.pop();
86 EXPECT_EQ(1, q.size());
87 }
88
TEST(PriorityQueueTest,TestEmpty)89 TEST(PriorityQueueTest, TestEmpty) {
90 PriorityQueue<int> q;
91
92 q.push(1);
93 EXPECT_FALSE(q.empty());
94 q.push(2);
95 EXPECT_FALSE(q.empty());
96 q.pop();
97 EXPECT_FALSE(q.empty());
98 q.pop();
99 EXPECT_TRUE(q.empty());
100 }
101
TEST(PriorityQueueTest,TestCapacity)102 TEST(PriorityQueueTest, TestCapacity) {
103 PriorityQueue<int> q;
104
105 q.push(1);
106 EXPECT_EQ(1, q.capacity());
107 q.push(2);
108 EXPECT_EQ(2, q.capacity());
109 q.push(3);
110 EXPECT_EQ(4, q.capacity());
111 }
112
TEST(PriorityQueueTest,PopWhenEmpty)113 TEST(PriorityQueueTest, PopWhenEmpty) {
114 PriorityQueue<int> q;
115 q.pop();
116 EXPECT_EQ(0, q.size());
117 }
118
TEST(PriorityQueueDeathTest,TopWhenEmpty)119 TEST(PriorityQueueDeathTest, TopWhenEmpty) {
120 PriorityQueue<int> q;
121 EXPECT_DEATH(q.top(), "");
122 }
123
TEST(PriorityQueueTest,TestTop)124 TEST(PriorityQueueTest, TestTop) {
125 PriorityQueue<int> q;
126 q.push(1);
127 EXPECT_EQ(1, q.top());
128 q.push(2);
129 q.push(3);
130 EXPECT_EQ(3, q.top());
131 q.pop();
132 EXPECT_EQ(2, q.top());
133 q.pop();
134 EXPECT_EQ(1, q.top());
135 }
136
TEST(PriorityQueueDeathTest,InvalidSubscript)137 TEST(PriorityQueueDeathTest, InvalidSubscript) {
138 PriorityQueue<int> q;
139 EXPECT_DEATH(q[0], "");
140 }
141
TEST(PriorityQueueTest,Subscript)142 TEST(PriorityQueueTest, Subscript) {
143 PriorityQueue<int> q;
144 q.push(1);
145 q.push(2);
146 EXPECT_EQ(2, q[0]);
147 EXPECT_EQ(1, q[1]);
148
149 q.pop();
150 EXPECT_EQ(1, q[0]);
151 }
152
TEST(PriorityQueueDeathTest,RemoveWithInvalidIndex)153 TEST(PriorityQueueDeathTest, RemoveWithInvalidIndex) {
154 PriorityQueue<int> q;
155 EXPECT_DEATH(q.remove(0), "");
156 EXPECT_EQ(0, q.size());
157 }
158
TEST(PriorityQueueTest,RemoveWithIndex)159 TEST(PriorityQueueTest, RemoveWithIndex) {
160 PriorityQueue<int> q;
161 q.push(1);
162 q.push(2);
163 q.remove(0);
164 EXPECT_EQ(1, q.top());
165 EXPECT_EQ(1, q.size());
166
167 q.push(3);
168 q.remove(1);
169 EXPECT_EQ(3, q.top());
170 EXPECT_EQ(1, q.size());
171 }
172
TEST(PriorityQueueTest,CompareGreater)173 TEST(PriorityQueueTest, CompareGreater) {
174 PriorityQueue<int, std::greater<int>> q;
175
176 EXPECT_TRUE(q.push(0));
177 EXPECT_TRUE(q.push(2));
178 EXPECT_TRUE(q.push(3));
179 EXPECT_TRUE(q.push(1));
180
181 for (size_t i = 0; i < 4; i++) {
182 EXPECT_EQ(i, q.top());
183 q.pop();
184 }
185 }
186
TEST(PriorityQueueTest,EmplaceCompareLambda)187 TEST(PriorityQueueTest, EmplaceCompareLambda) {
188 auto cmp = [](const FakeElement &left, const FakeElement &right) {
189 return left.getValue() > right.getValue();
190 };
191 PriorityQueue<FakeElement, decltype(cmp)> q(cmp);
192
193 EXPECT_TRUE(q.emplace(0, 0));
194 EXPECT_TRUE(q.emplace(1, 2));
195 EXPECT_TRUE(q.emplace(2, 1));
196 EXPECT_EQ(3, q.size());
197
198 EXPECT_EQ(0, q.top().getValue());
199 EXPECT_EQ(0, q.top().getIndex());
200
201 q.pop();
202 EXPECT_EQ(1, q.top().getValue());
203 EXPECT_EQ(2, q.top().getIndex());
204
205 q.pop();
206 EXPECT_EQ(2, q.top().getValue());
207 EXPECT_EQ(1, q.top().getIndex());
208 }
209
TEST(PriorityQueueTest,EmplaceCompareFunction)210 TEST(PriorityQueueTest, EmplaceCompareFunction) {
211 PriorityQueue<FakeElement,
212 std::function<bool(const FakeElement &, const FakeElement &)>>
213 q(compareFunction);
214
215 EXPECT_TRUE(q.emplace(0, 0));
216 EXPECT_TRUE(q.emplace(1, 2));
217 EXPECT_TRUE(q.emplace(2, 1));
218 EXPECT_EQ(3, q.size());
219
220 EXPECT_EQ(0, q.top().getValue());
221 EXPECT_EQ(0, q.top().getIndex());
222
223 q.pop();
224 EXPECT_EQ(1, q.top().getValue());
225 EXPECT_EQ(2, q.top().getIndex());
226
227 q.pop();
228 EXPECT_EQ(2, q.top().getValue());
229 EXPECT_EQ(1, q.top().getIndex());
230 }
231
TEST(PriorityQueueTest,EmplaceCompareClass)232 TEST(PriorityQueueTest, EmplaceCompareClass) {
233 PriorityQueue<FakeElement, CompareClass> q;
234
235 EXPECT_TRUE(q.emplace(0, 0));
236 EXPECT_TRUE(q.emplace(1, 2));
237 EXPECT_TRUE(q.emplace(2, 1));
238 EXPECT_EQ(3, q.size());
239
240 EXPECT_EQ(0, q.top().getValue());
241 EXPECT_EQ(0, q.top().getIndex());
242
243 q.pop();
244 EXPECT_EQ(1, q.top().getValue());
245 EXPECT_EQ(2, q.top().getIndex());
246
247 q.pop();
248 EXPECT_EQ(2, q.top().getValue());
249 EXPECT_EQ(1, q.top().getIndex());
250 }
251
TEST(PriorityQueuetest,Iterator)252 TEST(PriorityQueuetest, Iterator) {
253 PriorityQueue<int> q;
254 q.push(0);
255 q.push(1);
256 q.push(2);
257
258 PriorityQueue<int>::iterator it = q.begin();
259 EXPECT_EQ(q[0], *it);
260
261 it += q.size();
262 EXPECT_TRUE(it == q.end());
263 }
264
TEST(PriorityQueuetest,ConstIterator)265 TEST(PriorityQueuetest, ConstIterator) {
266 PriorityQueue<int> q;
267 q.push(0);
268 q.push(1);
269 q.push(2);
270
271 PriorityQueue<int>::const_iterator cit = q.cbegin();
272 EXPECT_EQ(q[0], *cit);
273
274 cit += q.size();
275 EXPECT_TRUE(cit == q.cend());
276 }
277