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 "testing/gtest/include/gtest/gtest.h"
10
11 namespace net {
12
13 namespace {
14
15 typedef PriorityQueue<int>::Priority Priority;
16 const Priority kPriorities[] = { 2, 1, 2, 0, 4, 3, 1, 4, 0 };
17 const Priority kNumPriorities = 5; // max(kPriorities) + 1
18 const size_t kNumElements = arraysize(kPriorities);
19 const int kFirstMinOrder[kNumElements] = { 3, 8, 1, 6, 0, 2, 5, 4, 7 };
20 const int kLastMaxOrderErase[kNumElements] = { 7, 4, 5, 2, 0, 6, 1, 8, 3 };
21 const int kFirstMaxOrder[kNumElements] = { 4, 7, 5, 0, 2, 1, 6, 3, 8 };
22 const int kLastMinOrder[kNumElements] = { 8, 3, 6, 1, 2, 0, 5, 7, 4 };
23
24 class PriorityQueueTest : public testing::Test {
25 protected:
PriorityQueueTest()26 PriorityQueueTest() : queue_(kNumPriorities) {}
27
SetUp()28 virtual void SetUp() OVERRIDE {
29 CheckEmpty();
30 for (size_t i = 0; i < kNumElements; ++i) {
31 EXPECT_EQ(i, queue_.size());
32 pointers_[i] = queue_.Insert(static_cast<int>(i), kPriorities[i]);
33 EXPECT_FALSE(queue_.empty());
34 }
35 EXPECT_EQ(kNumElements, queue_.size());
36 }
37
CheckEmpty()38 void CheckEmpty() {
39 EXPECT_TRUE(queue_.empty());
40 EXPECT_EQ(0u, queue_.size());
41 EXPECT_TRUE(queue_.FirstMin().is_null());
42 EXPECT_TRUE(queue_.LastMin().is_null());
43 EXPECT_TRUE(queue_.FirstMax().is_null());
44 EXPECT_TRUE(queue_.LastMax().is_null());
45 }
46
47 PriorityQueue<int> queue_;
48 PriorityQueue<int>::Pointer pointers_[kNumElements];
49 };
50
TEST_F(PriorityQueueTest,AddAndClear)51 TEST_F(PriorityQueueTest, AddAndClear) {
52 for (size_t i = 0; i < kNumElements; ++i) {
53 EXPECT_EQ(kPriorities[i], pointers_[i].priority());
54 EXPECT_EQ(static_cast<int>(i), pointers_[i].value());
55 }
56 queue_.Clear();
57 CheckEmpty();
58 }
59
TEST_F(PriorityQueueTest,FirstMinOrder)60 TEST_F(PriorityQueueTest, FirstMinOrder) {
61 for (size_t i = 0; i < kNumElements; ++i) {
62 EXPECT_EQ(kNumElements - i, queue_.size());
63 // Also check Equals.
64 EXPECT_TRUE(queue_.FirstMin().Equals(pointers_[kFirstMinOrder[i]]));
65 EXPECT_EQ(kFirstMinOrder[i], queue_.FirstMin().value());
66 queue_.Erase(queue_.FirstMin());
67 }
68 CheckEmpty();
69 }
70
TEST_F(PriorityQueueTest,LastMinOrder)71 TEST_F(PriorityQueueTest, LastMinOrder) {
72 for (size_t i = 0; i < kNumElements; ++i) {
73 EXPECT_EQ(kLastMinOrder[i], queue_.LastMin().value());
74 queue_.Erase(queue_.LastMin());
75 }
76 CheckEmpty();
77 }
78
TEST_F(PriorityQueueTest,FirstMaxOrder)79 TEST_F(PriorityQueueTest, FirstMaxOrder) {
80 PriorityQueue<int>::Pointer p = queue_.FirstMax();
81 size_t i = 0;
82 for (; !p.is_null() && i < kNumElements;
83 p = queue_.GetNextTowardsLastMin(p), ++i) {
84 EXPECT_EQ(kFirstMaxOrder[i], p.value());
85 }
86 EXPECT_TRUE(p.is_null());
87 EXPECT_EQ(kNumElements, i);
88 queue_.Clear();
89 CheckEmpty();
90 }
91
TEST_F(PriorityQueueTest,GetNextTowardsLastMinAndErase)92 TEST_F(PriorityQueueTest, GetNextTowardsLastMinAndErase) {
93 PriorityQueue<int>::Pointer current = queue_.FirstMax();
94 for (size_t i = 0; i < kNumElements; ++i) {
95 EXPECT_FALSE(current.is_null());
96 EXPECT_EQ(kFirstMaxOrder[i], current.value());
97 PriorityQueue<int>::Pointer next = queue_.GetNextTowardsLastMin(current);
98 queue_.Erase(current);
99 current = next;
100 }
101 EXPECT_TRUE(current.is_null());
102 CheckEmpty();
103 }
104
TEST_F(PriorityQueueTest,FirstMaxOrderErase)105 TEST_F(PriorityQueueTest, FirstMaxOrderErase) {
106 for (size_t i = 0; i < kNumElements; ++i) {
107 EXPECT_EQ(kFirstMaxOrder[i], queue_.FirstMax().value());
108 queue_.Erase(queue_.FirstMax());
109 }
110 CheckEmpty();
111 }
112
TEST_F(PriorityQueueTest,LastMaxOrderErase)113 TEST_F(PriorityQueueTest, LastMaxOrderErase) {
114 for (size_t i = 0; i < kNumElements; ++i) {
115 EXPECT_EQ(kLastMaxOrderErase[i], queue_.LastMax().value());
116 queue_.Erase(queue_.LastMax());
117 }
118 CheckEmpty();
119 }
120
TEST_F(PriorityQueueTest,EraseFromMiddle)121 TEST_F(PriorityQueueTest, EraseFromMiddle) {
122 queue_.Erase(pointers_[2]);
123 queue_.Erase(pointers_[3]);
124
125 const int expected_order[] = { 8, 1, 6, 0, 5, 4, 7 };
126
127 for (size_t i = 0; i < arraysize(expected_order); ++i) {
128 EXPECT_EQ(expected_order[i], queue_.FirstMin().value());
129 queue_.Erase(queue_.FirstMin());
130 }
131 CheckEmpty();
132 }
133
TEST_F(PriorityQueueTest,InsertAtFront)134 TEST_F(PriorityQueueTest, InsertAtFront) {
135 queue_.InsertAtFront(9, 2);
136 queue_.InsertAtFront(10, 0);
137 queue_.InsertAtFront(11, 1);
138 queue_.InsertAtFront(12, 1);
139
140 const int expected_order[] = { 10, 3, 8, 12, 11, 1, 6, 9, 0, 2, 5, 4, 7 };
141
142 for (size_t i = 0; i < arraysize(expected_order); ++i) {
143 EXPECT_EQ(expected_order[i], queue_.FirstMin().value());
144 queue_.Erase(queue_.FirstMin());
145 }
146 CheckEmpty();
147 }
148
149 } // namespace
150
151 } // namespace net
152