net/base/priority_queue_unittest.cc

   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