1 //#include "stdafx.h"
2 #include "sequential_tree.h"
3 #include <cassert>
4 #include <string>
5 #include <iostream>
6 class CAlpha;
7 using namespace tcl;
8 namespace utility {
9 void load_tree(tcl::sequential_tree<CAlpha>& alpha_tree );
10 template<typename T> void traverse_tree(T& alpha_tree);
11
12 template<typename T> void print_tree(T& alpha_tree, const int depth)
13 {
14 std::cout << alpha_tree.get()->get_text() << std::endl;
15
16 typename T::const_iterator it = alpha_tree.begin(), it_end = alpha_tree.end();
17 for ( ; it != it_end; ++it ) {
18 for ( int i = 0; i < depth; ++i ) {
19 T* parent = &alpha_tree;
20 for ( int j = depth - 1; j > i; --j )
21 parent = parent->parent();
22
23 std::cout << (is_last_child(parent) ? " " : "|");
24
25 std::cout << std::string(2, ' ');
26 }
27 std::cout << "|" << std::endl;
28 std::cout << std::string(depth * 3 + 1, ' ') << "- ";
29 print_tree(*it.node(), depth + 1);
30 }
31 }
32
33 template<typename T> bool is_last_child(const T* node)
34 {
35 const T* parent = node->parent();
36 typename T::const_iterator it = parent->end();
37 --it;
38 return it->get_text() == node->get()->get_text();
39 }
40 }
41
42 class CAlpha
43 {
44 public:
45 CAlpha() {}
46 CAlpha(const std::string& text_ ) : text(text_) {}
47 CAlpha(const char* text_ ) : text(text_) {}
48 ~CAlpha() {}
49
50 friend bool operator < (const CAlpha& lhs, const CAlpha& rhs)
51 { return lhs.get_text() < rhs.get_text(); }
52 std::string get_text() const { return text; }
53
54 private:
55 std::string text;
56 };
57
58 bool pred_fcn(const CAlpha& lhs, const CAlpha& rhs)
59 {
60 return lhs.get_text() > rhs.get_text();
61 }
62
63 struct comp_functor
64 {
65 bool operator() (const CAlpha& lhs, const CAlpha& rhs) const
66 {
67 return lhs.get_text() > rhs.get_text();
68 }
69 };
70
71 int main(int argc, char* argv[])
72 {
73 // load and print tree<>
74 tcl::sequential_tree<CAlpha> alpha_tree(CAlpha("sequential_tree<>"));
75
76 utility::load_tree( alpha_tree );
77 utility::print_tree(alpha_tree, 0);
78 std::cout << std::endl << std::endl << std::endl;
79
80 alpha_tree.sort();
81 std::cout << "Tree root sorted ascending" << std::endl;
82 utility::print_tree(alpha_tree, 0);
83 std::cout << std::endl << std::endl << std::endl;
84
85 alpha_tree.sort_descendants();
86 std::cout << "Whole tree sorted ascending" << std::endl;
87 utility::print_tree(alpha_tree, 0);
88 std::cout << std::endl << std::endl << std::endl;
89
90 alpha_tree.sort(&pred_fcn);
91 std::cout << "Tree root sorted descending" << std::endl;
92 utility::print_tree(alpha_tree, 0);
93 std::cout << std::endl << std::endl << std::endl;
94
95 alpha_tree.sort_descendants(comp_functor());
96 std::cout << "Whole tree sorted descending" << std::endl;
97 utility::print_tree(alpha_tree, 0);
98 std::cout << std::endl << std::endl << std::endl;
99
100 utility::traverse_tree(alpha_tree);
101 std::cout << std::endl << std::endl << std::endl;
102
103 return 0;
104 }
105
106 void utility::load_tree(tcl::sequential_tree<CAlpha>& alpha_tree)
107 {
108 // create a child iterator
109 tcl::sequential_tree<CAlpha>::iterator it;
110
111 // insert first node, A, and keep an iterator to it's node
112 it = alpha_tree.insert(CAlpha("A"));
113 assert(it != alpha_tree.end() && it->get_text() == "A" );
114
115 // insert D and E under A
116 it = alpha_tree.begin();
117 assert(it != alpha_tree.end() && it->get_text() == "A");
118 it.node()->insert(CAlpha("E"));
119 it.node()->insert(CAlpha("D"));
120
121 it = it.node()->begin();
122 ++it;
123 // insert J under D
124 it.node()->insert(CAlpha("J"));
125 // insert K under D and remember inserted node
126 tcl::sequential_tree<CAlpha>::iterator child_it = it.node()->insert(CAlpha("K"));
127 assert(child_it != it.node()->end() && child_it->get_text() == "K");
128 // insert R and S under K
129 child_it.node()->insert(CAlpha("S"));
130 child_it.node()->insert(CAlpha("R"));
131
132 // increment it (now at D) to point to E
133 --it;
134 // insert L under E
135 it.node()->insert(CAlpha("L"));
136
137 it = alpha_tree.insert(CAlpha("B"));
138 // insert F under B
139 child_it = it.node()->insert(CAlpha("F"));
140 // insert M under F
141 it = child_it;
142 child_it = it.node()->insert(CAlpha("M"));
143 // insert T and U under M
144 child_it.node()->insert(CAlpha("T"));
145 child_it.node()->insert(CAlpha("U"));
146
147 // insert N under F (it still points to F)
148 child_it = it.node()->insert(CAlpha("N"));
149 // insert V under N
150 child_it.node()->insert(CAlpha("V"));
151
152 it = alpha_tree.begin();
153 ++it;
154 it = alpha_tree.insert(it, CAlpha("C"));
155 // insert G and H under C
156 it.node()->insert(CAlpha("G"));
157 child_it = it.node()->insert(CAlpha("H"));
158 // insert O under H
159 it = child_it;
160 child_it = it.node()->insert(CAlpha("O"));
161
162 child_it = it.node()->begin();
163 assert(child_it != it.node()->end() && child_it->get_text() == "O");
164 // insert W under O
165 child_it.node()->insert(CAlpha("W"));
166 // insert P under H
167 it.node()->insert(CAlpha("P"));
168
169 // insert I under C using parent of H (which is C)
170 child_it = it.node()->parent()->insert(CAlpha("I"));
171 it = child_it;
172
173 // insert Q under original I
174 child_it = it.node()->insert(CAlpha("Q"));
175 // insert X under Q
176 it = child_it;
177 child_it = it.node()->insert(CAlpha("X"));
178 // insert Y and Z under X
179 it = child_it.node()->insert(CAlpha("Z"));
180 child_it.node()->insert(it, CAlpha("Y"));
181
182 std::cout << std::endl << std::endl;
183 }
184
185 template<typename T> void utility::traverse_tree(T& alpha_tree)
186 {
187 std::cout << std::endl;
188
189 std::cout << alpha_tree.get()->get_text() << "::pre_order_iterator" << std::endl;
190 typename T::pre_order_iterator pre_it = alpha_tree.pre_order_begin();
191 for ( ; pre_it != alpha_tree.pre_order_end(); ++pre_it ) {
192 std::cout << pre_it->get_text() << " ";
193 }
194 std::cout << std::endl << std::endl;
195
196 std::cout << alpha_tree.get()->get_text() << "::post_order_iterator" << std::endl;
197 typename T::const_post_order_iterator post_it = alpha_tree.post_order_begin();
198 for ( ; post_it != alpha_tree.post_order_end(); ++post_it ) {
199 std::cout << post_it.node()->get()->get_text() << " ";
200 }
201 std::cout << std::endl << std::endl;
202
203 std::cout << alpha_tree.get()->get_text() << "::level_order_iterator" << std::endl;
204 typename T::const_level_order_iterator level_it = alpha_tree.level_order_begin();
205 for ( ; level_it != alpha_tree.level_order_end(); ++level_it ) {
206 std::cout << level_it->get_text() << " ";
207 }
208
209 std::cout << std::endl;
210 }
211