source: tags/ms_r16q4/ARBDB/adtree.cxx

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