1 /* $Id: test_ncbi_tree.cpp 534857 2017-05-03 12:26:07Z ivanov $
2 * ===========================================================================
3 *
4 * PUBLIC DOMAIN NOTICE
5 * National Center for Biotechnology Information
6 *
7 * This software/database is a "United States Government Work" under the
8 * terms of the United States Copyright Act. It was written as part of
9 * the author's official duties as a United States Government employee and
10 * thus cannot be copyrighted. This software/database is freely available
11 * to the public for use. The National Library of Medicine and the U.S.
12 * Government have not placed any restriction on its use or reproduction.
13 *
14 * Although all reasonable efforts have been taken to ensure the accuracy
15 * and reliability of the software and data, the NLM and the U.S.
16 * Government do not and cannot warrant the performance or results that
17 * may be obtained by using this software or data. The NLM and the U.S.
18 * Government disclaim all warranties, express or implied, including
19 * warranties of performance, merchantability or fitness for any particular
20 * purpose.
21 *
22 * Please cite the author in any work or product based on this material.
23 *
24 * ===========================================================================
25 *
26 * Author: Anatoliy Kuznetov
27 *
28 * File Description:
29 * TEST for: NCBI C++ core tree related API
30 *
31 */
32
33 #include <ncbi_pch.hpp>
34 #include <corelib/ncbiapp.hpp>
35 #include <corelib/ncbienv.hpp>
36 #include <corelib/ncbireg.hpp>
37 #include <corelib/ncbi_tree.hpp>
38 #include <algorithm>
39
40 #include <common/test_assert.h> /* This header must go last */
41
42
43 // This is to use the ANSI C++ standard templates without the "std::" prefix
44 // and to use NCBI C++ entities without the "ncbi::" prefix
45 USING_NCBI_SCOPE;
46
47
48
49 /////////////////////////////////
50 // Test application
51 //
52
53 class CTestApplication : public CNcbiApplication
54 {
55 public:
56 void Init(void);
57 int Run(void);
58 };
59
60
Init(void)61 void CTestApplication::Init(void)
62 {
63 // Set err.-posting and tracing to maximum
64 SetDiagTrace(eDT_Enable);
65 SetDiagPostFlag(eDPF_All);
66 SetDiagPostLevel(eDiag_Info);
67 }
68
TestFunctor1(CTreeNode<int> & tr,int delta)69 ETreeTraverseCode TestFunctor1(CTreeNode<int>& tr, int delta)
70 {
71 cout << tr.GetValue() << " :" << delta << endl;
72 return eTreeTraverse;
73 }
74
TestFunctor2(CTreeNode<int> & tr)75 ETreeTraverseCode TestFunctor2(CTreeNode<int>& tr)
76 {
77 cout << tr.GetValue() << endl;
78 return eTreeTraverse;
79 }
80
TestFunctor3(int a,int b)81 bool TestFunctor3(int a, int b)
82 {
83 return (a == b);
84 }
85
86 // static string s_IntToStr(int i)
87 // {
88 // return NStr::IntToString(i);
89 // }
90
91
92
s_TEST_Tree()93 static void s_TEST_Tree()
94 {
95 typedef CTreeNode<int> TTree;
96
97 TTree* tr = new TTree(0);
98 TTree* tr10 = tr->AddNode(10);
99 tr->AddNode(11);
100 tr10->AddNode(20);
101 tr10->AddNode(21);
102
103 TTree* sr = new TTree(0);
104 sr->AddNode(10);
105 sr->AddNode(11);
106 delete sr;
107 sr = 0;
108
109 TTree* ur = new TTree(0);
110 ur->AddNode(10);
111 ur->AddNode(11);
112 ur->AddNode(20);
113 ur->AddNode(21);
114 delete ur;
115 ur = 0;
116
117
118 // TreePrint(cout, *tr, (IntConvType) NStr::IntToString);
119 // TreeReRoot(*tr10);
120 // TreePrint(cout, *tr10, (IntConvType) NStr::IntToString);
121
122 cout << "Testing Breadth First Traversal" << endl;
123 TreeBreadthFirstTraverse(*tr, TestFunctor2);
124 cout << endl;
125
126 cout << "Testing Depth First Traversal" << endl;
127 TreeDepthFirstTraverse(*tr, TestFunctor1);
128 cout << endl;
129
130 {{
131 unsigned int cnt;
132 TTree::TNodeList_CI it = tr->SubNodeBegin();
133 TTree::TNodeList_CI it_end = tr->SubNodeEnd();
134
135 for (cnt = 0; it != it_end; ++it, ++cnt) {
136 const TTree* t = *it;
137 int v = t->GetValue();
138 assert(v == 10 || v == 11);
139 }
140 assert(cnt == 2);
141 }}
142
143 {{
144 TTree* tr2 = new TTree(*tr);
145 unsigned int cnt;
146 TTree::TNodeList_CI it = tr2->SubNodeBegin();
147 TTree::TNodeList_CI it_end = tr2->SubNodeEnd();
148
149 for (cnt = 0; it != it_end; ++it, ++cnt) {
150 const TTree* t = *it;
151 int v = t->GetValue();
152 assert(v == 10 || v == 11);
153 }
154 assert(cnt == 2);
155 delete tr2;
156 }}
157
158
159 {{
160 TTree::TNodeList_I it = tr->SubNodeBegin();
161 TTree::TNodeList_I it_end = tr->SubNodeEnd();
162
163 for (; it != it_end; ++it) {
164 TTree* t = *it;
165 int v = t->GetValue();
166 if (v == 10)
167 {
168 tr->RemoveNode(t);
169 break;
170 }
171 }
172 }}
173
174 TreeDepthFirstTraverse(*tr, TestFunctor1);
175 cout << endl;
176
177 {{
178 unsigned int cnt;
179 TTree::TNodeList_CI it = tr->SubNodeBegin();
180 TTree::TNodeList_CI it_end = tr->SubNodeEnd();
181
182 for (cnt = 0; it != it_end; ++it, ++cnt) {
183 const TTree* t = *it;
184 int v = t->GetValue();
185 assert(v == 11);
186 }
187 assert(cnt == 1);
188 }}
189
190 delete tr;
191
192 TTree* str = tr = new TTree(0);
193
194 //
195 // 0 - 2
196 // - 4
197 // - 3
198 // - 5
199 // - 6
200 //
201
202 TTree* tr4 = tr->AddNode(2)->AddNode(4);
203 tr = tr->AddNode(3);
204 TTree* tr5 = tr->AddNode(5);
205 TTree* tr6 = tr->AddNode(6);
206
207 cout << "Test Tree: " << endl;
208
209 TreeDepthFirstTraverse(*str, TestFunctor1);
210 cout << endl;
211
212 delete str;
213 str = tr5 = tr4 = tr6; // just to eliminate "unused var" warning
214 }
215
216 struct IdValue
217 {
218 int id;
219
IdValueIdValue220 IdValue() : id(0) {}
IdValueIdValue221 IdValue(int v) : id(v) {}
222
operator intIdValue223 operator int() const { return id; }
GetIdIdValue224 int GetId() const { return id; }
225 };
226
227 // static string s_IdValueToStr(const IdValue& idv)
228 // {
229 // return NStr::IntToString(idv.id);
230 // }
231
232
s_TEST_CountNodes()233 static void s_TEST_CountNodes()
234 {
235 typedef CTreeNode<int> TTree;
236
237 // 0 - 10 - 20
238 // - 21 - 30
239 // - 31 - 40
240 // - 41
241 // - 42
242 // - 11 - 22
243 // - 23
244 // - 24
245 // - 25
246
247 std::unique_ptr<TTree> root( new TTree(0) );
248
249 TTree* node10 = root->AddNode(10);
250 node10->AddNode(20);
251
252 TTree* node21 = node10->AddNode(21);
253 node21->AddNode(30);
254
255 TTree* node31 = node21->AddNode(31);
256 node31->AddNode(40);
257 node31->AddNode(41);
258 node31->AddNode(42);
259
260 TTree* node11 = root->AddNode(11);
261 node11->AddNode(22);
262 node11->AddNode(23);
263 node11->AddNode(24);
264 node11->AddNode(25);
265
266 assert( root->CountNodes() == 2 );
267
268 assert( root->CountNodes(0) == 1 );
269 assert( root->CountNodes(0, TTree::fOnlyLeafs) == 0 );
270 assert( root->CountNodes(0, TTree::fOnlyLeafs | TTree::fCumulative) == 0 );
271 assert( root->CountNodes(0, TTree::fCumulative) == 1 );
272
273 assert( root->CountNodes(1) == 2);
274 assert( root->CountNodes(1, TTree::fOnlyLeafs) == 0 );
275 assert( root->CountNodes(1, TTree::fOnlyLeafs | TTree::fCumulative) == 0 );
276 assert( root->CountNodes(1, TTree::fCumulative) == 3 );
277
278 assert( root->CountNodes(2) == 6 );
279 assert( root->CountNodes(2, TTree::fOnlyLeafs) == 5 );
280 assert( root->CountNodes(2, TTree::fOnlyLeafs | TTree::fCumulative) == 5 );
281 assert( root->CountNodes(2, TTree::fCumulative) == 9 );
282
283 assert( root->CountNodes(3) == 2 );
284 assert( root->CountNodes(3, TTree::fOnlyLeafs) == 1 );
285 assert( root->CountNodes(3, TTree::fOnlyLeafs | TTree::fCumulative) == 6 );
286 assert( root->CountNodes(3, TTree::fCumulative) == 11 );
287
288 assert( root->CountNodes(4) == 3 );
289 assert( root->CountNodes(4, TTree::fOnlyLeafs) == 3 );
290 assert( root->CountNodes(4, TTree::fOnlyLeafs | TTree::fCumulative) == 9 );
291 assert( root->CountNodes(4, TTree::fCumulative) == 14 );
292
293 assert( root->CountNodes(100) == 0 );
294 return;
295 }
296
297
Run(void)298 int CTestApplication::Run(void)
299 {
300
301
302 // CExceptionReporterStream reporter(cerr);
303 // CExceptionReporter::SetDefault(&reporter);
304 // CExceptionReporter::EnableDefault(false);
305 // CExceptionReporter::EnableDefault(true);
306 // CExceptionReporter::SetDefault(0);
307
308 /*
309 CExceptionReporter::EnableDefault(true);
310 cerr << endl;
311 NCBI_REPORT_EXCEPTION(
312 "****** default reporter (stream) ******",e);
313
314 CExceptionReporter::SetDefault(0);
315 cerr << endl;
316 NCBI_REPORT_EXCEPTION(
317 "****** default reporter (diag) ******",e);
318 */
319
320 s_TEST_Tree();
321 s_TEST_CountNodes();
322
323 return 0;
324 }
325
326
327 /////////////////////////////////
328 // MAIN
329 //
330
main(int argc,const char * argv[])331 int main(int argc, const char* argv[])
332 {
333 return CTestApplication().AppMain(argc, argv);
334 }
335