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