source: branches/stable/ARBDB/adtree.cxx

Last change on this file was 17836, checked in by westram, 5 years ago
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 73.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 !NULp)
39     * @param groups_removed will be incremented for each removed group (if !NULp)
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); // 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 = NULp;
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 = NULp;
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 = NULp;
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 = NULp;
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 = NULp;
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    = NULp;
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   = NULp;
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              = NULp;
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, bool pedantic) {
230    GB_ERROR error = NULp;
231
232    gb_assert(strcmp(GB_read_key_pntr(gb_group_name), "group_name") == 0);
233
234    if (!error) {
235        // deny several uses of '!' (at start and in the middle after '=' or ' ')
236        for (const char *em = strchr(new_group_name, '!'); em && !error; em = strchr(em+1, '!')) {
237            if (em == new_group_name || em[-1] == ' ' || em[-1] == '=') {
238                error = GBS_global_string("Invalid placement of '!' in group name '%s'\n(reserved for keeled groups)", new_group_name);
239            }
240        }
241    }
242
243    if (!error) {
244        size_t len = strlen(new_group_name);
245        if (len >= GB_GROUP_NAME_MAX) {
246            error = GBS_global_string("Group name '%s' too long (max %i characters)", new_group_name, GB_GROUP_NAME_MAX);
247        }
248        else if (len<1) {
249            error = "Invalid empty group name";
250        }
251    }
252
253    // warn about unwanted groupnames:
254    if (!error && pedantic) {
255        // group names which may be misinterpreted as bootstrap-values (see also #767):
256        const char *num        = "0123456789.";
257        size_t      numAtStart = strspn(new_group_name, num);
258
259        if (numAtStart && !new_group_name[numAtStart]) {
260            GB_warningf("Warning: group name '%s' may be misinterpreted as bootstrap value\n"
261                        "(consider prefixing a non-numeric character)",
262                        new_group_name);
263        }
264
265        // warn about '/' in group name:
266        if (strchr(new_group_name, '/')) {
267            GB_warningf("Warning: group name '%s' contains a '/'\n"
268                        "(this will interfere with taxonomy!)",
269                        new_group_name);
270        }
271    }
272
273
274    if (!error) {
275        error = GB_write_string(gb_group_name, new_group_name);
276    }
277    return error;
278}
279GB_ERROR GBT_write_name_to_groupData(GBDATA *gb_group, bool createNameEntry, const char *new_group_name, bool pedantic) { 
280    GBDATA *gb_group_name = GB_search(gb_group, "group_name", createNameEntry ? GB_STRING : GB_FIND);
281    return gb_group_name
282        ? GBT_write_group_name(gb_group_name, new_group_name, pedantic)
283        : GB_await_error();
284}
285
286static GB_ERROR gbt_write_tree_nodes(GBDATA *gb_tree, TreeNode *node, long *startid) {
287    // increments '*startid' for each inner node (not for leafs)
288
289    GB_ERROR error = NULp;
290
291    if (!node->is_leaf()) {
292        bool node_is_used = false;
293
294        if (node->name && node->name[0]) {
295            if (!node->gb_node) {
296                node->gb_node = GB_create_container(gb_tree, "node");
297                if (!node->gb_node) error = GB_await_error();
298            }
299            if (!error) {
300                GBDATA *gb_name     = GB_search(node->gb_node, "group_name", GB_STRING);
301                if (!gb_name) error = GB_await_error();
302                else    error       = GBT_write_group_name(gb_name, node->name, false);
303
304                node_is_used = true; // wrote groupname -> node is used
305            }
306            if (!error) {
307                int     keeledState   = node->keeledStateInfo();
308                GBDATA *gb_keeled     = GB_search(node->gb_node, "keeled", keeledState ? GB_INT : GB_FIND); // only force creation if keeledState != 0
309                if (!gb_keeled) error = keeledState || GB_have_error() ? GB_await_error() : NULp;
310                else    error         = GB_write_int(gb_keeled, keeledState);
311            }
312        }
313
314        if (node->gb_node && !error) {
315            if (!node_is_used) {
316                GBDATA *gb_nonid = GB_child(node->gb_node);
317                while (gb_nonid && strcmp("id", GB_read_key_pntr(gb_nonid)) == 0) {
318                    gb_nonid = GB_nextChild(gb_nonid);
319                }
320                if (gb_nonid) node_is_used = true; // found child that is not "id" -> node is used
321            }
322
323            if (node_is_used) { // set id for used nodes
324                error = GBT_write_int(node->gb_node, "id", *startid);
325                if (!error) GB_clear_user_flag(node->gb_node, GB_USERFLAG_GHOSTNODE); // mark node as "used"
326            }
327            else {          // delete unused nodes
328                error = GB_delete(node->gb_node);
329                if (!error) node->gb_node = NULp;
330            }
331        }
332
333        (*startid)++;
334        if (!error) error = gbt_write_tree_nodes(gb_tree, node->get_leftson(), startid);
335        if (!error) error = gbt_write_tree_nodes(gb_tree, node->get_rightson(), startid);
336    }
337    return error;
338}
339
340static char *gbt_write_tree_rek_new(const TreeNode *node, char *dest, long mode) {
341    if (node->is_leaf()) {
342        gb_assert(node->has_no_remark());
343        if (mode == GBT_PUT_DATA) {
344            *(dest++) = 'L';
345            if (node->name) strcpy(dest, node->name);
346
347            char *c1;
348            while ((c1 = (char *)strchr(dest, 1))) {
349                *c1 = 2;
350            }
351            dest      += strlen(dest);
352            *(dest++)  = 1;
353           
354            return dest;
355        }
356        else {
357            if (node->name) return dest+1+strlen(node->name)+1; // N name term
358            return dest+1+1;
359        }
360    }
361    else {
362        { // write remark
363            const char *c1 = node->get_remark();
364            if (c1) {
365                if (mode == GBT_PUT_DATA) {
366                    int c;
367                    *(dest++) = 'R';
368                    while ((c = *(c1++))) {
369                        if (c == 1) continue;
370                        *(dest++) = c;
371                    }
372                    *(dest++) = 1;
373                }
374                else {
375                    dest += strlen(c1) + 2;
376                }
377            }
378        }
379        char buffer[40];
380        sprintf(buffer, "%g,%g;", node->leftlen, node->rightlen);
381        if (mode == GBT_PUT_DATA) {
382            *(dest++) = 'N';
383            strcpy(dest, buffer);
384            dest += strlen(buffer);
385        }
386        else {
387            dest += strlen(buffer)+1;
388        }
389        dest = gbt_write_tree_rek_new(node->get_leftson(),  dest, mode);
390        dest = gbt_write_tree_rek_new(node->get_rightson(), dest, mode);
391        return dest;
392    }
393}
394
395static GB_ERROR gbt_write_tree(GBDATA *gb_main, GBDATA *gb_tree, const char *tree_name, TreeNode *tree) {
396    /*! writes a tree to the database.
397     *
398     * If tree is loaded by function GBT_read_tree(..) then 'tree_name' should be NULp
399     * else 'gb_tree' should be set to NULp
400     *
401     * To copy a tree call GBT_copy_tree() or copy_tree_container()
402     * or set recursively all tree->gb_node variables to zero (that unlinks the tree),
403     */
404
405    GB_ERROR error = NULp;
406
407    if (tree) {
408        if (tree_name) {
409            if (gb_tree) error = GBS_global_string("can't change name of existing tree (to '%s')", tree_name);
410            else {
411                error = GBT_check_tree_name(tree_name);
412                if (!error) {
413                    GBDATA *gb_tree_data = GBT_get_tree_data(gb_main);
414                    gb_tree              = GB_search(gb_tree_data, tree_name, GB_CREATE_CONTAINER);
415
416                    if (!gb_tree) error = GB_await_error();
417                }
418            }
419        }
420        else {
421            if (!gb_tree) error = "No tree name given";
422        }
423
424        gb_assert(gb_tree || error);
425
426        if (!error) {
427            // mark all old style tree data for deletion
428            GBDATA *gb_node;
429            for (gb_node = GB_entry(gb_tree, "node"); gb_node; gb_node = GB_nextEntry(gb_node)) {
430                GB_raise_user_flag(gb_node, GB_USERFLAG_GHOSTNODE); // mark as "possibly unused"
431            }
432
433            // build tree-string and save to DB
434            {
435                char *t_size = gbt_write_tree_rek_new(tree, NULp, GBT_GET_SIZE); // calc size of tree-string
436                char *ctree  = ARB_calloc<char>(size_t(t_size+1));               // allocate buffer for tree-string
437
438                t_size = gbt_write_tree_rek_new(tree, ctree, GBT_PUT_DATA); // write into buffer
439                *(t_size) = 0;
440
441                bool was_allowed = GB_allow_compression(gb_main, false);
442                error            = GBT_write_string(gb_tree, "tree", ctree);
443                GB_allow_compression(gb_main, was_allowed);
444                free(ctree);
445            }
446        }
447
448        if (!error) {
449            // save nodes to DB
450            long size         = 0;
451            error             = gbt_write_tree_nodes(gb_tree, tree, &size); // reports number of nodes in 'size'
452            if (!error) error = GBT_write_int(gb_tree, "nnodes", size);
453
454            if (!error) {
455                if (!GB_entry(gb_tree, "keep_ghostnodes")) { // see ../PARSIMONY/PARS_main.cxx@keep_ghostnodes
456                    GBDATA *gb_node;
457                    GBDATA *gb_node_next;
458
459                    for (gb_node = GB_entry(gb_tree, "node"); // delete all ghost nodes
460                         gb_node && !error;
461                         gb_node = gb_node_next)
462                    {
463                        GBDATA *gbd = GB_entry(gb_node, "id");
464                        gb_node_next = GB_nextEntry(gb_node);
465                        if (!gbd || GB_user_flag(gb_node, GB_USERFLAG_GHOSTNODE)) error = GB_delete(gb_node);
466                    }
467                }
468            }
469        }
470
471        if (!error) tree_set_default_order(gb_tree);
472    }
473
474    return error;
475}
476
477GB_ERROR GBT_write_tree(GBDATA *gb_main, const char *tree_name, TreeNode *tree) {
478    return gbt_write_tree(gb_main, NULp, tree_name, tree);
479}
480GB_ERROR GBT_overwrite_tree(GBDATA *gb_tree, TreeNode *tree) {
481    return gbt_write_tree(GB_get_root(gb_tree), gb_tree, NULp, tree);
482}
483
484static GB_ERROR write_tree_remark(GBDATA *gb_tree, const char *remark) {
485    return GBT_write_string(gb_tree, "remark", remark);
486}
487GB_ERROR GBT_write_tree_remark(GBDATA *gb_main, const char *tree_name, const char *remark) {
488    return write_tree_remark(GBT_find_tree(gb_main, tree_name), remark);
489}
490
491GB_ERROR GBT_log_to_tree_remark(GBDATA *gb_tree, const char *log_entry, bool stamp) {
492    /*! append 'log_entry' to tree comment
493     * @param gb_tree     the tree
494     * @param log_entry   text to append
495     * @param stamp       true -> prefix date before 'log_entry'
496     * @return error in case of failure
497     */
498    GB_ERROR    error      = NULp;
499    const char *old_remark = GBT_read_char_pntr(gb_tree, "remark");
500    if (!old_remark && GB_have_error()) {
501        error = GB_await_error();
502    }
503    else {
504        char *new_remark = GBS_log_action_to(old_remark, log_entry, stamp);
505        error            = write_tree_remark(gb_tree, new_remark);
506        free(new_remark);
507    }
508    return error;
509}
510GB_ERROR GBT_log_to_tree_remark(GBDATA *gb_main, const char *tree_name, const char *log_entry, bool stamp) {
511    /*! append 'log_entry' to tree comment
512     * @param gb_main     database
513     * @param tree_name   name of tree
514     * @param log_entry   text to append
515     * @param stamp       true -> prefix date before 'log_entry'
516     * @return error in case of failure
517     */
518    GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
519    return gb_tree
520        ? GBT_log_to_tree_remark(gb_tree, log_entry, stamp)
521        : GBS_global_string("No such tree (%s)", tree_name);
522}
523
524GB_ERROR GBT_write_tree_with_remark(GBDATA *gb_main, const char *tree_name, TreeNode *tree, const char *remark) {
525    GB_ERROR error              = GBT_write_tree(gb_main, tree_name, tree);
526    if (!error && remark) error = GBT_write_tree_remark(gb_main, tree_name, remark);
527    return error;
528}
529
530// ----------------------------
531//      tree read functions
532
533static TreeNode *gbt_read_tree_rek(char **data, long *startid, GBDATA **gb_tree_nodes, TreeRoot *troot, int size_of_tree, GB_ERROR& error) {
534    TreeNode *node = NULp;
535    if (!error) {
536        node = troot->makeNode();
537
538        char  c = *((*data)++);
539        char *p1;
540
541        if (c=='R') {
542            p1      = strchr(*data, 1);
543            *(p1++) = 0;
544
545            node->set_remark(*data);
546            if (node->is_inner_node_with_remark()) {
547                double bootval;
548                if (node->parse_bootstrap(bootval) == REMARK_BOOTSTRAP) {
549                    if (bootval == 100.0) node->remove_remark(); // auto-remove 100% comments
550                    else troot->set_bootstrap_seen(true); // activate auto-100% only if bootstrap value != 100% was seen
551                }
552            }
553
554            c     = *(p1++);
555            *data = p1;
556        }
557
558
559        if (c=='N') {
560            p1 = (char *)strchr(*data, ',');
561            *(p1++) = 0;
562            node->leftlen = GB_atof(*data);
563            *data = p1;
564            p1 = (char *)strchr(*data, ';');
565            *(p1++) = 0;
566            node->rightlen = GB_atof(*data);
567            *data = p1;
568            if ((*startid < size_of_tree) && (node->gb_node = gb_tree_nodes[*startid])) {
569                GBDATA *gb_group_name = GB_entry(node->gb_node, "group_name");
570                if (gb_group_name) {
571                    node->name = GB_read_string(gb_group_name);
572                    if (!node->name || !node->name[0]) {
573                        char   *auto_rename = ARB_strdup("<missing groupname>");
574                        GBDATA *gb_main     = GB_get_root(gb_group_name);
575
576                        const char *warn;
577                        if (!node->name) {
578                            warn = GBS_global_string("Unreadable 'group_name' detected (Reason: %s)", GB_await_error());
579                        }
580                        else {
581                            warn = "Empty groupname detected";
582                        }
583                        warn = GBS_global_string("%s\nGroup has been named '%s'", warn, auto_rename);
584                        GBT_message(gb_main, warn);
585
586                        GB_ERROR rename_error = GBT_write_group_name(gb_group_name, auto_rename, false);
587                        if (rename_error) {
588                            GBT_message(gb_main,
589                                        GBS_global_string("Failed to name group (Reason: %s)\n"
590                                                          "Please check tree for corrupted groups, e.g. by using group search",
591                                                          rename_error));
592                        }
593                        node->name = auto_rename;
594                    }
595
596                    // init node according to saved "keeled" state:
597                    GBDATA *gb_keeled = GB_entry(node->gb_node, "keeled");
598                    if (gb_keeled) { // missing = default = not keeled
599                        int keeledState = GB_read_int(gb_keeled);
600                        node->setKeeledState(keeledState);
601                    }
602                }
603            }
604            (*startid)++;
605            node->leftson = gbt_read_tree_rek(data, startid, gb_tree_nodes, troot, size_of_tree, error);
606            if (!node->leftson) freenull(node);
607            else {
608                node->rightson = gbt_read_tree_rek(data, startid, gb_tree_nodes, troot, size_of_tree, error);
609                if (!node->rightson) {
610                    freenull(node->leftson);
611                    freenull(node);
612                }
613                else {
614                    node->leftson->father  = node;
615                    node->rightson->father = node;
616                }
617            }
618        }
619        else if (c=='L') {
620            node->markAsLeaf();
621            p1 = (char *)strchr(*data, 1);
622
623            gb_assert(p1);
624            gb_assert(p1[0] == 1);
625
626            *p1        = 0;
627            node->name = ARB_strdup(*data);
628            *data      = p1+1;
629        }
630        else {
631            if (!c) {
632                error = "Unexpected end of tree definition.";
633            }
634            else {
635                error = GBS_global_string("Can't interpret tree definition (expected 'N' or 'L' - not '%c')", c);
636            }
637            freenull(node);
638        }
639    }
640    gb_assert(contradicted(node, error));
641    return node;
642}
643
644
645static TreeNode *read_tree_and_size_internal(GBDATA *gb_tree, GBDATA *gb_ctree, TreeRoot *troot, int node_count, GB_ERROR& error) {
646    GBDATA   **gb_tree_nodes;
647    TreeNode  *node = NULp; // root node
648
649    ARB_calloc(gb_tree_nodes, node_count);
650    if (gb_tree) {
651        GBDATA *gb_node;
652
653        for (gb_node = GB_entry(gb_tree, "node"); gb_node && !error; gb_node = GB_nextEntry(gb_node)) {
654            long    i;
655            GBDATA *gbd = GB_entry(gb_node, "id");
656            if (!gbd) continue;
657
658            i = GB_read_int(gbd);
659            if (i<0 || i >= node_count) {
660                error = "An inner node of the tree is corrupt";
661            }
662            else {
663                gb_tree_nodes[i] = gb_node;
664            }
665        }
666    }
667    if (!error) {
668        char * const treeString = GB_read_string(gb_ctree);
669        if (!treeString) {
670            error = GB_await_error();
671        }
672        else {
673            char *ts = treeString;
674            long  id = 0;
675
676            troot->set_bootstrap_seen(false); // will be update by gbt_read_tree_rek
677            node = gbt_read_tree_rek(&ts, &id, gb_tree_nodes, troot, node_count, error);
678        }
679        free(treeString);
680    }
681
682    free(gb_tree_nodes);
683
684    if (node) {
685        gb_assert(!node->father); // @@@ if never fails -> if condition is ok!
686
687        if (node->has_group_info()) {
688            if (node->is_normal_group()) {
689                // workaround for #753:
690                GBDATA *gb_group      = node->gb_node;
691                GBDATA *gb_main       = GB_get_root(gb_group);
692                GBDATA *gb_group_name = GB_entry(gb_group, "group_name");
693
694                gb_assert(gb_group_name);
695                if (gb_group_name) {
696                    char *groupAtRoot_name = GB_read_string(gb_group_name);
697
698                    GBT_message(gb_main, GBS_global_string("Warning: invalid group '%s' at root of '%s' removed", groupAtRoot_name, GB_read_key_pntr(gb_tree)));
699                    error = GB_delete(gb_group_name);
700                    if (error) {
701                        GBT_message(gb_main, GBS_global_string("Failed to delete 'group_name' of root-node (Reason: %s)", error));
702                        error = NULp; // dont fail loading the tree
703                    }
704                    free(groupAtRoot_name);
705                }
706                freenull(node->name); // erase name from tree-structure
707                gb_assert(!node->is_normal_group());
708            }
709            else {
710                gb_assert(!node->keelTarget()); // root shall not host keeled group
711                // Assumed to be impossible; otherwise could be resolved by moving unkeeled group to other son(-of-root)
712            }
713        }
714    }
715    else {
716        gb_assert(error);
717    }
718
719    gb_assert(contradicted(node, error));
720    gb_assert(implicated(node, !node->is_normal_group()));
721    return node;
722}
723
724TreeNode *GBT_read_tree_and_size(GBDATA *gb_main, const char *tree_name, TreeRoot *troot, int *tree_size) {
725    /*! Loads a tree from DB into any user defined structure.
726     *
727     * @param gb_main DB root node
728     * @param tree_name is the name of the tree in the db
729     * @param troot constructs the tree-node instances
730     * @param tree_size if specified -> will be set to "size of tree" (aka number of leafs minus 1)
731     *
732     * @return
733     * - NULp if any error occurs (which is exported then)
734     * - root of loaded tree (dynamic type depends on 'nodeFactory')
735     */
736
737    GB_ERROR error = NULp;
738
739    if (!tree_name) {
740        error = "no treename given";
741    }
742    else {
743        error = GBT_check_tree_name(tree_name);
744        if (!error) {
745            GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
746
747            if (!gb_tree) {
748                error = "tree not found";
749            }
750            else {
751                GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
752                if (!gb_nnodes) {
753                    error = "tree is empty";
754                }
755                else {
756                    long size = GB_read_int(gb_nnodes);
757                    if (!size) {
758                        error = "has no nodes";
759                    }
760                    else {
761                        GBDATA *gb_ctree = GB_search(gb_tree, "tree", GB_FIND);
762                        if (!gb_ctree) {
763                            error = "old unsupported tree format";
764                        }
765                        else { // "new" style tree
766                            TreeNode *tree = read_tree_and_size_internal(gb_tree, gb_ctree, troot, size, error);
767                            if (!error) {
768                                gb_assert(tree);
769                                if (tree_size) *tree_size = size; // return size of tree (=leafs-1)
770                                tree->announce_tree_constructed();
771
772                                gb_assert(!tree->is_normal_group()); // root shall not be a group (see #753)
773
774                                return tree;
775                            }
776
777                            gb_assert(!tree);
778                        }
779                    }
780                }
781            }
782        }
783    }
784
785    gb_assert(error);
786    GB_export_errorf("Failed to read tree '%s' (Reason: %s)", tree_name, error);
787    troot->delete_by_node();
788    return NULp;
789}
790
791TreeNode *GBT_read_tree(GBDATA *gb_main, const char *tree_name, TreeRoot *troot) {
792    //! @see GBT_read_tree_and_size()
793    return GBT_read_tree_and_size(gb_main, tree_name, troot, NULp);
794}
795
796size_t GBT_count_leafs(const TreeNode *tree) {
797    if (tree->is_leaf()) {
798        return 1;
799    }
800    return GBT_count_leafs(tree->get_leftson()) + GBT_count_leafs(tree->get_rightson());
801}
802
803static GB_ERROR gbt_invalid_because(const TreeNode *tree, const char *reason) {
804    return GBS_global_string("((TreeNode*)0x%p) %s", tree, reason);
805}
806
807inline bool has_son(const TreeNode *father, const TreeNode *son) {
808    return !father->is_leaf() && (father->leftson == son || father->rightson == son);
809}
810
811static GB_ERROR gbt_is_invalid(bool is_root, const TreeNode *tree) {
812    if (tree->father) {
813        if (!has_son(tree->get_father(), tree)) return gbt_invalid_because(tree, "is not son of its father");
814    }
815    else {
816        if (!is_root) return gbt_invalid_because(tree, "has no father (but isn't root)");
817    }
818
819    GB_ERROR error = NULp;
820    if (tree->is_leaf()) {
821        if (tree->leftson) return gbt_invalid_because(tree, "is leaf, but has leftson");
822        if (tree->rightson) return gbt_invalid_because(tree, "is leaf, but has rightson");
823    }
824    else {
825        if (!tree->leftson) return gbt_invalid_because(tree, "is inner node, but has no leftson");
826        if (!tree->rightson) return gbt_invalid_because(tree, "is inner node, but has no rightson");
827
828        error             = gbt_is_invalid(false, tree->get_leftson());
829        if (!error) error = gbt_is_invalid(false, tree->get_rightson());
830    }
831    return error;
832}
833
834GB_ERROR GBT_is_invalid(const TreeNode *tree) {
835    if (tree->father) return gbt_invalid_because(tree, "is expected to be the root-node, but has father");
836    if (tree->is_leaf()) return gbt_invalid_because(tree, "is expected to be the root-node, but is a leaf (tree too small)");
837    return gbt_is_invalid(true, tree);
838}
839
840// -------------------------------------------
841//      link the tree tips to the database
842
843struct link_tree_data {
844    GB_HASH      *species_hash;
845    GB_HASH      *seen_species;                     // used to count duplicates
846    arb_progress *progress;
847    int           zombies;                          // counts zombies
848    int           duplicates;                       // counts duplicates
849};
850
851static GB_ERROR gbt_link_tree_to_hash_rek(TreeNode *tree, link_tree_data *ltd) {
852    GB_ERROR error = NULp;
853    if (tree->is_leaf()) {
854        tree->gb_node = NULp;
855        if (tree->name) {
856            GBDATA *gbd = (GBDATA*)GBS_read_hash(ltd->species_hash, tree->name);
857            if (gbd) tree->gb_node = gbd;
858            else ltd->zombies++;
859
860            if (ltd->seen_species) {
861                if (GBS_read_hash(ltd->seen_species, tree->name)) ltd->duplicates++;
862                else GBS_write_hash(ltd->seen_species, tree->name, 1);
863            }
864        }
865
866        if (ltd->progress) ++(*ltd->progress);
867    }
868    else {
869        error             = gbt_link_tree_to_hash_rek(tree->get_leftson(), ltd);
870        if (!error) error = gbt_link_tree_to_hash_rek(tree->get_rightson(), ltd);
871    }
872    return error;
873}
874
875static GB_ERROR GBT_link_tree_using_species_hash(TreeNode *tree, bool show_status, GB_HASH *species_hash, int *zombies, int *duplicates) {
876    GB_ERROR       error;
877    link_tree_data ltd;
878    long           leafs = 0;
879
880    if (duplicates || show_status) {
881        leafs = GBT_count_leafs(tree);
882    }
883
884    ltd.species_hash = species_hash;
885    ltd.seen_species = leafs ? GBS_create_hash(leafs, GB_IGNORE_CASE) : NULp;
886    ltd.zombies      = 0;
887    ltd.duplicates   = 0;
888
889    if (show_status) {
890        ltd.progress = new arb_progress("Relinking tree to database", leafs);
891    }
892    else {
893        ltd.progress = NULp;
894    }
895
896    error = gbt_link_tree_to_hash_rek(tree, &ltd);
897    if (ltd.seen_species) GBS_free_hash(ltd.seen_species);
898
899    if (zombies) *zombies       = ltd.zombies;
900    if (duplicates) *duplicates = ltd.duplicates;
901
902    delete ltd.progress;
903
904    return error;
905}
906
907GB_ERROR GBT_link_tree(TreeNode *tree, GBDATA *gb_main, bool show_status, int *zombies, int *duplicates) { // @@@ most callers use NULp for last 2 args -> split like GBT_read_tree vs GBT_read_tree_and_size
908    /*! Link a given tree to the database. That means that for all tips the member
909     * 'gb_node' is set to the database container holding the species data.
910     *
911     * @param tree which will be linked to DB
912     * @param gb_main DB root node
913     * @param show_status show a progress indicator?
914     * @param zombies if specified -> set to number of zombies (aka non-existing species) in tree
915     * @param duplicates if specified -> set to number of duplicated species in tree
916     *
917     * @return error on failure
918     *
919     * @see GBT_unlink_tree()
920     */
921
922    GB_HASH  *species_hash = GBT_create_species_hash(gb_main);
923    GB_ERROR  error        = GBT_link_tree_using_species_hash(tree, show_status, species_hash, zombies, duplicates);
924
925    GBS_free_hash(species_hash);
926
927    return error;
928}
929
930void TreeNode::unlink_from_DB() {
931    /*! Unlink tree from the database.
932     * @see GBT_link_tree()
933     */
934    gb_node = NULp;
935    if (!is_leaf()) {
936        get_leftson()->unlink_from_DB();
937        get_rightson()->unlink_from_DB();
938    }
939}
940void GBT_unlink_tree(TreeNode *tree) {
941    tree->unlink_from_DB();
942}
943
944// ----------------------
945//      search trees
946
947GBDATA *GBT_find_tree(GBDATA *gb_main, const char *tree_name) {
948    /*! @return
949     * - DB tree container associated with tree_name
950     * - NULp if no such tree exists
951     */
952    return GB_entry(GBT_get_tree_data(gb_main), tree_name);
953}
954
955inline bool is_tree(GBDATA *gb_tree) {
956    if (!gb_tree) return false;
957    GBDATA *gb_tree_data = GB_get_father(gb_tree);
958    return gb_tree_data && GB_has_key(gb_tree_data, "tree_data");
959}
960
961inline GBDATA *get_first_tree(GBDATA *gb_main) {
962    return GB_child(GBT_get_tree_data(gb_main));
963}
964
965inline GBDATA *get_next_tree(GBDATA *gb_tree) {
966    if (!gb_tree) return NULp;
967    gb_assert(is_tree(gb_tree));
968    return GB_nextChild(gb_tree);
969}
970
971static GBDATA *find_largest_tree(GBDATA *gb_main) {
972    long    maxnodes   = 0;
973    GBDATA *gb_largest = NULp;
974
975    for (GBDATA *gb_tree = get_first_tree(gb_main); gb_tree; gb_tree = get_next_tree(gb_tree)) {
976        long *nnodes = GBT_read_int(gb_tree, "nnodes");
977        if (nnodes && *nnodes>maxnodes) {
978            gb_largest = gb_tree;
979            maxnodes   = *nnodes;
980        }
981    }
982    return gb_largest;
983}
984
985GBDATA *GBT_tree_infrontof(GBDATA *gb_tree) {
986    GBDATA *gb_treedata = GB_get_father(gb_tree);
987    ensure_trees_have_order(gb_treedata);
988    return get_tree_infrontof_idx(gb_treedata, get_tree_idx(gb_tree));
989}
990GBDATA *GBT_tree_behind(GBDATA *gb_tree) {
991    GBDATA *gb_treedata = GB_get_father(gb_tree);
992    ensure_trees_have_order(gb_treedata);
993    return get_tree_behind_idx(gb_treedata, get_tree_idx(gb_tree));
994}
995
996GBDATA *GBT_find_top_tree(GBDATA *gb_main) {
997    GBDATA *gb_treedata = GBT_get_tree_data(gb_main);
998    ensure_trees_have_order(gb_treedata);
999
1000    GBDATA *gb_top = get_tree_with_idx(gb_treedata, 1);
1001    if (!gb_top) gb_top = get_tree_behind_idx(gb_treedata, 1);
1002    return gb_top;
1003}
1004GBDATA *GBT_find_bottom_tree(GBDATA *gb_main) {
1005    GBDATA *gb_treedata = GBT_get_tree_data(gb_main);
1006    ensure_trees_have_order(gb_treedata);
1007    return get_tree_infrontof_idx(gb_treedata, INT_MAX);
1008}
1009
1010const char *GBT_existing_tree(GBDATA *gb_main, const char *tree_name) {
1011    // search for a specify existing tree (and fallback to any existing)
1012    GBDATA *gb_tree       = GBT_find_tree(gb_main, tree_name);
1013    if (!gb_tree) gb_tree = get_first_tree(gb_main);
1014    return GBT_get_tree_name(gb_tree);
1015}
1016
1017GBDATA *GBT_find_next_tree(GBDATA *gb_tree) {
1018    GBDATA *gb_other = NULp;
1019    if (gb_tree) {
1020        gb_other = GBT_tree_behind(gb_tree);
1021        if (!gb_other) {
1022            gb_other = GBT_find_top_tree(GB_get_root(gb_tree));
1023            if (gb_other == gb_tree) gb_other = NULp;
1024        }
1025    }
1026    gb_assert(gb_other != gb_tree);
1027    return gb_other;
1028}
1029
1030// --------------------
1031//      tree names
1032
1033const char *GBT_get_tree_name(GBDATA *gb_tree) {
1034    if (!gb_tree) return NULp;
1035    gb_assert(is_tree(gb_tree));
1036    return GB_read_key_pntr(gb_tree);
1037}
1038
1039GB_ERROR GBT_check_tree_name(const char *tree_name) {
1040    GB_ERROR error = GB_check_key(tree_name);
1041    if (!error) {
1042        if (strncmp(tree_name, "tree_", 5) != 0) {
1043            error = "has to start with 'tree_'";
1044        }
1045    }
1046    if (error) {
1047        if (strcmp(tree_name, NO_TREE_SELECTED) == 0) {
1048            error = "no tree selected"; // overwrites existing error
1049        }
1050        else {
1051            error = GBS_global_string("not a valid treename '%s' (Reason: %s)", tree_name, error);
1052        }
1053    }
1054    return error;
1055}
1056
1057const char *GBT_name_of_largest_tree(GBDATA *gb_main) {
1058    return GBT_get_tree_name(find_largest_tree(gb_main));
1059}
1060
1061const char *GBT_name_of_bottom_tree(GBDATA *gb_main) {
1062    return GBT_get_tree_name(GBT_find_bottom_tree(gb_main));
1063}
1064
1065// -------------------
1066//      tree info
1067
1068const char *GBT_tree_info_string(GBDATA *gb_main, const char *tree_name, int maxTreeNameLen) {
1069    // maxTreeNameLen shall be the max len of the longest tree name (or -1 -> do not format)
1070
1071    const char *result  = NULp;
1072    GBDATA     *gb_tree = GBT_find_tree(gb_main, tree_name);
1073
1074    if (!gb_tree) {
1075        GB_export_errorf("tree '%s' not found", tree_name);
1076    }
1077    else {
1078        GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
1079        if (!gb_nnodes) {
1080            GB_export_errorf("nnodes not found in tree '%s'", tree_name);
1081        }
1082        else {
1083            const char *sizeInfo = GBS_global_string("(%li:%i)", GB_read_int(gb_nnodes)+1, GB_read_security_write(gb_tree));
1084            GBDATA     *gb_rem   = GB_entry(gb_tree, "remark");
1085            int         len;
1086
1087            if (maxTreeNameLen == -1) {
1088                result = GBS_global_string("%s %11s", tree_name, sizeInfo);
1089                len    = strlen(tree_name);
1090            }
1091            else {
1092                result = GBS_global_string("%-*s %11s", maxTreeNameLen, tree_name, sizeInfo);
1093                len    = maxTreeNameLen;
1094            }
1095            if (gb_rem) {
1096                const char *remark    = GB_read_char_pntr(gb_rem);
1097                const int   remarkLen = 800;
1098                char       *res2      = GB_give_other_buffer(remark, len+1+11+2+remarkLen+1);
1099
1100                strcpy(res2, result);
1101                strcat(res2, "  ");
1102                strncat(res2, remark, remarkLen);
1103
1104                result = res2;
1105            }
1106        }
1107    }
1108    return result;
1109}
1110
1111long GBT_size_of_tree(GBDATA *gb_main, const char *tree_name) {
1112    // return the number of inner nodes in binary tree (or -1 if unknown)
1113    // Note:
1114    //        leafs                        = size + 1
1115    //        inner nodes in unrooted tree = size - 1
1116
1117    long    nnodes  = -1;
1118    GBDATA *gb_tree = GBT_find_tree(gb_main, tree_name);
1119    if (gb_tree) {
1120        GBDATA *gb_nnodes = GB_entry(gb_tree, "nnodes");
1121        if (gb_nnodes) {
1122            nnodes = GB_read_int(gb_nnodes);
1123        }
1124    }
1125    return nnodes;
1126}
1127
1128
1129struct indexed_name {
1130    int         idx;
1131    const char *name;
1132
1133    bool operator<(const indexed_name& other) const { return idx < other.idx; }
1134};
1135
1136void GBT_get_tree_names(ConstStrArray& names, GBDATA *gb_main, bool sorted) {
1137    // stores tree names in 'names'
1138
1139    GBDATA *gb_treedata = GBT_get_tree_data(gb_main);
1140    ensure_trees_have_order(gb_treedata);
1141
1142    long tree_count = GB_number_of_subentries(gb_treedata);
1143
1144    names.reserve(tree_count);
1145    typedef std::set<indexed_name> ordered_trees;
1146    ordered_trees trees;
1147
1148    {
1149        int t     = 0;
1150        int count = 0;
1151        for (GBDATA *gb_tree = GB_child(gb_treedata); gb_tree; gb_tree = GB_nextChild(gb_tree), ++t) {
1152            indexed_name iname;
1153            iname.name = GB_read_key_pntr(gb_tree);
1154            iname.idx  = sorted ? get_tree_idx(gb_tree) : ++count;
1155
1156            trees.insert(iname);
1157        }
1158    }
1159
1160    if (tree_count != (long)trees.size()) { // there are duplicated "order" entries
1161        gb_assert(sorted); // should not happen in unsorted mode
1162
1163        typedef std::set<int> ints;
1164
1165        ints    used_indices;
1166        GBDATA *gb_first_tree = GB_child(gb_treedata);
1167        GBDATA *gb_tree       = gb_first_tree;
1168
1169        while (gb_tree) {
1170            int idx = get_tree_idx(gb_tree);
1171            if (used_indices.find(idx) != used_indices.end()) { // duplicate order
1172                GB_ERROR error    = reserve_tree_idx(gb_treedata, idx+1);
1173                if (!error) error = set_tree_idx(gb_tree, idx+1);
1174                if (error) GBK_terminatef("failed to fix tree-order (Reason: %s)", error);
1175
1176                // now restart
1177                used_indices.clear();
1178                gb_tree = gb_first_tree;
1179            }
1180            else {
1181                used_indices.insert(idx);
1182                gb_tree = GB_nextChild(gb_tree);
1183            }
1184        }
1185        GBT_get_tree_names(names, gb_main, sorted);
1186        return;
1187    }
1188
1189    for (ordered_trees::const_iterator t = trees.begin(); t != trees.end(); ++t) {
1190        names.put(t->name);
1191    }
1192}
1193
1194NOT4PERL GB_ERROR GBT_move_tree(GBDATA *gb_moved_tree, GBT_ORDER_MODE mode, GBDATA *gb_target_tree) {
1195    // moves 'gb_moved_tree' next to 'gb_target_tree' (only changes tree-order)
1196    gb_assert(gb_moved_tree && gb_target_tree);
1197
1198    GBDATA *gb_treedata = GB_get_father(gb_moved_tree);
1199    ensure_trees_have_order(gb_treedata);
1200
1201    int target_idx = get_tree_idx(gb_target_tree);
1202    gb_assert(target_idx);
1203
1204    if (mode == GBT_BEHIND) target_idx++;
1205
1206    GB_ERROR error    = reserve_tree_idx(gb_treedata, target_idx);
1207    if (!error) error = set_tree_idx(gb_moved_tree, target_idx);
1208
1209    return error;
1210}
1211
1212static GBDATA *get_source_and_check_target_tree(GBDATA *gb_main, const char *source_tree, const char *dest_tree, GB_ERROR& error) {
1213    GBDATA *gb_source_tree = NULp;
1214
1215    error             = GBT_check_tree_name(source_tree);
1216    if (!error) error = GBT_check_tree_name(dest_tree);
1217
1218    if (error && strcmp(source_tree, NO_TREE_SELECTED) == 0) {
1219        error = "No tree selected";
1220    }
1221
1222    if (!error && strcmp(source_tree, dest_tree) == 0) error = "source- and dest-tree are the same";
1223
1224    if (!error) {
1225        gb_source_tree = GBT_find_tree(gb_main, source_tree);
1226        if (!gb_source_tree) error = GBS_global_string("tree '%s' not found", source_tree);
1227        else {
1228            GBDATA *gb_dest_tree = GBT_find_tree(gb_main, dest_tree);
1229            if (gb_dest_tree) {
1230                error = GBS_global_string("tree '%s' already exists", dest_tree);
1231                gb_source_tree = NULp;
1232            }
1233        }
1234    }
1235
1236    gb_assert(contradicted(error, gb_source_tree));
1237    return gb_source_tree;
1238}
1239
1240static GBDATA *copy_tree_container(GBDATA *gb_source_tree, const char *newName, GB_ERROR& error) {
1241    GBDATA *gb_treedata  = GB_get_father(gb_source_tree);
1242    GBDATA *gb_dest_tree = GB_create_container(gb_treedata, newName);
1243
1244    if (!gb_dest_tree) error = GB_await_error();
1245    else error               = GB_copy_dropProtectMarksAndTempstate(gb_dest_tree, gb_source_tree);
1246
1247    gb_assert(contradicted(error, gb_dest_tree));
1248    return gb_dest_tree;
1249}
1250
1251GB_ERROR GBT_copy_tree(GBDATA *gb_main, const char *source_name, const char *dest_name) {
1252    GB_ERROR  error;
1253    GBDATA   *gb_source_tree = get_source_and_check_target_tree(gb_main, source_name, dest_name, error);
1254
1255    if (gb_source_tree) {
1256        GBDATA *gb_dest_tree = copy_tree_container(gb_source_tree, dest_name, error);
1257        if (gb_dest_tree) {
1258            int source_idx = get_tree_idx(gb_source_tree);
1259            int dest_idx   = source_idx+1;
1260
1261            error             = reserve_tree_idx(GB_get_father(gb_dest_tree), dest_idx);
1262            if (!error) error = set_tree_idx(gb_dest_tree, dest_idx);
1263        }
1264    }
1265
1266    return error;
1267}
1268
1269GB_ERROR GBT_rename_tree(GBDATA *gb_main, const char *source_name, const char *dest_name) {
1270    GB_ERROR  error;
1271    GBDATA   *gb_source_tree = get_source_and_check_target_tree(gb_main, source_name, dest_name, error);
1272
1273    if (gb_source_tree) {
1274        GBDATA *gb_dest_tree = copy_tree_container(gb_source_tree, dest_name, error);
1275        if (gb_dest_tree) error = GB_delete(gb_source_tree);
1276    }
1277
1278    return error;
1279}
1280
1281static GB_CSTR *fill_species_name_array(GB_CSTR *current, const TreeNode *tree) {
1282    if (tree->is_leaf()) {
1283        current[0] = tree->name;
1284        return current+1;
1285    }
1286    current = fill_species_name_array(current, tree->get_leftson());
1287    current = fill_species_name_array(current, tree->get_rightson());
1288    return current;
1289}
1290
1291GB_CSTR *GBT_get_names_of_species_in_tree(const TreeNode *tree, size_t *count) {
1292    /* creates an array of all species names in a tree,
1293     * The names are not allocated (so they may change as side effect of renaming species) */
1294
1295    size_t   size   = GBT_count_leafs(tree);
1296    GB_CSTR *result = ARB_calloc<GB_CSTR>(size + 1);
1297   
1298    IF_ASSERTION_USED(GB_CSTR *check =) fill_species_name_array(result, tree);
1299    gb_assert(check - size == result);
1300
1301    if (count) *count = size;
1302
1303    return result;
1304}
1305
1306static void tree2newick(const TreeNode *tree, GBS_strstruct& out, NewickFormat format, int indent) {
1307    gb_assert(tree);
1308    if ((format&nWRAP) && indent>0) { out.put('\n'); out.nput(' ', indent); }
1309    if (tree->is_leaf()) {
1310        out.cat(tree->name);
1311    }
1312    else {
1313        out.put('(');
1314        tree2newick(tree->get_leftson(), out, format, indent+1);
1315        out.put(',');
1316        tree2newick(tree->get_rightson(), out, format, indent+1);
1317        if ((format&nWRAP) && indent>0) { out.put('\n'); out.nput(' ', indent); }
1318        out.put(')');
1319
1320        if (format & (nGROUP|nREMARK)) {
1321            const char *remark = format&nREMARK ? tree->get_remark() : NULp;
1322            const char *group  = NULp;
1323            const char *kgroup = NULp;
1324
1325            if (format&nGROUP) {
1326                if (tree->is_normal_group()) group  = tree->name;
1327                if (tree->is_keeled_group()) kgroup = tree->get_father()->name;
1328            }
1329
1330            if (remark || group || kgroup) {
1331                out.put('\'');
1332                if (remark) {
1333                    out.cat(remark);
1334                    if (group) out.put(':');
1335                }
1336                if (group) out.cat(group);
1337                if (kgroup) {
1338                    if (group) out.cat(" = ");
1339                    out.put('!');
1340                    out.cat(kgroup);
1341                }
1342                out.put('\'');
1343            }
1344        }
1345    }
1346
1347    if (format&nLENGTH && !tree->is_root_node()) {
1348        out.put(':');
1349        out.nprintf(10, "%5.3f", tree->get_branchlength());
1350    }
1351}
1352
1353char *GBT_tree_2_newick(const TreeNode *tree, NewickFormat format, bool compact) {
1354    // testcode-only newick exporter
1355    // see also ../SL/TREE_WRITE/TreeWrite.cxx@NEWICK_EXPORTER
1356    gb_assert(RUNNING_TEST());
1357
1358    GBS_strstruct out(1000);
1359    if (tree) tree2newick(tree, out, format, 0);
1360    out.put(';');
1361
1362    char *result = out.release();
1363    if (compact && (format&nWRAP)) {
1364        GB_ERROR error = NULp;
1365
1366        char *compact1 = GBS_regreplace(result, "/[\n ]*[)]/)/", &error);
1367        if (compact1) {
1368            char *compact2 = GBS_regreplace(compact1, "/[(][\n ]*/(/", &error);
1369            if (compact2) freeset(result, compact2);
1370            free(compact1);
1371        }
1372        if (error) {
1373            fprintf(stderr, "Error in GBT_tree_2_newick: %s\n", error);
1374            gb_assert(!error); // should be impossible; falls back to 'result' if happens
1375        }
1376    }
1377    return result;
1378}
1379
1380
1381// --------------------------------------------------------------------------------
1382
1383#ifdef UNIT_TESTS
1384#include <test_unit.h>
1385
1386static const char *getTreeOrder(GBDATA *gb_main) {
1387    ConstStrArray names;
1388    GBT_get_tree_names(names, gb_main, true);
1389
1390    char *joined         = GBT_join_strings(names, '|');
1391    char *size_and_names = GBS_global_string_copy("%zu:%s", names.size(), joined);
1392    free(joined);
1393
1394    RETURN_LOCAL_ALLOC(size_and_names);
1395}
1396
1397void TEST_tree_names() {
1398    TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name(""),               "not a valid treename");
1399    TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name("not_a_treename"), "not a valid treename");
1400    TEST_EXPECT_ERROR_CONTAINS(GBT_check_tree_name("tree_bad.dot"),   "not a valid treename");
1401
1402    TEST_EXPECT_NO_ERROR(GBT_check_tree_name("tree_")); // ugly but ok
1403    TEST_EXPECT_NO_ERROR(GBT_check_tree_name("tree_ok"));
1404}
1405
1406void TEST_tree_contraints() {
1407    // test minima
1408    const int MIN_LEAFS = 2;
1409
1410    TEST_EXPECT_EQUAL(leafs_2_nodes     (MIN_LEAFS, ROOTED),   3);
1411    TEST_EXPECT_EQUAL(leafs_2_nodes     (MIN_LEAFS, UNROOTED), 2);
1412    TEST_EXPECT_EQUAL(leafs_2_edges     (MIN_LEAFS, ROOTED),   2);
1413    TEST_EXPECT_EQUAL(leafs_2_edges     (MIN_LEAFS, UNROOTED), 1);
1414    TEST_EXPECT_EQUAL(leafs_2_innerNodes(MIN_LEAFS, ROOTED),   1);
1415    TEST_EXPECT_EQUAL(leafs_2_innerNodes(MIN_LEAFS, UNROOTED), 0);
1416
1417    TEST_EXPECT_EQUAL(MIN_LEAFS, nodes_2_leafs(3, ROOTED));   // test minimum (3 nodes rooted)
1418    TEST_EXPECT_EQUAL(MIN_LEAFS, nodes_2_leafs(2, UNROOTED)); // test minimum (2 nodes unrooted)
1419
1420    TEST_EXPECT_EQUAL(MIN_LEAFS, edges_2_leafs(2, ROOTED));   // test minimum (2 edges rooted)
1421    TEST_EXPECT_EQUAL(MIN_LEAFS, edges_2_leafs(1, UNROOTED)); // test minimum (1 edge unrooted)
1422
1423    // test inverse functions:
1424    for (int i = 3; i<=7; ++i) {
1425        // test "leaf->XXX" and back conversions (any number of leafs is possible)
1426        TEST_EXPECT_EQUAL(i, nodes_2_leafs(leafs_2_nodes(i, ROOTED),   ROOTED));
1427        TEST_EXPECT_EQUAL(i, nodes_2_leafs(leafs_2_nodes(i, UNROOTED), UNROOTED));
1428
1429        TEST_EXPECT_EQUAL(i, edges_2_leafs(leafs_2_edges(i, ROOTED),   ROOTED));
1430        TEST_EXPECT_EQUAL(i, edges_2_leafs(leafs_2_edges(i, UNROOTED), UNROOTED));
1431
1432        bool odd = i%2;
1433        if (odd) {
1434            TEST_EXPECT_EQUAL(i, leafs_2_nodes(nodes_2_leafs(i, ROOTED),   ROOTED));   // rooted trees only contain odd numbers of nodes
1435            TEST_EXPECT_EQUAL(i, leafs_2_edges(edges_2_leafs(i, UNROOTED), UNROOTED)); // unrooted trees only contain odd numbers of edges
1436        }
1437        else { // even
1438            TEST_EXPECT_EQUAL(i, leafs_2_nodes(nodes_2_leafs(i, UNROOTED), UNROOTED)); // unrooted trees only contain even numbers of nodes
1439            TEST_EXPECT_EQUAL(i, leafs_2_edges(edges_2_leafs(i, ROOTED),   ROOTED));   // rooted trees only contain even numbers of edges
1440        }
1441
1442        TEST_EXPECT_EQUAL(i + leafs_2_innerNodes(i, ROOTED),   leafs_2_nodes(i, ROOTED));
1443        TEST_EXPECT_EQUAL(i + leafs_2_innerNodes(i, UNROOTED), leafs_2_nodes(i, UNROOTED));
1444
1445        TEST_EXPECT_EQUAL(i + nodes_2_innerNodes(leafs_2_nodes(i, ROOTED),   ROOTED),   leafs_2_nodes(i, ROOTED));
1446        TEST_EXPECT_EQUAL(i + nodes_2_innerNodes(leafs_2_nodes(i, UNROOTED), UNROOTED), leafs_2_nodes(i, UNROOTED));
1447
1448        // test adding a leaf adds two nodes:
1449        int added = i+1;
1450        TEST_EXPECT_EQUAL(leafs_2_nodes(added, ROOTED)-leafs_2_nodes(i, ROOTED), 2);
1451        TEST_EXPECT_EQUAL(leafs_2_nodes(added, UNROOTED)-leafs_2_nodes(i, UNROOTED), 2);
1452    }
1453}
1454
1455void TEST_copy_rename_delete_tree_order() {
1456    GB_shell  shell;
1457    GBDATA   *gb_main = GB_open("TEST_trees.arb", "r");
1458
1459    {
1460        GB_transaction ta(gb_main);
1461
1462        {
1463            TEST_EXPECT_NULL(GBT_get_tree_name(NULp));
1464           
1465            TEST_EXPECT_EQUAL(GBT_name_of_largest_tree(gb_main), "tree_removal");
1466
1467            TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_top_tree(gb_main)), "tree_test");
1468            TEST_EXPECT_EQUAL(GBT_name_of_bottom_tree(gb_main), "tree_removal");
1469
1470            long inner_nodes = GBT_size_of_tree(gb_main, "tree_nj_bs");
1471            TEST_EXPECT_EQUAL(inner_nodes, 5);
1472            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");
1473            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");
1474
1475            {
1476                TreeNode *tree = GBT_read_tree(gb_main, "tree_nj_bs", new SimpleRoot);
1477
1478                TEST_REJECT_NULL(tree);
1479
1480                size_t leaf_count = GBT_count_leafs(tree);
1481
1482                size_t   species_count;
1483                GB_CSTR *species = GBT_get_names_of_species_in_tree(tree, &species_count);
1484
1485                StrArray species2;
1486                for (int i = 0; species[i]; ++i) species2.put(ARB_strdup(species[i]));
1487
1488                TEST_EXPECT_EQUAL(species_count, leaf_count);
1489                TEST_EXPECT_EQUAL(long(species_count), inner_nodes+1);
1490
1491                {
1492                    char *joined = GBT_join_strings(species2, '*');
1493                    TEST_EXPECT_EQUAL(joined, "CloButyr*CloButy2*CorGluta*CorAquat*CurCitre*CytAquat");
1494                    free(joined);
1495                }
1496
1497                free(species);
1498
1499                TEST_EXPECT_NEWICK(nSIMPLE, tree, "(CloButyr,(CloButy2,((CorGluta,(CorAquat,CurCitre)),CytAquat)));");
1500                TEST_EXPECT_NEWICK(nSIMPLE, NULp, ";");
1501
1502                destroy(tree);
1503            }
1504
1505            TEST_EXPECT_EQUAL(GBT_existing_tree(gb_main, "tree_nj_bs"), "tree_nj_bs");
1506            TEST_EXPECT_EQUAL(GBT_existing_tree(gb_main, "tree_nosuch"), "tree_test");
1507        }
1508
1509        // changing tree order
1510        {
1511            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_test|tree_tree2|tree_groups|tree_keeled|tree_keeled_2|tree_nj|tree_nj_bs|tree_removal");
1512
1513            GBDATA *gb_test    = GBT_find_tree(gb_main, "tree_test");
1514            GBDATA *gb_tree2   = GBT_find_tree(gb_main, "tree_tree2");
1515            GBDATA *gb_groups  = GBT_find_tree(gb_main, "tree_groups");
1516            GBDATA *gb_keeled  = GBT_find_tree(gb_main, "tree_keeled");
1517            GBDATA *gb_keeled2 = GBT_find_tree(gb_main, "tree_keeled_2");
1518            GBDATA *gb_nj      = GBT_find_tree(gb_main, "tree_nj");
1519            GBDATA *gb_nj_bs   = GBT_find_tree(gb_main, "tree_nj_bs");
1520            GBDATA *gb_removal = GBT_find_tree(gb_main, "tree_removal");
1521
1522            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_removal)); // move to bottom
1523            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_tree2|tree_groups|tree_keeled|tree_keeled_2|tree_nj|tree_nj_bs|tree_removal|tree_test");
1524
1525            TEST_EXPECT_EQUAL(GBT_tree_behind(gb_tree2), gb_groups);
1526            TEST_EXPECT_EQUAL(GBT_tree_behind(gb_keeled), gb_keeled2);
1527            TEST_EXPECT_EQUAL(GBT_tree_behind(gb_nj), gb_nj_bs);
1528            TEST_EXPECT_EQUAL(GBT_tree_behind(gb_nj_bs), gb_removal);
1529            TEST_EXPECT_EQUAL(GBT_tree_behind(gb_removal), gb_test);
1530            TEST_EXPECT_NULL(GBT_tree_behind(gb_test));
1531
1532            TEST_EXPECT_NULL(GBT_tree_infrontof(gb_tree2));
1533            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_groups), gb_tree2);
1534            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj), gb_keeled2);
1535            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj_bs), gb_nj);
1536            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_removal), gb_nj_bs);
1537            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_test), gb_removal);
1538
1539            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_INFRONTOF, gb_tree2)); // move back to top
1540            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_test|tree_tree2|tree_groups|tree_keeled|tree_keeled_2|tree_nj|tree_nj_bs|tree_removal");
1541
1542            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_tree2)); // move from top
1543            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_tree2|tree_test|tree_groups|tree_keeled|tree_keeled_2|tree_nj|tree_nj_bs|tree_removal");
1544
1545            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_removal, GBT_INFRONTOF, gb_nj)); // move from end
1546            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_tree2|tree_test|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_nj|tree_nj_bs");
1547
1548            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_nj_bs, GBT_INFRONTOF, gb_nj_bs)); // noop
1549            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "8:tree_tree2|tree_test|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_nj|tree_nj_bs");
1550
1551            TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_top_tree(gb_main)), "tree_tree2");
1552
1553            TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_next_tree(gb_removal)), "tree_nj");
1554            TEST_EXPECT_EQUAL(GBT_get_tree_name(GBT_find_next_tree(gb_nj_bs)), "tree_tree2"); // last -> first
1555        }
1556
1557        // check tree order is maintained by copy, rename and delete
1558
1559        {
1560            // copy
1561            TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_nosuch", "tree_whatever"), "tree 'tree_nosuch' not found");
1562            TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_test",   "tree_test"),     "source- and dest-tree are the same");
1563            TEST_EXPECT_ERROR_CONTAINS(GBT_copy_tree(gb_main, "tree_tree2",  "tree_test"),     "tree 'tree_test' already exists");
1564
1565            TEST_EXPECT_NO_ERROR(GBT_copy_tree(gb_main, "tree_test", "tree_test_copy"));
1566            TEST_REJECT_NULL(GBT_find_tree(gb_main, "tree_test_copy"));
1567            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "9:tree_tree2|tree_test|tree_test_copy|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_nj|tree_nj_bs");
1568
1569            // rename
1570            TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_nj", "tree_renamed_nj"));
1571            TEST_REJECT_NULL(GBT_find_tree(gb_main, "tree_renamed_nj"));
1572            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "9:tree_tree2|tree_test|tree_test_copy|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_renamed_nj|tree_nj_bs");
1573
1574            TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_tree2", "tree_renamed_tree2"));
1575            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "9:tree_renamed_tree2|tree_test|tree_test_copy|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_renamed_nj|tree_nj_bs");
1576
1577            TEST_EXPECT_NO_ERROR(GBT_rename_tree(gb_main, "tree_test_copy", "tree_renamed_test_copy"));
1578            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "9:tree_renamed_tree2|tree_test|tree_renamed_test_copy|tree_groups|tree_keeled|tree_keeled_2|tree_removal|tree_renamed_nj|tree_nj_bs");
1579
1580            // delete
1581
1582            GBDATA *gb_nj_bs             = GBT_find_tree(gb_main, "tree_nj_bs");
1583            GBDATA *gb_renamed_nj        = GBT_find_tree(gb_main, "tree_renamed_nj");
1584            GBDATA *gb_renamed_test_copy = GBT_find_tree(gb_main, "tree_renamed_test_copy");
1585            GBDATA *gb_renamed_tree2     = GBT_find_tree(gb_main, "tree_renamed_tree2");
1586            GBDATA *gb_test              = GBT_find_tree(gb_main, "tree_test");
1587            GBDATA *gb_removal           = GBT_find_tree(gb_main, "tree_removal");
1588            GBDATA *gb_groups            = GBT_find_tree(gb_main, "tree_groups");
1589            GBDATA *gb_keeled            = GBT_find_tree(gb_main, "tree_keeled");
1590            GBDATA *gb_keeled2           = GBT_find_tree(gb_main, "tree_keeled_2");
1591
1592            TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_tree2));
1593            TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_test_copy));
1594            TEST_EXPECT_NO_ERROR(GB_delete(gb_renamed_nj));
1595            TEST_EXPECT_NO_ERROR(GB_delete(gb_removal));
1596            TEST_EXPECT_NO_ERROR(GB_delete(gb_groups));
1597            TEST_EXPECT_NO_ERROR(GB_delete(gb_keeled));
1598            TEST_EXPECT_NO_ERROR(GB_delete(gb_keeled2));
1599
1600            // .. two trees left
1601
1602            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_test|tree_nj_bs");
1603
1604            TEST_EXPECT_EQUAL(find_largest_tree(gb_main), gb_test);
1605            TEST_EXPECT_EQUAL(GBT_find_top_tree(gb_main), gb_test);
1606            TEST_EXPECT_EQUAL(GBT_find_bottom_tree(gb_main), gb_nj_bs);
1607           
1608            TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_test), gb_nj_bs);
1609            TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_test), gb_nj_bs);
1610            TEST_EXPECT_EQUAL(GBT_find_next_tree(gb_nj_bs), gb_test);
1611
1612            TEST_EXPECT_NULL (GBT_tree_infrontof(gb_test));
1613            TEST_EXPECT_EQUAL(GBT_tree_behind   (gb_test), gb_nj_bs);
1614           
1615            TEST_EXPECT_EQUAL(GBT_tree_infrontof(gb_nj_bs), gb_test);
1616            TEST_EXPECT_NULL (GBT_tree_behind   (gb_nj_bs));
1617
1618            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_BEHIND, gb_nj_bs)); // move to bottom
1619            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_nj_bs|tree_test");
1620            TEST_EXPECT_NO_ERROR(GBT_move_tree(gb_test, GBT_INFRONTOF, gb_nj_bs)); // move to top
1621            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "2:tree_test|tree_nj_bs");
1622           
1623            TEST_EXPECT_NO_ERROR(GB_delete(gb_nj_bs));
1624
1625            // .. one tree left
1626
1627            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "1:tree_test");
1628
1629            TEST_EXPECT_EQUAL(find_largest_tree(gb_main), gb_test);
1630            TEST_EXPECT_EQUAL(GBT_find_top_tree(gb_main), gb_test);
1631            TEST_EXPECT_EQUAL(GBT_find_bottom_tree(gb_main), gb_test);
1632           
1633            TEST_EXPECT_NULL(GBT_find_next_tree(gb_test)); // no other tree left
1634            TEST_EXPECT_NULL(GBT_tree_behind(gb_test));
1635            TEST_EXPECT_NULL(GBT_tree_infrontof(gb_test));
1636
1637            TEST_EXPECT_NO_ERROR(GB_delete(gb_test));
1638
1639            // .. no tree left
1640           
1641            TEST_EXPECT_EQUAL(getTreeOrder(gb_main), "0:");
1642
1643            TEST_EXPECT_NULL(GBT_find_tree(gb_main, "tree_test"));
1644            TEST_EXPECT_NULL(GBT_existing_tree(gb_main, "tree_whatever"));
1645            TEST_EXPECT_NULL(find_largest_tree(gb_main));
1646        }
1647    }
1648
1649    GB_close(gb_main);
1650}
1651TEST_PUBLISH(TEST_copy_rename_delete_tree_order);
1652
1653
1654void TEST_group_keeling() {
1655    GB_shell  shell;
1656    GBDATA   *gb_main = GB_open("TEST_trees.arb", "r");
1657
1658    {
1659        GB_transaction ta(gb_main);
1660
1661        const char *topo_tree2   = "(((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc),(((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste)),((CloTyrob,CloTyro2),CloTyro4)'g2')'outer');";
1662        const char *topo_groups  = "(((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc)'upper',(((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste))'low1',((CloTyrob,CloTyro2)'twoleafs',CloTyro4)'low2')'lower');";
1663        const char *topo_keeled  = "(CloTyrob,(((((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste))'low1',((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc)'upper = !lower')'!low2',CloTyro4)'!twoleafs',CloTyro2));";
1664        // Note: shows fixed semantics (#735)
1665        // e.g.
1666        //  - compare members of group 'twoleafs' in
1667        //    * topo_groups (2 members) and
1668        //    * topo_keeled (all but former 2 members in inverse group)
1669        //  - compares locations of groups 'upper' and 'lower'
1670        //    * topo_groups: located at sons of root
1671        //    * topo_keeled: located at same node!
1672
1673        {
1674            TreeNode *tree = GBT_read_tree(gb_main, "tree_tree2", new SimpleRoot);
1675            TEST_EXPECT_NEWICK(nGROUP, tree, topo_tree2);
1676            destroy(tree);
1677        }
1678        {
1679            TreeNode *tree = GBT_read_tree(gb_main, "tree_groups", new SimpleRoot);
1680            TEST_EXPECT_NEWICK(nGROUP, tree, topo_groups);
1681
1682            TreeNode *CloTyrob = tree->findLeafNamed("CloTyrob");
1683            TEST_REJECT_NULL(CloTyrob);
1684            CloTyrob->set_root();
1685
1686            tree = tree->get_root_node();
1687            TEST_EXPECT(tree->is_root_node());
1688
1689            TEST_EXPECT_NEWICK(nGROUP, tree, topo_keeled);
1690
1691            destroy(tree);
1692        }
1693        {
1694            TreeNode *tree = GBT_read_tree(gb_main, "tree_keeled", new SimpleRoot);
1695            TEST_EXPECT_NEWICK(nGROUP, tree, topo_keeled);
1696            destroy(tree);
1697        }
1698        {
1699            // Note: there is a HIDDEN_KEELED_GROUP at CytAquat (not shown here in topo, but displayed in dendro-tree-display)!
1700            //       Group is found by group-search; see ../SL/GROUP_SEARCH/group_search.cxx@HIDDEN_KEELED_GROUP
1701            const char *topo_keeled2 = "(CloTyro4,((((CytAquat,(((CurCitre,CorAquat),CelBiazo),CorGluta)),(CloCarni,CloPaste))'low1',((CloTyro3,((CloButyr,CloButy2),CloBifer)),CloInnoc)'upper = !lower')'!low2',(CloTyrob,CloTyro2)'twoleafs'));";
1702            TreeNode   *tree         = GBT_read_tree(gb_main, "tree_keeled_2", new SimpleRoot);
1703            TEST_EXPECT_NEWICK(nGROUP, tree, topo_keeled2);
1704            destroy(tree);
1705        }
1706    }
1707
1708    GB_close(gb_main);
1709}
1710
1711void TEST_tree_remove_leafs() {
1712    GB_shell  shell;
1713    GBDATA   *gb_main = GB_open("TEST_trees.arb", "r");
1714
1715    {
1716        GBT_TreeRemoveType tested_modes[] = {
1717            GBT_REMOVE_MARKED,
1718            GBT_REMOVE_UNMARKED,
1719            GBT_REMOVE_ZOMBIES,
1720            GBT_KEEP_MARKED,
1721        };
1722
1723        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);";
1724        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);";
1725        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);";
1726        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);";
1727        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);";
1728
1729        const char *kept_zombies_topo        = "(Zombie1:0.131,Zombie2:0.162);";
1730        const char *kept_zombies_broken_topo = "Zombie2;";
1731
1732        const char *empty_topo = ";";
1733
1734        GB_transaction ta(gb_main);
1735        for (unsigned mode = 0; mode<ARRAY_ELEMS(tested_modes); ++mode) {
1736            GBT_TreeRemoveType what = tested_modes[mode];
1737
1738            for (int linked = 0; linked<=1; ++linked) {
1739                TEST_ANNOTATE(GBS_global_string("mode=%u linked=%i", mode, linked));
1740
1741                TreeNode *tree = GBT_read_tree(gb_main, "tree_removal", new SimpleRoot);
1742                gb_assert(tree);
1743                bool once = mode == 0 && linked == 0;
1744
1745                if (linked) {
1746                    int zombies    = 0;
1747                    int duplicates = 0;
1748
1749                    TEST_EXPECT_NO_ERROR(GBT_link_tree(tree, gb_main, false, &zombies, &duplicates));
1750
1751                    TEST_EXPECT_EQUAL(zombies, 2);
1752                    TEST_EXPECT_EQUAL(duplicates, 0);
1753                }
1754
1755                if (once) TEST_EXPECT_NEWICK(nLENGTH, tree, org_topo);
1756
1757                int removedCount       = 0;
1758                int groupsRemovedCount = 0;
1759
1760                tree = GBT_remove_leafs(tree, what, NULp, &removedCount, &groupsRemovedCount);
1761
1762                if (linked) {
1763                    GBT_TreeRemoveType what_next = what;
1764
1765                    switch (what) {
1766                        case GBT_REMOVE_MARKED:
1767                            TEST_EXPECT_EQUAL(removedCount, 6);
1768                            TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1769                            TEST_EXPECT_NEWICK(nLENGTH, tree, rem_marked_topo);
1770                            what_next = GBT_REMOVE_UNMARKED;
1771                            break;
1772                        case GBT_REMOVE_UNMARKED:
1773                            TEST_EXPECT_EQUAL(removedCount, 9);
1774                            TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1775                            TEST_EXPECT_NEWICK(nLENGTH, tree, rem_unmarked_topo);
1776                            what_next = GBT_REMOVE_MARKED;
1777                            break;
1778                        case GBT_REMOVE_ZOMBIES:
1779                            TEST_EXPECT_EQUAL(removedCount, 2);
1780                            TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1781                            TEST_EXPECT_NEWICK(nLENGTH, tree, rem_zombies_topo);
1782                            break;
1783                        case GBT_KEEP_MARKED:
1784                            TEST_EXPECT_EQUAL(removedCount, 11);
1785                            TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1786                            TEST_EXPECT_NEWICK(nLENGTH, tree, kept_marked_topo);
1787                            {
1788                                // just a test for nWRAP NewickFormat (may be removed later)
1789                                const char *kept_marked_topo_wrapped =
1790                                    "(\n"
1791                                    " CurCitre:1.000,\n"
1792                                    " (\n"
1793                                    "  (\n"
1794                                    "   CloButy2:0.009,\n"
1795                                    "   CloButyr:0.000\n"
1796                                    "  ):0.131,\n"
1797                                    "  (\n"
1798                                    "   CytAquat:0.711,\n"
1799                                    "   (\n"
1800                                    "    CorGluta:0.522,\n"
1801                                    "    CorAquat:0.103\n"
1802                                    "   ):0.207\n"
1803                                    "  ):0.162\n"
1804                                    " ):0.124);";
1805                                TEST_EXPECT_NEWICK(NewickFormat(nLENGTH|nWRAP), tree, kept_marked_topo_wrapped);
1806
1807                                const char *expected_compacted =
1808                                    "(CurCitre:1.000,\n"
1809                                    " ((CloButy2:0.009,\n"
1810                                    "   CloButyr:0.000):0.131,\n"
1811                                    "  (CytAquat:0.711,\n"
1812                                    "   (CorGluta:0.522,\n"
1813                                    "    CorAquat:0.103):0.207):0.162):0.124);";
1814                                char *compacted = GBT_tree_2_newick(tree, NewickFormat(nLENGTH|nWRAP), true);
1815                                TEST_EXPECT_EQUAL(compacted, expected_compacted);
1816                                free(compacted);
1817                            }
1818                            what_next = GBT_REMOVE_MARKED;
1819                            break;
1820                    }
1821
1822                    if (what_next != what) {
1823                        gb_assert(tree);
1824                        tree = GBT_remove_leafs(tree, what_next, NULp, &removedCount, &groupsRemovedCount);
1825
1826                        switch (what) {
1827                            case GBT_REMOVE_MARKED: // + GBT_REMOVE_UNMARKED
1828                                TEST_EXPECT_EQUAL(removedCount, 16);
1829                                TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1830                                TEST_EXPECT_NEWICK__BROKEN(nLENGTH, tree, kept_zombies_topo);
1831                                TEST_EXPECT_NEWICK(nLENGTH, tree, kept_zombies_broken_topo); // @@@ invalid topology (single leaf)
1832                                break;
1833                            case GBT_REMOVE_UNMARKED: // + GBT_REMOVE_MARKED
1834                                TEST_EXPECT_EQUAL(removedCount, 15);
1835                                TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1836                                TEST_EXPECT_NEWICK(nLENGTH, tree, kept_zombies_topo);
1837                                break;
1838                            case GBT_KEEP_MARKED: // + GBT_REMOVE_MARKED
1839                                TEST_EXPECT_EQUAL(removedCount, 17);
1840                                TEST_EXPECT_EQUAL__BROKEN(groupsRemovedCount, 2, 1); // @@@ expect that all groups have been removed!
1841                                TEST_EXPECT_EQUAL(groupsRemovedCount, 1);
1842                                TEST_EXPECT_NEWICK(nLENGTH, tree, empty_topo);
1843                                break;
1844                            default:
1845                                TEST_REJECT(true);
1846                                break;
1847                        }
1848                    }
1849                }
1850                else {
1851                    switch (what) {
1852                        case GBT_REMOVE_MARKED:
1853                        case GBT_REMOVE_UNMARKED:
1854                            TEST_EXPECT_EQUAL(removedCount, 0);
1855                            TEST_EXPECT_EQUAL(groupsRemovedCount, 0);
1856                            TEST_EXPECT_NEWICK(nLENGTH, tree, org_topo);
1857                            break;
1858                        case GBT_REMOVE_ZOMBIES:
1859                        case GBT_KEEP_MARKED:
1860                            TEST_EXPECT_EQUAL(removedCount, 17);
1861                            TEST_EXPECT_EQUAL(groupsRemovedCount, 2);
1862                            TEST_EXPECT_NEWICK(nLENGTH, tree, empty_topo);
1863                            break;
1864                    }
1865                }
1866
1867                if (tree) {
1868                    gb_assert(tree->is_root_node());
1869                    destroy(tree);
1870                }
1871            }
1872        }
1873    }
1874
1875    GB_close(gb_main);
1876}
1877TEST_PUBLISH(TEST_tree_remove_leafs);
1878
1879
1880#endif // UNIT_TESTS
Note: See TracBrowser for help on using the repository browser.