BinTreeTest.cpp revision f33f6de54db174aa679a4b6d1e040d37e95541c0 
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
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, b = 10, c = 9, d = 8, e = 7;
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,b);
133  m_pTestee->join<InputTree::Inclusive>(pos,c);
134  pos.move<InputTree::Inclusive>();
135  m_pTestee->join<InputTree::Positional>(pos,d);
136  m_pTestee->join<InputTree::Inclusive>(pos,e);
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  EXPECT_EQ(9, **dfs_it);
144  ++dfs_it;
145  EXPECT_EQ(7, **dfs_it);
146  ++dfs_it;
147  EXPECT_EQ(8, **dfs_it);
148  ++dfs_it;
149  EXPECT_EQ(10, **dfs_it);
150  ++dfs_it;
151  EXPECT_TRUE( dfs_it ==  dfs_end);
152}
153
154TEST_F( BinTreeTest, DFSIterator_RightMostTree)
155{
156  int a = 0, b = 1, c = 2, d = 3, e = 4;
157  BinaryTree<int>::iterator pos = m_pTestee->root();
158  m_pTestee->join<InputTree::Inclusive>(pos,a);
159  pos.move<InputTree::Inclusive>();
160  m_pTestee->join<InputTree::Positional>(pos,b);
161  pos.move<InputTree::Positional>();
162  m_pTestee->join<InputTree::Positional>(pos,c);
163  pos.move<InputTree::Positional>();
164  m_pTestee->join<InputTree::Positional>(pos,d);
165  pos.move<InputTree::Positional>();
166  m_pTestee->join<InputTree::Positional>(pos,e);
167
168  BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin();
169  BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end();
170
171  ASSERT_EQ(0, **dfs_it);
172  ++dfs_it;
173  ASSERT_EQ(1, **dfs_it);
174  ++dfs_it;
175  ASSERT_EQ(2, **dfs_it);
176  ++dfs_it;
177  ASSERT_EQ(3, **dfs_it);
178  ++dfs_it;
179  ASSERT_EQ(4, **dfs_it);
180  ++dfs_it;
181  ASSERT_TRUE( dfs_it ==  dfs_end);
182}
183
184
185TEST_F( BinTreeTest, DFSIterator_SingleNode)
186{
187  BinaryTree<int>::iterator pos = m_pTestee->root();
188  m_pTestee->join<InputTree::Inclusive>(pos,0);
189  BinaryTree<int>::dfs_iterator dfs_it = m_pTestee->dfs_begin();
190  BinaryTree<int>::dfs_iterator dfs_end = m_pTestee->dfs_end();
191  int counter = 0;
192  while( dfs_it != dfs_end ) {
193    ++counter;
194    ++dfs_it;
195  }
196  ASSERT_EQ(1, counter);
197}
198
199TEST_F( BinTreeTest, BFSIterator_BasicTraversal)
200{
201  int a = 111, b = 10, c = 9, d = 8, e = 7;
202  BinaryTree<int>::iterator pos = m_pTestee->root();
203
204  m_pTestee->join<InputTree::Inclusive>(pos,a);
205  pos.move<InputTree::Inclusive>();
206  m_pTestee->join<InputTree::Positional>(pos,b);
207  m_pTestee->join<InputTree::Inclusive>(pos,c);
208  pos.move<InputTree::Inclusive>();
209  m_pTestee->join<InputTree::Positional>(pos,d);
210  m_pTestee->join<InputTree::Inclusive>(pos,e);
211
212  BinaryTree<int>::bfs_iterator bfs_it = m_pTestee->bfs_begin();
213  BinaryTree<int>::bfs_iterator bfs_end = m_pTestee->bfs_end();
214
215  ASSERT_EQ(111, **bfs_it);
216  ++bfs_it;
217  ASSERT_EQ(10, **bfs_it);
218  ++bfs_it;
219  ASSERT_EQ(9, **bfs_it);
220  ++bfs_it;
221  ASSERT_EQ(8, **bfs_it);
222  ++bfs_it;
223  ASSERT_EQ(7, **bfs_it);
224  ++bfs_it;
225  ASSERT_TRUE(bfs_it ==  bfs_end);
226  bfs_it = m_pTestee->bfs_begin();
227  bfs_end = m_pTestee->bfs_end();
228}
229
230TEST_F( BinTreeTest, BFSIterator_RightMostTree)
231{
232  int a = 0, b = 1, c = 2, d = 3, e = 4;
233  BinaryTree<int>::iterator pos = m_pTestee->root();
234  m_pTestee->join<InputTree::Inclusive>(pos,a);
235  pos.move<InputTree::Inclusive>();
236  m_pTestee->join<InputTree::Positional>(pos,b);
237  pos.move<InputTree::Positional>();
238  m_pTestee->join<InputTree::Positional>(pos,c);
239  pos.move<InputTree::Positional>();
240  m_pTestee->join<InputTree::Positional>(pos,d);
241  pos.move<InputTree::Positional>();
242  m_pTestee->join<InputTree::Positional>(pos,e);
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
275TEST_F( BinTreeTest, TreeIterator)
276{
277  int a = 0, b = 1, c = 2, d = 3, e = 4, f = 5;
278  BinaryTree<int>::iterator pos = m_pTestee->root();
279  m_pTestee->join<InputTree::Inclusive>(pos,a);
280  pos.move<InputTree::Inclusive>();
281  m_pTestee->join<InputTree::Positional>(pos,b);
282  pos.move<InputTree::Positional>();
283  m_pTestee->join<InputTree::Inclusive>(pos,c);
284  m_pTestee->join<InputTree::Positional>(pos,f);
285  pos.move<InputTree::Inclusive>();
286  m_pTestee->join<InputTree::Positional>(pos,d);
287  pos.move<InputTree::Positional>();
288  m_pTestee->join<InputTree::Positional>(pos,e);
289
290  BinaryTree<int>::iterator it = m_pTestee->begin();
291  BinaryTree<int>::iterator end = m_pTestee->end();
292
293  ASSERT_EQ(0, **it);
294  ++it;
295  ASSERT_EQ(1, **it);
296  --it;
297  ASSERT_EQ(2, **it);
298  ++it;
299  ASSERT_EQ(3, **it);
300  ++it;
301  ASSERT_EQ(4, **it);
302  ++it;
303  ASSERT_TRUE(it == end);
304
305  it = m_pTestee->begin();
306  ++it;
307  ++it;
308  ASSERT_EQ(5, **it);
309  ++it;
310  ASSERT_TRUE(it == end);
311}
312
313