BinTreeTest.cpp revision 37b74a387bb3993387029859c2d9d051c41c724e 
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// Constructor can do set-up work for all test here.
19BinTreeTest::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.
25BinTreeTest::~BinTreeTest() {
26  delete m_pTestee;
27}
28
29// SetUp() will be called immediately before each test.
30void BinTreeTest::SetUp() {
31}
32
33// TearDown() will be called immediately after each test.
34void BinTreeTest::TearDown() {
35}
36
37//==========================================================================//
38// Testcases
39//
40
41/// General
42TEST_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 ----
65TEST_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
83TEST_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
102TEST_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
115TEST_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
143TEST_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
172TEST_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
185TEST_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
215TEST_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
244TEST_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
257TEST_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