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