source: tags/ms_r17q3/ARBDB/adtree.cxx

Last change on this file was 15966, checked in by westram, 8 years ago
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 64.0 KB
Line 
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
26GBDATA *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
33TreeNode *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
112inline 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
122inline 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
131inline 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
142inline 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
158inline 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
174inline 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
185static 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
195static 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
219static 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
229GB_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
242static 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
290static 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
344static 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
426GB_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}
429GB_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
433static GB_ERROR write_tree_remark(GBDATA *gb_tree, const char *remark) {
434    return GBT_write_string(gb_tree, "remark", remark);
435}
436GB_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
440GB_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}
459GB_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
473GB_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
482static 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
575static 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
644TreeNode *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
711TreeNode *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
716size_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
723static GB_ERROR gbt_invalid_because(const TreeNode *tree, const char *reason) {
724    return GBS_global_string("((TreeNode*)0x%p) %s", tree, reason);
725}
726
727inline bool has_son(const TreeNode *father, const TreeNode *son) {
728    return !father->is_leaf && (father->leftson == son || father->rightson == son);
729}
730
731static 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
754GB_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
763struct 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
771static 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
795static 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, &ltd);
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
827GB_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
850void 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}
860void GBT_unlink_tree(TreeNode *tree) {
861    tree->unlink_from_DB();
862}
863
864// ----------------------
865//      search trees
866
867GBDATA *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
875inline 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
881inline GBDATA *get_first_tree(GBDATA *gb_main) {
882    return GB_child(GBT_get_tree_data(gb_main));
883}
884
885inline 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
891GBDATA *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
905GBDATA *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}
910GBDATA *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
916GBDATA *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}
924GBDATA *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
930const 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
937GBDATA *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
953const 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
959GB_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
972const char *GBT_name_of_largest_tree(GBDATA *gb_main) {
973    return GBT_get_tree_name(GBT_find_largest_tree(gb_main));
974}
975
976const 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
983const 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
1026long 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
1044struct indexed_name {
1045    int         idx;
1046    const char *name;
1047
1048    bool operator<(const indexed_name& other) const { return idx < other.idx; }
1049};
1050
1051void 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
1109NOT4PERL 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
1127static 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
1155static 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
1166GB_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
1184GB_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
1196static 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
1206GB_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
1221static 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
1257char *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
1286static 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
1297void 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
1306void 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
1349void 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}
1534TEST_PUBLISH(TEST_copy_rename_delete_tree_order);
1535
1536void 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}
1702TEST_PUBLISH(TEST_tree_remove_leafs);
1703
1704
1705#endif // UNIT_TESTS
Note: See TracBrowser for help on using the repository browser.