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