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