248 lines
7.8 KiB
C++
248 lines
7.8 KiB
C++
// Copyright 2012 The Chromium Authors
|
|
// 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/functional/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
|