source: trunk/ARBDB/adtree.cxx

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