1 //#include "stdafx.h"
2 #include "tree.h"
3 #include "multitree.h"
4 #include "unique_tree.h"
5 #include <cassert>
6 #include <string>
7 #include <iostream>
8 using namespace tcl;
9 namespace utility
10 {
11 template<typename T> void load_tree(T& alpha_tree );
12 template<typename T> void traverse_tree(T& alpha_tree);
13
14 template<typename T> void print_tree(T& alpha_tree, const int depth)
15 {
16 std::cout << alpha_tree.get()->get_text() << std::endl;
17
18 typename T::const_iterator it = alpha_tree.begin(), it_end = alpha_tree.end();
19 for ( ; it != it_end; ++it ) {
20 for ( int i = 0; i < depth; ++i ) {
21 T* parent = &alpha_tree;
22 for ( int j = depth - 1; j > i; --j )
23 parent = parent->parent();
24
25 std::cout << (is_last_child(parent) ? " " : "|");
26
27 std::cout << std::string(2, ' ');
28 }
29 std::cout << "|" << std::endl;
30 std::cout << std::string(depth * 3 + 1, ' ') << "- ";
31 print_tree(*it.node(), depth + 1);
32 }
33 }
34
35 template<typename T> bool is_last_child(const T* node)
36 {
37 const T* parent = node->parent();
38 typename T::const_iterator it = parent->end();
39 --it;
40 return it->get_text() == node->get()->get_text();
41 }
42 }
43
44 class CAlpha
45 {
46 public:
47 CAlpha() {}
48 CAlpha(const std::string& text_ ) : text(text_) {}
49 CAlpha(const char* text_ ) : text(text_) {}
50 ~CAlpha() {}
51
52 friend bool operator < (const CAlpha& lhs, const CAlpha& rhs)
53 { return lhs.get_text() < rhs.get_text(); }
54 std::string get_text() const { return text; }
55
56 private:
57 std::string text;
58 };
59
60 int main(int argc, char* argv[])
61 {
62 // load and print tree<>
63 tcl::tree<CAlpha> alpha_tree(CAlpha("tree<>"));
64
65 utility::load_tree( alpha_tree );
66 utility::print_tree(alpha_tree, 0);
67 utility::traverse_tree(alpha_tree);
68 std::cout << std::endl << std::endl << std::endl;
69
70 // load and print multitree<>
71 tcl::multitree<CAlpha> alpha_multitree(CAlpha("multitree<>"));
72
73 utility::load_tree( alpha_multitree );
74 utility::print_tree( alpha_multitree, 0 );
75 utility::traverse_tree(alpha_multitree);
76 std::cout << std::endl << std::endl << std::endl;
77
78 // load and print unique_tree<>
79 tcl::unique_tree<CAlpha> alpha_uniquetree(CAlpha("unique_tree<>"));
80
81 utility::load_tree( alpha_uniquetree );
82 utility::print_tree( alpha_uniquetree, 0 );
83 utility::traverse_tree(alpha_uniquetree);
84 std::cout << std::endl << std::endl << std::endl;
85
86 return 0;
87 }
88
89 template<typename T> void utility::load_tree(T& alpha_tree)
90 {
91 // create a child iterator
92 typename T::iterator it;
93
94 // insert first node, A, and keep an iterator to it's node
95 it = alpha_tree.insert(CAlpha("A"));
96 assert(it != alpha_tree.end() && it->get_text() == "A" );
97 // try to insert another A. Should fail for tree & unique_tree
98 it = alpha_tree.insert(CAlpha("A"));
99 if ( it == alpha_tree.end() )
100 std::cout << alpha_tree.get()->get_text() << ": Couldn't insert second A." << std::endl;
101
102 // insert D and E under A
103 it = alpha_tree.begin();
104 assert(it != alpha_tree.end() && it->get_text() == "A");
105 typename T::iterator child_it = it.node()->insert(CAlpha("D"));
106 it.node()->insert(CAlpha("E"));
107 assert(child_it != it.node()->end() && child_it->get_text() == "D");
108
109 it = child_it;
110 // insert J under D
111 it.node()->insert(CAlpha("J"));
112 // insert K under D and remember inserted node
113 child_it = it.node()->insert(CAlpha("K"));
114 assert(child_it != it.node()->end() && child_it->get_text() == "K");
115 // insert R and S under K
116 child_it.node()->insert(CAlpha("R"));
117 child_it.node()->insert(CAlpha("S"));
118
119 // increment it (now at D) to point to E
120 ++it;
121 // insert L under E
122 it.node()->insert(CAlpha("L"));
123
124 it = alpha_tree.insert(CAlpha("B"));
125 // insert second E and F under B
126 child_it = it.node()->insert(CAlpha("E")); // should fail for unique_tree
127 if ( child_it == it.node()->end() )
128 std::cout << alpha_tree.get()->get_text() << ": Couldn't insert second E." << std::endl;
129 child_it = it.node()->insert(CAlpha("F"));
130 // insert M under F
131 it = child_it;
132 child_it = it.node()->insert(CAlpha("M"));
133 // insert T and U under M
134 child_it.node()->insert(CAlpha("T"));
135 child_it.node()->insert(CAlpha("U"));
136
137 // insert N under F (it still points to F)
138 child_it = it.node()->insert(CAlpha("N"));
139 // insert second U and V under N
140 if ( child_it.node()->insert(CAlpha("U")) == child_it.node()->end() ) // should fail for unique_tree
141 std::cout << alpha_tree.get()->get_text() << ": Couldn't insert second U." << std::endl;
142
143 child_it.node()->insert(CAlpha("V"));
144
145 it = alpha_tree.insert(CAlpha("C"));
146 // insert G and H under C
147 it.node()->insert(CAlpha("G"));
148 child_it = it.node()->insert(CAlpha("H"));
149 // insert O under H
150 it = child_it;
151 child_it = it.node()->insert(CAlpha("O"));
152 // try to insert another O
153 child_it = it.node()->insert(CAlpha("O")); // should fail for tree/unique_tree
154 if ( child_it == it.node()->end() )
155 std::cout << alpha_tree.get()->get_text() << ": Couldn't insert second O." << std::endl;
156
157 child_it = it.node()->begin();
158 assert(child_it != it.node()->end() && child_it->get_text() == "O");
159 // insert W under O
160 child_it.node()->insert(CAlpha("W"));
161 // insert P under H
162 it.node()->insert(CAlpha("P"));
163
164 // insert I under C using parent of H (which is C)
165 child_it = it.node()->parent()->insert(CAlpha("I"));
166 assert(child_it != it.node()->parent()->end() && child_it->get_text() == "I");
167 // insert second I under I
168 it = child_it;
169 child_it = it.node()->insert(CAlpha("I")); // should fail for unique tree
170 if ( child_it == it.node()->end() )
171 std::cout << alpha_tree.get()->get_text() << ": Couldn't insert second I." << std::endl;
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 child_it.node()->insert(CAlpha("Y"));
180 child_it.node()->insert(CAlpha("Z"));
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->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
