123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247 |
- // Copyright (c) 2012 The Chromium Authors. All rights reserved.
- // Use of this source code is governed by a BSD-style license that can be
- // found in the LICENSE file.
- #include "net/base/priority_queue.h"
- #include <cstddef>
- #include "base/bind.h"
- #include "testing/gtest/include/gtest/gtest.h"
- namespace net {
- namespace {
- typedef PriorityQueue<int>::Priority Priority;
- // Queue 0 has empty lists for first and last priorities.
- // Queue 1 has multiple empty lists in a row, and occupied first and last
- // priorities.
- // Queue 2 has multiple empty lists in a row at the first and last priorities.
- // Queue 0 Queue 1 Queue 2
- // Priority 0: {} {3, 7} {}
- // Priority 1: {2, 3, 7} {2} {}
- // Priority 2: {1, 5} {1, 5} {1, 2, 3, 5, 7}
- // Priority 3: {0} {} {0, 4, 6}
- // Priority 4: {} {} {}
- // Priority 5: {4, 6} {6} {}
- // Priority 6: {} {0, 4} {}
- constexpr Priority kNumPriorities = 7;
- constexpr size_t kNumElements = 8;
- constexpr size_t kNumQueues = 3;
- constexpr Priority kPriorities[kNumQueues][kNumElements] = {
- {3, 2, 1, 1, 5, 2, 5, 1},
- {6, 2, 1, 0, 6, 2, 5, 0},
- {3, 2, 2, 2, 3, 2, 3, 2}};
- constexpr int kFirstMinOrder[kNumQueues][kNumElements] = {
- {2, 3, 7, 1, 5, 0, 4, 6},
- {3, 7, 2, 1, 5, 6, 0, 4},
- {1, 2, 3, 5, 7, 0, 4, 6}};
- constexpr int kLastMaxOrderErase[kNumQueues][kNumElements] = {
- {6, 4, 0, 5, 1, 7, 3, 2},
- {4, 0, 6, 5, 1, 2, 7, 3},
- {6, 4, 0, 7, 5, 3, 2, 1}};
- constexpr int kFirstMaxOrder[kNumQueues][kNumElements] = {
- {4, 6, 0, 1, 5, 2, 3, 7},
- {0, 4, 6, 1, 5, 2, 3, 7},
- {0, 4, 6, 1, 2, 3, 5, 7}};
- constexpr int kLastMinOrder[kNumQueues][kNumElements] = {
- {7, 3, 2, 5, 1, 0, 6, 4},
- {7, 3, 2, 5, 1, 6, 4, 0},
- {7, 5, 3, 2, 1, 6, 4, 0}};
- class PriorityQueueTest : public testing::TestWithParam<size_t> {
- public:
- PriorityQueueTest() : queue_(kNumPriorities) {}
- void SetUp() override {
- CheckEmpty();
- for (size_t i = 0; i < kNumElements; ++i) {
- EXPECT_EQ(i, queue_.size());
- pointers_[i] =
- queue_.Insert(static_cast<int>(i), kPriorities[GetParam()][i]);
- EXPECT_FALSE(queue_.empty());
- }
- EXPECT_EQ(kNumElements, queue_.size());
- }
- void CheckEmpty() {
- EXPECT_TRUE(queue_.empty());
- EXPECT_EQ(0u, queue_.size());
- EXPECT_TRUE(queue_.FirstMin().is_null());
- EXPECT_TRUE(queue_.LastMin().is_null());
- EXPECT_TRUE(queue_.FirstMax().is_null());
- EXPECT_TRUE(queue_.LastMax().is_null());
- }
- protected:
- PriorityQueue<int> queue_;
- PriorityQueue<int>::Pointer pointers_[kNumElements];
- };
- TEST_P(PriorityQueueTest, AddAndClear) {
- for (size_t i = 0; i < kNumElements; ++i) {
- EXPECT_EQ(kPriorities[GetParam()][i], pointers_[i].priority());
- EXPECT_EQ(static_cast<int>(i), pointers_[i].value());
- }
- queue_.Clear();
- CheckEmpty();
- }
- TEST_P(PriorityQueueTest, PointerComparison) {
- for (PriorityQueue<int>::Pointer p = queue_.FirstMax();
- !p.Equals(queue_.LastMin()); p = queue_.GetNextTowardsLastMin(p)) {
- for (PriorityQueue<int>::Pointer q = queue_.GetNextTowardsLastMin(p);
- !q.is_null(); q = queue_.GetNextTowardsLastMin(q)) {
- EXPECT_TRUE(queue_.IsCloserToFirstMaxThan(p, q));
- EXPECT_FALSE(queue_.IsCloserToFirstMaxThan(q, p));
- EXPECT_FALSE(queue_.IsCloserToLastMinThan(p, q));
- EXPECT_TRUE(queue_.IsCloserToLastMinThan(q, p));
- EXPECT_FALSE(p.Equals(q));
- }
- }
- for (PriorityQueue<int>::Pointer p = queue_.LastMin();
- !p.Equals(queue_.FirstMax()); p = queue_.GetPreviousTowardsFirstMax(p)) {
- for (PriorityQueue<int>::Pointer q = queue_.GetPreviousTowardsFirstMax(p);
- !q.is_null(); q = queue_.GetPreviousTowardsFirstMax(q)) {
- EXPECT_FALSE(queue_.IsCloserToFirstMaxThan(p, q));
- EXPECT_TRUE(queue_.IsCloserToFirstMaxThan(q, p));
- EXPECT_TRUE(queue_.IsCloserToLastMinThan(p, q));
- EXPECT_FALSE(queue_.IsCloserToLastMinThan(q, p));
- EXPECT_FALSE(p.Equals(q));
- }
- }
- }
- TEST_P(PriorityQueueTest, FirstMinOrder) {
- for (size_t i = 0; i < kNumElements; ++i) {
- EXPECT_EQ(kNumElements - i, queue_.size());
- // Also check Equals.
- EXPECT_TRUE(
- queue_.FirstMin().Equals(pointers_[kFirstMinOrder[GetParam()][i]]));
- EXPECT_EQ(kFirstMinOrder[GetParam()][i], queue_.FirstMin().value());
- queue_.Erase(queue_.FirstMin());
- }
- CheckEmpty();
- }
- TEST_P(PriorityQueueTest, LastMinOrder) {
- for (size_t i = 0; i < kNumElements; ++i) {
- EXPECT_EQ(kLastMinOrder[GetParam()][i], queue_.LastMin().value());
- queue_.Erase(queue_.LastMin());
- }
- CheckEmpty();
- }
- TEST_P(PriorityQueueTest, FirstMaxOrder) {
- PriorityQueue<int>::Pointer p = queue_.FirstMax();
- size_t i = 0;
- for (; !p.is_null() && i < kNumElements;
- p = queue_.GetNextTowardsLastMin(p), ++i) {
- EXPECT_EQ(kFirstMaxOrder[GetParam()][i], p.value());
- }
- EXPECT_TRUE(p.is_null());
- EXPECT_EQ(kNumElements, i);
- queue_.Clear();
- CheckEmpty();
- }
- TEST_P(PriorityQueueTest, GetNextTowardsLastMinAndErase) {
- PriorityQueue<int>::Pointer current = queue_.FirstMax();
- for (size_t i = 0; i < kNumElements; ++i) {
- EXPECT_FALSE(current.is_null());
- EXPECT_EQ(kFirstMaxOrder[GetParam()][i], current.value());
- PriorityQueue<int>::Pointer next = queue_.GetNextTowardsLastMin(current);
- queue_.Erase(current);
- current = next;
- }
- EXPECT_TRUE(current.is_null());
- CheckEmpty();
- }
- TEST_P(PriorityQueueTest, GetPreviousTowardsFirstMaxAndErase) {
- PriorityQueue<int>::Pointer current = queue_.LastMin();
- for (size_t i = 0; i < kNumElements; ++i) {
- EXPECT_FALSE(current.is_null());
- EXPECT_EQ(kLastMinOrder[GetParam()][i], current.value());
- PriorityQueue<int>::Pointer next =
- queue_.GetPreviousTowardsFirstMax(current);
- queue_.Erase(current);
- current = next;
- }
- EXPECT_TRUE(current.is_null());
- CheckEmpty();
- }
- TEST_P(PriorityQueueTest, FirstMaxOrderErase) {
- for (size_t i = 0; i < kNumElements; ++i) {
- EXPECT_EQ(kFirstMaxOrder[GetParam()][i], queue_.FirstMax().value());
- queue_.Erase(queue_.FirstMax());
- }
- CheckEmpty();
- }
- TEST_P(PriorityQueueTest, LastMaxOrderErase) {
- for (size_t i = 0; i < kNumElements; ++i) {
- EXPECT_EQ(kLastMaxOrderErase[GetParam()][i], queue_.LastMax().value());
- queue_.Erase(queue_.LastMax());
- }
- CheckEmpty();
- }
- TEST_P(PriorityQueueTest, EraseFromMiddle) {
- queue_.Erase(pointers_[2]);
- queue_.Erase(pointers_[0]);
- const int expected_order[kNumQueues][kNumElements - 2] = {
- {3, 7, 1, 5, 4, 6}, {3, 7, 1, 5, 6, 4}, {1, 3, 5, 7, 4, 6}};
- for (const auto& value : expected_order[GetParam()]) {
- EXPECT_EQ(value, queue_.FirstMin().value());
- queue_.Erase(queue_.FirstMin());
- }
- CheckEmpty();
- }
- TEST_P(PriorityQueueTest, InsertAtFront) {
- queue_.InsertAtFront(8, 6);
- queue_.InsertAtFront(9, 2);
- queue_.InsertAtFront(10, 0);
- queue_.InsertAtFront(11, 1);
- queue_.InsertAtFront(12, 1);
- const int expected_order[kNumQueues][kNumElements + 5] = {
- {10, 12, 11, 2, 3, 7, 9, 1, 5, 0, 4, 6, 8},
- {10, 3, 7, 12, 11, 2, 9, 1, 5, 6, 8, 0, 4},
- {10, 12, 11, 9, 1, 2, 3, 5, 7, 0, 4, 6, 8}};
- for (const auto& value : expected_order[GetParam()]) {
- EXPECT_EQ(value, queue_.FirstMin().value());
- queue_.Erase(queue_.FirstMin());
- }
- CheckEmpty();
- }
- TEST_P(PriorityQueueTest, FindIf) {
- auto pred = [](size_t i, int value) -> bool {
- return value == static_cast<int>(i);
- };
- for (size_t i = 0; i < kNumElements; ++i) {
- PriorityQueue<int>::Pointer pointer =
- queue_.FindIf(base::BindRepeating(pred, i));
- EXPECT_FALSE(pointer.is_null());
- EXPECT_EQ(static_cast<int>(i), pointer.value());
- queue_.Erase(pointer);
- pointer = queue_.FindIf(base::BindRepeating(pred, i));
- EXPECT_TRUE(pointer.is_null());
- }
- }
- INSTANTIATE_TEST_SUITE_P(PriorityQueues,
- PriorityQueueTest,
- testing::Range(static_cast<size_t>(0), kNumQueues));
- } // namespace
- } // namespace net
|