priority_queue_unittest.cc 7.8 KB

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