BinTreeTest.cpp revision 5460a1f25d9ddecb5c70667267d66d51af177a99 
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/MCLDInputTree.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