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
11namespace net {
12
13namespace {
14
15typedef PriorityQueue<int>::Priority Priority;
16const Priority kPriorities[] = { 2, 1, 2, 0, 4, 3, 1, 4, 0 };
17const Priority kNumPriorities = 5;  // max(kPriorities) + 1
18const size_t kNumElements = arraysize(kPriorities);
19const int kFirstMinOrder[kNumElements] = { 3, 8, 1, 6, 0, 2, 5, 4, 7 };
20const int kLastMaxOrderErase[kNumElements] = { 7, 4, 5, 2, 0, 6, 1, 8, 3 };
21const int kFirstMaxOrder[kNumElements] = { 4, 7, 5, 0, 2, 1, 6, 3, 8 };
22const int kLastMinOrder[kNumElements] = { 8, 3, 6, 1, 2, 0, 5, 7, 4 };
23
24class PriorityQueueTest : public testing::Test {
25 protected:
26  PriorityQueueTest() : queue_(kNumPriorities) {}
27
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
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
51TEST_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
60TEST_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
71TEST_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
79TEST_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
92TEST_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
105TEST_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
113TEST_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
121TEST_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
134TEST_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