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