1 | // =============================================================== // |
---|
2 | // // |
---|
3 | // File : adtree.cxx // |
---|
4 | // Purpose : tree functions // |
---|
5 | // // |
---|
6 | // Institute of Microbiology (Technical University Munich) // |
---|
7 | // http://www.arb-home.de/ // |
---|
8 | // // |
---|
9 | // =============================================================== // |
---|
10 | |
---|
11 | #include <arb_progress.h> |
---|
12 | #include "gb_local.h" |
---|
13 | #include <arb_strarray.h> |
---|
14 | #include <set> |
---|
15 | #include <limits.h> |
---|
16 | #include <arb_global_defs.h> |
---|
17 | #include <arb_strbuf.h> |
---|
18 | #include <arb_diff.h> |
---|
19 | #include <arb_defs.h> |
---|
20 | #include <arb_match.h> |
---|
21 | #include "TreeNode.h" |
---|
22 | |
---|
23 | #define GBT_PUT_DATA 1 |
---|
24 | #define GBT_GET_SIZE 0 |
---|
25 | |
---|
26 | GBDATA *GBT_get_tree_data(GBDATA *gb_main) { |
---|
27 | return GBT_find_or_create(gb_main, "tree_data", 7); |
---|
28 | } |
---|
29 | |
---|
30 | // ---------------------- |
---|
31 | // remove leafs |
---|
32 | |
---|
33 | TreeNode *GBT_remove_leafs(TreeNode *tree, GBT_TreeRemoveType mode, const GB_HASH *species_hash, int *removed, int *groups_removed) { // @@@ add tests for GBT_remove_leafs() |
---|
34 | /*! Remove leafs from given 'tree'. |
---|
35 | * @param tree tree from which species will be removed |
---|
36 | * @param mode defines what to remove |
---|
37 | * @param species_hash hash translation from leaf-name to species-dbnode (not needed if tree is linked; see GBT_link_tree) |
---|
38 | * @param removed will be incremented for each removed leaf (if !NULL) |
---|
39 | * @param groups_removed will be incremented for each removed group (if !NULL) |
---|
40 | * @return new root node |
---|
41 | * |
---|
42 | * if 'species_hash' is not provided and tree is not linked, |
---|
43 | * the function will silently act strange: |
---|
44 | * - GBT_REMOVE_MARKED and GBT_REMOVE_UNMARKED will remove any leaf |
---|
45 | * - GBT_REMOVE_ZOMBIES and GBT_KEEP_MARKED will remove all leafs |
---|
46 | */ |
---|
47 | |
---|
48 | if (tree->is_leaf) { |
---|
49 | if (tree->name) { |
---|
50 | bool deleteSelf = false; |
---|
51 | GBDATA *gb_node; |
---|
52 | |
---|
53 | if (species_hash) { |
---|
54 | gb_node = (GBDATA*)GBS_read_hash(species_hash, tree->name); |
---|
55 | gb_assert(tree->gb_node == 0); // don't call linked tree with 'species_hash'! |
---|
56 | } |
---|
57 | else gb_node = tree->gb_node; |
---|
58 | |
---|
59 | if (gb_node) { |
---|
60 | if (mode & (GBT_REMOVE_MARKED|GBT_REMOVE_UNMARKED)) { |
---|
61 | long flag = GB_read_flag(gb_node); |
---|
62 | deleteSelf = (flag && (mode&GBT_REMOVE_MARKED)) || (!flag && (mode&GBT_REMOVE_UNMARKED)); |
---|
63 | } |
---|
64 | } |
---|
65 | else { // zombie |
---|
66 | if (mode & GBT_REMOVE_ZOMBIES) deleteSelf = true; |
---|
67 | } |
---|
68 | |
---|
69 | if (deleteSelf) { |
---|
70 | gb_assert(!tree->is_root_node()); |
---|
71 | |
---|
72 | TreeRoot *troot = tree->get_tree_root(); |
---|
73 | tree->forget_origin(); |
---|
74 | destroy(tree, troot); |
---|
75 | |
---|
76 | tree = NULL; |
---|
77 | if (removed) (*removed)++; |
---|
78 | } |
---|
79 | } |
---|
80 | } |
---|
81 | else { |
---|
82 | tree->leftson = GBT_remove_leafs(tree->get_leftson(), mode, species_hash, removed, groups_removed); |
---|
83 | tree->rightson = GBT_remove_leafs(tree->get_rightson(), mode, species_hash, removed, groups_removed); |
---|
84 | |
---|
85 | if (tree->leftson) { |
---|
86 | if (!tree->rightson) { // right son deleted |
---|
87 | tree = tree->fixDeletedSon(); |
---|
88 | } |
---|
89 | // otherwise no son deleted |
---|
90 | } |
---|
91 | else if (tree->rightson) { // left son deleted |
---|
92 | tree = tree->fixDeletedSon(); |
---|
93 | } |
---|
94 | else { // everything deleted -> delete self |
---|
95 | if (tree->name && groups_removed) (*groups_removed)++; |
---|
96 | |
---|
97 | TreeRoot *troot = tree->get_tree_root(); |
---|
98 | if (!tree->is_root_node()) tree->forget_origin(); |
---|
99 | tree->forget_relatives(); |
---|
100 | destroy(tree, troot); |
---|
101 | |
---|
102 | tree = NULL; |
---|
103 | } |
---|
104 | } |
---|
105 | |
---|
106 | return tree; |
---|
107 | } |
---|
108 | |
---|
109 | // --------------------- |
---|
110 | // trees order |
---|
111 | |
---|
112 | inline int get_tree_idx(GBDATA *gb_tree) { |
---|
113 | GBDATA *gb_order = GB_entry(gb_tree, "order"); |
---|
114 | int idx = 0; |
---|
115 | if (gb_order) { |
---|
116 | idx = GB_read_int(gb_order); |
---|
117 | gb_assert(idx>0); // invalid index |
---|
118 | } |
---|
119 | return idx; |
---|
120 | } |
---|
121 | |
---|
122 | inline int get_max_tree_idx(GBDATA *gb_treedata) { |
---|
123 | int max_idx = 0; |
---|
124 | for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree)) { |
---|
125 | int idx = get_tree_idx(gb_tree); |
---|
126 | if (idx>max_idx) max_idx = idx; |
---|
127 | } |
---|
128 | return max_idx; |
---|
129 | } |
---|
130 | |
---|
131 | inline GBDATA *get_tree_with_idx(GBDATA *gb_treedata, int at_idx) { |
---|
132 | GBDATA *gb_found = NULL; |
---|
133 | for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree && !gb_found; gb_tree = GB_nextChild(gb_tree)) { |
---|
134 | int idx = get_tree_idx(gb_tree); |
---|
135 | if (idx == at_idx) { |
---|
136 | gb_found = gb_tree; |
---|
137 | } |
---|
138 | } |
---|
139 | return gb_found; |
---|
140 | } |
---|
141 | |
---|
142 | inline GBDATA *get_tree_infrontof_idx(GBDATA *gb_treedata, int infrontof_idx) { |
---|
143 | GBDATA *gb_infrontof = NULL; |
---|
144 | if (infrontof_idx) { |
---|
145 | int best_idx = 0; |
---|
146 | for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree)) { |
---|
147 | int idx = get_tree_idx(gb_tree); |
---|
148 | gb_assert(idx); |
---|
149 | if (idx>best_idx && idx<infrontof_idx) { |
---|
150 | best_idx = idx; |
---|
151 | gb_infrontof = gb_tree; |
---|
152 | } |
---|
153 | } |
---|
154 | } |
---|
155 | return gb_infrontof; |
---|
156 | } |
---|
157 | |
---|
158 | inline GBDATA *get_tree_behind_idx(GBDATA *gb_treedata, int behind_idx) { |
---|
159 | GBDATA *gb_behind = NULL; |
---|
160 | if (behind_idx) { |
---|
161 | int best_idx = INT_MAX; |
---|
162 | for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree)) { |
---|
163 | int idx = get_tree_idx(gb_tree); |
---|
164 | gb_assert(idx); |
---|
165 | if (idx>behind_idx && idx<best_idx) { |
---|
166 | best_idx = idx; |
---|
167 | gb_behind = gb_tree; |
---|
168 | } |
---|
169 | } |
---|
170 | } |
---|
171 | return gb_behind; |
---|
172 | } |
---|
173 | |
---|
174 | inline GB_ERROR set_tree_idx(GBDATA *gb_tree, int idx) { |
---|
175 | GB_ERROR error = NULL; |
---|
176 | GBDATA *gb_order = GB_entry(gb_tree, "order"); |
---|
177 | if (!gb_order) { |
---|
178 | gb_order = GB_create(gb_tree, "order", GB_INT); |
---|
179 | if (!gb_order) error = GB_await_error(); |
---|
180 | } |
---|
181 | if (!error) error = GB_write_int(gb_order, idx); |
---|
182 | return error; |
---|
183 | } |
---|
184 | |
---|
185 | static GB_ERROR reserve_tree_idx(GBDATA *gb_treedata, int idx) { |
---|
186 | GB_ERROR error = NULL; |
---|
187 | GBDATA *gb_tree = get_tree_with_idx(gb_treedata, idx); |
---|
188 | if (gb_tree) { |
---|
189 | error = reserve_tree_idx(gb_treedata, idx+1); |
---|
190 | if (!error) error = set_tree_idx(gb_tree, idx+1); |
---|
191 | } |
---|
192 | return error; |
---|
193 | } |
---|
194 | |
---|
195 | static void ensure_trees_have_order(GBDATA *gb_treedata) { |
---|
196 | GBDATA *gb_main = GB_get_father(gb_treedata); |
---|
197 | |
---|
198 | gb_assert(GB_get_root(gb_main) == gb_main); |
---|
199 | gb_assert(GBT_get_tree_data(gb_main) == gb_treedata); |
---|
200 | |
---|
201 | GB_ERROR error = NULL; |
---|
202 | GBDATA *gb_tree_order_flag = GB_search(gb_main, "/tmp/trees_have_order", GB_INT); |
---|
203 | |
---|
204 | if (!gb_tree_order_flag) error = GB_await_error(); |
---|
205 | else { |
---|
206 | if (GB_read_int(gb_tree_order_flag) == 0) { // not checked yet |
---|
207 | int max_idx = get_max_tree_idx(gb_treedata); |
---|
208 | for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree && !error; gb_tree = GB_nextChild(gb_tree)) { |
---|
209 | if (!get_tree_idx(gb_tree)) { |
---|
210 | error = set_tree_idx(gb_tree, ++max_idx); |
---|
211 | } |
---|
212 | } |
---|
213 | if (!error) error = GB_write_int(gb_tree_order_flag, 1); |
---|
214 | } |
---|
215 | } |
---|
216 | if (error) GBK_terminatef("failed to order trees (Reason: %s)", error); |
---|
217 | } |
---|
218 | |
---|
219 | static void tree_set_default_order(GBDATA *gb_tree) { |
---|
220 | // if 'gb_tree' has no order yet, move it to the bottom (as done previously) |
---|
221 | if (!get_tree_idx(gb_tree)) { |
---|
222 | set_tree_idx(gb_tree, get_max_tree_idx(GB_get_father(gb_tree))+1); |
---|
223 | } |
---|
224 | } |
---|
225 | |
---|
226 | // ----------------------------- |
---|
227 | // tree write functions |
---|
228 | |
---|
229 | GB_ERROR GBT_write_group_name(GBDATA *gb_group_name, const char *new_group_name) { |
---|
230 | GB_ERROR error = 0; |
---|
231 | size_t len = strlen(new_group_name); |
---|
232 | |
---|
233 | if (len >= GB_GROUP_NAME_MAX) { |
---|
234 | error = GBS_global_string("Group name '%s' too long (max %i characters)", new_group_name, GB_GROUP_NAME_MAX); |
---|
235 | } |
---|
236 | else { |
---|
237 | error = GB_write_string(gb_group_name, new_group_name); |
---|
238 | } |
---|
239 | return error; |
---|
240 | } |
---|
241 | |
---|
242 | static GB_ERROR gbt_write_tree_nodes(GBDATA *gb_tree, TreeNode *node, long *startid) { |
---|
243 | // increments '*startid' for each inner node (not for leafs) |
---|
244 | |
---|
245 | GB_ERROR error = NULL; |
---|
246 | |
---|
247 | if (!node->is_leaf) { |
---|
248 | bool node_is_used = false; |
---|
249 | |
---|
250 | if (node->name && node->name[0]) { |
---|
251 | if (!node->gb_node) { |
---|
252 | node->gb_node = GB_create_container(gb_tree, "node"); |
---|
253 | if (!node->gb_node) error = GB_await_error(); |
---|
254 | } |
---|
255 | if (!error) { |
---|
256 | GBDATA *gb_name = GB_search(node->gb_node, "group_name", GB_STRING); |
---|
257 | if (!gb_name) error = GB_await_error(); |
---|
258 | else error = GBT_write_group_name(gb_name, node->name); |
---|
259 | |
---|
260 | node_is_used = true; // wrote groupname -> node is used |
---|
261 | } |
---|
262 | } |
---|
263 | |
---|
264 | if (node->gb_node && !error) { |
---|
265 | if (!node_is_used) { |
---|
266 | GBDATA *gb_nonid = GB_child(node->gb_node); |
---|
267 | while (gb_nonid && strcmp("id", GB_read_key_pntr(gb_nonid)) == 0) { |
---|
268 | gb_nonid = GB_nextChild(gb_nonid); |
---|
269 | } |
---|
270 | if (gb_nonid) node_is_used = true; // found child that is not "id" -> node is used |
---|
271 | } |
---|
272 | |
---|
273 | if (node_is_used) { // set id for used nodes |
---|
274 | error = GBT_write_int(node->gb_node, "id", *startid); |
---|
275 | if (!error) GB_clear_user_flag(node->gb_node, GB_USERFLAG_GHOSTNODE); // mark node as "used" |
---|
276 | } |
---|
277 | else { // delete unused nodes |
---|
278 | error = GB_delete(node->gb_node); |
---|
279 | if (!error) node->gb_node = 0; |
---|
280 | } |
---|
281 | } |
---|
282 | |
---|
283 | (*startid)++; |
---|
284 | if (!error) error = gbt_write_tree_nodes(gb_tree, node->get_leftson(), startid); |
---|
285 | if (!error) error = gbt_write_tree_nodes(gb_tree, node->get_rightson(), startid); |
---|
286 | } |
---|
287 | return error; |
---|
288 | } |
---|
289 | |
---|
290 | static char *gbt_write_tree_rek_new(const TreeNode *node, char *dest, long mode) { |
---|
291 | { |
---|
292 | const char *c1 = node->get_remark(); |
---|
293 | if (c1) { |
---|
294 | if (mode == GBT_PUT_DATA) { |
---|
295 | int c; |
---|
296 | *(dest++) = 'R'; |
---|
297 | while ((c = *(c1++))) { |
---|
298 | if (c == 1) continue; |
---|
299 | *(dest++) = c; |
---|
300 | } |
---|
301 | *(dest++) = 1; |
---|
302 | } |
---|
303 | else { |
---|
304 | dest += strlen(c1) + 2; |
---|
305 | } |
---|
306 | } |
---|
307 | } |
---|
308 | if (node->is_leaf) { |
---|
309 | if (mode == GBT_PUT_DATA) { |
---|
310 | *(dest++) = 'L'; |
---|
311 | if (node->name) strcpy(dest, node->name); |
---|
312 | |
---|
313 | char *c1; |
---|
314 | while ((c1 = (char *)strchr(dest, 1))) { |
---|
315 | *c1 = 2; |
---|
316 | } |
---|
317 | dest += strlen(dest); |
---|
318 | *(dest++) = 1; |
---|
319 | |
---|
320 | return dest; |
---|
321 | } |
---|
322 | else { |
---|
323 | if (node->name) return dest+1+strlen(node->name)+1; // N name term |
---|
324 | return dest+1+1; |
---|
325 | } |
---|
326 | } |
---|
327 | else { |
---|
328 | char buffer[40]; |
---|
329 | sprintf(buffer, "%g,%g;", node->leftlen, node->rightlen); |
---|
330 | if (mode == GBT_PUT_DATA) { |
---|
331 | *(dest++) = 'N'; |
---|
332 | strcpy(dest, buffer); |
---|
333 | dest += strlen(buffer); |
---|
334 | } |
---|
335 | else { |
---|
336 | dest += strlen(buffer)+1; |
---|
337 | } |
---|
338 | dest = gbt_write_tree_rek_new(node->get_leftson(), dest, mode); |
---|
339 | dest = gbt_write_tree_rek_new(node->get_rightson(), dest, mode); |
---|
340 | return dest; |
---|
341 | } |
---|
342 | } |
---|
343 | |
---|
344 | static GB_ERROR gbt_write_tree(GBDATA *gb_main, GBDATA *gb_tree, const char *tree_name, TreeNode *tree) { |
---|
345 | /*! writes a tree to the database. |
---|
346 | * |
---|
347 | * If tree is loaded by function GBT_read_tree(..) then 'tree_name' should be NULL |
---|
348 | * else 'gb_tree' should be set to NULL |
---|
349 | * |
---|
350 | * To copy a tree call GB_copy(dest,source); |
---|
351 | * or set recursively all tree->gb_node variables to zero (that unlinks the tree), |
---|
352 | */ |
---|
353 | |
---|
354 | GB_ERROR error = 0; |
---|
355 | |
---|
356 | if (tree) { |
---|
357 | if (tree_name) { |
---|
358 | if (gb_tree) error = GBS_global_string("can't change name of existing tree (to '%s')", tree_name); |
---|
359 | else { |
---|
360 | error = GBT_check_tree_name(tree_name); |
---|
361 | if (!error) { |
---|
362 | GBDATA *gb_tree_data = GBT_get_tree_data(gb_main); |
---|
363 | gb_tree = GB_search(gb_tree_data, tree_name, GB_CREATE_CONTAINER); |
---|
364 | |
---|
365 | if (!gb_tree) error = GB_await_error(); |
---|
366 | } |
---|
367 | } |
---|
368 | } |
---|
369 | else { |
---|
370 | if (!gb_tree) error = "No tree name given"; |
---|
371 | } |
---|
372 | |
---|
373 | gb_assert(gb_tree || error); |
---|
374 | |
---|
375 | if (!error) { |
---|
376 | // mark all old style tree data for deletion |
---|
377 | GBDATA *gb_node; |
---|
378 | for (gb_node = GB_entry(gb_tree, "node"); gb_node; gb_node = GB_nextEntry(gb_node)) { |
---|
379 | GB_raise_user_flag(gb_node, GB_USERFLAG_GHOSTNODE); // mark as "possibly unused" |
---|
380 | } |
---|
381 | |
---|
382 | // build tree-string and save to DB |
---|
383 | { |
---|
384 | char *t_size = gbt_write_tree_rek_new(tree, 0, GBT_GET_SIZE); // calc size of tree-string |
---|
385 | char *ctree = ARB_calloc<char>(size_t(t_size+1)); // allocate buffer for tree-string |
---|
386 | |
---|
387 | t_size = gbt_write_tree_rek_new(tree, ctree, GBT_PUT_DATA); // write into buffer |
---|
388 | *(t_size) = 0; |
---|
389 | |
---|
390 | bool was_allowed = GB_allow_compression(gb_main, false); |
---|
391 | error = GBT_write_string(gb_tree, "tree", ctree); |
---|
392 | GB_allow_compression(gb_main, was_allowed); |
---|
393 | free(ctree); |
---|
394 | } |
---|
395 | } |
---|
396 | |
---|
397 | if (!error) { |
---|
398 | // save nodes to DB |
---|
399 | long size = 0; |
---|
400 | error = gbt_write_tree_nodes(gb_tree, tree, &size); // reports number of nodes in 'size' |
---|
401 | if (!error) error = GBT_write_int(gb_tree, "nnodes", size); |
---|
402 | |
---|
403 | if (!error) { |
---|
404 | if (!GB_entry(gb_tree, "keep_ghostnodes")) { // see ../PARSIMONY/PARS_main.cxx@keep_ghostnodes |
---|
405 | GBDATA *gb_node; |
---|
406 | GBDATA *gb_node_next; |
---|
407 | |
---|
408 | for (gb_node = GB_entry(gb_tree, "node"); // delete all ghost nodes |
---|
409 | gb_node && !error; |
---|
410 | gb_node = gb_node_next) |
---|
411 | { |
---|
412 | GBDATA *gbd = GB_entry(gb_node, "id"); |
---|
413 | gb_node_next = GB_nextEntry(gb_node); |
---|
414 | if (!gbd || GB_user_flag(gb_node, GB_USERFLAG_GHOSTNODE)) error = GB_delete(gb_node); |
---|
415 | } |
---|
416 | } |
---|
417 | } |
---|
418 | } |
---|
419 | |
---|
420 | if (!error) tree_set_default_order(gb_tree); |
---|
421 | } |
---|
422 | |
---|
423 | return error; |
---|
424 | } |
---|
425 | |
---|
426 | GB_ERROR GBT_write_tree(GBDATA *gb_main, const char *tree_name, TreeNode *tree) { |
---|
427 | return gbt_write_tree(gb_main, NULL, tree_name, tree); |
---|
428 | } |
---|
429 | GB_ERROR GBT_overwrite_tree(GBDATA *gb_tree, TreeNode *tree) { |
---|
430 | return gbt_write_tree(GB_get_root(gb_tree), gb_tree, NULL, tree); |
---|
431 | } |
---|
432 | |
---|
433 | static GB_ERROR write_tree_remark(GBDATA *gb_tree, const char *remark) { |
---|
434 | return GBT_write_string(gb_tree, "remark", remark); |
---|
435 | } |
---|
436 | GB_ERROR GBT_write_tree_remark(GBDATA *gb_main, const char *tree_name, const char *remark) { |
---|
437 | return write_tree_remark(GBT_find_tree(gb_main, tree_name), remark); |
---|
438 | } |
---|
439 | |
---|
440 | GB_ERROR GBT_log_to_tree_remark(GBDATA *gb_tree, const char *log_entry, bool stamp) { |
---|
441 | /*! append 'log_entry' to tree comment |
---|
442 | * @param gb_tree the tree |
---|
443 | * @param log_entry text to append |
---|
444 | * @param stamp true -> prefix date before 'log_entry' |
---|
445 | * @return error in case of failure |
---|
446 | */ |
---|
447 | GB_ERROR error = NULL; |
---|
448 | const char *old_remark = GBT_read_char_pntr(gb_tree, "remark"); |
---|
449 | if (!old_remark && GB_have_error()) { |
---|
450 | error = GB_await_error(); |
---|
451 | } |
---|
452 | else { |
---|
453 | char *new_remark = GBS_log_action_to(old_remark, log_entry, stamp); |
---|
454 | error = write_tree_remark(gb_tree, new_remark); |
---|
455 | free(new_remark); |
---|
456 | } |
---|
457 | return error; |
---|
458 | } |
---|
459 | GB_ERROR GBT_log_to_tree_remark(GBDATA *gb_main, const char *tree_name, const char *log_entry, bool stamp) { |
---|
460 | /*! append 'log_entry' to tree comment |
---|
461 | * @param gb_main database |
---|
462 | * @param tree_name name of tree |
---|
463 | * @param log_entry text to append |
---|
464 | * @param stamp true -> prefix date before 'log_entry' |
---|
465 | * @return error in case of failure |
---|
466 | */ |
---|
467 | GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name); |
---|
468 | return gb_tree |
---|
469 | ? GBT_log_to_tree_remark(gb_tree, log_entry, stamp) |
---|
470 | : GBS_global_string("No such tree (%s)", tree_name); |
---|
471 | } |
---|
472 | |
---|
473 | GB_ERROR GBT_write_tree_with_remark(GBDATA *gb_main, const char *tree_name, TreeNode *tree, const char *remark) { |
---|
474 | GB_ERROR error = GBT_write_tree(gb_main, tree_name, tree); |
---|
475 | if (!error && remark) error = GBT_write_tree_remark(gb_main, tree_name, remark); |
---|
476 | return error; |
---|
477 | } |
---|
478 | |
---|
479 | // ---------------------------- |
---|
480 | // tree read functions |
---|
481 | |
---|
482 | static TreeNode *gbt_read_tree_rek(char **data, long *startid, GBDATA **gb_tree_nodes, const TreeRoot *troot, int size_of_tree, GB_ERROR& error) { |
---|
483 | TreeNode *node = NULL; |
---|
484 | if (!error) { |
---|
485 | node = troot->makeNode(); |
---|
486 | |
---|
487 | char c = *((*data)++); |
---|
488 | char *p1; |
---|
489 | |
---|
490 | if (c=='R') { |
---|
491 | p1 = strchr(*data, 1); |
---|
492 | *(p1++) = 0; |
---|
493 | node->set_remark(*data); |
---|
494 | c = *(p1++); |
---|
495 | *data = p1; |
---|
496 | } |
---|
497 | |
---|
498 | |
---|
499 | if (c=='N') { |
---|
500 | p1 = (char *)strchr(*data, ','); |
---|
501 | *(p1++) = 0; |
---|
502 | node->leftlen = GB_atof(*data); |
---|
503 | *data = p1; |
---|
504 | p1 = (char *)strchr(*data, ';'); |
---|
505 | *(p1++) = 0; |
---|
506 | node->rightlen = GB_atof(*data); |
---|
507 | *data = p1; |
---|
508 | if ((*startid < size_of_tree) && (node->gb_node = gb_tree_nodes[*startid])) { |
---|
509 | GBDATA *gb_group_name = GB_entry(node->gb_node, "group_name"); |
---|
510 | if (gb_group_name) { |
---|
511 | node->name = GB_read_string(gb_group_name); |
---|
512 | if (!node->name || !node->name[0]) { |
---|
513 | char *auto_rename = ARB_strdup("<missing groupname>"); |
---|
514 | GBDATA *gb_main = GB_get_root(gb_group_name); |
---|
515 | |
---|
516 | const char *warn; |
---|
517 | if (!node->name) { |
---|
518 | warn = GBS_global_string("Unreadable 'group_name' detected (Reason: %s)", GB_await_error()); |
---|
519 | } |
---|
520 | else { |
---|
521 | warn = "Empty groupname detected"; |
---|
522 | } |
---|
523 | warn = GBS_global_string("%s\nGroup has been named '%s'", warn, auto_rename); |
---|
524 | GBT_message(gb_main, warn); |
---|
525 | |
---|
526 | GB_ERROR rename_error = GB_write_string(gb_group_name, auto_rename); |
---|
527 | if (rename_error) { |
---|
528 | GBT_message(gb_main, GBS_global_string("Failed to name group (Reason: %s)", rename_error)); |
---|
529 | } |
---|
530 | node->name = auto_rename; |
---|
531 | } |
---|
532 | } |
---|
533 | } |
---|
534 | (*startid)++; |
---|
535 | node->leftson = gbt_read_tree_rek(data, startid, gb_tree_nodes, troot, size_of_tree, error); |
---|
536 | if (!node->leftson) freenull(node); |
---|
537 | else { |
---|
538 | node->rightson = gbt_read_tree_rek(data, startid, gb_tree_nodes, troot, size_of_tree, error); |
---|
539 | if (!node->rightson) { |
---|
540 | freenull(node->leftson); |
---|
541 | freenull(node); |
---|
542 | } |
---|
543 | else { |
---|
544 | node->leftson->father = node; |
---|
545 | node->rightson->father = node; |
---|
546 | } |
---|
547 | } |
---|
548 | } |
---|
549 | else if (c=='L') { |
---|
550 | node->is_leaf = true; |
---|
551 | p1 = (char *)strchr(*data, 1); |
---|
552 | |
---|
553 | gb_assert(p1); |
---|
554 | gb_assert(p1[0] == 1); |
---|
555 | |
---|
556 | *p1 = 0; |
---|
557 | node->name = ARB_strdup(*data); |
---|
558 | *data = p1+1; |
---|
559 | } |
---|
560 | else { |
---|
561 | if (!c) { |
---|
562 | error = "Unexpected end of tree definition."; |
---|
563 | } |
---|
564 | else { |
---|
565 | error = GBS_global_string("Can't interpret tree definition (expected 'N' or 'L' - not '%c')", c); |
---|
566 | } |
---|
567 | freenull(node); |
---|
568 | } |
---|
569 | } |
---|
570 | gb_assert(contradicted(node, error)); |
---|
571 | return node; |
---|
572 | } |
---|
573 | |
---|
574 | |
---|
575 | static TreeNode *read_tree_and_size_internal(GBDATA *gb_tree, GBDATA *gb_ctree, const TreeRoot *troot, int node_count, GB_ERROR& error) { |
---|
576 | GBDATA **gb_tree_nodes; |
---|
577 | TreeNode *node = 0; |
---|
578 | |
---|
579 | ARB_calloc(gb_tree_nodes, node_count); |
---|
580 | if (gb_tree) { |
---|
581 | GBDATA *gb_node; |
---|
582 | |
---|
583 | for (gb_node = GB_entry(gb_tree, "node"); gb_node && !error; gb_node = GB_nextEntry(gb_node)) { |
---|
584 | long i; |
---|
585 | GBDATA *gbd = GB_entry(gb_node, "id"); |
---|
586 | if (!gbd) continue; |
---|
587 | |
---|
588 | i = GB_read_int(gbd); |
---|
589 | if (i<0 || i >= node_count) { |
---|
590 | error = "An inner node of the tree is corrupt"; |
---|
591 | } |
---|
592 | else { |
---|
593 | gb_tree_nodes[i] = gb_node; |
---|
594 | } |
---|
595 | } |
---|
596 | } |
---|
597 | if (!error) { |
---|
598 | char * const treeString = GB_read_string(gb_ctree); |
---|
599 | if (!treeString) { |
---|
600 | error = GB_await_error(); |
---|
601 | } |
---|
602 | else { |
---|
603 | char *ts = treeString; |
---|
604 | long id = 0; |
---|
605 | node = gbt_read_tree_rek(&ts, &id, gb_tree_nodes, troot, node_count, error); |
---|
606 | } |
---|
607 | free(treeString); |
---|
608 | } |
---|
609 | |
---|
610 | free(gb_tree_nodes); |
---|
611 | |
---|
612 | if (node) { |
---|
613 | if (node->is_named_group()) { |
---|
614 | // workaround for #753: |
---|
615 | GBDATA *gb_group = node->gb_node; |
---|
616 | GBDATA *gb_main = GB_get_root(gb_group); |
---|
617 | GBDATA *gb_group_name = GB_entry(gb_group, "group_name"); |
---|
618 | |
---|
619 | gb_assert(gb_group_name); |
---|
620 | if (gb_group_name) { |
---|
621 | char *groupAtRoot_name = GB_read_string(gb_group_name); |
---|
622 | |
---|
623 | GBT_message(gb_main, GBS_global_string("Warning: invalid group '%s' at root of '%s' removed", groupAtRoot_name, GB_read_key_pntr(gb_tree))); |
---|
624 | error = GB_delete(gb_group_name); |
---|
625 | if (error) { |
---|
626 | GBT_message(gb_main, GBS_global_string("Failed to delete 'group_name' of root-node (Reason: %s)", error)); |
---|
627 | error = NULL; // dont fail loading the tree |
---|
628 | } |
---|
629 | free(groupAtRoot_name); |
---|
630 | } |
---|
631 | freenull(node->name); // erase name from tree-structure |
---|
632 | gb_assert(!node->is_named_group()); |
---|
633 | } |
---|
634 | } |
---|
635 | else { |
---|
636 | gb_assert(error); |
---|
637 | } |
---|
638 | |
---|
639 | gb_assert(contradicted(node, error)); |
---|
640 | gb_assert(implicated(node, !node->is_named_group())); |
---|
641 | return node; |
---|
642 | } |
---|
643 | |
---|
644 | TreeNode *GBT_read_tree_and_size(GBDATA *gb_main, const char *tree_name, TreeRoot *troot, int *tree_size) { |
---|
645 | /*! Loads a tree from DB into any user defined structure. |
---|
646 | * |
---|
647 | * @param gb_main DB root node |
---|
648 | * @param tree_name is the name of the tree in the db |
---|
649 | * @param troot constructs the tree-node instances |
---|
650 | * @param tree_size if != NULL -> gets set to "size of tree" (aka number of leafs minus 1) |
---|
651 | * |
---|
652 | * @return |
---|
653 | * - NULL if any error occurs (which is exported then) |
---|
654 | * - root of loaded tree (dynamic type depends on 'nodeFactory') |
---|
655 | */ |
---|
656 | |
---|
657 | GB_ERROR error = 0; |
---|
658 | |
---|
659 | if (!tree_name) { |
---|
660 | error = "no treename given"; |
---|
661 | } |
---|
662 | else { |
---|
663 | error = GBT_check_tree_name(tree_name); |
---|
664 | if (!error) { |
---|
665 | GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name); |
---|
666 | |
---|
667 | if (!gb_tree) { |
---|
668 | error = "tree not found"; |
---|
669 | } |
---|
670 | else { |
---|
671 | GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes"); |
---|
672 | if (!gb_nnodes) { |
---|
673 | error = "tree is empty"; |
---|
674 | } |
---|
675 | else { |
---|
676 | long size = GB_read_int(gb_nnodes); |
---|
677 | if (!size) { |
---|
678 | error = "has no nodes"; |
---|
679 | } |
---|
680 | else { |
---|
681 | GBDATA *gb_ctree = GB_search(gb_tree, "tree", GB_FIND); |
---|
682 | if (!gb_ctree) { |
---|
683 | error = "old unsupported tree format"; |
---|
684 | } |
---|
685 | else { // "new" style tree |
---|
686 | TreeNode *tree = read_tree_and_size_internal(gb_tree, gb_ctree, troot, size, error); |
---|
687 | if (!error) { |
---|
688 | gb_assert(tree); |
---|
689 | if (tree_size) *tree_size = size; // return size of tree (=leafs-1) |
---|
690 | tree->announce_tree_constructed(); |
---|
691 | |
---|
692 | gb_assert(!tree->is_named_group()); // root shall not be a group (see #753) |
---|
693 | |
---|
694 | return tree; |
---|
695 | } |
---|
696 | |
---|
697 | gb_assert(!tree); |
---|
698 | } |
---|
699 | } |
---|
700 | } |
---|
701 | } |
---|
702 | } |
---|
703 | } |
---|
704 | |
---|
705 | gb_assert(error); |
---|
706 | GB_export_errorf("Failed to read tree '%s' (Reason: %s)", tree_name, error); |
---|
707 | troot->delete_by_node(); |
---|
708 | return NULL; |
---|
709 | } |
---|
710 | |
---|
711 | TreeNode *GBT_read_tree(GBDATA *gb_main, const char *tree_name, TreeRoot *troot) { |
---|
712 | //! @see GBT_read_tree_and_size() |
---|
713 | return GBT_read_tree_and_size(gb_main, tree_name, troot, 0); |
---|
714 | } |
---|
715 | |
---|
716 | size_t GBT_count_leafs(const TreeNode *tree) { |
---|
717 | if (tree->is_leaf) { |
---|
718 | return 1; |
---|
719 | } |
---|
720 | return GBT_count_leafs(tree->get_leftson()) + GBT_count_leafs(tree->get_rightson()); |
---|
721 | } |
---|
722 | |
---|
723 | static GB_ERROR gbt_invalid_because(const TreeNode *tree, const char *reason) { |
---|
724 | return GBS_global_string("((TreeNode*)0x%p) %s", tree, reason); |
---|
725 | } |
---|
726 | |
---|
727 | inline bool has_son(const TreeNode *father, const TreeNode *son) { |
---|
728 | return !father->is_leaf && (father->leftson == son || father->rightson == son); |
---|
729 | } |
---|
730 | |
---|
731 | static GB_ERROR gbt_is_invalid(bool is_root, const TreeNode *tree) { |
---|
732 | if (tree->father) { |
---|
733 | if (!has_son(tree->get_father(), tree)) return gbt_invalid_because(tree, "is not son of its father"); |
---|
734 | } |
---|
735 | else { |
---|
736 | if (!is_root) return gbt_invalid_because(tree, "has no father (but isn't root)"); |
---|
737 | } |
---|
738 | |
---|
739 | GB_ERROR error = NULL; |
---|
740 | if (tree->is_leaf) { |
---|
741 | if (tree->leftson) return gbt_invalid_because(tree, "is leaf, but has leftson"); |
---|
742 | if (tree->rightson) return gbt_invalid_because(tree, "is leaf, but has rightson"); |
---|
743 | } |
---|
744 | else { |
---|
745 | if (!tree->leftson) return gbt_invalid_because(tree, "is inner node, but has no leftson"); |
---|
746 | if (!tree->rightson) return gbt_invalid_because(tree, "is inner node, but has no rightson"); |
---|
747 | |
---|
748 | error = gbt_is_invalid(false, tree->get_leftson()); |
---|
749 | if (!error) error = gbt_is_invalid(false, tree->get_rightson()); |
---|
750 | } |
---|
751 | return error; |
---|
752 | } |
---|
753 | |
---|
754 | GB_ERROR GBT_is_invalid(const TreeNode *tree) { |
---|
755 | if (tree->father) return gbt_invalid_because(tree, "is expected to be the root-node, but has father"); |
---|
756 | if (tree->is_leaf) return gbt_invalid_because(tree, "is expected to be the root-node, but is a leaf (tree too small)"); |
---|
757 | return gbt_is_invalid(true, tree); |
---|
758 | } |
---|
759 | |
---|
760 | // ------------------------------------------- |
---|
761 | // link the tree tips to the database |
---|
762 | |
---|
763 | struct link_tree_data { |
---|
764 | GB_HASH *species_hash; |
---|
765 | GB_HASH *seen_species; // used to count duplicates |
---|
766 | arb_progress *progress; |
---|
767 | int zombies; // counts zombies |
---|
768 | int duplicates; // counts duplicates |
---|
769 | }; |
---|
770 | |
---|
771 | static GB_ERROR gbt_link_tree_to_hash_rek(TreeNode *tree, link_tree_data *ltd) { |
---|
772 | GB_ERROR error = 0; |
---|
773 | if (tree->is_leaf) { |
---|
774 | tree->gb_node = 0; |
---|
775 | if (tree->name) { |
---|
776 | GBDATA *gbd = (GBDATA*)GBS_read_hash(ltd->species_hash, tree->name); |
---|
777 | if (gbd) tree->gb_node = gbd; |
---|
778 | else ltd->zombies++; |
---|
779 | |
---|
780 | if (ltd->seen_species) { |
---|
781 | if (GBS_read_hash(ltd->seen_species, tree->name)) ltd->duplicates++; |
---|
782 | else GBS_write_hash(ltd->seen_species, tree->name, 1); |
---|
783 | } |
---|
784 | } |
---|
785 | |
---|
786 | if (ltd->progress) ++(*ltd->progress); |
---|
787 | } |
---|
788 | else { |
---|
789 | error = gbt_link_tree_to_hash_rek(tree->get_leftson(), ltd); |
---|
790 | if (!error) error = gbt_link_tree_to_hash_rek(tree->get_rightson(), ltd); |
---|
791 | } |
---|
792 | return error; |
---|
793 | } |
---|
794 | |
---|
795 | static GB_ERROR GBT_link_tree_using_species_hash(TreeNode *tree, bool show_status, GB_HASH *species_hash, int *zombies, int *duplicates) { |
---|
796 | GB_ERROR error; |
---|
797 | link_tree_data ltd; |
---|
798 | long leafs = 0; |
---|
799 | |
---|
800 | if (duplicates || show_status) { |
---|
801 | leafs = GBT_count_leafs(tree); |
---|
802 | } |
---|
803 | |
---|
804 | ltd.species_hash = species_hash; |
---|
805 | ltd.seen_species = leafs ? GBS_create_hash(leafs, GB_IGNORE_CASE) : 0; |
---|
806 | ltd.zombies = 0; |
---|
807 | ltd.duplicates = 0; |
---|
808 | |
---|
809 | if (show_status) { |
---|
810 | ltd.progress = new arb_progress("Relinking tree to database", leafs); |
---|
811 | } |
---|
812 | else { |
---|
813 | ltd.progress = NULL; |
---|
814 | } |
---|
815 | |
---|
816 | error = gbt_link_tree_to_hash_rek(tree, <d); |
---|
817 | if (ltd.seen_species) GBS_free_hash(ltd.seen_species); |
---|
818 | |
---|
819 | if (zombies) *zombies = ltd.zombies; |
---|
820 | if (duplicates) *duplicates = ltd.duplicates; |
---|
821 | |
---|
822 | delete ltd.progress; |
---|
823 | |
---|
824 | return error; |
---|
825 | } |
---|
826 | |
---|
827 | GB_ERROR GBT_link_tree(TreeNode *tree, GBDATA *gb_main, bool show_status, int *zombies, int *duplicates) { |
---|
828 | /*! Link a given tree to the database. That means that for all tips the member |
---|
829 | * 'gb_node' is set to the database container holding the species data. |
---|
830 | * |
---|
831 | * @param tree which will be linked to DB |
---|
832 | * @param gb_main DB root node |
---|
833 | * @param show_status show a progress indicator? |
---|
834 | * @param zombies if != NULL -> set to number of zombies (aka non-existing species) in tree |
---|
835 | * @param duplicates if != NULL -> set to number of duplicated species in tree |
---|
836 | * |
---|
837 | * @return error on failure |
---|
838 | * |
---|
839 | * @see GBT_unlink_tree() |
---|
840 | */ |
---|
841 | |
---|
842 | GB_HASH *species_hash = GBT_create_species_hash(gb_main); |
---|
843 | GB_ERROR error = GBT_link_tree_using_species_hash(tree, show_status, species_hash, zombies, duplicates); |
---|
844 | |
---|
845 | GBS_free_hash(species_hash); |
---|
846 | |
---|
847 | return error; |
---|
848 | } |
---|
849 | |
---|
850 | void TreeNode::unlink_from_DB() { |
---|
851 | /*! Unlink tree from the database. |
---|
852 | * @see GBT_link_tree() |
---|
853 | */ |
---|
854 | gb_node = 0; |
---|
855 | if (!is_leaf) { |
---|
856 | get_leftson()->unlink_from_DB(); |
---|
857 | get_rightson()->unlink_from_DB(); |
---|
858 | } |
---|
859 | } |
---|
860 | void GBT_unlink_tree(TreeNode *tree) { |
---|
861 | tree->unlink_from_DB(); |
---|
862 | } |
---|
863 | |
---|
864 | // ---------------------- |
---|
865 | // search trees |
---|
866 | |
---|
867 | GBDATA *GBT_find_tree(GBDATA *gb_main, const char *tree_name) { |
---|
868 | /*! @return |
---|
869 | * - DB tree container associated with tree_name |
---|
870 | * - NULL if no such tree exists |
---|
871 | */ |
---|
872 | return GB_entry(GBT_get_tree_data(gb_main), tree_name); |
---|
873 | } |
---|
874 | |
---|
875 | inline bool is_tree(GBDATA *gb_tree) { |
---|
876 | if (!gb_tree) return false; |
---|
877 | GBDATA *gb_tree_data = GB_get_father(gb_tree); |
---|
878 | return gb_tree_data && GB_has_key(gb_tree_data, "tree_data"); |
---|
879 | } |
---|
880 | |
---|
881 | inline GBDATA *get_first_tree(GBDATA *gb_main) { |
---|
882 | return GB_child(GBT_get_tree_data(gb_main)); |
---|
883 | } |
---|
884 | |
---|
885 | inline GBDATA *get_next_tree(GBDATA *gb_tree) { |
---|
886 | if (!gb_tree) return NULL; |
---|
887 | gb_assert(is_tree(gb_tree)); |
---|
888 | return GB_nextChild(gb_tree); |
---|
889 | } |
---|
890 | |
---|
891 | GBDATA *GBT_find_largest_tree(GBDATA *gb_main) { |
---|
892 | long maxnodes = 0; |
---|
893 | GBDATA *gb_largest = NULL; |
---|
894 | |
---|
895 | for (GBDATA *gb_tree = get_first_tree(gb_main); gb_tree; gb_tree = get_next_tree(gb_tree)) { |
---|
896 | long *nnodes = GBT_read_int(gb_tree, "nnodes"); |
---|
897 | if (nnodes && *nnodes>maxnodes) { |
---|
898 | gb_largest = gb_tree; |
---|
899 | maxnodes = *nnodes; |
---|
900 | } |
---|
901 | } |
---|
902 | return gb_largest; |
---|
903 | } |
---|
904 | |
---|
905 | GBDATA *GBT_tree_infrontof(GBDATA *gb_tree) { |
---|
906 | GBDATA *gb_treedata = GB_get_father(gb_tree); |
---|
907 | ensure_trees_have_order(gb_treedata); |
---|
908 | return get_tree_infrontof_idx(gb_treedata, get_tree_idx(gb_tree)); |
---|
909 | } |
---|
910 | GBDATA *GBT_tree_behind(GBDATA *gb_tree) { |
---|
911 | GBDATA *gb_treedata = GB_get_father(gb_tree); |
---|
912 | ensure_trees_have_order(gb_treedata); |
---|
913 | return get_tree_behind_idx(gb_treedata, get_tree_idx(gb_tree)); |
---|
914 | } |
---|
915 | |
---|
916 | GBDATA *GBT_find_top_tree(GBDATA *gb_main) { |
---|
917 | GBDATA *gb_treedata = GBT_get_tree_data(gb_main); |
---|
918 | ensure_trees_have_order(gb_treedata); |
---|
919 | |
---|
920 | GBDATA *gb_top = get_tree_with_idx(gb_treedata, 1); |
---|
921 | if (!gb_top) gb_top = get_tree_behind_idx(gb_treedata, 1); |
---|
922 | return gb_top; |
---|
923 | } |
---|
924 | GBDATA *GBT_find_bottom_tree(GBDATA *gb_main) { |
---|
925 | GBDATA *gb_treedata = GBT_get_tree_data(gb_main); |
---|
926 | ensure_trees_have_order(gb_treedata); |
---|
927 | return get_tree_infrontof_idx(gb_treedata, INT_MAX); |
---|
928 | } |
---|
929 | |
---|
930 | const char *GBT_existing_tree(GBDATA *gb_main, const char *tree_name) { |
---|
931 | // search for a specify existing tree (and fallback to any existing) |
---|
932 | GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name); |
---|
933 | if (!gb_tree) gb_tree = get_first_tree(gb_main); |
---|
934 | return GBT_get_tree_name(gb_tree); |
---|
935 | } |
---|
936 | |
---|
937 | GBDATA *GBT_find_next_tree(GBDATA *gb_tree) { |
---|
938 | GBDATA *gb_other = NULL; |
---|
939 | if (gb_tree) { |
---|
940 | gb_other = GBT_tree_behind(gb_tree); |
---|
941 | if (!gb_other) { |
---|
942 | gb_other = GBT_find_top_tree(GB_get_root(gb_tree)); |
---|
943 | if (gb_other == gb_tree) gb_other = NULL; |
---|
944 | } |
---|
945 | } |
---|
946 | gb_assert(gb_other != gb_tree); |
---|
947 | return gb_other; |
---|
948 | } |
---|
949 | |
---|
950 | // -------------------- |
---|
951 | // tree names |
---|
952 | |
---|
953 | const char *GBT_get_tree_name(GBDATA *gb_tree) { |
---|
954 | if (!gb_tree) return NULL; |
---|
955 | gb_assert(is_tree(gb_tree)); |
---|
956 | return GB_read_key_pntr(gb_tree); |
---|
957 | } |
---|
958 | |
---|
959 | GB_ERROR GBT_check_tree_name(const char *tree_name) { |
---|
960 | GB_ERROR error = GB_check_key(tree_name); |
---|
961 | if (!error) { |
---|
962 | if (strncmp(tree_name, "tree_", 5) != 0) { |
---|
963 | error = "has to start with 'tree_'"; |
---|
964 | } |
---|
965 | } |
---|
966 | if (error) { |
---|
967 | error = GBS_global_string("not a valid treename '%s' (Reason: %s)", tree_name, error); |
---|
968 | } |
---|
969 | return error; |
---|
970 | } |
---|
971 | |
---|
972 | const char *GBT_name_of_largest_tree(GBDATA *gb_main) { |
---|
973 | return GBT_get_tree_name(GBT_find_largest_tree(gb_main)); |
---|
974 | } |
---|
975 | |
---|
976 | const char *GBT_name_of_bottom_tree(GBDATA *gb_main) { |
---|
977 | return GBT_get_tree_name(GBT_find_bottom_tree(gb_main)); |
---|
978 | } |
---|
979 | |
---|
980 | // ------------------- |
---|
981 | // tree info |
---|
982 | |
---|
983 | const char *GBT_tree_info_string(GBDATA *gb_main, const char *tree_name, int maxTreeNameLen) { |
---|
984 | // maxTreeNameLen shall be the max len of the longest tree name (or -1 -> do not format) |
---|
985 | |
---|
986 | const char *result = 0; |
---|
987 | GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name); |
---|
988 | |
---|
989 | if (!gb_tree) { |
---|
990 | GB_export_errorf("tree '%s' not found", tree_name); |
---|
991 | } |
---|
992 | else { |
---|
993 | GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes"); |
---|
994 | if (!gb_nnodes) { |
---|
995 | GB_export_errorf("nnodes not found in tree '%s'", tree_name); |
---|
996 | } |
---|
997 | else { |
---|
998 | const char *sizeInfo = GBS_global_string("(%li:%i)", GB_read_int(gb_nnodes)+1, GB_read_security_write(gb_tree)); |
---|
999 | GBDATA *gb_rem = GB_entry(gb_tree, "remark"); |
---|
1000 | int len; |
---|
1001 | |
---|
1002 | if (maxTreeNameLen == -1) { |
---|
1003 | result = GBS_global_string("%s %11s", tree_name, sizeInfo); |
---|
1004 | len = strlen(tree_name); |
---|
1005 | } |
---|
1006 | else { |
---|
1007 | result = GBS_global_string("%-*s %11s", maxTreeNameLen, tree_name, sizeInfo); |
---|
1008 | len = maxTreeNameLen; |
---|
1009 | } |
---|
1010 | if (gb_rem) { |
---|
1011 | const char *remark = GB_read_char_pntr(gb_rem); |
---|
1012 | const int remarkLen = 800; |
---|
1013 | char *res2 = GB_give_other_buffer(remark, len+1+11+2+remarkLen+1); |
---|
1014 | |
---|
1015 | strcpy(res2, result); |
---|
1016 | strcat(res2, " "); |
---|
1017 | strncat(res2, remark, remarkLen); |
---|
1018 | |
---|
1019 | result = res2; |
---|
1020 | } |
---|
1021 | } |
---|
1022 | } |
---|
1023 | return result; |
---|
1024 | } |
---|
1025 | |
---|
1026 | long GBT_size_of_tree(GBDATA *gb_main, const char *tree_name) { |
---|
1027 | // return the number of inner nodes in binary tree (or -1 if unknown) |
---|
1028 | // Note: |
---|
1029 | // leafs = size + 1 |
---|
1030 | // inner nodes in unrooted tree = size - 1 |
---|
1031 | |
---|
1032 | long nnodes = -1; |
---|
1033 | GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name); |
---|
1034 | if (gb_tree) { |
---|
1035 | GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes"); |
---|
1036 | if (gb_nnodes) { |
---|
1037 | nnodes = GB_read_int(gb_nnodes); |
---|
1038 | } |
---|
1039 | } |
---|
1040 | return nnodes; |
---|
1041 | } |
---|
1042 | |
---|
1043 | |
---|
1044 | struct indexed_name { |
---|
1045 | int idx; |
---|
1046 | const char *name; |
---|
1047 | |
---|
1048 | bool operator<(const indexed_name& other) const { return idx < other.idx; } |
---|
1049 | }; |
---|
1050 | |
---|
1051 | void GBT_get_tree_names(ConstStrArray& names, GBDATA *gb_main, bool sorted) { |
---|
1052 | // stores tree names in 'names' |
---|
1053 | |
---|
1054 | GBDATA *gb_treedata = GBT_get_tree_data(gb_main); |
---|
1055 | ensure_trees_have_order(gb_treedata); |
---|
1056 | |
---|
1057 | long tree_count = GB_number_of_subentries(gb_treedata); |
---|
1058 | |
---|
1059 | names.reserve(tree_count); |
---|
1060 | typedef std::set<indexed_name> ordered_trees; |
---|
1061 | ordered_trees trees; |
---|
1062 | |
---|
1063 | { |
---|
1064 | int t = 0; |
---|
1065 | int count = 0; |
---|
1066 | for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree), ++t) { |
---|
1067 | indexed_name iname; |
---|
1068 | iname.name = GB_read_key_pntr(gb_tree); |
---|
1069 | iname.idx = sorted ? get_tree_idx(gb_tree) : ++count; |
---|
1070 | |
---|
1071 | trees.insert(iname); |
---|
1072 | } |
---|
1073 | } |
---|
1074 | |
---|
1075 | if (tree_count != (long)trees.size()) { // there are duplicated "order" entries |
---|
1076 | gb_assert(sorted); // should not happen in unsorted mode |
---|
1077 | |
---|
1078 | typedef std::set<int> ints; |
---|
1079 | |
---|
1080 | ints used_indices; |
---|
1081 | GBDATA *gb_first_tree = GB_child(gb_treedata); |
---|
1082 | GBDATA *gb_tree = gb_first_tree; |
---|
1083 | |
---|
1084 | while (gb_tree) { |
---|
1085 | int idx = get_tree_idx(gb_tree); |
---|
1086 | if (used_indices.find(idx) != used_indices.end()) { // duplicate order |
---|
1087 | GB_ERROR error = reserve_tree_idx(gb_treedata, idx+1); |
---|
1088 | if (!error) error = set_tree_idx(gb_tree, idx+1); |
---|
1089 | if (error) GBK_terminatef("failed to fix tree-order (Reason: %s)", error); |
---|
1090 | |
---|
1091 | // now restart |
---|
1092 | used_indices.clear(); |
---|
1093 | gb_tree = gb_first_tree; |
---|
1094 | } |
---|
1095 | else { |
---|
1096 | used_indices.insert(idx); |
---|
1097 | gb_tree = GB_nextChild(gb_tree); |
---|
1098 | } |
---|
1099 | } |
---|
1100 | GBT_get_tree_names(names, gb_main, sorted); |
---|
1101 | return; |
---|
1102 | } |
---|
1103 | |
---|
1104 | for (ordered_trees::const_iterator t = trees.begin(); t != trees.end(); ++t) { |
---|
1105 | names.put(t->name); |
---|
1106 | } |
---|
1107 | } |
---|
1108 | |
---|
1109 | NOT4PERL GB_ERROR GBT_move_tree(GBDATA *gb_moved_tree, GBT_ORDER_MODE mode, GBDATA *gb_target_tree) { |
---|
1110 | // moves 'gb_moved_tree' next to 'gb_target_tree' (only changes tree-order) |
---|
1111 | gb_assert(gb_moved_tree && gb_target_tree); |
---|
1112 | |
---|
1113 | GBDATA *gb_treedata = GB_get_father(gb_moved_tree); |
---|
1114 | ensure_trees_have_order(gb_treedata); |
---|
1115 | |
---|
1116 | int target_idx = get_tree_idx(gb_target_tree); |
---|
1117 | gb_assert(target_idx); |
---|
1118 | |
---|
1119 | if (mode == GBT_BEHIND) target_idx++; |
---|
1120 | |
---|
1121 | GB_ERROR error = reserve_tree_idx(gb_treedata, target_idx); |
---|
1122 | if (!error) error = set_tree_idx(gb_moved_tree, target_idx); |
---|
1123 | |
---|
1124 | return error; |
---|
1125 | } |
---|
1126 | |
---|
1127 | static GBDATA *get_source_and_check_target_tree(GBDATA *gb_main, const char *source_tree, const char *dest_tree, GB_ERROR& error) { |
---|
1128 | GBDATA *gb_source_tree = NULL; |
---|
1129 | |
---|
1130 | error = GBT_check_tree_name(source_tree); |
---|
1131 | if (!error) error = GBT_check_tree_name(dest_tree); |
---|
1132 | |
---|
1133 | if (error && strcmp(source_tree, NO_TREE_SELECTED) == 0) { |
---|
1134 | error = "No tree selected"; |
---|
1135 | } |
---|
1136 | |
---|
1137 | if (!error && strcmp(source_tree, dest_tree) == 0) error = "source- and dest-tree are the same"; |
---|
1138 | |
---|
1139 | if (!error) { |
---|
1140 | gb_source_tree = GBT_find_tree(gb_main, source_tree); |
---|
1141 | if (!gb_source_tree) error = GBS_global_string("tree '%s' not found", source_tree); |
---|
1142 | else { |
---|
1143 | GBDATA *gb_dest_tree = GBT_find_tree(gb_main, dest_tree); |
---|
1144 | if (gb_dest_tree) { |
---|
1145 | error = GBS_global_string("tree '%s' already exists", dest_tree); |
---|
1146 | gb_source_tree = NULL; |
---|
1147 | } |
---|
1148 | } |
---|
1149 | } |
---|
1150 | |
---|
1151 | gb_assert(contradicted(error, gb_source_tree)); |
---|
1152 | return gb_source_tree; |
---|
1153 | } |
---|
1154 | |
---|
1155 | static GBDATA *copy_tree_container(GBDATA *gb_source_tree, const char *newName, GB_ERROR& error) { |
---|
1156 | GBDATA *gb_treedata = GB_get_father(gb_source_tree); |
---|
1157 | GBDATA *gb_dest_tree = GB_create_container(gb_treedata, newName); |
---|
1158 | |
---|
1159 | if (!gb_dest_tree) error = GB_await_error(); |
---|
1160 | else error = GB_copy(gb_dest_tree, gb_source_tree); |
---|
1161 | |
---|
1162 | gb_assert(contradicted(error, gb_dest_tree)); |
---|
1163 | return gb_dest_tree; |
---|
1164 | } |
---|
1165 | |
---|
1166 | GB_ERROR GBT_copy_tree(GBDATA *gb_main, const char *source_name, const char *dest_name) { |
---|
1167 | GB_ERROR error; |
---|
1168 | GBDATA *gb_source_tree = get_source_and_check_target_tree(gb_main, source_name, dest_name, error); |
---|
1169 | |
---|
1170 | if (gb_source_tree) { |
---|
1171 | GBDATA *gb_dest_tree = copy_tree_container(gb_source_tree, dest_name, error); |
---|
1172 | if (gb_dest_tree) { |
---|
1173 | int source_idx = get_tree_idx(gb_source_tree); |
---|
1174 | int dest_idx = source_idx+1; |
---|
1175 | |
---|
1176 | error = reserve_tree_idx(GB_get_father(gb_dest_tree), dest_idx); |
---|
1177 | if (!error) error = set_tree_idx(gb_dest_tree, dest_idx); |
---|
1178 | } |
---|
1179 | } |
---|
1180 | |
---|
1181 | return error; |
---|
1182 | } |
---|
1183 | |
---|
1184 | GB_ERROR GBT_rename_tree(GBDATA *gb_main, const char *source_name, const char *dest_name) { |
---|
1185 | GB_ERROR error; |
---|
1186 | GBDATA *gb_source_tree = get_source_and_check_target_tree(gb_main, source_name, dest_name, error); |
---|
1187 | |
---|
1188 | if (gb_source_tree) { |
---|
1189 | GBDATA *gb_dest_tree = copy_tree_container(gb_source_tree, dest_name, error); |
---|
1190 | if (gb_dest_tree) error = GB_delete(gb_source_tree); |
---|
1191 | } |
---|
1192 | |
---|
1193 | return error; |
---|
1194 | } |
---|
1195 | |
---|
1196 | static GB_CSTR *fill_species_name_array(GB_CSTR *current, const TreeNode *tree) { |
---|
1197 | if (tree->is_leaf) { |
---|
1198 | current[0] = tree->name; |
---|
1199 | return current+1; |
---|
1200 | } |
---|
1201 | current = fill_species_name_array(current, tree->get_leftson()); |
---|
1202 | current = fill_species_name_array(current, tree->get_rightson()); |
---|
1203 | return current; |
---|
1204 | } |
---|
1205 | |
---|
1206 | GB_CSTR *GBT_get_names_of_species_in_tree(const TreeNode *tree, size_t *count) { |
---|
1207 | /* creates an array of all species names in a tree, |
---|
1208 | * The names are not allocated (so they may change as side effect of renaming species) */ |
---|
1209 | |
---|
1210 | size_t size = GBT_count_leafs(tree); |
---|
1211 | GB_CSTR *result = ARB_calloc<GB_CSTR>(size + 1); |
---|
1212 | |
---|
1213 | IF_ASSERTION_USED(GB_CSTR *check =) fill_species_name_array(result, tree); |
---|
1214 | gb_assert(check - size == result); |
---|
1215 | |
---|
1216 | if (count) *count = size; |
---|
1217 | |
---|
1218 | return result; |
---|
1219 | } |
---|
1220 | |
---|
1221 | static void tree2newick(const TreeNode *tree, GBS_strstruct& out, NewickFormat format, int indent) { |
---|
1222 | gb_assert(tree); |
---|
1223 | if ((format&nWRAP) && indent>0) { out.put('\n'); out.nput(' ', indent); } |
---|
1224 | if (tree->is_leaf) { |
---|
1225 | out.cat(tree->name); |
---|
1226 | } |
---|
1227 | else { |
---|
1228 | out.put('('); |
---|
1229 | tree2newick(tree->get_leftson(), out, format, indent+1); |
---|
1230 | out.put(','); |
---|
1231 | tree2newick(tree->get_rightson(), out, format, indent+1); |
---|
1232 | if ((format&nWRAP) && indent>0) { out.put('\n'); out.nput(' ', indent); } |
---|
1233 | out.put(')'); |
---|
1234 | |
---|
1235 | if (format & (nGROUP|nREMARK)) { |
---|
1236 | const char *remark = format&nREMARK ? tree->get_remark() : NULL; |
---|
1237 | const char *group = format&nGROUP ? tree->name : NULL; |
---|
1238 | |
---|
1239 | if (remark || group) { |
---|
1240 | out.put('\''); |
---|
1241 | if (remark) { |
---|
1242 | out.cat(remark); |
---|
1243 | if (group) out.put(':'); |
---|
1244 | } |
---|
1245 | if (group) out.cat(group); |
---|
1246 | out.put('\''); |
---|
1247 | } |
---|
1248 | } |
---|
1249 | } |
---|
1250 | |
---|
1251 | if (format&nLENGTH && !tree->is_root_node()) { |
---|
1252 | out.put(':'); |
---|
1253 | out.nprintf(10, "%5.3f", tree->get_branchlength()); |
---|
1254 | } |
---|
1255 | } |
---|
1256 | |
---|
1257 | char *GBT_tree_2_newick(const TreeNode *tree, NewickFormat format, bool compact) { |
---|
1258 | GBS_strstruct out(1000); |
---|
1259 | if (tree) tree2newick(tree, out, format, 0); |
---|
1260 | out.put(';'); |
---|
1261 | |
---|
1262 | char *result = out.release(); |
---|
1263 | if (compact && (format&nWRAP)) { |
---|
1264 | GB_ERROR error = NULL; |
---|
1265 | |
---|
1266 | char *compact1 = GBS_regreplace(result, "/[\n ]*[)]/)/", &error); |
---|
1267 | if (compact1) { |
---|
1268 | char *compact2 = GBS_regreplace(compact1, "/[(][\n ]*/(/", &error); |
---|
1269 | if (compact2) freeset(result, compact2); |
---|
1270 | free(compact1); |
---|
1271 | } |
---|
1272 | if (error) { |
---|
1273 | fprintf(stderr, "Error in GBT_tree_2_newick: %s\n", error); |
---|
1274 | gb_assert(!error); // should be impossible; falls back to 'result' if happens |
---|
1275 | } |
---|
1276 | } |
---|
1277 | return result; |
---|
1278 | } |
---|
1279 | |
---|
1280 | |
---|
1281 | // -------------------------------------------------------------------------------- |
---|
1282 | |
---|
1283 | #ifdef UNIT_TESTS |
---|
1284 | #include <test_unit.h> |
---|
1285 | |
---|
1286 | static const char *getTreeOrder(GBDATA *gb_main) { |
---|
1287 | ConstStrArray names; |
---|
1288 | GBT_get_tree_names(names, gb_main, true); |
---|
1289 | |
---|
1290 | char *joined = GBT_join_strings(names, '|'); |
---|
1291 | char *size_and_names = GBS_global_string_copy("%zu:%s", names.size(), joined); |
---|
1292 | free(joined); |
---|
1293 | |
---|
1294 | RETURN_LOCAL_ALLOC(size_and_names); |
---|
1295 | } |
---|
1296 | |
---|
1297 | void TEST_tree_names() { |
---|
1298 | TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name(""), "not a valid treename"); |
---|
1299 | TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name("not_a_treename"), "not a valid treename"); |
---|
1300 | TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name("tree_bad.dot"), "not a valid treename"); |
---|
1301 | |
---|
1302 | TEST_EXPECT_NO_ERROR(GBT_check_tree_name("tree_")); // ugly but ok |
---|
1303 | TEST_EXPECT_NO_ERROR(GBT_check_tree_name("tree_ok")); |
---|
1304 | } |
---|
1305 | |
---|
1306 | void TEST_tree_contraints() { |
---|
1307 | // test minima |
---|
1308 | const int MIN_LEAFS = 2; |
---|
1309 | |
---|
1310 | TEST_EXPECT_EQUAL(leafs_2_nodes(MIN_LEAFS, ROOTED), 3); |
---|
1311 | TEST_EXPECT_EQUAL(leafs_2_nodes(MIN_LEAFS, UNROOTED), 2); |
---|
1312 | TEST_EXPECT_EQUAL(leafs_2_edges(MIN_LEAFS, ROOTED), 2); |
---|
1313 | TEST_EXPECT_EQUAL(leafs_2_edges(MIN_LEAFS, UNROOTED), 1); |
---|
1314 | |
---|
1315 | TEST_EXPECT_EQUAL(MIN_LEAFS, nodes_2_leafs(3, ROOTED)); // test minimum (3 nodes rooted) |
---|
1316 | TEST_EXPECT_EQUAL(MIN_LEAFS, nodes_2_leafs(2, UNROOTED)); // test minimum (2 nodes unrooted) |
---|
1317 | |
---|
1318 | TEST_EXPECT_EQUAL(MIN_LEAFS, edges_2_leafs(2, ROOTED)); // test minimum (2 edges rooted) |
---|
1319 | TEST_EXPECT_EQUAL(MIN_LEAFS, edges_2_leafs(1, UNROOTED)); // test minimum (1 edge unrooted) |
---|
1320 | |
---|
1321 | // test inverse functions: |
---|
1322 | for (int i = 3; i<=7; ++i) { |
---|
1323 | // test "leaf->XXX" and back conversions (any number of leafs is possible) |
---|
1324 | TEST_EXPECT_EQUAL(i, nodes_2_leafs(leafs_2_nodes(i, ROOTED), ROOTED)); |
---|
1325 | TEST_EXPECT_EQUAL(i, nodes_2_leafs(leafs_2_nodes(i, UNROOTED), UNROOTED)); |
---|
1326 | |
---|
1327 | TEST_EXPECT_EQUAL(i, edges_2_leafs(leafs_2_edges(i, ROOTED), ROOTED)); |
---|
1328 | TEST_EXPECT_EQUAL(i, edges_2_leafs(leafs_2_edges(i, UNROOTED), UNROOTED)); |
---|
1329 | |
---|
1330 | bool odd = i%2; |
---|
1331 | if (odd) { |
---|
1332 | TEST_EXPECT_EQUAL(i, leafs_2_nodes(nodes_2_leafs(i, ROOTED), ROOTED)); // rooted trees only contain odd numbers of nodes |
---|
1333 | TEST_EXPECT_EQUAL(i, leafs_2_edges(edges_2_leafs(i, UNROOTED), UNROOTED)); // unrooted trees only contain odd numbers of edges |
---|
1334 | } |
---|
1335 | else { // even |
---|
1336 | TEST_EXPECT_EQUAL(i, leafs_2_nodes(nodes_2_leafs(i, UNROOTED), UNROOTED)); // unrooted trees only contain even numbers of nodes |
---|
1337 | TEST_EXPECT_EQUAL(i, leafs_2_edges(edges_2_leafs(i, ROOTED), ROOTED)); // rooted trees only contain even numbers of edges |
---|
1338 | } |
---|
1339 | |
---|
1340 | // test adding a leaf adds two nodes: |
---|
1341 | int added = i+1; |
---|
1342 | TEST_EXPECT_EQUAL(leafs_2_nodes(added, ROOTED)-leafs_2_nodes(i, ROOTED), 2); |
---|
1343 | TEST_EXPECT_EQUAL(leafs_2_nodes(added, UNROOTED)-leafs_2_nodes(i, UNROOTED), 2); |
---|
1344 | } |
---|
1345 | |
---|
1346 | |
---|
1347 | } |
---|
1348 | |
---|
1349 | void TEST_copy_rename_delete_tree_order() { |
---|
1350 | GB_shell shell; |
---|
1351 | GBDATA *gb_main = GB_open("TEST_trees.arb", "r"); |
---|
1352 | |
---|
1353 | { |
---|
1354 | GB_transaction ta(gb_main); |
---|
1355 | |
---|
1356 | { |
---|
1357 | TEST_EXPECT_NULL(GBT_get_tree_name(NULL)); |
---|
1358 | |
---|
1359 | TEST_EXPECT_EQUAL(GBT_name_of_largest_tree(gb_main), "tree_removal"); |
---|
1360 | |
---|
1361 | TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_top_tree(gb_main)), "tree_test"); |
---|
1362 | TEST_EXPECT_EQUAL(GBT_name_of_bottom_tree(gb_main), "tree_removal"); |
---|
1363 | |
---|
1364 | long inner_nodes = GBT_size_of_tree(gb_main, "tree_nj_bs"); |
---|
1365 | TEST_EXPECT_EQUAL(inner_nodes, 5); |
---|
1366 | TEST_EXPECT_EQUAL(GBT_tree_info_string(gb_main, "tree_nj_bs", -1), "tree_nj_bs (6:0) PRG=dnadist CORR=none FILTER=none PKG=ARB"); |
---|
1367 | TEST_EXPECT_EQUAL(GBT_tree_info_string(gb_main, "tree_nj_bs", 20), "tree_nj_bs (6:0) PRG=dnadist CORR=none FILTER=none PKG=ARB"); |
---|
1368 | |
---|
1369 | { |
---|
1370 | TreeNode *tree = GBT_read_tree(gb_main, "tree_nj_bs", new SimpleRoot); |
---|
1371 | |
---|
1372 | TEST_REJECT_NULL(tree); |
---|
1373 | |
---|
1374 | size_t leaf_count = GBT_count_leafs(tree); |
---|
1375 | |
---|
1376 | size_t species_count; |
---|
1377 | GB_CSTR *species = GBT_get_names_of_species_in_tree(tree, &species_count); |
---|
1378 | |
---|
1379 | StrArray species2; |
---|
1380 | for (int i = 0; species[i]; ++i) species2.put(ARB_strdup(species[i])); |
---|
1381 | |
---|
1382 | TEST_EXPECT_EQUAL(species_count, leaf_count); |
---|
1383 | TEST_EXPECT_EQUAL(long(species_count), inner_nodes+1); |
---|
1384 | |
---|
1385 | { |
---|
1386 | char *joined = GBT_join_strings(species2, '*'); |
---|
1387 | TEST_EXPECT_EQUAL(joined, "CloButyr*CloButy2*CorGluta*CorAquat*CurCitre*CytAquat"); |
---|
1388 | free(joined); |
---|
1389 | } |
---|
1390 | |
---|
1391 | free(species); |
---|
1392 | |
---|
1393 | TEST_EXPECT_NEWICK(nSIMPLE, tree, "(CloButyr,(CloButy2,((CorGluta,(CorAquat,CurCitre)),CytAquat)));"); |
---|
1394 | TEST_EXPECT_NEWICK(nSIMPLE, NULL, ";"); |
---|
1395 | |
---|
1396 | destroy(tree); |
---|
1397 | } |
---|
1398 | |
---|
1399 | TEST_EXPECT_EQUAL(GBT_existing_tree(gb_main, "tree_nj_bs"), "tree_nj_bs"); |
---|
1400 | TEST_EXPECT_EQUAL(GBT_existing_tree(gb_main, "tree_nosuch"), "tree_test"); |
---|
1401 | } |
---|
1402 | |
---|
1403 | // changing tree order |
---|
1404 | { |
---|
1405 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_test|tree_tree2|tree_nj|tree_nj_bs|tree_removal"); |
---|
1406 | |
---|
1407 | GBDATA *gb_test = GBT_find_tree(gb_main, "tree_test"); |
---|
1408 | GBDATA *gb_tree2 = GBT_find_tree(gb_main, "tree_tree2"); |
---|
1409 | GBDATA *gb_nj = GBT_find_tree(gb_main, "tree_nj"); |
---|
1410 | GBDATA *gb_nj_bs = GBT_find_tree(gb_main, "tree_nj_bs"); |
---|
1411 | GBDATA *gb_removal = GBT_find_tree(gb_main, "tree_removal"); |
---|
1412 | |
---|
1413 | TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_removal)); // move to bottom |
---|
1414 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_tree2|tree_nj|tree_nj_bs|tree_removal|tree_test"); |
---|
1415 | |
---|
1416 | TEST_EXPECT_EQUAL(GBT_tree_behind(gb_tree2), gb_nj); |
---|
1417 | TEST_EXPECT_EQUAL(GBT_tree_behind(gb_nj), gb_nj_bs); |
---|
1418 | TEST_EXPECT_EQUAL(GBT_tree_behind(gb_nj_bs), gb_removal); |
---|
1419 | TEST_EXPECT_EQUAL(GBT_tree_behind(gb_removal), gb_test); |
---|
1420 | TEST_EXPECT_NULL(GBT_tree_behind(gb_test)); |
---|
1421 | |
---|
1422 | TEST_EXPECT_NULL(GBT_tree_infrontof(gb_tree2)); |
---|
1423 | TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj), gb_tree2); |
---|
1424 | TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj_bs), gb_nj); |
---|
1425 | TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_removal), gb_nj_bs); |
---|
1426 | TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_test), gb_removal); |
---|
1427 | |
---|
1428 | TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_INFRONTOF, gb_tree2)); // move back to top |
---|
1429 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_test|tree_tree2|tree_nj|tree_nj_bs|tree_removal"); |
---|
1430 | |
---|
1431 | TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_tree2)); // move from top |
---|
1432 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_tree2|tree_test|tree_nj|tree_nj_bs|tree_removal"); |
---|
1433 | |
---|
1434 | TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_removal, GBT_INFRONTOF, gb_nj)); // move from end |
---|
1435 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_tree2|tree_test|tree_removal|tree_nj|tree_nj_bs"); |
---|
1436 | |
---|
1437 | TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_nj_bs, GBT_INFRONTOF, gb_nj_bs)); // noop |
---|
1438 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_tree2|tree_test|tree_removal|tree_nj|tree_nj_bs"); |
---|
1439 | |
---|
1440 | TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_top_tree(gb_main)), "tree_tree2"); |
---|
1441 | |
---|
1442 | TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_next_tree(gb_removal)), "tree_nj"); |
---|
1443 | TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_next_tree(gb_nj_bs)), "tree_tree2"); // last -> first |
---|
1444 | } |
---|
1445 | |
---|
1446 | // check tree order is maintained by copy, rename and delete |
---|
1447 | |
---|
1448 | { |
---|
1449 | // copy |
---|
1450 | TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_nosuch", "tree_whatever"), "tree 'tree_nosuch' not found"); |
---|
1451 | TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_test", "tree_test"), "source- and dest-tree are the same"); |
---|
1452 | TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_tree2", "tree_test"), "tree 'tree_test' already exists"); |
---|
1453 | |
---|
1454 | TEST_EXPECT_NO_ERROR(GBT_copy_tree(gb_main, "tree_test", "tree_test_copy")); |
---|
1455 | TEST_REJECT_NULL(GBT_find_tree(gb_main, "tree_test_copy")); |
---|
1456 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "6:tree_tree2|tree_test|tree_test_copy|tree_removal|tree_nj|tree_nj_bs"); |
---|
1457 | |
---|
1458 | // rename |
---|
1459 | TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_nj", "tree_renamed_nj")); |
---|
1460 | TEST_REJECT_NULL(GBT_find_tree(gb_main, "tree_renamed_nj")); |
---|
1461 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "6:tree_tree2|tree_test|tree_test_copy|tree_removal|tree_renamed_nj|tree_nj_bs"); |
---|
1462 | |
---|
1463 | TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_tree2", "tree_renamed_tree2")); |
---|
1464 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "6:tree_renamed_tree2|tree_test|tree_test_copy|tree_removal|tree_renamed_nj|tree_nj_bs"); |
---|
1465 | |
---|
1466 | TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_test_copy", "tree_renamed_test_copy")); |
---|
1467 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "6:tree_renamed_tree2|tree_test|tree_renamed_test_copy|tree_removal|tree_renamed_nj|tree_nj_bs"); |
---|
1468 | |
---|
1469 | // delete |
---|
1470 | |
---|
1471 | GBDATA *gb_nj_bs = GBT_find_tree(gb_main, "tree_nj_bs"); |
---|
1472 | GBDATA *gb_renamed_nj = GBT_find_tree(gb_main, "tree_renamed_nj"); |
---|
1473 | GBDATA *gb_renamed_test_copy = GBT_find_tree(gb_main, "tree_renamed_test_copy"); |
---|
1474 | GBDATA *gb_renamed_tree2 = GBT_find_tree(gb_main, "tree_renamed_tree2"); |
---|
1475 | GBDATA *gb_test = GBT_find_tree(gb_main, "tree_test"); |
---|
1476 | GBDATA *gb_removal = GBT_find_tree(gb_main, "tree_removal"); |
---|
1477 | |
---|
1478 | TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_tree2)); |
---|
1479 | TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_test_copy)); |
---|
1480 | TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_nj)); |
---|
1481 | TEST_EXPECT_NO_ERROR(GB_delete(gb_removal)); |
---|
1482 | |
---|
1483 | // .. two trees left |
---|
1484 | |
---|
1485 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_test|tree_nj_bs"); |
---|
1486 | |
---|
1487 | TEST_EXPECT_EQUAL(GBT_find_largest_tree(gb_main), gb_test); |
---|
1488 | TEST_EXPECT_EQUAL(GBT_find_top_tree(gb_main), gb_test); |
---|
1489 | TEST_EXPECT_EQUAL(GBT_find_bottom_tree(gb_main), gb_nj_bs); |
---|
1490 | |
---|
1491 | TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_test), gb_nj_bs); |
---|
1492 | TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_test), gb_nj_bs); |
---|
1493 | TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_nj_bs), gb_test); |
---|
1494 | |
---|
1495 | TEST_EXPECT_NULL (GBT_tree_infrontof(gb_test)); |
---|
1496 | TEST_EXPECT_EQUAL(GBT_tree_behind (gb_test), gb_nj_bs); |
---|
1497 | |
---|
1498 | TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj_bs), gb_test); |
---|
1499 | TEST_EXPECT_NULL (GBT_tree_behind (gb_nj_bs)); |
---|
1500 | |
---|
1501 | TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_nj_bs)); // move to bottom |
---|
1502 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_nj_bs|tree_test"); |
---|
1503 | TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_INFRONTOF, gb_nj_bs)); // move to top |
---|
1504 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_test|tree_nj_bs"); |
---|
1505 | |
---|
1506 | TEST_EXPECT_NO_ERROR(GB_delete(gb_nj_bs)); |
---|
1507 | |
---|
1508 | // .. one tree left |
---|
1509 | |
---|
1510 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "1:tree_test"); |
---|
1511 | |
---|
1512 | TEST_EXPECT_EQUAL(GBT_find_largest_tree(gb_main), gb_test); |
---|
1513 | TEST_EXPECT_EQUAL(GBT_find_top_tree(gb_main), gb_test); |
---|
1514 | TEST_EXPECT_EQUAL(GBT_find_bottom_tree(gb_main), gb_test); |
---|
1515 | |
---|
1516 | TEST_EXPECT_NULL(GBT_find_next_tree(gb_test)); // no other tree left |
---|
1517 | TEST_EXPECT_NULL(GBT_tree_behind(gb_test)); |
---|
1518 | TEST_EXPECT_NULL(GBT_tree_infrontof(gb_test)); |
---|
1519 | |
---|
1520 | TEST_EXPECT_NO_ERROR(GB_delete(gb_test)); |
---|
1521 | |
---|
1522 | // .. no tree left |
---|
1523 | |
---|
1524 | TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "0:"); |
---|
1525 | |
---|
1526 | TEST_EXPECT_NULL(GBT_find_tree(gb_main, "tree_test")); |
---|
1527 | TEST_EXPECT_NULL(GBT_existing_tree(gb_main, "tree_whatever")); |
---|
1528 | TEST_EXPECT_NULL(GBT_find_largest_tree(gb_main)); |
---|
1529 | } |
---|
1530 | } |
---|
1531 | |
---|
1532 | GB_close(gb_main); |
---|
1533 | } |
---|
1534 | TEST_PUBLISH(TEST_copy_rename_delete_tree_order); |
---|
1535 | |
---|
1536 | void TEST_tree_remove_leafs() { |
---|
1537 | GB_shell shell; |
---|
1538 | GBDATA *gb_main = GB_open("TEST_trees.arb", "r"); |
---|
1539 | |
---|
1540 | { |
---|
1541 | GBT_TreeRemoveType tested_modes[] = { |
---|
1542 | GBT_REMOVE_MARKED, |
---|
1543 | GBT_REMOVE_UNMARKED, |
---|
1544 | GBT_REMOVE_ZOMBIES, |
---|
1545 | GBT_KEEP_MARKED, |
---|
1546 | }; |
---|
1547 | |
---|
1548 | const char *org_topo = "((CloInnoc:0.371,(CloTyrob:0.009,(CloTyro2:0.017,(CloTyro3:1.046,CloTyro4:0.061):0.026):0.017):0.274):0.029,(CloBifer:0.388,((CloCarni:0.120,CurCitre:0.058):1.000,((CloPaste:0.179,(Zombie1:0.120,(CloButy2:0.009,CloButyr:0.000):0.564):0.010):0.131,(CytAquat:0.711,(CelBiazo:0.059,(CorGluta:0.522,(CorAquat:0.084,Zombie2:0.058):0.103):0.054):0.207):0.162):0.124):0.124):0.029);"; |
---|
1549 | const char *rem_marked_topo = "((CloInnoc:0.371,(CloTyrob:0.009,(CloTyro2:0.017,(CloTyro3:1.046,CloTyro4:0.061):0.026):0.017):0.274):0.029,(CloBifer:0.388,(CloCarni:1.000,((CloPaste:0.179,Zombie1:0.010):0.131,(CelBiazo:0.059,Zombie2:0.054):0.162):0.124):0.124):0.029);"; |
---|
1550 | const char *rem_unmarked_topo = "(CurCitre:1.000,((Zombie1:0.120,(CloButy2:0.009,CloButyr:0.000):0.564):0.131,(CytAquat:0.711,(CorGluta:0.522,(CorAquat:0.084,Zombie2:0.058):0.103):0.207):0.162):0.124);"; |
---|
1551 | const char *rem_zombies_topo = "((CloInnoc:0.371,(CloTyrob:0.009,(CloTyro2:0.017,(CloTyro3:1.046,CloTyro4:0.061):0.026):0.017):0.274):0.029,(CloBifer:0.388,((CloCarni:0.120,CurCitre:0.058):1.000,((CloPaste:0.179,(CloButy2:0.009,CloButyr:0.000):0.010):0.131,(CytAquat:0.711,(CelBiazo:0.059,(CorGluta:0.522,CorAquat:0.103):0.054):0.207):0.162):0.124):0.124):0.029);"; |
---|
1552 | const char *kept_marked_topo = "(CurCitre:1.000,((CloButy2:0.009,CloButyr:0.000):0.131,(CytAquat:0.711,(CorGluta:0.522,CorAquat:0.103):0.207):0.162):0.124);"; |
---|
1553 | |
---|
1554 | const char *kept_zombies_topo = "(Zombie1:0.131,Zombie2:0.162);"; |
---|
1555 | const char *kept_zombies_broken_topo = "Zombie2;"; |
---|
1556 | |
---|
1557 | const char *empty_topo = ";"; |
---|
1558 | |
---|
1559 | GB_transaction ta(gb_main); |
---|
1560 | for (unsigned mode = 0; mode<ARRAY_ELEMS(tested_modes); ++mode) { |
---|
1561 | GBT_TreeRemoveType what = tested_modes[mode]; |
---|
1562 | |
---|
1563 | for (int linked = 0; linked<=1; ++linked) { |
---|
1564 | TEST_ANNOTATE(GBS_global_string("mode=%u linked=%i", mode, linked)); |
---|
1565 | |
---|
1566 | TreeNode *tree = GBT_read_tree(gb_main, "tree_removal", new SimpleRoot); |
---|
1567 | gb_assert(tree); |
---|
1568 | bool once = mode == 0 && linked == 0; |
---|
1569 | |
---|
1570 | if (linked) { |
---|
1571 | int zombies = 0; |
---|
1572 | int duplicates = 0; |
---|
1573 | |
---|
1574 | TEST_EXPECT_NO_ERROR(GBT_link_tree(tree, gb_main, false, &zombies, &duplicates)); |
---|
1575 | |
---|
1576 | TEST_EXPECT_EQUAL(zombies, 2); |
---|
1577 | TEST_EXPECT_EQUAL(duplicates, 0); |
---|
1578 | } |
---|
1579 | |
---|
1580 | if (once) TEST_EXPECT_NEWICK(nLENGTH, tree, org_topo); |
---|
1581 | |
---|
1582 | int removedCount = 0; |
---|
1583 | int groupsRemovedCount = 0; |
---|
1584 | |
---|
1585 | tree = GBT_remove_leafs(tree, what, NULL, &removedCount, &groupsRemovedCount); |
---|
1586 | |
---|
1587 | if (linked) { |
---|
1588 | GBT_TreeRemoveType what_next = what; |
---|
1589 | |
---|
1590 | switch (what) { |
---|
1591 | case GBT_REMOVE_MARKED: |
---|
1592 | TEST_EXPECT_EQUAL(removedCount, 6); |
---|
1593 | TEST_EXPECT_EQUAL(groupsRemovedCount, 0); |
---|
1594 | TEST_EXPECT_NEWICK(nLENGTH, tree, rem_marked_topo); |
---|
1595 | what_next = GBT_REMOVE_UNMARKED; |
---|
1596 | break; |
---|
1597 | case GBT_REMOVE_UNMARKED: |
---|
1598 | TEST_EXPECT_EQUAL(removedCount, 9); |
---|
1599 | TEST_EXPECT_EQUAL(groupsRemovedCount, 1); |
---|
1600 | TEST_EXPECT_NEWICK(nLENGTH, tree, rem_unmarked_topo); |
---|
1601 | what_next = GBT_REMOVE_MARKED; |
---|
1602 | break; |
---|
1603 | case GBT_REMOVE_ZOMBIES: |
---|
1604 | TEST_EXPECT_EQUAL(removedCount, 2); |
---|
1605 | TEST_EXPECT_EQUAL(groupsRemovedCount, 0); |
---|
1606 | TEST_EXPECT_NEWICK(nLENGTH, tree, rem_zombies_topo); |
---|
1607 | break; |
---|
1608 | case GBT_KEEP_MARKED: |
---|
1609 | TEST_EXPECT_EQUAL(removedCount, 11); |
---|
1610 | TEST_EXPECT_EQUAL(groupsRemovedCount, 1); |
---|
1611 | TEST_EXPECT_NEWICK(nLENGTH, tree, kept_marked_topo); |
---|
1612 | { |
---|
1613 | // just a test for nWRAP NewickFormat (may be removed later) |
---|
1614 | const char *kept_marked_topo_wrapped = |
---|
1615 | "(\n" |
---|
1616 | " CurCitre:1.000,\n" |
---|
1617 | " (\n" |
---|
1618 | " (\n" |
---|
1619 | " CloButy2:0.009,\n" |
---|
1620 | " CloButyr:0.000\n" |
---|
1621 | " ):0.131,\n" |
---|
1622 | " (\n" |
---|
1623 | " CytAquat:0.711,\n" |
---|
1624 | " (\n" |
---|
1625 | " CorGluta:0.522,\n" |
---|
1626 | " CorAquat:0.103\n" |
---|
1627 | " ):0.207\n" |
---|
1628 | " ):0.162\n" |
---|
1629 | " ):0.124);"; |
---|
1630 | TEST_EXPECT_NEWICK(NewickFormat(nLENGTH|nWRAP), tree, kept_marked_topo_wrapped); |
---|
1631 | |
---|
1632 | const char *expected_compacted = |
---|
1633 | "(CurCitre:1.000,\n" |
---|
1634 | " ((CloButy2:0.009,\n" |
---|
1635 | " CloButyr:0.000):0.131,\n" |
---|
1636 | " (CytAquat:0.711,\n" |
---|
1637 | " (CorGluta:0.522,\n" |
---|
1638 | " CorAquat:0.103):0.207):0.162):0.124);"; |
---|
1639 | char *compacted = GBT_tree_2_newick(tree, NewickFormat(nLENGTH|nWRAP), true); |
---|
1640 | TEST_EXPECT_EQUAL(compacted, expected_compacted); |
---|
1641 | free(compacted); |
---|
1642 | } |
---|
1643 | what_next = GBT_REMOVE_MARKED; |
---|
1644 | break; |
---|
1645 | } |
---|
1646 | |
---|
1647 | if (what_next != what) { |
---|
1648 | gb_assert(tree); |
---|
1649 | tree = GBT_remove_leafs(tree, what_next, NULL, &removedCount, &groupsRemovedCount); |
---|
1650 | |
---|
1651 | switch (what) { |
---|
1652 | case GBT_REMOVE_MARKED: // + GBT_REMOVE_UNMARKED |
---|
1653 | TEST_EXPECT_EQUAL(removedCount, 16); |
---|
1654 | TEST_EXPECT_EQUAL(groupsRemovedCount, 1); |
---|
1655 | TEST_EXPECT_NEWICK__BROKEN(nLENGTH, tree, kept_zombies_topo); |
---|
1656 | TEST_EXPECT_NEWICK(nLENGTH, tree, kept_zombies_broken_topo); // @@@ invalid topology (single leaf) |
---|
1657 | break; |
---|
1658 | case GBT_REMOVE_UNMARKED: // + GBT_REMOVE_MARKED |
---|
1659 | TEST_EXPECT_EQUAL(removedCount, 15); |
---|
1660 | TEST_EXPECT_EQUAL(groupsRemovedCount, 1); |
---|
1661 | TEST_EXPECT_NEWICK(nLENGTH, tree, kept_zombies_topo); |
---|
1662 | break; |
---|
1663 | case GBT_KEEP_MARKED: // + GBT_REMOVE_MARKED |
---|
1664 | TEST_EXPECT_EQUAL(removedCount, 17); |
---|
1665 | TEST_EXPECT_EQUAL__BROKEN(groupsRemovedCount, 2, 1); // @@@ expect that all groups have been removed! |
---|
1666 | TEST_EXPECT_EQUAL(groupsRemovedCount, 1); |
---|
1667 | TEST_EXPECT_NEWICK(nLENGTH, tree, empty_topo); |
---|
1668 | break; |
---|
1669 | default: |
---|
1670 | TEST_REJECT(true); |
---|
1671 | break; |
---|
1672 | } |
---|
1673 | } |
---|
1674 | } |
---|
1675 | else { |
---|
1676 | switch (what) { |
---|
1677 | case GBT_REMOVE_MARKED: |
---|
1678 | case GBT_REMOVE_UNMARKED: |
---|
1679 | TEST_EXPECT_EQUAL(removedCount, 0); |
---|
1680 | TEST_EXPECT_EQUAL(groupsRemovedCount, 0); |
---|
1681 | TEST_EXPECT_NEWICK(nLENGTH, tree, org_topo); |
---|
1682 | break; |
---|
1683 | case GBT_REMOVE_ZOMBIES: |
---|
1684 | case GBT_KEEP_MARKED: |
---|
1685 | TEST_EXPECT_EQUAL(removedCount, 17); |
---|
1686 | TEST_EXPECT_EQUAL(groupsRemovedCount, 2); |
---|
1687 | TEST_EXPECT_NEWICK(nLENGTH, tree, empty_topo); |
---|
1688 | break; |
---|
1689 | } |
---|
1690 | } |
---|
1691 | |
---|
1692 | if (tree) { |
---|
1693 | gb_assert(tree->is_root_node()); |
---|
1694 | destroy(tree); |
---|
1695 | } |
---|
1696 | } |
---|
1697 | } |
---|
1698 | } |
---|
1699 | |
---|
1700 | GB_close(gb_main); |
---|
1701 | } |
---|
1702 | TEST_PUBLISH(TEST_tree_remove_leafs); |
---|
1703 | |
---|
1704 | |
---|
1705 | #endif // UNIT_TESTS |
---|