1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
|
#include <iostream>
#include <glibmm.h>
typedef Glib::NodeTree<std::string> type_nodetree_string;
static bool node_build_string(type_nodetree_string& node, std::string& string)
{
string += node.data();
return false;
}
int main()
{
std::list<std::string> alma;
std::string tstring, cstring;
type_nodetree_string* root;
type_nodetree_string* node;
type_nodetree_string* node_B;
type_nodetree_string* node_D;
type_nodetree_string* node_F;
type_nodetree_string* node_G;
type_nodetree_string* node_J;
std::string str_A("A");
std::string str_B("B");
std::string str_C("C");
std::string str_D("D");
std::string str_E("E");
std::string str_F("F");
std::string str_G("G");
std::string str_H("H");
std::string str_I("I");
std::string str_J("J");
std::string str_K("K");
std::string str_empty;
root = new type_nodetree_string(str_A);
g_assert(root->depth() == 1 && root->get_max_height() == 1);
node_B = new type_nodetree_string(str_B);
root->append(*node_B);
g_assert(root->first_child() == node_B);
node_B->append_data(str_E);
node_B->prepend_data(str_C);
node_D = &node_B->insert(1, *(new type_nodetree_string(str_D)));
node_F = new type_nodetree_string(str_F);
root->append(*node_F);
g_assert(root->first_child()->next_sibling() == node_F);
node_G = new type_nodetree_string(str_G);
node_F->append(*node_G);
node_J = new type_nodetree_string(str_J);
node_G->prepend(*node_J);
node_G->insert(42, *(new type_nodetree_string(str_K)));
node_G->insert_data(0, str_H);
node_G->insert(1, *(new type_nodetree_string(str_I)));
g_assert(root->depth() == 1);
g_assert(root->get_max_height() == 4);
g_assert(node_G->first_child()->next_sibling()->depth() == 4);
g_assert(root->node_count(type_nodetree_string::TRAVERSE_LEAVES) == 7);
g_assert(root->node_count(type_nodetree_string::TRAVERSE_NON_LEAVES) == 4);
g_assert(root->node_count(type_nodetree_string::TRAVERSE_ALL) == 11);
g_assert(node_F->get_max_height() == 3);
g_assert(node_G->child_count() == 4);
g_assert(root->find_child(str_F, type_nodetree_string::TRAVERSE_ALL) == node_F);
g_assert(root->find(str_I, Glib::TRAVERSE_LEVEL_ORDER, type_nodetree_string::TRAVERSE_NON_LEAVES) == NULL);
g_assert(root->find(str_J, Glib::TRAVERSE_IN_ORDER, type_nodetree_string::TRAVERSE_LEAVES) == node_J);
for(guint i = 0; i < node_B->child_count(); i++)
{
node = node_B->nth_child(i);
g_assert(node->data() == std::string(1, ('C' + i)));
}
for(guint i = 0; i < node_G->child_count(); i++)
g_assert(node_G->child_position(*node_G->nth_child(i)) == (int)i);
/* we have built: A
* / \
* B F
* / | \ \
* C D E G
* / /\ \
* H I J K
*
* for in-order traversal, 'G' is considered to be the "left"
* child of 'F', which will cause 'F' to be the last node visited.
*/
tstring.clear();
root->traverse(sigc::bind(sigc::ptr_fun(node_build_string), sigc::ref(tstring)), Glib::TRAVERSE_PRE_ORDER, type_nodetree_string::TRAVERSE_ALL, -1);
g_assert(tstring == "ABCDEFGHIJK");
tstring.clear();
root->traverse(sigc::bind(sigc::ptr_fun(node_build_string), sigc::ref(tstring)), Glib::TRAVERSE_POST_ORDER, type_nodetree_string::TRAVERSE_ALL, -1);
g_assert(tstring == "CDEBHIJKGFA");
tstring.clear();
root->traverse(sigc::bind(sigc::ptr_fun(node_build_string), sigc::ref(tstring)), Glib::TRAVERSE_IN_ORDER, type_nodetree_string::TRAVERSE_ALL, -1);
g_assert(tstring == "CBDEAHGIJKF");
tstring.clear();
root->traverse(sigc::bind(sigc::ptr_fun(node_build_string), sigc::ref(tstring)), Glib::TRAVERSE_LEVEL_ORDER, type_nodetree_string::TRAVERSE_ALL, -1);
g_assert(tstring == "ABFCDEGHIJK");
tstring.clear();
root->traverse(sigc::bind(sigc::ptr_fun(node_build_string), sigc::ref(tstring)), Glib::TRAVERSE_LEVEL_ORDER, type_nodetree_string::TRAVERSE_LEAVES, -1);
g_assert(tstring == "CDEHIJK");
tstring.clear();
root->traverse(sigc::bind(sigc::ptr_fun(node_build_string), sigc::ref(tstring)), Glib::TRAVERSE_PRE_ORDER, type_nodetree_string::TRAVERSE_NON_LEAVES, -1);
g_assert(tstring == "ABFG");
tstring.clear();
node_B->reverse_children();
node_G->reverse_children();
root->traverse(sigc::bind(sigc::ptr_fun(node_build_string), sigc::ref(tstring)), Glib::TRAVERSE_LEVEL_ORDER, type_nodetree_string::TRAVERSE_ALL, -1);
g_assert(tstring == "ABFEDCGKJIH");
tstring.clear();
/* TODO:
node = root->copy();
g_assert(root->node_count(type_nodetree_string::TRAVERSE_ALL) == node->node_count(type_nodetree_string::TRAVERSE_ALL));
g_assert(root->get_max_height() == node->get_max_height());
root->traverse(sigc::bind(sigc::ptr_fun(node_build_string), sigc::ref(tstring)), Glib::TRAVERSE_IN_ORDER, type_nodetree_string::TRAVERSE_ALL, -1);
node->traverse(sigc::bind(sigc::ptr_fun(node_build_string), sigc::ref(cstring)), Glib::TRAVERSE_IN_ORDER, type_nodetree_string::TRAVERSE_ALL, -1);
g_assert(tstring == cstring);
delete node;
*/
delete root;
/* allocation tests */
root = new type_nodetree_string(str_empty);
node = root;
for(guint i = 0; i < 2048; i++)
{
node->append(*(new type_nodetree_string(str_empty)));
if((i % 5) == 4)
node = node->first_child()->next_sibling();
}
g_assert(root->get_max_height() > 100);
g_assert(root->node_count(type_nodetree_string::TRAVERSE_ALL) == 1 + 2048);
delete root;
return 0;
}
|
