Home | History | Annotate | Download | only in base 
      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 
      8 namespace net {
      9 
     10 namespace {
     11 
     12 typedef PriorityQueue<int>::Priority Priority;
     13 const Priority kPriorities[] = { 2, 1, 2, 0, 4, 3, 1, 4, 0 };
     14 const Priority kNumPriorities = 5;  // max(kPriorities) + 1
     15 const size_t kNumElements = arraysize(kPriorities);
     16 const int kFirstMinOrder[kNumElements] = { 3, 8, 1, 6, 0, 2, 5, 4, 7 };
     17 const int kLastMaxOrder[kNumElements] = { 7, 4, 5, 2, 0, 6, 1, 8, 3 };
     18 const int kFirstMaxOrder[kNumElements] = { 4, 7, 5, 0, 2, 1, 6, 3, 8 };
     19 const int kLastMinOrder[kNumElements] = { 8, 3, 6, 1, 2, 0, 5, 7, 4 };
     20 
     21 class 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 
     46 TEST_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 
     55 TEST_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 
     66 TEST_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 
     74 TEST_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 
     82 TEST_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 
     90 TEST_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