1 // Copyright (c) 2012 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "net/base/priority_queue.h"
6
7 #include <cstddef>
8
9 #include "base/bind.h"
10 #include "base/stl_util.h"
11 #include "testing/gtest/include/gtest/gtest.h"
12
13 namespace net {
14
15 namespace {
16
17 typedef PriorityQueue<int>::Priority Priority;
18 // Queue 0 has empty lists for first and last priorities.
19 // Queue 1 has multiple empty lists in a row, and occupied first and last
20 // priorities.
21 // Queue 2 has multiple empty lists in a row at the first and last priorities.
22 // Queue 0 Queue 1 Queue 2
23 // Priority 0: {} {3, 7} {}
24 // Priority 1: {2, 3, 7} {2} {}
25 // Priority 2: {1, 5} {1, 5} {1, 2, 3, 5, 7}
26 // Priority 3: {0} {} {0, 4, 6}
27 // Priority 4: {} {} {}
28 // Priority 5: {4, 6} {6} {}
29 // Priority 6: {} {0, 4} {}
30 constexpr Priority kNumPriorities = 7;
31 constexpr size_t kNumElements = 8;
32 constexpr size_t kNumQueues = 3;
33 constexpr Priority kPriorities[kNumQueues][kNumElements] = {
34 {3, 2, 1, 1, 5, 2, 5, 1},
35 {6, 2, 1, 0, 6, 2, 5, 0},
36 {3, 2, 2, 2, 3, 2, 3, 2}};
37 constexpr int kFirstMinOrder[kNumQueues][kNumElements] = {
38 {2, 3, 7, 1, 5, 0, 4, 6},
39 {3, 7, 2, 1, 5, 6, 0, 4},
40 {1, 2, 3, 5, 7, 0, 4, 6}};
41 constexpr int kLastMaxOrderErase[kNumQueues][kNumElements] = {
42 {6, 4, 0, 5, 1, 7, 3, 2},
43 {4, 0, 6, 5, 1, 2, 7, 3},
44 {6, 4, 0, 7, 5, 3, 2, 1}};
45 constexpr int kFirstMaxOrder[kNumQueues][kNumElements] = {
46 {4, 6, 0, 1, 5, 2, 3, 7},
47 {0, 4, 6, 1, 5, 2, 3, 7},
48 {0, 4, 6, 1, 2, 3, 5, 7}};
49 constexpr int kLastMinOrder[kNumQueues][kNumElements] = {
50 {7, 3, 2, 5, 1, 0, 6, 4},
51 {7, 3, 2, 5, 1, 6, 4, 0},
52 {7, 5, 3, 2, 1, 6, 4, 0}};
53
54 class PriorityQueueTest : public testing::TestWithParam<size_t> {
55 public:
PriorityQueueTest()56 PriorityQueueTest() : queue_(kNumPriorities) {}
57
SetUp()58 void SetUp() override {
59 CheckEmpty();
60 for (size_t i = 0; i < kNumElements; ++i) {
61 EXPECT_EQ(i, queue_.size());
62 pointers_[i] =
63 queue_.Insert(static_cast<int>(i), kPriorities[GetParam()][i]);
64 EXPECT_FALSE(queue_.empty());
65 }
66 EXPECT_EQ(kNumElements, queue_.size());
67 }
68
CheckEmpty()69 void CheckEmpty() {
70 EXPECT_TRUE(queue_.empty());
71 EXPECT_EQ(0u, queue_.size());
72 EXPECT_TRUE(queue_.FirstMin().is_null());
73 EXPECT_TRUE(queue_.LastMin().is_null());
74 EXPECT_TRUE(queue_.FirstMax().is_null());
75 EXPECT_TRUE(queue_.LastMax().is_null());
76 }
77
78 protected:
79 PriorityQueue<int> queue_;
80 PriorityQueue<int>::Pointer pointers_[kNumElements];
81 };
82
TEST_P(PriorityQueueTest,AddAndClear)83 TEST_P(PriorityQueueTest, AddAndClear) {
84 for (size_t i = 0; i < kNumElements; ++i) {
85 EXPECT_EQ(kPriorities[GetParam()][i], pointers_[i].priority());
86 EXPECT_EQ(static_cast<int>(i), pointers_[i].value());
87 }
88 queue_.Clear();
89 CheckEmpty();
90 }
91
TEST_P(PriorityQueueTest,PointerComparison)92 TEST_P(PriorityQueueTest, PointerComparison) {
93 for (PriorityQueue<int>::Pointer p = queue_.FirstMax();
94 !p.Equals(queue_.LastMin()); p = queue_.GetNextTowardsLastMin(p)) {
95 for (PriorityQueue<int>::Pointer q = queue_.GetNextTowardsLastMin(p);
96 !q.is_null(); q = queue_.GetNextTowardsLastMin(q)) {
97 EXPECT_TRUE(queue_.IsCloserToFirstMaxThan(p, q));
98 EXPECT_FALSE(queue_.IsCloserToFirstMaxThan(q, p));
99 EXPECT_FALSE(queue_.IsCloserToLastMinThan(p, q));
100 EXPECT_TRUE(queue_.IsCloserToLastMinThan(q, p));
101 EXPECT_FALSE(p.Equals(q));
102 }
103 }
104
105 for (PriorityQueue<int>::Pointer p = queue_.LastMin();
106 !p.Equals(queue_.FirstMax()); p = queue_.GetPreviousTowardsFirstMax(p)) {
107 for (PriorityQueue<int>::Pointer q = queue_.GetPreviousTowardsFirstMax(p);
108 !q.is_null(); q = queue_.GetPreviousTowardsFirstMax(q)) {
109 EXPECT_FALSE(queue_.IsCloserToFirstMaxThan(p, q));
110 EXPECT_TRUE(queue_.IsCloserToFirstMaxThan(q, p));
111 EXPECT_TRUE(queue_.IsCloserToLastMinThan(p, q));
112 EXPECT_FALSE(queue_.IsCloserToLastMinThan(q, p));
113 EXPECT_FALSE(p.Equals(q));
114 }
115 }
116 }
117
TEST_P(PriorityQueueTest,FirstMinOrder)118 TEST_P(PriorityQueueTest, FirstMinOrder) {
119 for (size_t i = 0; i < kNumElements; ++i) {
120 EXPECT_EQ(kNumElements - i, queue_.size());
121 // Also check Equals.
122 EXPECT_TRUE(
123 queue_.FirstMin().Equals(pointers_[kFirstMinOrder[GetParam()][i]]));
124 EXPECT_EQ(kFirstMinOrder[GetParam()][i], queue_.FirstMin().value());
125 queue_.Erase(queue_.FirstMin());
126 }
127 CheckEmpty();
128 }
129
TEST_P(PriorityQueueTest,LastMinOrder)130 TEST_P(PriorityQueueTest, LastMinOrder) {
131 for (size_t i = 0; i < kNumElements; ++i) {
132 EXPECT_EQ(kLastMinOrder[GetParam()][i], queue_.LastMin().value());
133 queue_.Erase(queue_.LastMin());
134 }
135 CheckEmpty();
136 }
137
TEST_P(PriorityQueueTest,FirstMaxOrder)138 TEST_P(PriorityQueueTest, FirstMaxOrder) {
139 PriorityQueue<int>::Pointer p = queue_.FirstMax();
140 size_t i = 0;
141 for (; !p.is_null() && i < kNumElements;
142 p = queue_.GetNextTowardsLastMin(p), ++i) {
143 EXPECT_EQ(kFirstMaxOrder[GetParam()][i], p.value());
144 }
145 EXPECT_TRUE(p.is_null());
146 EXPECT_EQ(kNumElements, i);
147 queue_.Clear();
148 CheckEmpty();
149 }
150
TEST_P(PriorityQueueTest,GetNextTowardsLastMinAndErase)151 TEST_P(PriorityQueueTest, GetNextTowardsLastMinAndErase) {
152 PriorityQueue<int>::Pointer current = queue_.FirstMax();
153 for (size_t i = 0; i < kNumElements; ++i) {
154 EXPECT_FALSE(current.is_null());
155 EXPECT_EQ(kFirstMaxOrder[GetParam()][i], current.value());
156 PriorityQueue<int>::Pointer next = queue_.GetNextTowardsLastMin(current);
157 queue_.Erase(current);
158 current = next;
159 }
160 EXPECT_TRUE(current.is_null());
161 CheckEmpty();
162 }
163
TEST_P(PriorityQueueTest,GetPreviousTowardsFirstMaxAndErase)164 TEST_P(PriorityQueueTest, GetPreviousTowardsFirstMaxAndErase) {
165 PriorityQueue<int>::Pointer current = queue_.LastMin();
166 for (size_t i = 0; i < kNumElements; ++i) {
167 EXPECT_FALSE(current.is_null());
168 EXPECT_EQ(kLastMinOrder[GetParam()][i], current.value());
169 PriorityQueue<int>::Pointer next =
170 queue_.GetPreviousTowardsFirstMax(current);
171 queue_.Erase(current);
172 current = next;
173 }
174 EXPECT_TRUE(current.is_null());
175 CheckEmpty();
176 }
177
TEST_P(PriorityQueueTest,FirstMaxOrderErase)178 TEST_P(PriorityQueueTest, FirstMaxOrderErase) {
179 for (size_t i = 0; i < kNumElements; ++i) {
180 EXPECT_EQ(kFirstMaxOrder[GetParam()][i], queue_.FirstMax().value());
181 queue_.Erase(queue_.FirstMax());
182 }
183 CheckEmpty();
184 }
185
TEST_P(PriorityQueueTest,LastMaxOrderErase)186 TEST_P(PriorityQueueTest, LastMaxOrderErase) {
187 for (size_t i = 0; i < kNumElements; ++i) {
188 EXPECT_EQ(kLastMaxOrderErase[GetParam()][i], queue_.LastMax().value());
189 queue_.Erase(queue_.LastMax());
190 }
191 CheckEmpty();
192 }
193
TEST_P(PriorityQueueTest,EraseFromMiddle)194 TEST_P(PriorityQueueTest, EraseFromMiddle) {
195 queue_.Erase(pointers_[2]);
196 queue_.Erase(pointers_[0]);
197
198 const int expected_order[kNumQueues][kNumElements - 2] = {
199 {3, 7, 1, 5, 4, 6}, {3, 7, 1, 5, 6, 4}, {1, 3, 5, 7, 4, 6}};
200
201 for (const auto& value : expected_order[GetParam()]) {
202 EXPECT_EQ(value, queue_.FirstMin().value());
203 queue_.Erase(queue_.FirstMin());
204 }
205 CheckEmpty();
206 }
207
TEST_P(PriorityQueueTest,InsertAtFront)208 TEST_P(PriorityQueueTest, InsertAtFront) {
209 queue_.InsertAtFront(8, 6);
210 queue_.InsertAtFront(9, 2);
211 queue_.InsertAtFront(10, 0);
212 queue_.InsertAtFront(11, 1);
213 queue_.InsertAtFront(12, 1);
214
215 const int expected_order[kNumQueues][kNumElements + 5] = {
216 {10, 12, 11, 2, 3, 7, 9, 1, 5, 0, 4, 6, 8},
217 {10, 3, 7, 12, 11, 2, 9, 1, 5, 6, 8, 0, 4},
218 {10, 12, 11, 9, 1, 2, 3, 5, 7, 0, 4, 6, 8}};
219
220 for (const auto& value : expected_order[GetParam()]) {
221 EXPECT_EQ(value, queue_.FirstMin().value());
222 queue_.Erase(queue_.FirstMin());
223 }
224 CheckEmpty();
225 }
226
TEST_P(PriorityQueueTest,FindIf)227 TEST_P(PriorityQueueTest, FindIf) {
228 auto pred = [](size_t i, int value) -> bool {
229 return value == static_cast<int>(i);
230 };
231 for (size_t i = 0; i < kNumElements; ++i) {
232 PriorityQueue<int>::Pointer pointer =
233 queue_.FindIf(base::BindRepeating(pred, i));
234 EXPECT_FALSE(pointer.is_null());
235 EXPECT_EQ(static_cast<int>(i), pointer.value());
236 queue_.Erase(pointer);
237 pointer = queue_.FindIf(base::BindRepeating(pred, i));
238 EXPECT_TRUE(pointer.is_null());
239 }
240 }
241
242 INSTANTIATE_TEST_SUITE_P(PriorityQueues,
243 PriorityQueueTest,
244 testing::Range(static_cast<size_t>(0), kNumQueues));
245
246 } // namespace
247
248 } // namespace net
249