| OLD | NEW |
| 1 // Copyright (c) 2012 The Chromium Authors. All rights reserved. | 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 | 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
| 4 | 4 |
| 5 #include "net/base/priority_queue.h" | 5 #include "net/base/priority_queue.h" |
| 6 | 6 |
| 7 #include <cstddef> | 7 #include <cstddef> |
| 8 | 8 |
| 9 #include "testing/gtest/include/gtest/gtest.h" | 9 #include "testing/gtest/include/gtest/gtest.h" |
| 10 | 10 |
| 11 namespace net { | 11 namespace net { |
| 12 | 12 |
| 13 namespace { | 13 namespace { |
| 14 | 14 |
| 15 typedef PriorityQueue<int>::Priority Priority; | 15 typedef PriorityQueue<int>::Priority Priority; |
| 16 const Priority kPriorities[] = { 2, 1, 2, 0, 4, 3, 1, 4, 0 }; | 16 const Priority kPriorities[] = {2, 1, 2, 0, 4, 3, 1, 4, 0}; |
| 17 const Priority kNumPriorities = 5; // max(kPriorities) + 1 | 17 const Priority kNumPriorities = 5; // max(kPriorities) + 1 |
| 18 const size_t kNumElements = arraysize(kPriorities); | 18 const size_t kNumElements = arraysize(kPriorities); |
| 19 const int kFirstMinOrder[kNumElements] = { 3, 8, 1, 6, 0, 2, 5, 4, 7 }; | 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 }; | 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 }; | 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 }; | 22 const int kLastMinOrder[kNumElements] = {8, 3, 6, 1, 2, 0, 5, 7, 4}; |
| 23 | 23 |
| 24 class PriorityQueueTest : public testing::Test { | 24 class PriorityQueueTest : public testing::Test { |
| 25 protected: | 25 protected: |
| 26 PriorityQueueTest() : queue_(kNumPriorities) {} | 26 PriorityQueueTest() : queue_(kNumPriorities) {} |
| 27 | 27 |
| 28 virtual void SetUp() override { | 28 virtual void SetUp() override { |
| 29 CheckEmpty(); | 29 CheckEmpty(); |
| 30 for (size_t i = 0; i < kNumElements; ++i) { | 30 for (size_t i = 0; i < kNumElements; ++i) { |
| 31 EXPECT_EQ(i, queue_.size()); | 31 EXPECT_EQ(i, queue_.size()); |
| 32 pointers_[i] = queue_.Insert(static_cast<int>(i), kPriorities[i]); | 32 pointers_[i] = queue_.Insert(static_cast<int>(i), kPriorities[i]); |
| (...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 115 EXPECT_EQ(kLastMaxOrderErase[i], queue_.LastMax().value()); | 115 EXPECT_EQ(kLastMaxOrderErase[i], queue_.LastMax().value()); |
| 116 queue_.Erase(queue_.LastMax()); | 116 queue_.Erase(queue_.LastMax()); |
| 117 } | 117 } |
| 118 CheckEmpty(); | 118 CheckEmpty(); |
| 119 } | 119 } |
| 120 | 120 |
| 121 TEST_F(PriorityQueueTest, EraseFromMiddle) { | 121 TEST_F(PriorityQueueTest, EraseFromMiddle) { |
| 122 queue_.Erase(pointers_[2]); | 122 queue_.Erase(pointers_[2]); |
| 123 queue_.Erase(pointers_[3]); | 123 queue_.Erase(pointers_[3]); |
| 124 | 124 |
| 125 const int expected_order[] = { 8, 1, 6, 0, 5, 4, 7 }; | 125 const int expected_order[] = {8, 1, 6, 0, 5, 4, 7}; |
| 126 | 126 |
| 127 for (size_t i = 0; i < arraysize(expected_order); ++i) { | 127 for (size_t i = 0; i < arraysize(expected_order); ++i) { |
| 128 EXPECT_EQ(expected_order[i], queue_.FirstMin().value()); | 128 EXPECT_EQ(expected_order[i], queue_.FirstMin().value()); |
| 129 queue_.Erase(queue_.FirstMin()); | 129 queue_.Erase(queue_.FirstMin()); |
| 130 } | 130 } |
| 131 CheckEmpty(); | 131 CheckEmpty(); |
| 132 } | 132 } |
| 133 | 133 |
| 134 TEST_F(PriorityQueueTest, InsertAtFront) { | 134 TEST_F(PriorityQueueTest, InsertAtFront) { |
| 135 queue_.InsertAtFront(9, 2); | 135 queue_.InsertAtFront(9, 2); |
| 136 queue_.InsertAtFront(10, 0); | 136 queue_.InsertAtFront(10, 0); |
| 137 queue_.InsertAtFront(11, 1); | 137 queue_.InsertAtFront(11, 1); |
| 138 queue_.InsertAtFront(12, 1); | 138 queue_.InsertAtFront(12, 1); |
| 139 | 139 |
| 140 const int expected_order[] = { 10, 3, 8, 12, 11, 1, 6, 9, 0, 2, 5, 4, 7 }; | 140 const int expected_order[] = {10, 3, 8, 12, 11, 1, 6, 9, 0, 2, 5, 4, 7}; |
| 141 | 141 |
| 142 for (size_t i = 0; i < arraysize(expected_order); ++i) { | 142 for (size_t i = 0; i < arraysize(expected_order); ++i) { |
| 143 EXPECT_EQ(expected_order[i], queue_.FirstMin().value()); | 143 EXPECT_EQ(expected_order[i], queue_.FirstMin().value()); |
| 144 queue_.Erase(queue_.FirstMin()); | 144 queue_.Erase(queue_.FirstMin()); |
| 145 } | 145 } |
| 146 CheckEmpty(); | 146 CheckEmpty(); |
| 147 } | 147 } |
| 148 | 148 |
| 149 } // namespace | 149 } // namespace |
| 150 | 150 |
| 151 } // namespace net | 151 } // namespace net |
| OLD | NEW |