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