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#include "testing/gtest/include/gtest/gtest.h"
7
8namespace net {
9
10namespace {
11
12typedef PriorityQueue<int>::Priority Priority;
13const Priority kPriorities[] = { 2, 1, 2, 0, 4, 3, 1, 4, 0 };
14const Priority kNumPriorities = 5;  // max(kPriorities) + 1
15const size_t kNumElements = arraysize(kPriorities);
16const int kFirstMinOrder[kNumElements] = { 3, 8, 1, 6, 0, 2, 5, 4, 7 };
17const int kLastMaxOrder[kNumElements] = { 7, 4, 5, 2, 0, 6, 1, 8, 3 };
18const int kFirstMaxOrder[kNumElements] = { 4, 7, 5, 0, 2, 1, 6, 3, 8 };
19const int kLastMinOrder[kNumElements] = { 8, 3, 6, 1, 2, 0, 5, 7, 4 };
20
21class PriorityQueueTest : public testing::Test {
22 protected:
23  PriorityQueueTest() : queue_(kNumPriorities) {}
24
25  virtual void SetUp() OVERRIDE {
26    CheckEmpty();
27    for (size_t i = 0; i < kNumElements; ++i) {
28      EXPECT_EQ(i, queue_.size());
29      pointers_[i] = queue_.Insert(static_cast<int>(i), kPriorities[i]);
30    }
31    EXPECT_EQ(kNumElements, queue_.size());
32  }
33
34  void CheckEmpty() {
35    EXPECT_EQ(0u, queue_.size());
36    EXPECT_TRUE(queue_.FirstMin().is_null());
37    EXPECT_TRUE(queue_.LastMin().is_null());
38    EXPECT_TRUE(queue_.FirstMax().is_null());
39    EXPECT_TRUE(queue_.LastMax().is_null());
40  }
41
42  PriorityQueue<int> queue_;
43  PriorityQueue<int>::Pointer pointers_[kNumElements];
44};
45
46TEST_F(PriorityQueueTest, AddAndClear) {
47  for (size_t i = 0; i < kNumElements; ++i) {
48    EXPECT_EQ(kPriorities[i], pointers_[i].priority());
49    EXPECT_EQ(static_cast<int>(i), pointers_[i].value());
50  }
51  queue_.Clear();
52  CheckEmpty();
53}
54
55TEST_F(PriorityQueueTest, FirstMinOrder) {
56  for (size_t i = 0; i < kNumElements; ++i) {
57    EXPECT_EQ(kNumElements - i, queue_.size());
58    // Also check Equals.
59    EXPECT_TRUE(queue_.FirstMin().Equals(pointers_[kFirstMinOrder[i]]));
60    EXPECT_EQ(kFirstMinOrder[i], queue_.FirstMin().value());
61    queue_.Erase(queue_.FirstMin());
62  }
63  CheckEmpty();
64}
65
66TEST_F(PriorityQueueTest, LastMinOrder) {
67  for (size_t i = 0; i < kNumElements; ++i) {
68    EXPECT_EQ(kLastMinOrder[i], queue_.LastMin().value());
69    queue_.Erase(queue_.LastMin());
70  }
71  CheckEmpty();
72}
73
74TEST_F(PriorityQueueTest, FirstMaxOrder) {
75  for (size_t i = 0; i < kNumElements; ++i) {
76    EXPECT_EQ(kFirstMaxOrder[i], queue_.FirstMax().value());
77    queue_.Erase(queue_.FirstMax());
78  }
79  CheckEmpty();
80}
81
82TEST_F(PriorityQueueTest, LastMaxOrder) {
83  for (size_t i = 0; i < kNumElements; ++i) {
84    EXPECT_EQ(kLastMaxOrder[i], queue_.LastMax().value());
85    queue_.Erase(queue_.LastMax());
86  }
87  CheckEmpty();
88}
89
90TEST_F(PriorityQueueTest, EraseFromMiddle) {
91  queue_.Erase(pointers_[2]);
92  queue_.Erase(pointers_[3]);
93
94  int expected_order[] = { 8, 1, 6, 0, 5, 4, 7 };
95
96  for (size_t i = 0; i < arraysize(expected_order); ++i) {
97    EXPECT_EQ(expected_order[i], queue_.FirstMin().value());
98    queue_.Erase(queue_.FirstMin());
99  }
100  CheckEmpty();
101}
102
103}  // namespace
104
105}  // namespace net
106