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/MC/InputTree.h" 13#include <string> 14 15using namespace mcld; 16using namespace mcldtest; 17 18 19// Constructor can do set-up work for all test here. 20BinTreeTest::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. 27BinTreeTest::~BinTreeTest() 28{ 29 delete m_pTestee; 30} 31 32// SetUp() will be called immediately before each test. 33void BinTreeTest::SetUp() 34{ 35} 36 37// TearDown() will be called immediately after each test. 38void BinTreeTest::TearDown() 39{ 40} 41 42//==========================================================================// 43// Testcases 44// 45 46 47/// General 48TEST_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 ---- 72TEST_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 91TEST_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 111TEST_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 125TEST_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 156TEST_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 186TEST_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 200TEST_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 231TEST_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 261TEST_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 276