Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 1 | //===- BinTreeTest.cpp ----------------------------------------------------===// |
| 2 | // |
| 3 | // The MCLinker Project |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | #include "BinTreeTest.h" |
| 10 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 11 | #include "mcld/ADT/TypeTraits.h" |
| 12 | #include "mcld/InputTree.h" |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 13 | #include <string> |
| 14 | |
| 15 | using namespace mcld; |
| 16 | using namespace mcldtest; |
| 17 | |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 18 | // Constructor can do set-up work for all test here. |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 19 | BinTreeTest::BinTreeTest() { |
| 20 | // create testee. modify it if need |
| 21 | m_pTestee = new BinaryTree<int>(); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 22 | } |
| 23 | |
| 24 | // Destructor can do clean-up work that doesn't throw exceptions here. |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 25 | BinTreeTest::~BinTreeTest() { |
| 26 | delete m_pTestee; |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 27 | } |
| 28 | |
| 29 | // SetUp() will be called immediately before each test. |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 30 | void BinTreeTest::SetUp() { |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 31 | } |
| 32 | |
| 33 | // TearDown() will be called immediately after each test. |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 34 | void BinTreeTest::TearDown() { |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 35 | } |
| 36 | |
| 37 | //==========================================================================// |
| 38 | // Testcases |
| 39 | // |
| 40 | |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 41 | /// General |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 42 | TEST_F(BinTreeTest, Two_non_null_tree_merge) { |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 43 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 44 | m_pTestee->join<TreeIteratorBase::Rightward>(pos, 0); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 45 | --pos; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 46 | m_pTestee->join<TreeIteratorBase::Rightward>(pos, 1); |
| 47 | m_pTestee->join<TreeIteratorBase::Leftward>(pos, 1); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 48 | --pos; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 49 | m_pTestee->join<TreeIteratorBase::Rightward>(pos, 2); |
| 50 | m_pTestee->join<TreeIteratorBase::Leftward>(pos, 2); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 51 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 52 | BinaryTree<int>* mergeTree = new BinaryTree<int>; |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 53 | BinaryTree<int>::iterator pos2 = mergeTree->root(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 54 | mergeTree->join<TreeIteratorBase::Rightward>(pos2, 1); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 55 | --pos2; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 56 | mergeTree->join<TreeIteratorBase::Rightward>(pos2, 1); |
| 57 | mergeTree->join<TreeIteratorBase::Leftward>(pos2, 1); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 58 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 59 | m_pTestee->merge<TreeIteratorBase::Rightward>(pos, *mergeTree); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 60 | delete mergeTree; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 61 | EXPECT_TRUE(m_pTestee->size() == 8); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 62 | } |
| 63 | |
| 64 | /// ---- TEST - 2 ---- |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 65 | TEST_F(BinTreeTest, A_null_tree_merge_a_non_null_tree) { |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 66 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 67 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 68 | BinaryTree<int>* mergeTree = new BinaryTree<int>; |
| 69 | mergeTree->join<TreeIteratorBase::Rightward>(pos, 0); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 70 | --pos; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 71 | mergeTree->join<TreeIteratorBase::Rightward>(pos, 1); |
| 72 | mergeTree->join<TreeIteratorBase::Leftward>(pos, 1); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 73 | --pos; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 74 | mergeTree->join<TreeIteratorBase::Rightward>(pos, 2); |
| 75 | mergeTree->join<TreeIteratorBase::Leftward>(pos, 2); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 76 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 77 | m_pTestee->merge<TreeIteratorBase::Rightward>(pos, *mergeTree); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 78 | |
| 79 | delete mergeTree; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 80 | EXPECT_TRUE(m_pTestee->size() == 5); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 81 | } |
| 82 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 83 | TEST_F(BinTreeTest, A_non_null_tree_merge_a_null_tree) { |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 84 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 85 | m_pTestee->join<TreeIteratorBase::Rightward>(pos, 0); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 86 | --pos; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 87 | m_pTestee->join<TreeIteratorBase::Rightward>(pos, 1); |
| 88 | m_pTestee->join<TreeIteratorBase::Leftward>(pos, 1); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 89 | --pos; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 90 | m_pTestee->join<TreeIteratorBase::Rightward>(pos, 2); |
| 91 | m_pTestee->join<TreeIteratorBase::Leftward>(pos, 2); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 92 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 93 | BinaryTree<int>* mergeTree = new BinaryTree<int>; |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 94 | BinaryTree<int>::iterator pos2 = mergeTree->root(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 95 | mergeTree->merge<TreeIteratorBase::Rightward>(pos2, *m_pTestee); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 96 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 97 | // delete m_pTestee; |
| 98 | EXPECT_TRUE(mergeTree->size() == 5); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 99 | delete mergeTree; |
| 100 | } |
| 101 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 102 | TEST_F(BinTreeTest, Two_null_tree_merge) { |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 103 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 104 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 105 | BinaryTree<int>* mergeTree = new BinaryTree<int>; |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 106 | BinaryTree<int>::iterator pos2 = mergeTree->root(); |
| 107 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 108 | mergeTree->merge<TreeIteratorBase::Rightward>(pos2, *m_pTestee); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 109 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 110 | // delete m_pTestee; |
| 111 | EXPECT_TRUE(mergeTree->size() == 0); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 112 | delete mergeTree; |
| 113 | } |
| 114 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 115 | TEST_F(BinTreeTest, DFSIterator_BasicTraversal) { |
Stephen Hines | f33f6de | 2014-02-14 18:00:16 -0800 | [diff] [blame] | 116 | int a = 111, b = 10, c = 9, d = 8, e = 7; |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 117 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 118 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 119 | m_pTestee->join<InputTree::Inclusive>(pos, a); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 120 | pos.move<InputTree::Inclusive>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 121 | m_pTestee->join<InputTree::Positional>(pos, b); |
| 122 | m_pTestee->join<InputTree::Inclusive>(pos, c); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 123 | pos.move<InputTree::Inclusive>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 124 | m_pTestee->join<InputTree::Positional>(pos, d); |
| 125 | m_pTestee->join<InputTree::Inclusive>(pos, e); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 126 | |
| 127 | BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); |
| 128 | BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 129 | |
| 130 | ASSERT_EQ(111, **dfs_it); |
| 131 | ++dfs_it; |
Stephen Hines | f33f6de | 2014-02-14 18:00:16 -0800 | [diff] [blame] | 132 | EXPECT_EQ(9, **dfs_it); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 133 | ++dfs_it; |
Stephen Hines | f33f6de | 2014-02-14 18:00:16 -0800 | [diff] [blame] | 134 | EXPECT_EQ(7, **dfs_it); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 135 | ++dfs_it; |
Stephen Hines | f33f6de | 2014-02-14 18:00:16 -0800 | [diff] [blame] | 136 | EXPECT_EQ(8, **dfs_it); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 137 | ++dfs_it; |
Stephen Hines | f33f6de | 2014-02-14 18:00:16 -0800 | [diff] [blame] | 138 | EXPECT_EQ(10, **dfs_it); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 139 | ++dfs_it; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 140 | EXPECT_TRUE(dfs_it == dfs_end); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 141 | } |
| 142 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 143 | TEST_F(BinTreeTest, DFSIterator_RightMostTree) { |
Stephen Hines | f33f6de | 2014-02-14 18:00:16 -0800 | [diff] [blame] | 144 | int a = 0, b = 1, c = 2, d = 3, e = 4; |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 145 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 146 | m_pTestee->join<InputTree::Inclusive>(pos, a); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 147 | pos.move<InputTree::Inclusive>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 148 | m_pTestee->join<InputTree::Positional>(pos, b); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 149 | pos.move<InputTree::Positional>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 150 | m_pTestee->join<InputTree::Positional>(pos, c); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 151 | pos.move<InputTree::Positional>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 152 | m_pTestee->join<InputTree::Positional>(pos, d); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 153 | pos.move<InputTree::Positional>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 154 | m_pTestee->join<InputTree::Positional>(pos, e); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 155 | |
| 156 | BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); |
| 157 | BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 158 | |
| 159 | ASSERT_EQ(0, **dfs_it); |
| 160 | ++dfs_it; |
| 161 | ASSERT_EQ(1, **dfs_it); |
| 162 | ++dfs_it; |
| 163 | ASSERT_EQ(2, **dfs_it); |
| 164 | ++dfs_it; |
| 165 | ASSERT_EQ(3, **dfs_it); |
| 166 | ++dfs_it; |
| 167 | ASSERT_EQ(4, **dfs_it); |
| 168 | ++dfs_it; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 169 | ASSERT_TRUE(dfs_it == dfs_end); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 170 | } |
| 171 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 172 | TEST_F(BinTreeTest, DFSIterator_SingleNode) { |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 173 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 174 | m_pTestee->join<InputTree::Inclusive>(pos, 0); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 175 | BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); |
| 176 | BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 177 | int counter = 0; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 178 | while (dfs_it != dfs_end) { |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 179 | ++counter; |
| 180 | ++dfs_it; |
| 181 | } |
| 182 | ASSERT_EQ(1, counter); |
| 183 | } |
| 184 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 185 | TEST_F(BinTreeTest, BFSIterator_BasicTraversal) { |
Stephen Hines | f33f6de | 2014-02-14 18:00:16 -0800 | [diff] [blame] | 186 | int a = 111, b = 10, c = 9, d = 8, e = 7; |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 187 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 188 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 189 | m_pTestee->join<InputTree::Inclusive>(pos, a); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 190 | pos.move<InputTree::Inclusive>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 191 | m_pTestee->join<InputTree::Positional>(pos, b); |
| 192 | m_pTestee->join<InputTree::Inclusive>(pos, c); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 193 | pos.move<InputTree::Inclusive>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 194 | m_pTestee->join<InputTree::Positional>(pos, d); |
| 195 | m_pTestee->join<InputTree::Inclusive>(pos, e); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 196 | |
| 197 | BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); |
| 198 | BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 199 | |
| 200 | ASSERT_EQ(111, **bfs_it); |
| 201 | ++bfs_it; |
| 202 | ASSERT_EQ(10, **bfs_it); |
| 203 | ++bfs_it; |
| 204 | ASSERT_EQ(9, **bfs_it); |
| 205 | ++bfs_it; |
| 206 | ASSERT_EQ(8, **bfs_it); |
| 207 | ++bfs_it; |
| 208 | ASSERT_EQ(7, **bfs_it); |
| 209 | ++bfs_it; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 210 | ASSERT_TRUE(bfs_it == bfs_end); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 211 | bfs_it = m_pTestee->bfs_begin(); |
| 212 | bfs_end = m_pTestee->bfs_end(); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 213 | } |
| 214 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 215 | TEST_F(BinTreeTest, BFSIterator_RightMostTree) { |
Stephen Hines | f33f6de | 2014-02-14 18:00:16 -0800 | [diff] [blame] | 216 | int a = 0, b = 1, c = 2, d = 3, e = 4; |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 217 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 218 | m_pTestee->join<InputTree::Inclusive>(pos, a); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 219 | pos.move<InputTree::Inclusive>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 220 | m_pTestee->join<InputTree::Positional>(pos, b); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 221 | pos.move<InputTree::Positional>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 222 | m_pTestee->join<InputTree::Positional>(pos, c); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 223 | pos.move<InputTree::Positional>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 224 | m_pTestee->join<InputTree::Positional>(pos, d); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 225 | pos.move<InputTree::Positional>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 226 | m_pTestee->join<InputTree::Positional>(pos, e); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 227 | |
| 228 | BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); |
| 229 | BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 230 | |
| 231 | ASSERT_EQ(0, **bfs_it); |
| 232 | ++bfs_it; |
| 233 | ASSERT_EQ(1, **bfs_it); |
| 234 | ++bfs_it; |
| 235 | ASSERT_EQ(2, **bfs_it); |
| 236 | ++bfs_it; |
| 237 | ASSERT_EQ(3, **bfs_it); |
| 238 | ++bfs_it; |
| 239 | ASSERT_EQ(4, **bfs_it); |
| 240 | ++bfs_it; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 241 | ASSERT_TRUE(bfs_it == bfs_end); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 242 | } |
| 243 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 244 | TEST_F(BinTreeTest, BFSIterator_SingleNode) { |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 245 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 246 | m_pTestee->join<InputTree::Inclusive>(pos, 0); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 247 | BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); |
| 248 | BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 249 | int counter = 0; |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 250 | while (bfs_it != bfs_end) { |
Shih-wei Liao | 5460a1f | 2012-03-16 22:41:16 -0700 | [diff] [blame] | 251 | ++counter; |
| 252 | ++bfs_it; |
| 253 | } |
| 254 | ASSERT_EQ(1, counter); |
| 255 | } |
| 256 | |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 257 | TEST_F(BinTreeTest, TreeIterator) { |
Stephen Hines | f33f6de | 2014-02-14 18:00:16 -0800 | [diff] [blame] | 258 | int a = 0, b = 1, c = 2, d = 3, e = 4, f = 5; |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 259 | BinaryTree<int>::iterator pos = m_pTestee->root(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 260 | m_pTestee->join<InputTree::Inclusive>(pos, a); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 261 | pos.move<InputTree::Inclusive>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 262 | m_pTestee->join<InputTree::Positional>(pos, b); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 263 | pos.move<InputTree::Positional>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 264 | m_pTestee->join<InputTree::Inclusive>(pos, c); |
| 265 | m_pTestee->join<InputTree::Positional>(pos, f); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 266 | pos.move<InputTree::Inclusive>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 267 | m_pTestee->join<InputTree::Positional>(pos, d); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 268 | pos.move<InputTree::Positional>(); |
Stephen Hines | 37b74a3 | 2014-11-26 18:48:20 -0800 | [diff] [blame] | 269 | m_pTestee->join<InputTree::Positional>(pos, e); |
Shih-wei Liao | 22add6f | 2012-12-15 17:21:00 -0800 | [diff] [blame] | 270 | |
| 271 | BinaryTree<int>::iterator it = m_pTestee->begin(); |
| 272 | BinaryTree<int>::iterator end = m_pTestee->end(); |
| 273 | |
| 274 | ASSERT_EQ(0, **it); |
| 275 | ++it; |
| 276 | ASSERT_EQ(1, **it); |
| 277 | --it; |
| 278 | ASSERT_EQ(2, **it); |
| 279 | ++it; |
| 280 | ASSERT_EQ(3, **it); |
| 281 | ++it; |
| 282 | ASSERT_EQ(4, **it); |
| 283 | ++it; |
| 284 | ASSERT_TRUE(it == end); |
| 285 | |
| 286 | it = m_pTestee->begin(); |
| 287 | ++it; |
| 288 | ++it; |
| 289 | ASSERT_EQ(5, **it); |
| 290 | ++it; |
| 291 | ASSERT_TRUE(it == end); |
| 292 | } |