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
15 using namespace mcld;
16 using namespace mcldtest;
17
18
19 // Constructor can do set-up work for all test here.
BinTreeTest()20 BinTreeTest::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.
~BinTreeTest()27 BinTreeTest::~BinTreeTest()
28 {
29 delete m_pTestee;
30 }
31
32 // SetUp() will be called immediately before each test.
SetUp()33 void BinTreeTest::SetUp()
34 {
35 }
36
37 // TearDown() will be called immediately after each test.
TearDown()38 void BinTreeTest::TearDown()
39 {
40 }
41
42 //==========================================================================//
43 // Testcases
44 //
45
46
47 /// General
TEST_F(BinTreeTest,Two_non_null_tree_merge)48 TEST_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 ----
TEST_F(BinTreeTest,A_null_tree_merge_a_non_null_tree)72 TEST_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
TEST_F(BinTreeTest,A_non_null_tree_merge_a_null_tree)91 TEST_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
TEST_F(BinTreeTest,Two_null_tree_merge)111 TEST_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
TEST_F(BinTreeTest,DFSIterator_BasicTraversal)125 TEST_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
TEST_F(BinTreeTest,DFSIterator_RightMostTree)156 TEST_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
TEST_F(BinTreeTest,DFSIterator_SingleNode)186 TEST_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
TEST_F(BinTreeTest,BFSIterator_BasicTraversal)200 TEST_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
TEST_F(BinTreeTest,BFSIterator_RightMostTree)231 TEST_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
TEST_F(BinTreeTest,BFSIterator_SingleNode)261 TEST_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