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 11 #include "mcld/ADT/TypeTraits.h" 12 #include "mcld/InputTree.h" 13 #include <string> 14 15 using namespace mcld; 16 using namespace mcldtest; 17 18 // Constructor can do set-up work for all test here. 19 BinTreeTest::BinTreeTest() { 20 // create testee. modify it if need 21 m_pTestee = new BinaryTree<int>(); 22 } 23 24 // Destructor can do clean-up work that doesn't throw exceptions here. 25 BinTreeTest::~BinTreeTest() { 26 delete m_pTestee; 27 } 28 29 // SetUp() will be called immediately before each test. 30 void BinTreeTest::SetUp() { 31 } 32 33 // TearDown() will be called immediately after each test. 34 void BinTreeTest::TearDown() { 35 } 36 37 //==========================================================================// 38 // Testcases 39 // 40 41 /// General 42 TEST_F(BinTreeTest, Two_non_null_tree_merge) { 43 BinaryTree<int>::iterator pos = m_pTestee->root(); 44 m_pTestee->join<TreeIteratorBase::Rightward>(pos, 0); 45 --pos; 46 m_pTestee->join<TreeIteratorBase::Rightward>(pos, 1); 47 m_pTestee->join<TreeIteratorBase::Leftward>(pos, 1); 48 --pos; 49 m_pTestee->join<TreeIteratorBase::Rightward>(pos, 2); 50 m_pTestee->join<TreeIteratorBase::Leftward>(pos, 2); 51 52 BinaryTree<int>* mergeTree = new BinaryTree<int>; 53 BinaryTree<int>::iterator pos2 = mergeTree->root(); 54 mergeTree->join<TreeIteratorBase::Rightward>(pos2, 1); 55 --pos2; 56 mergeTree->join<TreeIteratorBase::Rightward>(pos2, 1); 57 mergeTree->join<TreeIteratorBase::Leftward>(pos2, 1); 58 59 m_pTestee->merge<TreeIteratorBase::Rightward>(pos, *mergeTree); 60 delete mergeTree; 61 EXPECT_TRUE(m_pTestee->size() == 8); 62 } 63 64 /// ---- TEST - 2 ---- 65 TEST_F(BinTreeTest, A_null_tree_merge_a_non_null_tree) { 66 BinaryTree<int>::iterator pos = m_pTestee->root(); 67 68 BinaryTree<int>* mergeTree = new BinaryTree<int>; 69 mergeTree->join<TreeIteratorBase::Rightward>(pos, 0); 70 --pos; 71 mergeTree->join<TreeIteratorBase::Rightward>(pos, 1); 72 mergeTree->join<TreeIteratorBase::Leftward>(pos, 1); 73 --pos; 74 mergeTree->join<TreeIteratorBase::Rightward>(pos, 2); 75 mergeTree->join<TreeIteratorBase::Leftward>(pos, 2); 76 77 m_pTestee->merge<TreeIteratorBase::Rightward>(pos, *mergeTree); 78 79 delete mergeTree; 80 EXPECT_TRUE(m_pTestee->size() == 5); 81 } 82 83 TEST_F(BinTreeTest, A_non_null_tree_merge_a_null_tree) { 84 BinaryTree<int>::iterator pos = m_pTestee->root(); 85 m_pTestee->join<TreeIteratorBase::Rightward>(pos, 0); 86 --pos; 87 m_pTestee->join<TreeIteratorBase::Rightward>(pos, 1); 88 m_pTestee->join<TreeIteratorBase::Leftward>(pos, 1); 89 --pos; 90 m_pTestee->join<TreeIteratorBase::Rightward>(pos, 2); 91 m_pTestee->join<TreeIteratorBase::Leftward>(pos, 2); 92 93 BinaryTree<int>* mergeTree = new BinaryTree<int>; 94 BinaryTree<int>::iterator pos2 = mergeTree->root(); 95 mergeTree->merge<TreeIteratorBase::Rightward>(pos2, *m_pTestee); 96 97 // delete m_pTestee; 98 EXPECT_TRUE(mergeTree->size() == 5); 99 delete mergeTree; 100 } 101 102 TEST_F(BinTreeTest, Two_null_tree_merge) { 103 BinaryTree<int>::iterator pos = m_pTestee->root(); 104 105 BinaryTree<int>* mergeTree = new BinaryTree<int>; 106 BinaryTree<int>::iterator pos2 = mergeTree->root(); 107 108 mergeTree->merge<TreeIteratorBase::Rightward>(pos2, *m_pTestee); 109 110 // delete m_pTestee; 111 EXPECT_TRUE(mergeTree->size() == 0); 112 delete mergeTree; 113 } 114 115 TEST_F(BinTreeTest, DFSIterator_BasicTraversal) { 116 int a = 111, b = 10, c = 9, d = 8, e = 7; 117 BinaryTree<int>::iterator pos = m_pTestee->root(); 118 119 m_pTestee->join<InputTree::Inclusive>(pos, a); 120 pos.move<InputTree::Inclusive>(); 121 m_pTestee->join<InputTree::Positional>(pos, b); 122 m_pTestee->join<InputTree::Inclusive>(pos, c); 123 pos.move<InputTree::Inclusive>(); 124 m_pTestee->join<InputTree::Positional>(pos, d); 125 m_pTestee->join<InputTree::Inclusive>(pos, e); 126 127 BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); 128 BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); 129 130 ASSERT_EQ(111, **dfs_it); 131 ++dfs_it; 132 EXPECT_EQ(9, **dfs_it); 133 ++dfs_it; 134 EXPECT_EQ(7, **dfs_it); 135 ++dfs_it; 136 EXPECT_EQ(8, **dfs_it); 137 ++dfs_it; 138 EXPECT_EQ(10, **dfs_it); 139 ++dfs_it; 140 EXPECT_TRUE(dfs_it == dfs_end); 141 } 142 143 TEST_F(BinTreeTest, DFSIterator_RightMostTree) { 144 int a = 0, b = 1, c = 2, d = 3, e = 4; 145 BinaryTree<int>::iterator pos = m_pTestee->root(); 146 m_pTestee->join<InputTree::Inclusive>(pos, a); 147 pos.move<InputTree::Inclusive>(); 148 m_pTestee->join<InputTree::Positional>(pos, b); 149 pos.move<InputTree::Positional>(); 150 m_pTestee->join<InputTree::Positional>(pos, c); 151 pos.move<InputTree::Positional>(); 152 m_pTestee->join<InputTree::Positional>(pos, d); 153 pos.move<InputTree::Positional>(); 154 m_pTestee->join<InputTree::Positional>(pos, e); 155 156 BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); 157 BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); 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; 169 ASSERT_TRUE(dfs_it == dfs_end); 170 } 171 172 TEST_F(BinTreeTest, DFSIterator_SingleNode) { 173 BinaryTree<int>::iterator pos = m_pTestee->root(); 174 m_pTestee->join<InputTree::Inclusive>(pos, 0); 175 BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin(); 176 BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end(); 177 int counter = 0; 178 while (dfs_it != dfs_end) { 179 ++counter; 180 ++dfs_it; 181 } 182 ASSERT_EQ(1, counter); 183 } 184 185 TEST_F(BinTreeTest, BFSIterator_BasicTraversal) { 186 int a = 111, b = 10, c = 9, d = 8, e = 7; 187 BinaryTree<int>::iterator pos = m_pTestee->root(); 188 189 m_pTestee->join<InputTree::Inclusive>(pos, a); 190 pos.move<InputTree::Inclusive>(); 191 m_pTestee->join<InputTree::Positional>(pos, b); 192 m_pTestee->join<InputTree::Inclusive>(pos, c); 193 pos.move<InputTree::Inclusive>(); 194 m_pTestee->join<InputTree::Positional>(pos, d); 195 m_pTestee->join<InputTree::Inclusive>(pos, e); 196 197 BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); 198 BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); 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; 210 ASSERT_TRUE(bfs_it == bfs_end); 211 bfs_it = m_pTestee->bfs_begin(); 212 bfs_end = m_pTestee->bfs_end(); 213 } 214 215 TEST_F(BinTreeTest, BFSIterator_RightMostTree) { 216 int a = 0, b = 1, c = 2, d = 3, e = 4; 217 BinaryTree<int>::iterator pos = m_pTestee->root(); 218 m_pTestee->join<InputTree::Inclusive>(pos, a); 219 pos.move<InputTree::Inclusive>(); 220 m_pTestee->join<InputTree::Positional>(pos, b); 221 pos.move<InputTree::Positional>(); 222 m_pTestee->join<InputTree::Positional>(pos, c); 223 pos.move<InputTree::Positional>(); 224 m_pTestee->join<InputTree::Positional>(pos, d); 225 pos.move<InputTree::Positional>(); 226 m_pTestee->join<InputTree::Positional>(pos, e); 227 228 BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); 229 BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); 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; 241 ASSERT_TRUE(bfs_it == bfs_end); 242 } 243 244 TEST_F(BinTreeTest, BFSIterator_SingleNode) { 245 BinaryTree<int>::iterator pos = m_pTestee->root(); 246 m_pTestee->join<InputTree::Inclusive>(pos, 0); 247 BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin(); 248 BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end(); 249 int counter = 0; 250 while (bfs_it != bfs_end) { 251 ++counter; 252 ++bfs_it; 253 } 254 ASSERT_EQ(1, counter); 255 } 256 257 TEST_F(BinTreeTest, TreeIterator) { 258 int a = 0, b = 1, c = 2, d = 3, e = 4, f = 5; 259 BinaryTree<int>::iterator pos = m_pTestee->root(); 260 m_pTestee->join<InputTree::Inclusive>(pos, a); 261 pos.move<InputTree::Inclusive>(); 262 m_pTestee->join<InputTree::Positional>(pos, b); 263 pos.move<InputTree::Positional>(); 264 m_pTestee->join<InputTree::Inclusive>(pos, c); 265 m_pTestee->join<InputTree::Positional>(pos, f); 266 pos.move<InputTree::Inclusive>(); 267 m_pTestee->join<InputTree::Positional>(pos, d); 268 pos.move<InputTree::Positional>(); 269 m_pTestee->join<InputTree::Positional>(pos, e); 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 } 293
