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: 9 DummyElement() {}; 10 DummyElement(int index, int value) { 11 mValue = value; 12 mIndex = index; 13 }; 14 ~DummyElement() {}; 15 void setValue(int value) { 16 mValue = value; 17 } 18 int getValue() const { 19 return mValue; 20 } 21 int getIndex() const { 22 return mIndex; 23 } 24 25 private: 26 int mIndex = -1; 27 int mValue = -1; 28 }; 29 30 bool compareFunction(const DummyElement& left, const DummyElement& right) { 31 return left.getValue() > right.getValue(); 32 }; 33 34 class CompareClass { 35 public: 36 bool operator() (const DummyElement& left, const DummyElement& right) const { 37 return left.getValue() > right.getValue(); 38 } 39 }; 40 } // namespace 41 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 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 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 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 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 95 TEST(PriorityQueueTest, PopWhenEmpty) { 96 PriorityQueue<int> q; 97 q.pop(); 98 EXPECT_EQ(0, q.size()); 99 } 100 101 TEST(PriorityQueueDeathTest, TopWhenEmpty) { 102 PriorityQueue<int> q; 103 EXPECT_DEATH(q.top(), ""); 104 } 105 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 119 TEST(PriorityQueueDeathTest, InvalidSubscript) { 120 PriorityQueue<int> q; 121 EXPECT_DEATH(q[0], ""); 122 } 123 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 135 TEST(PriorityQueueDeathTest, RemoveWithInvalidIndex) { 136 PriorityQueue<int> q; 137 EXPECT_DEATH(q.remove(0), ""); 138 EXPECT_EQ(0, q.size()); 139 } 140 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 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 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 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 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 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 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
