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 
      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:
     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 
     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 
     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 
     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 
     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 
     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 
    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 
    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 
    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 
    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