source: tags/ms_r16q2/ARBDB/adtree.cxx

Last change on this file was 14239, checked in by westram, 9 years ago
  • add GB_USERFLAG_WASMARKED
  • rename GB_set_user_flag → GB_raise_user_flag
  • add GB_write_user_flag
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 62.1 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  = (char *)GB_calloc(sizeof(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) {
441    GB_ERROR    error      = NULL;
442    const char *old_remark = GBT_read_char_pntr(gb_tree, "remark");
443    if (!old_remark && GB_have_error()) {
444        error = GB_await_error();
445    }
446    else {
447        char *new_remark = GBS_log_dated_action_to(old_remark, log_entry);
448        error            = write_tree_remark(gb_tree, new_remark);
449        free(new_remark);
450    }
451    return error;
452}
453GB_ERROR GBT_log_to_tree_remark(GBDATA *gb_main, const char *tree_name, const char *log_entry) {
454    return GBT_log_to_tree_remark(GBT_find_tree(gb_main, tree_name), log_entry);
455}
456
457GB_ERROR GBT_write_tree_with_remark(GBDATA *gb_main, const char *tree_name, TreeNode *tree, const char *remark) {
458    GB_ERROR error              = GBT_write_tree(gb_main, tree_name, tree);
459    if (!error && remark) error = GBT_write_tree_remark(gb_main, tree_name, remark);
460    return error;
461}
462
463// ----------------------------
464//      tree read functions
465
466static TreeNode *gbt_read_tree_rek(char **data, long *startid, GBDATA **gb_tree_nodes, const TreeRoot *troot, int size_of_tree, GB_ERROR& error) {
467    TreeNode *node = NULL;
468    if (!error) {
469        node = troot->makeNode();
470
471        char  c = *((*data)++);
472        char *p1;
473
474        if (c=='R') {
475            p1 = strchr(*data, 1);
476            *(p1++) = 0;
477            node->set_remark(*data);
478            c = *(p1++);
479            *data = p1;
480        }
481
482
483        if (c=='N') {
484            p1 = (char *)strchr(*data, ',');
485            *(p1++) = 0;
486            node->leftlen = GB_atof(*data);
487            *data = p1;
488            p1 = (char *)strchr(*data, ';');
489            *(p1++) = 0;
490            node->rightlen = GB_atof(*data);
491            *data = p1;
492            if ((*startid < size_of_tree) && (node->gb_node = gb_tree_nodes[*startid])) {
493                GBDATA *gb_group_name = GB_entry(node->gb_node, "group_name");
494                if (gb_group_name) {
495                    node->name = GB_read_string(gb_group_name);
496                    if (!node->name || !node->name[0]) {
497                        char   *auto_rename = strdup("<missing groupname>");
498                        GBDATA *gb_main     = GB_get_root(gb_group_name);
499
500                        const char *warn;
501                        if (!node->name) {
502                            warn = GBS_global_string("Unreadable 'group_name' detected (Reason: %s)", GB_await_error());
503                        }
504                        else {
505                            warn = "Empty groupname detected";
506                        }
507                        warn = GBS_global_string("%s\nGroup has been named '%s'", warn, auto_rename);
508                        GBT_message(gb_main, warn);
509
510                        GB_ERROR rename_error = GB_write_string(gb_group_name, auto_rename);
511                        if (rename_error) {
512                            GBT_message(gb_main, GBS_global_string("Failed to name group (Reason: %s)", rename_error));
513                        }
514                        node->name = auto_rename;
515                    }
516                }
517            }
518            (*startid)++;
519            node->leftson = gbt_read_tree_rek(data, startid, gb_tree_nodes, troot, size_of_tree, error);
520            if (!node->leftson) freenull(node);
521            else {
522                node->rightson = gbt_read_tree_rek(data, startid, gb_tree_nodes, troot, size_of_tree, error);
523                if (!node->rightson) {
524                    freenull(node->leftson);
525                    freenull(node);
526                }
527                else {
528                    node->leftson->father  = node;
529                    node->rightson->father = node;
530                }
531            }
532        }
533        else if (c=='L') {
534            node->is_leaf = true;
535            p1            = (char *)strchr(*data, 1);
536
537            gb_assert(p1);
538            gb_assert(p1[0] == 1);
539
540            *p1        = 0;
541            node->name = strdup(*data);
542            *data      = p1+1;
543        }
544        else {
545            if (!c) {
546                error = "Unexpected end of tree definition.";
547            }
548            else {
549                error = GBS_global_string("Can't interpret tree definition (expected 'N' or 'L' - not '%c')", c);
550            }
551            freenull(node);
552        }
553    }
554    gb_assert(contradicted(node, error));
555    return node;
556}
557
558
559static TreeNode *read_tree_and_size_internal(GBDATA *gb_tree, GBDATA *gb_ctree, const TreeRoot *troot, int node_count, GB_ERROR& error) {
560    GBDATA   **gb_tree_nodes;
561    TreeNode  *node = 0;
562
563    gb_tree_nodes = (GBDATA **)GB_calloc(sizeof(GBDATA *), (size_t)node_count);
564    if (gb_tree) {
565        GBDATA *gb_node;
566
567        for (gb_node = GB_entry(gb_tree, "node"); gb_node && !error; gb_node = GB_nextEntry(gb_node)) {
568            long    i;
569            GBDATA *gbd = GB_entry(gb_node, "id");
570            if (!gbd) continue;
571
572            i = GB_read_int(gbd);
573            if (i<0 || i >= node_count) {
574                error = "An inner node of the tree is corrupt";
575            }
576            else {
577                gb_tree_nodes[i] = gb_node;
578            }
579        }
580    }
581    if (!error) {
582        char *cptr[1];
583        long  startid[1];
584        char *fbuf;
585
586        startid[0] = 0;
587        fbuf       = cptr[0] = GB_read_string(gb_ctree);
588        node       = gbt_read_tree_rek(cptr, startid, gb_tree_nodes, troot, node_count, error);
589        free (fbuf);
590    }
591
592    free(gb_tree_nodes);
593
594    gb_assert(contradicted(node, error));
595    return node;
596}
597
598TreeNode *GBT_read_tree_and_size(GBDATA *gb_main, const char *tree_name, TreeRoot *troot, int *tree_size) {
599    /*! Loads a tree from DB into any user defined structure.
600     *
601     * @param gb_main DB root node
602     * @param tree_name is the name of the tree in the db
603     * @param nodeFactory makes the tree-node instances
604     * @param tree_size if != NULL -> gets set to "size of tree" (aka number of leafs minus 1)
605     *
606     * @return
607     * - NULL if any error occurs (which is exported then)
608     * - root of loaded tree (dynamic type depends on 'nodeFactory')
609     */
610
611    GB_ERROR error = 0;
612
613    if (!tree_name) {
614        error = "no treename given";
615    }
616    else {
617        error = GBT_check_tree_name(tree_name);
618        if (!error) {
619            GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
620
621            if (!gb_tree) {
622                error = "tree not found";
623            }
624            else {
625                GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
626                if (!gb_nnodes) {
627                    error = "tree is empty";
628                }
629                else {
630                    long size = GB_read_int(gb_nnodes);
631                    if (!size) {
632                        error = "has no nodes";
633                    }
634                    else {
635                        GBDATA *gb_ctree = GB_search(gb_tree, "tree", GB_FIND);
636                        if (!gb_ctree) {
637                            error = "old unsupported tree format";
638                        }
639                        else { // "new" style tree
640                            TreeNode *tree = read_tree_and_size_internal(gb_tree, gb_ctree, troot, size, error);
641                            if (!error) {
642                                gb_assert(tree);
643                                if (tree_size) *tree_size = size; // return size of tree (=leafs-1)
644                                tree->announce_tree_constructed();
645                                return tree;
646                            }
647
648                            gb_assert(!tree);
649                        }
650                    }
651                }
652            }
653        }
654    }
655
656    gb_assert(error);
657    GB_export_errorf("Failed to read tree '%s' (Reason: %s)", tree_name, error);
658    troot->delete_by_node();
659    return NULL;
660}
661
662TreeNode *GBT_read_tree(GBDATA *gb_main, const char *tree_name, TreeRoot *troot) {
663    //! @see GBT_read_tree_and_size()
664    return GBT_read_tree_and_size(gb_main, tree_name, troot, 0);
665}
666
667size_t GBT_count_leafs(const TreeNode *tree) {
668    if (tree->is_leaf) {
669        return 1;
670    }
671    return GBT_count_leafs(tree->get_leftson()) + GBT_count_leafs(tree->get_rightson());
672}
673
674static GB_ERROR gbt_invalid_because(const TreeNode *tree, const char *reason) {
675    return GBS_global_string("((TreeNode*)0x%p) %s", tree, reason);
676}
677
678inline bool has_son(const TreeNode *father, const TreeNode *son) {
679    return !father->is_leaf && (father->leftson == son || father->rightson == son);
680}
681
682static GB_ERROR gbt_is_invalid(bool is_root, const TreeNode *tree) {
683    if (tree->father) {
684        if (!has_son(tree->get_father(), tree)) return gbt_invalid_because(tree, "is not son of its father");
685    }
686    else {
687        if (!is_root) return gbt_invalid_because(tree, "has no father (but isn't root)");
688    }
689
690    GB_ERROR error = NULL;
691    if (tree->is_leaf) {
692        if (tree->leftson) return gbt_invalid_because(tree, "is leaf, but has leftson");
693        if (tree->rightson) return gbt_invalid_because(tree, "is leaf, but has rightson");
694    }
695    else {
696        if (!tree->leftson) return gbt_invalid_because(tree, "is inner node, but has no leftson");
697        if (!tree->rightson) return gbt_invalid_because(tree, "is inner node, but has no rightson");
698
699        error             = gbt_is_invalid(false, tree->get_leftson());
700        if (!error) error = gbt_is_invalid(false, tree->get_rightson());
701    }
702    return error;
703}
704
705GB_ERROR GBT_is_invalid(const TreeNode *tree) {
706    if (tree->father) return gbt_invalid_because(tree, "is expected to be the root-node, but has father");
707    if (tree->is_leaf) return gbt_invalid_because(tree, "is expected to be the root-node, but is a leaf (tree too small)");
708    return gbt_is_invalid(true, tree);
709}
710
711// -------------------------------------------
712//      link the tree tips to the database
713
714struct link_tree_data {
715    GB_HASH      *species_hash;
716    GB_HASH      *seen_species;                     // used to count duplicates
717    arb_progress *progress;
718    int           zombies;                          // counts zombies
719    int           duplicates;                       // counts duplicates
720};
721
722static GB_ERROR gbt_link_tree_to_hash_rek(TreeNode *tree, link_tree_data *ltd) {
723    GB_ERROR error = 0;
724    if (tree->is_leaf) {
725        tree->gb_node = 0;
726        if (tree->name) {
727            GBDATA *gbd = (GBDATA*)GBS_read_hash(ltd->species_hash, tree->name);
728            if (gbd) tree->gb_node = gbd;
729            else ltd->zombies++;
730
731            if (ltd->seen_species) {
732                if (GBS_read_hash(ltd->seen_species, tree->name)) ltd->duplicates++;
733                else GBS_write_hash(ltd->seen_species, tree->name, 1);
734            }
735        }
736
737        if (ltd->progress) ++(*ltd->progress);
738    }
739    else {
740        error             = gbt_link_tree_to_hash_rek(tree->get_leftson(), ltd);
741        if (!error) error = gbt_link_tree_to_hash_rek(tree->get_rightson(), ltd);
742    }
743    return error;
744}
745
746static GB_ERROR GBT_link_tree_using_species_hash(TreeNode *tree, bool show_status, GB_HASH *species_hash, int *zombies, int *duplicates) {
747    GB_ERROR       error;
748    link_tree_data ltd;
749    long           leafs = 0;
750
751    if (duplicates || show_status) {
752        leafs = GBT_count_leafs(tree);
753    }
754
755    ltd.species_hash = species_hash;
756    ltd.seen_species = leafs ? GBS_create_hash(leafs, GB_IGNORE_CASE) : 0;
757    ltd.zombies      = 0;
758    ltd.duplicates   = 0;
759
760    if (show_status) {
761        ltd.progress = new arb_progress("Relinking tree to database", leafs);
762    }
763    else {
764        ltd.progress = NULL;
765    }
766
767    error = gbt_link_tree_to_hash_rek(tree, &ltd);
768    if (ltd.seen_species) GBS_free_hash(ltd.seen_species);
769
770    if (zombies) *zombies       = ltd.zombies;
771    if (duplicates) *duplicates = ltd.duplicates;
772
773    delete ltd.progress;
774
775    return error;
776}
777
778GB_ERROR GBT_link_tree(TreeNode *tree, GBDATA *gb_main, bool show_status, int *zombies, int *duplicates) {
779    /*! Link a given tree to the database. That means that for all tips the member
780     * 'gb_node' is set to the database container holding the species data.
781     *
782     * @param tree which will be linked to DB
783     * @param gb_main DB root node
784     * @param show_status show a progress indicator?
785     * @param zombies if != NULL -> set to number of zombies (aka non-existing species) in tree
786     * @param duplicates if != NULL -> set to number of duplicated species in tree
787     *
788     * @return error on failure
789     *
790     * @see GBT_unlink_tree()
791     */
792
793    GB_HASH  *species_hash = GBT_create_species_hash(gb_main);
794    GB_ERROR  error        = GBT_link_tree_using_species_hash(tree, show_status, species_hash, zombies, duplicates);
795
796    GBS_free_hash(species_hash);
797
798    return error;
799}
800
801void TreeNode::unlink_from_DB() {
802    /*! Unlink tree from the database.
803     * @see GBT_link_tree()
804     */
805    gb_node = 0;
806    if (!is_leaf) {
807        get_leftson()->unlink_from_DB();
808        get_rightson()->unlink_from_DB();
809    }
810}
811void GBT_unlink_tree(TreeNode *tree) {
812    tree->unlink_from_DB();
813}
814
815// ----------------------
816//      search trees
817
818GBDATA *GBT_find_tree(GBDATA *gb_main, const char *tree_name) {
819    /*! @return
820     * - DB tree container associated with tree_name
821     * - NULL if no such tree exists
822     */
823    return GB_entry(GBT_get_tree_data(gb_main), tree_name);
824}
825
826inline bool is_tree(GBDATA *gb_tree) {
827    if (!gb_tree) return false;
828    GBDATA *gb_tree_data = GB_get_father(gb_tree);
829    return gb_tree_data && GB_has_key(gb_tree_data, "tree_data");
830}
831
832inline GBDATA *get_first_tree(GBDATA *gb_main) {
833    return GB_child(GBT_get_tree_data(gb_main));
834}
835
836inline GBDATA *get_next_tree(GBDATA *gb_tree) {
837    if (!gb_tree) return NULL;
838    gb_assert(is_tree(gb_tree));
839    return GB_nextChild(gb_tree);
840}
841
842GBDATA *GBT_find_largest_tree(GBDATA *gb_main) {
843    long    maxnodes   = 0;
844    GBDATA *gb_largest = NULL;
845
846    for (GBDATA *gb_tree = get_first_tree(gb_main); gb_tree; gb_tree = get_next_tree(gb_tree)) {
847        long *nnodes = GBT_read_int(gb_tree, "nnodes");
848        if (nnodes && *nnodes>maxnodes) {
849            gb_largest = gb_tree;
850            maxnodes   = *nnodes;
851        }
852    }
853    return gb_largest;
854}
855
856GBDATA *GBT_tree_infrontof(GBDATA *gb_tree) {
857    GBDATA *gb_treedata = GB_get_father(gb_tree);
858    ensure_trees_have_order(gb_treedata);
859    return get_tree_infrontof_idx(gb_treedata, get_tree_idx(gb_tree));
860}
861GBDATA *GBT_tree_behind(GBDATA *gb_tree) {
862    GBDATA *gb_treedata = GB_get_father(gb_tree);
863    ensure_trees_have_order(gb_treedata);
864    return get_tree_behind_idx(gb_treedata, get_tree_idx(gb_tree));
865}
866
867GBDATA *GBT_find_top_tree(GBDATA *gb_main) {
868    GBDATA *gb_treedata = GBT_get_tree_data(gb_main);
869    ensure_trees_have_order(gb_treedata);
870
871    GBDATA *gb_top = get_tree_with_idx(gb_treedata, 1);
872    if (!gb_top) gb_top = get_tree_behind_idx(gb_treedata, 1);
873    return gb_top;
874}
875GBDATA *GBT_find_bottom_tree(GBDATA *gb_main) {
876    GBDATA *gb_treedata = GBT_get_tree_data(gb_main);
877    ensure_trees_have_order(gb_treedata);
878    return get_tree_infrontof_idx(gb_treedata, INT_MAX);
879}
880
881const char *GBT_existing_tree(GBDATA *gb_main, const char *tree_name) {
882    // search for a specify existing tree (and fallback to any existing)
883    GBDATA *gb_tree       = GBT_find_tree(gb_main, tree_name);
884    if (!gb_tree) gb_tree = get_first_tree(gb_main);
885    return GBT_get_tree_name(gb_tree);
886}
887
888GBDATA *GBT_find_next_tree(GBDATA *gb_tree) {
889    GBDATA *gb_other = NULL;
890    if (gb_tree) {
891        gb_other = GBT_tree_behind(gb_tree);
892        if (!gb_other) {
893            gb_other = GBT_find_top_tree(GB_get_root(gb_tree));
894            if (gb_other == gb_tree) gb_other = NULL;
895        }
896    }
897    gb_assert(gb_other != gb_tree);
898    return gb_other;
899}
900
901// --------------------
902//      tree names
903
904const char *GBT_get_tree_name(GBDATA *gb_tree) {
905    if (!gb_tree) return NULL;
906    gb_assert(is_tree(gb_tree));
907    return GB_read_key_pntr(gb_tree);
908}
909
910GB_ERROR GBT_check_tree_name(const char *tree_name) {
911    GB_ERROR error = GB_check_key(tree_name);
912    if (!error) {
913        if (strncmp(tree_name, "tree_", 5) != 0) {
914            error = "has to start with 'tree_'";
915        }
916    }
917    if (error) {
918        error = GBS_global_string("not a valid treename '%s' (Reason: %s)", tree_name, error);
919    }
920    return error;
921}
922
923const char *GBT_name_of_largest_tree(GBDATA *gb_main) {
924    return GBT_get_tree_name(GBT_find_largest_tree(gb_main));
925}
926
927const char *GBT_name_of_bottom_tree(GBDATA *gb_main) {
928    return GBT_get_tree_name(GBT_find_bottom_tree(gb_main));
929}
930
931// -------------------
932//      tree info
933
934const char *GBT_tree_info_string(GBDATA *gb_main, const char *tree_name, int maxTreeNameLen) {
935    // maxTreeNameLen shall be the max len of the longest tree name (or -1 -> do not format)
936
937    const char *result  = 0;
938    GBDATA     *gb_tree = GBT_find_tree(gb_main, tree_name);
939
940    if (!gb_tree) {
941        GB_export_errorf("tree '%s' not found", tree_name);
942    }
943    else {
944        GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
945        if (!gb_nnodes) {
946            GB_export_errorf("nnodes not found in tree '%s'", tree_name);
947        }
948        else {
949            const char *sizeInfo = GBS_global_string("(%li:%i)", GB_read_int(gb_nnodes)+1, GB_read_security_write(gb_tree));
950            GBDATA     *gb_rem   = GB_entry(gb_tree, "remark");
951            int         len;
952
953            if (maxTreeNameLen == -1) {
954                result = GBS_global_string("%s %11s", tree_name, sizeInfo);
955                len    = strlen(tree_name);
956            }
957            else {
958                result = GBS_global_string("%-*s %11s", maxTreeNameLen, tree_name, sizeInfo);
959                len    = maxTreeNameLen;
960            }
961            if (gb_rem) {
962                const char *remark    = GB_read_char_pntr(gb_rem);
963                const int   remarkLen = 800;
964                char       *res2      = GB_give_other_buffer(remark, len+1+11+2+remarkLen+1);
965
966                strcpy(res2, result);
967                strcat(res2, "  ");
968                strncat(res2, remark, remarkLen);
969
970                result = res2;
971            }
972        }
973    }
974    return result;
975}
976
977long GBT_size_of_tree(GBDATA *gb_main, const char *tree_name) {
978    // return the number of inner nodes in binary tree (or -1 if unknown)
979    // Note:
980    //        leafs                        = size + 1
981    //        inner nodes in unrooted tree = size - 1
982
983    long    nnodes  = -1;
984    GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
985    if (gb_tree) {
986        GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
987        if (gb_nnodes) {
988            nnodes = GB_read_int(gb_nnodes);
989        }
990    }
991    return nnodes;
992}
993
994
995struct indexed_name {
996    int         idx;
997    const char *name;
998
999    bool operator<(const indexed_name& other) const { return idx < other.idx; }
1000};
1001
1002void GBT_get_tree_names(ConstStrArray& names, GBDATA *gb_main, bool sorted) {
1003    // stores tree names in 'names'
1004
1005    GBDATA *gb_treedata = GBT_get_tree_data(gb_main);
1006    ensure_trees_have_order(gb_treedata);
1007
1008    long tree_count = GB_number_of_subentries(gb_treedata);
1009
1010    names.reserve(tree_count);
1011    typedef std::set<indexed_name> ordered_trees;
1012    ordered_trees trees;
1013
1014    {
1015        int t     = 0;
1016        int count = 0;
1017        for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree), ++t) {
1018            indexed_name iname;
1019            iname.name = GB_read_key_pntr(gb_tree);
1020            iname.idx  = sorted ? get_tree_idx(gb_tree) : ++count;
1021
1022            trees.insert(iname);
1023        }
1024    }
1025
1026    if (tree_count != (long)trees.size()) { // there are duplicated "order" entries
1027        gb_assert(sorted); // should not happen in unsorted mode
1028
1029        typedef std::set<int> ints;
1030
1031        ints    used_indices;
1032        GBDATA *gb_first_tree = GB_child(gb_treedata);
1033        GBDATA *gb_tree       = gb_first_tree;
1034
1035        while (gb_tree) {
1036            int idx = get_tree_idx(gb_tree);
1037            if (used_indices.find(idx) != used_indices.end()) { // duplicate order
1038                GB_ERROR error    = reserve_tree_idx(gb_treedata, idx+1);
1039                if (!error) error = set_tree_idx(gb_tree, idx+1);
1040                if (error) GBK_terminatef("failed to fix tree-order (Reason: %s)", error);
1041
1042                // now restart
1043                used_indices.clear();
1044                gb_tree = gb_first_tree;
1045            }
1046            else {
1047                used_indices.insert(idx);
1048                gb_tree = GB_nextChild(gb_tree);
1049            }
1050        }
1051        GBT_get_tree_names(names, gb_main, sorted);
1052        return;
1053    }
1054
1055    for (ordered_trees::const_iterator t = trees.begin(); t != trees.end(); ++t) {
1056        names.put(t->name);
1057    }
1058}
1059
1060NOT4PERL GB_ERROR GBT_move_tree(GBDATA *gb_moved_tree, GBT_ORDER_MODE mode, GBDATA *gb_target_tree) {
1061    // moves 'gb_moved_tree' next to 'gb_target_tree' (only changes tree-order)
1062    gb_assert(gb_moved_tree && gb_target_tree);
1063
1064    GBDATA *gb_treedata = GB_get_father(gb_moved_tree);
1065    ensure_trees_have_order(gb_treedata);
1066
1067    int target_idx = get_tree_idx(gb_target_tree);
1068    gb_assert(target_idx);
1069
1070    if (mode == GBT_BEHIND) target_idx++;
1071
1072    GB_ERROR error    = reserve_tree_idx(gb_treedata, target_idx);
1073    if (!error) error = set_tree_idx(gb_moved_tree, target_idx);
1074
1075    return error;
1076}
1077
1078static GBDATA *get_source_and_check_target_tree(GBDATA *gb_main, const char *source_tree, const char *dest_tree, GB_ERROR& error) {
1079    GBDATA *gb_source_tree = NULL;
1080
1081    error             = GBT_check_tree_name(source_tree);
1082    if (!error) error = GBT_check_tree_name(dest_tree);
1083
1084    if (error && strcmp(source_tree, NO_TREE_SELECTED) == 0) {
1085        error = "No tree selected";
1086    }
1087
1088    if (!error && strcmp(source_tree, dest_tree) == 0) error = "source- and dest-tree are the same";
1089
1090    if (!error) {
1091        gb_source_tree = GBT_find_tree(gb_main, source_tree);
1092        if (!gb_source_tree) error = GBS_global_string("tree '%s' not found", source_tree);
1093        else {
1094            GBDATA *gb_dest_tree = GBT_find_tree(gb_main, dest_tree);
1095            if (gb_dest_tree) {
1096                error = GBS_global_string("tree '%s' already exists", dest_tree);
1097                gb_source_tree = NULL;
1098            }
1099        }
1100    }
1101
1102    gb_assert(contradicted(error, gb_source_tree));
1103    return gb_source_tree;
1104}
1105
1106static GBDATA *copy_tree_container(GBDATA *gb_source_tree, const char *newName, GB_ERROR& error) {
1107    GBDATA *gb_treedata  = GB_get_father(gb_source_tree);
1108    GBDATA *gb_dest_tree = GB_create_container(gb_treedata, newName);
1109
1110    if (!gb_dest_tree) error = GB_await_error();
1111    else error               = GB_copy(gb_dest_tree, gb_source_tree);
1112
1113    gb_assert(contradicted(error, gb_dest_tree));
1114    return gb_dest_tree;
1115}
1116
1117GB_ERROR GBT_copy_tree(GBDATA *gb_main, const char *source_name, const char *dest_name) {
1118    GB_ERROR  error;
1119    GBDATA   *gb_source_tree = get_source_and_check_target_tree(gb_main, source_name, dest_name, error);
1120
1121    if (gb_source_tree) {
1122        GBDATA *gb_dest_tree = copy_tree_container(gb_source_tree, dest_name, error);
1123        if (gb_dest_tree) {
1124            int source_idx = get_tree_idx(gb_source_tree);
1125            int dest_idx   = source_idx+1;
1126
1127            error             = reserve_tree_idx(GB_get_father(gb_dest_tree), dest_idx);
1128            if (!error) error = set_tree_idx(gb_dest_tree, dest_idx);
1129        }
1130    }
1131
1132    return error;
1133}
1134
1135GB_ERROR GBT_rename_tree(GBDATA *gb_main, const char *source_name, const char *dest_name) {
1136    GB_ERROR  error;
1137    GBDATA   *gb_source_tree = get_source_and_check_target_tree(gb_main, source_name, dest_name, error);
1138
1139    if (gb_source_tree) {
1140        GBDATA *gb_dest_tree = copy_tree_container(gb_source_tree, dest_name, error);
1141        if (gb_dest_tree) error = GB_delete(gb_source_tree);
1142    }
1143
1144    return error;
1145}
1146
1147static GB_CSTR *fill_species_name_array(GB_CSTR *current, const TreeNode *tree) {
1148    if (tree->is_leaf) {
1149        current[0] = tree->name;
1150        return current+1;
1151    }
1152    current = fill_species_name_array(current, tree->get_leftson());
1153    current = fill_species_name_array(current, tree->get_rightson());
1154    return current;
1155}
1156
1157GB_CSTR *GBT_get_names_of_species_in_tree(const TreeNode *tree, size_t *count) {
1158    /* creates an array of all species names in a tree,
1159     * The names are not allocated (so they may change as side effect of renaming species) */
1160
1161    size_t   size   = GBT_count_leafs(tree);
1162    GB_CSTR *result = (GB_CSTR *)GB_calloc(sizeof(char *), size + 1);
1163   
1164    IF_ASSERTION_USED(GB_CSTR *check =) fill_species_name_array(result, tree);
1165    gb_assert(check - size == result);
1166
1167    if (count) *count = size;
1168
1169    return result;
1170}
1171
1172static void tree2newick(const TreeNode *tree, GBS_strstruct& out, NewickFormat format, int indent) {
1173    gb_assert(tree);
1174    if ((format&nWRAP) && indent>0) { out.put('\n'); out.nput(' ', indent); }
1175    if (tree->is_leaf) {
1176        out.cat(tree->name);
1177    }
1178    else {
1179        out.put('(');
1180        tree2newick(tree->get_leftson(), out, format, indent+1);
1181        out.put(',');
1182        tree2newick(tree->get_rightson(), out, format, indent+1);
1183        if ((format&nWRAP) && indent>0) { out.put('\n'); out.nput(' ', indent); }
1184        out.put(')');
1185
1186        if (format & (nGROUP|nREMARK)) {
1187            const char *remark = format&nREMARK ? tree->get_remark() : NULL;
1188            const char *group  = format&nGROUP ? tree->name : NULL;
1189
1190            if (remark || group) {
1191                out.put('\'');
1192                if (remark) {
1193                    out.cat(remark);
1194                    if (group) out.put(':');
1195                }
1196                if (group) out.cat(group);
1197                out.put('\'');
1198            }
1199        }
1200    }
1201
1202    if (format&nLENGTH && !tree->is_root_node()) {
1203        out.put(':');
1204        out.nprintf(10, "%5.3f", tree->get_branchlength());
1205    }
1206}
1207
1208char *GBT_tree_2_newick(const TreeNode *tree, NewickFormat format, bool compact) {
1209    GBS_strstruct out(1000);
1210    if (tree) tree2newick(tree, out, format, 0);
1211    out.put(';');
1212
1213    char *result = out.release();
1214    if (compact && (format&nWRAP)) {
1215        GB_ERROR error = NULL;
1216
1217        char *compact1 = GBS_regreplace(result, "/[\n ]*[)]/)/", &error);
1218        if (compact1) {
1219            char *compact2 = GBS_regreplace(compact1, "/[(][\n ]*/(/", &error);
1220            if (compact2) freeset(result, compact2);
1221            free(compact1);
1222        }
1223        if (error) {
1224            fprintf(stderr, "Error in GBT_tree_2_newick: %s\n", error);
1225            gb_assert(!error); // should be impossible; falls back to 'result' if happens
1226        }
1227    }
1228    return result;
1229}
1230
1231
1232// --------------------------------------------------------------------------------
1233
1234#ifdef UNIT_TESTS
1235#include <test_unit.h>
1236
1237static const char *getTreeOrder(GBDATA *gb_main) {
1238    ConstStrArray names;
1239    GBT_get_tree_names(names, gb_main, true);
1240
1241    char *joined         = GBT_join_strings(names, '|');
1242    char *size_and_names = GBS_global_string_copy("%zu:%s", names.size(), joined);
1243    free(joined);
1244
1245    RETURN_LOCAL_ALLOC(size_and_names);
1246}
1247
1248void TEST_tree_names() {
1249    TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name(""),               "not a valid treename");
1250    TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name("not_a_treename"), "not a valid treename");
1251    TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name("tree_bad.dot"),   "not a valid treename");
1252
1253    TEST_EXPECT_NO_ERROR(GBT_check_tree_name("tree_")); // ugly but ok
1254    TEST_EXPECT_NO_ERROR(GBT_check_tree_name("tree_ok"));
1255}
1256
1257void TEST_tree_contraints() {
1258    // test minima
1259    const int MIN_LEAFS = 2;
1260
1261    TEST_EXPECT_EQUAL(leafs_2_nodes(MIN_LEAFS, ROOTED), 3);
1262    TEST_EXPECT_EQUAL(leafs_2_nodes(MIN_LEAFS, UNROOTED), 2);
1263    TEST_EXPECT_EQUAL(leafs_2_edges(MIN_LEAFS, ROOTED), 2);
1264    TEST_EXPECT_EQUAL(leafs_2_edges(MIN_LEAFS, UNROOTED), 1);
1265
1266    TEST_EXPECT_EQUAL(MIN_LEAFS, nodes_2_leafs(3, ROOTED));   // test minimum (3 nodes rooted)
1267    TEST_EXPECT_EQUAL(MIN_LEAFS, nodes_2_leafs(2, UNROOTED)); // test minimum (2 nodes unrooted)
1268
1269    TEST_EXPECT_EQUAL(MIN_LEAFS, edges_2_leafs(2, ROOTED));   // test minimum (2 edges rooted)
1270    TEST_EXPECT_EQUAL(MIN_LEAFS, edges_2_leafs(1, UNROOTED)); // test minimum (1 edge unrooted)
1271
1272    // test inverse functions:
1273    for (int i = 3; i<=7; ++i) {
1274        // test "leaf->XXX" and back conversions (any number of leafs is possible)
1275        TEST_EXPECT_EQUAL(i, nodes_2_leafs(leafs_2_nodes(i, ROOTED), ROOTED));
1276        TEST_EXPECT_EQUAL(i, nodes_2_leafs(leafs_2_nodes(i, UNROOTED), UNROOTED));
1277
1278        TEST_EXPECT_EQUAL(i, edges_2_leafs(leafs_2_edges(i, ROOTED), ROOTED));
1279        TEST_EXPECT_EQUAL(i, edges_2_leafs(leafs_2_edges(i, UNROOTED), UNROOTED));
1280
1281        bool odd = i%2;
1282        if (odd) {
1283            TEST_EXPECT_EQUAL(i, leafs_2_nodes(nodes_2_leafs(i, ROOTED), ROOTED)); // rooted trees only contain odd numbers of nodes
1284            TEST_EXPECT_EQUAL(i, leafs_2_edges(edges_2_leafs(i, UNROOTED), UNROOTED)); // unrooted trees only contain odd numbers of edges
1285        }
1286        else { // even
1287            TEST_EXPECT_EQUAL(i, leafs_2_nodes(nodes_2_leafs(i, UNROOTED), UNROOTED)); // unrooted trees only contain even numbers of nodes
1288            TEST_EXPECT_EQUAL(i, leafs_2_edges(edges_2_leafs(i, ROOTED), ROOTED)); // rooted trees only contain even numbers of edges
1289        }
1290
1291        // test adding a leaf adds two nodes:
1292        int added = i+1;
1293        TEST_EXPECT_EQUAL(leafs_2_nodes(added, ROOTED)-leafs_2_nodes(i, ROOTED), 2);
1294        TEST_EXPECT_EQUAL(leafs_2_nodes(added, UNROOTED)-leafs_2_nodes(i, UNROOTED), 2);
1295    }
1296
1297
1298}
1299
1300void TEST_copy_rename_delete_tree_order() {
1301    GB_shell  shell;
1302    GBDATA   *gb_main = GB_open("TEST_trees.arb", "r");
1303
1304    {
1305        GB_transaction ta(gb_main);
1306
1307        {
1308            TEST_EXPECT_NULL(GBT_get_tree_name(NULL));
1309           
1310            TEST_EXPECT_EQUAL(GBT_name_of_largest_tree(gb_main), "tree_removal");
1311
1312            TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_top_tree(gb_main)), "tree_test");
1313            TEST_EXPECT_EQUAL(GBT_name_of_bottom_tree(gb_main), "tree_removal");
1314
1315            long inner_nodes = GBT_size_of_tree(gb_main, "tree_nj_bs");
1316            TEST_EXPECT_EQUAL(inner_nodes, 5);
1317            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");
1318            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");
1319
1320            {
1321                TreeNode *tree = GBT_read_tree(gb_main, "tree_nj_bs", new SimpleRoot);
1322
1323                TEST_REJECT_NULL(tree);
1324
1325                size_t leaf_count = GBT_count_leafs(tree);
1326
1327                size_t   species_count;
1328                GB_CSTR *species = GBT_get_names_of_species_in_tree(tree, &species_count);
1329
1330                StrArray species2;
1331                for (int i = 0; species[i]; ++i) species2.put(strdup(species[i]));
1332
1333                TEST_EXPECT_EQUAL(species_count, leaf_count);
1334                TEST_EXPECT_EQUAL(long(species_count), inner_nodes+1);
1335
1336                {
1337                    char *joined = GBT_join_strings(species2, '*');
1338                    TEST_EXPECT_EQUAL(joined, "CloButyr*CloButy2*CorGluta*CorAquat*CurCitre*CytAquat");
1339                    free(joined);
1340                }
1341
1342                free(species);
1343
1344                TEST_EXPECT_NEWICK(nSIMPLE, tree, "(CloButyr,(CloButy2,((CorGluta,(CorAquat,CurCitre)),CytAquat)));");
1345                TEST_EXPECT_NEWICK(nSIMPLE, NULL, ";");
1346
1347                destroy(tree);
1348            }
1349
1350            TEST_EXPECT_EQUAL(GBT_existing_tree(gb_main, "tree_nj_bs"), "tree_nj_bs");
1351            TEST_EXPECT_EQUAL(GBT_existing_tree(gb_main, "tree_nosuch"), "tree_test");
1352        }
1353
1354        // changing tree order
1355        {
1356            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_test|tree_tree2|tree_nj|tree_nj_bs|tree_removal");
1357
1358            GBDATA *gb_test    = GBT_find_tree(gb_main, "tree_test");
1359            GBDATA *gb_tree2   = GBT_find_tree(gb_main, "tree_tree2");
1360            GBDATA *gb_nj      = GBT_find_tree(gb_main, "tree_nj");
1361            GBDATA *gb_nj_bs   = GBT_find_tree(gb_main, "tree_nj_bs");
1362            GBDATA *gb_removal = GBT_find_tree(gb_main, "tree_removal");
1363
1364            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_removal)); // move to bottom
1365            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_tree2|tree_nj|tree_nj_bs|tree_removal|tree_test");
1366
1367            TEST_EXPECT_EQUAL(GBT_tree_behind(gb_tree2), gb_nj);
1368            TEST_EXPECT_EQUAL(GBT_tree_behind(gb_nj), gb_nj_bs);
1369            TEST_EXPECT_EQUAL(GBT_tree_behind(gb_nj_bs), gb_removal);
1370            TEST_EXPECT_EQUAL(GBT_tree_behind(gb_removal), gb_test);
1371            TEST_EXPECT_NULL(GBT_tree_behind(gb_test));
1372
1373            TEST_EXPECT_NULL(GBT_tree_infrontof(gb_tree2));
1374            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj), gb_tree2);
1375            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj_bs), gb_nj);
1376            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_removal), gb_nj_bs);
1377            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_test), gb_removal);
1378
1379            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_INFRONTOF, gb_tree2)); // move back to top
1380            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_test|tree_tree2|tree_nj|tree_nj_bs|tree_removal");
1381
1382            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_tree2)); // move from top
1383            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_tree2|tree_test|tree_nj|tree_nj_bs|tree_removal");
1384
1385            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_removal, GBT_INFRONTOF, gb_nj)); // move from end
1386            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_tree2|tree_test|tree_removal|tree_nj|tree_nj_bs");
1387
1388            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_nj_bs, GBT_INFRONTOF, gb_nj_bs)); // noop
1389            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "5:tree_tree2|tree_test|tree_removal|tree_nj|tree_nj_bs");
1390
1391            TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_top_tree(gb_main)), "tree_tree2");
1392
1393            TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_next_tree(gb_removal)), "tree_nj");
1394            TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_next_tree(gb_nj_bs)), "tree_tree2"); // last -> first
1395        }
1396
1397        // check tree order is maintained by copy, rename and delete
1398
1399        {
1400            // copy
1401            TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_nosuch", "tree_whatever"), "tree 'tree_nosuch' not found");
1402            TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_test",   "tree_test"),     "source- and dest-tree are the same");
1403            TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_tree2",  "tree_test"),     "tree 'tree_test' already exists");
1404
1405            TEST_EXPECT_NO_ERROR(GBT_copy_tree(gb_main, "tree_test", "tree_test_copy"));
1406            TEST_REJECT_NULL(GBT_find_tree(gb_main, "tree_test_copy"));
1407            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "6:tree_tree2|tree_test|tree_test_copy|tree_removal|tree_nj|tree_nj_bs");
1408
1409            // rename
1410            TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_nj", "tree_renamed_nj"));
1411            TEST_REJECT_NULL(GBT_find_tree(gb_main, "tree_renamed_nj"));
1412            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "6:tree_tree2|tree_test|tree_test_copy|tree_removal|tree_renamed_nj|tree_nj_bs");
1413
1414            TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_tree2", "tree_renamed_tree2"));
1415            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "6:tree_renamed_tree2|tree_test|tree_test_copy|tree_removal|tree_renamed_nj|tree_nj_bs");
1416
1417            TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_test_copy", "tree_renamed_test_copy"));
1418            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "6:tree_renamed_tree2|tree_test|tree_renamed_test_copy|tree_removal|tree_renamed_nj|tree_nj_bs");
1419
1420            // delete
1421
1422            GBDATA *gb_nj_bs             = GBT_find_tree(gb_main, "tree_nj_bs");
1423            GBDATA *gb_renamed_nj        = GBT_find_tree(gb_main, "tree_renamed_nj");
1424            GBDATA *gb_renamed_test_copy = GBT_find_tree(gb_main, "tree_renamed_test_copy");
1425            GBDATA *gb_renamed_tree2     = GBT_find_tree(gb_main, "tree_renamed_tree2");
1426            GBDATA *gb_test              = GBT_find_tree(gb_main, "tree_test");
1427            GBDATA *gb_removal           = GBT_find_tree(gb_main, "tree_removal");
1428
1429            TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_tree2));
1430            TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_test_copy));
1431            TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_nj));
1432            TEST_EXPECT_NO_ERROR(GB_delete(gb_removal));
1433
1434            // .. two trees left
1435
1436            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_test|tree_nj_bs");
1437
1438            TEST_EXPECT_EQUAL(GBT_find_largest_tree(gb_main), gb_test);
1439            TEST_EXPECT_EQUAL(GBT_find_top_tree(gb_main), gb_test);
1440            TEST_EXPECT_EQUAL(GBT_find_bottom_tree(gb_main), gb_nj_bs);
1441           
1442            TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_test), gb_nj_bs);
1443            TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_test), gb_nj_bs);
1444            TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_nj_bs), gb_test);
1445
1446            TEST_EXPECT_NULL (GBT_tree_infrontof(gb_test));
1447            TEST_EXPECT_EQUAL(GBT_tree_behind   (gb_test), gb_nj_bs);
1448           
1449            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj_bs), gb_test);
1450            TEST_EXPECT_NULL (GBT_tree_behind   (gb_nj_bs));
1451
1452            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_nj_bs)); // move to bottom
1453            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_nj_bs|tree_test");
1454            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_INFRONTOF, gb_nj_bs)); // move to top
1455            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_test|tree_nj_bs");
1456           
1457            TEST_EXPECT_NO_ERROR(GB_delete(gb_nj_bs));
1458
1459            // .. one tree left
1460
1461            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "1:tree_test");
1462
1463            TEST_EXPECT_EQUAL(GBT_find_largest_tree(gb_main), gb_test);
1464            TEST_EXPECT_EQUAL(GBT_find_top_tree(gb_main), gb_test);
1465            TEST_EXPECT_EQUAL(GBT_find_bottom_tree(gb_main), gb_test);
1466           
1467            TEST_EXPECT_NULL(GBT_find_next_tree(gb_test)); // no other tree left
1468            TEST_EXPECT_NULL(GBT_tree_behind(gb_test));
1469            TEST_EXPECT_NULL(GBT_tree_infrontof(gb_test));
1470
1471            TEST_EXPECT_NO_ERROR(GB_delete(gb_test));
1472
1473            // .. no tree left
1474           
1475            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "0:");
1476
1477            TEST_EXPECT_NULL(GBT_find_tree(gb_main, "tree_test"));
1478            TEST_EXPECT_NULL(GBT_existing_tree(gb_main, "tree_whatever"));
1479            TEST_EXPECT_NULL(GBT_find_largest_tree(gb_main));
1480        }
1481    }
1482
1483    GB_close(gb_main);
1484}
1485TEST_PUBLISH(TEST_copy_rename_delete_tree_order);
1486
1487void TEST_tree_remove_leafs() {
1488    GB_shell  shell;
1489    GBDATA   *gb_main = GB_open("TEST_trees.arb", "r");
1490
1491    {
1492        GBT_TreeRemoveType tested_modes[] = {
1493            GBT_REMOVE_MARKED,
1494            GBT_REMOVE_UNMARKED,
1495            GBT_REMOVE_ZOMBIES,
1496            GBT_KEEP_MARKED,
1497        };
1498
1499        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);";
1500        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);";
1501        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);";
1502        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);";
1503        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);";
1504
1505        const char *kept_zombies_topo        = "(Zombie1:0.131,Zombie2:0.162);";
1506        const char *kept_zombies_broken_topo = "Zombie2;";
1507
1508        const char *empty_topo = ";";
1509
1510        GB_transaction ta(gb_main);
1511        for (unsigned mode = 0; mode<ARRAY_ELEMS(tested_modes); ++mode) {
1512            GBT_TreeRemoveType what = tested_modes[mode];
1513
1514            for (int linked = 0; linked<=1; ++linked) {
1515                TEST_ANNOTATE(GBS_global_string("mode=%u linked=%i", mode, linked));
1516
1517                TreeNode *tree = GBT_read_tree(gb_main, "tree_removal", new SimpleRoot);
1518                gb_assert(tree);
1519                bool once = mode == 0 && linked == 0;
1520
1521                if (linked) {
1522                    int zombies    = 0;
1523                    int duplicates = 0;
1524
1525                    TEST_EXPECT_NO_ERROR(GBT_link_tree(tree, gb_main, false, &zombies, &duplicates));
1526
1527                    TEST_EXPECT_EQUAL(zombies, 2);
1528                    TEST_EXPECT_EQUAL(duplicates, 0);
1529                }
1530
1531                if (once) TEST_EXPECT_NEWICK(nLENGTH, tree, org_topo);
1532
1533                int removedCount       = 0;
1534                int groupsRemovedCount = 0;
1535
1536                tree = GBT_remove_leafs(tree, what, NULL, &removedCount, &groupsRemovedCount);
1537
1538                if (linked) {
1539                    GBT_TreeRemoveType what_next = what;
1540
1541                    switch (what) {
1542                        case GBT_REMOVE_MARKED:
1543                            TEST_EXPECT_EQUAL(removedCount, 6);
1544                            TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1545                            TEST_EXPECT_NEWICK(nLENGTH, tree, rem_marked_topo);
1546                            what_next = GBT_REMOVE_UNMARKED;
1547                            break;
1548                        case GBT_REMOVE_UNMARKED:
1549                            TEST_EXPECT_EQUAL(removedCount, 9);
1550                            TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1551                            TEST_EXPECT_NEWICK(nLENGTH, tree, rem_unmarked_topo);
1552                            what_next = GBT_REMOVE_MARKED;
1553                            break;
1554                        case GBT_REMOVE_ZOMBIES:
1555                            TEST_EXPECT_EQUAL(removedCount, 2);
1556                            TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1557                            TEST_EXPECT_NEWICK(nLENGTH, tree, rem_zombies_topo);
1558                            break;
1559                        case GBT_KEEP_MARKED:
1560                            TEST_EXPECT_EQUAL(removedCount, 11);
1561                            TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1562                            TEST_EXPECT_NEWICK(nLENGTH, tree, kept_marked_topo);
1563                            {
1564                                // just a test for nWRAP NewickFormat (may be removed later)
1565                                const char *kept_marked_topo_wrapped =
1566                                    "(\n"
1567                                    " CurCitre:1.000,\n"
1568                                    " (\n"
1569                                    "  (\n"
1570                                    "   CloButy2:0.009,\n"
1571                                    "   CloButyr:0.000\n"
1572                                    "  ):0.131,\n"
1573                                    "  (\n"
1574                                    "   CytAquat:0.711,\n"
1575                                    "   (\n"
1576                                    "    CorGluta:0.522,\n"
1577                                    "    CorAquat:0.103\n"
1578                                    "   ):0.207\n"
1579                                    "  ):0.162\n"
1580                                    " ):0.124);";
1581                                TEST_EXPECT_NEWICK(NewickFormat(nLENGTH|nWRAP), tree, kept_marked_topo_wrapped);
1582
1583                                const char *expected_compacted =
1584                                    "(CurCitre:1.000,\n"
1585                                    " ((CloButy2:0.009,\n"
1586                                    "   CloButyr:0.000):0.131,\n"
1587                                    "  (CytAquat:0.711,\n"
1588                                    "   (CorGluta:0.522,\n"
1589                                    "    CorAquat:0.103):0.207):0.162):0.124);";
1590                                char *compacted = GBT_tree_2_newick(tree, NewickFormat(nLENGTH|nWRAP), true);
1591                                TEST_EXPECT_EQUAL(compacted, expected_compacted);
1592                                free(compacted);
1593                            }
1594                            what_next = GBT_REMOVE_MARKED;
1595                            break;
1596                    }
1597
1598                    if (what_next != what) {
1599                        gb_assert(tree);
1600                        tree = GBT_remove_leafs(tree, what_next, NULL, &removedCount, &groupsRemovedCount);
1601
1602                        switch (what) {
1603                            case GBT_REMOVE_MARKED: // + GBT_REMOVE_UNMARKED
1604                                TEST_EXPECT_EQUAL(removedCount, 16);
1605                                TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1606                                TEST_EXPECT_NEWICK__BROKEN(nLENGTH, tree, kept_zombies_topo);
1607                                TEST_EXPECT_NEWICK(nLENGTH, tree, kept_zombies_broken_topo); // @@@ invalid topology (single leaf)
1608                                break;
1609                            case GBT_REMOVE_UNMARKED: // + GBT_REMOVE_MARKED
1610                                TEST_EXPECT_EQUAL(removedCount, 15);
1611                                TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1612                                TEST_EXPECT_NEWICK(nLENGTH, tree, kept_zombies_topo);
1613                                break;
1614                            case GBT_KEEP_MARKED: // + GBT_REMOVE_MARKED
1615                                TEST_EXPECT_EQUAL(removedCount, 17);
1616                                TEST_EXPECT_EQUAL__BROKEN(groupsRemovedCount, 2, 1); // @@@ expect that all groups have been removed!
1617                                TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1618                                TEST_EXPECT_NEWICK(nLENGTH, tree, empty_topo);
1619                                break;
1620                            default:
1621                                TEST_REJECT(true);
1622                                break;
1623                        }
1624                    }
1625                }
1626                else {
1627                    switch (what) {
1628                        case GBT_REMOVE_MARKED:
1629                        case GBT_REMOVE_UNMARKED:
1630                            TEST_EXPECT_EQUAL(removedCount, 0);
1631                            TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1632                            TEST_EXPECT_NEWICK(nLENGTH, tree, org_topo);
1633                            break;
1634                        case GBT_REMOVE_ZOMBIES:
1635                        case GBT_KEEP_MARKED:
1636                            TEST_EXPECT_EQUAL(removedCount, 17);
1637                            TEST_EXPECT_EQUAL(groupsRemovedCount, 2);
1638                            TEST_EXPECT_NEWICK(nLENGTH, tree, empty_topo);
1639                            break;
1640                    }
1641                }
1642
1643                if (tree) {
1644                    gb_assert(tree->is_root_node());
1645                    destroy(tree);
1646                }
1647            }
1648        }
1649    }
1650
1651    GB_close(gb_main);
1652}
1653TEST_PUBLISH(TEST_tree_remove_leafs);
1654
1655
1656#endif // UNIT_TESTS
Note: See TracBrowser for help on using the repository browser.