ad_trees.cxx

Go to the documentation of this file.

// =============================================================== //
//                                                                 //
//   File      : ad_trees.cxx                                      //
//   Purpose   :                                                   //
//                                                                 //
//   Institute of Microbiology (Technical University Munich)       //
//   http://www.arb-home.de/                                       //
//                                                                 //
// =============================================================== //

#include "tree_position.h"
#include "ad_trees.h"
#include "NT_tree_cmp.h"

#include <CT_ctree.hxx>

#include <TreeAdmin.h>
#include <TreeRead.h>
#include <TreeWrite.h>
#include <TreeCallbacks.hxx>

#include <awt_sel_boxes.hxx>
#include <awt_modules.hxx>
#include <awt_TreeAwars.hxx>

#include <aw_awars.hxx>
#include <aw_edit.hxx>
#include <aw_file.hxx>
#include <aw_msg.hxx>
#include <aw_root.hxx>
#include <aw_select.hxx>

#include <arb_strbuf.h>
#include <arb_file.h>
#include <arb_diff.h>
#include <arb_defs.h>

#include <cctype>
#include <awt_config_manager.hxx>
#include <xcmd.hxx>

#define AWAR_TREE_SAV "ad_tree/"
#define AWAR_TREE_TMP "tmp/ad_tree/"

#define AWAR_TREE_SECURITY AWAR_TREE_TMP "tree_security"
#define AWAR_TREE_REM      AWAR_TREE_TMP "tree_rem"
#define AWAR_TREE_IMPORT   AWAR_TREE_TMP "import_tree"

#define AWAR_GROUPXFER_SAV AWAR_TREE_SAV "groupxfer/"

#define AWAR_GROUPXFER_SOURCE         AWAR_GROUPXFER_SAV "restrict"
#define AWAR_GROUPXFER_OVERWRITE_MODE AWAR_GROUPXFER_SAV "overwrite"
#define AWAR_GROUPXFER_INGROUP_ABS    AWAR_GROUPXFER_SAV "ingroup/abs"
#define AWAR_GROUPXFER_INGROUP_REL    AWAR_GROUPXFER_SAV "ingroup/rel"
#define AWAR_GROUPXFER_INGROUP_LIM    AWAR_GROUPXFER_SAV "ingroup/lim"
#define AWAR_GROUPXFER_OUTGROUP_ABS   AWAR_GROUPXFER_SAV "outgroup/abs"
#define AWAR_GROUPXFER_OUTGROUP_REL   AWAR_GROUPXFER_SAV "outgroup/rel"
#define AWAR_GROUPXFER_OUTGROUP_LIM   AWAR_GROUPXFER_SAV "outgroup/lim"
#define AWAR_GROUPXFER_UNKNOWN_ABS    AWAR_GROUPXFER_SAV "unknown"
#define AWAR_GROUPXFER_KEELING        AWAR_GROUPXFER_SAV "keeling"
#define AWAR_GROUPXFER_ACI            AWAR_GROUPXFER_SAV "aci"

#define AWAR_TREE_EXPORT_FILEBASE AWAR_TREE_TMP "export_tree"
#define AWAR_TREE_EXPORT_FILTER   AWAR_TREE_EXPORT_FILEBASE "/filter"
#define AWAR_TREE_EXPORT_NAME     AWAR_TREE_EXPORT_FILEBASE "/file_name"

#define AWAR_TREE_EXPORT_SAV AWAR_TREE_SAV "export_tree/"

#define AWAR_TREE_EXPORT_FORMAT             AWAR_TREE_EXPORT_SAV "format"
#define AWAR_TREE_EXPORT_NDS                AWAR_TREE_EXPORT_SAV "NDS"
#define AWAR_TREE_EXPORT_INCLUDE_BOOTSTRAPS AWAR_TREE_EXPORT_SAV "bootstraps"
#define AWAR_TREE_EXPORT_INCLUDE_BRANCHLENS AWAR_TREE_EXPORT_SAV "branchlens"
#define AWAR_TREE_EXPORT_INCLUDE_GROUPNAMES AWAR_TREE_EXPORT_SAV "groupnames"
#define AWAR_TREE_EXPORT_HIDE_FOLDED_GROUPS AWAR_TREE_EXPORT_SAV "hide_folded"
#define AWAR_TREE_EXPORT_QUOTEMODE          AWAR_TREE_EXPORT_SAV "quote_mode"
#define AWAR_TREE_EXPORT_NON_ASCII          AWAR_TREE_EXPORT_SAV "non_ASCII"
#define AWAR_TREE_EXPORT_REPLACE            AWAR_TREE_EXPORT_SAV "replace"


#define AWAR_TREE_CONSENSE_TMP AWAR_TREE_TMP "consense/"
#define AWAR_TREE_CONSENSE_SAV AWAR_TREE_SAV "consense/"

#define AWAR_TREE_CONSENSE_TREE     AWAR_TREE_CONSENSE_SAV "tree"
#define AWAR_TREE_CONSENSE_SELECTED AWAR_TREE_CONSENSE_TMP "selected"

static void tree_vars_callback(AW_root *aw_root) {
    // map tree awars to display database entries (security+comment)

    if (GLOBAL.gb_main) {
        GB_transaction ta(GLOBAL.gb_main);

        char   *treename = aw_root->awar(AWAR_TREE_NAME)->read_string();
        GBDATA *gb_tree  = GBT_find_tree(GLOBAL.gb_main, treename);

        if (!gb_tree) {
            aw_root->awar(AWAR_TREE_SECURITY)->unmap();
            aw_root->awar(AWAR_TREE_REM)->unmap();
        }
        else {
            GBDATA *tree_prot = GB_search(gb_tree, "security", GB_FIND);
            if (!tree_prot) GBT_readOrCreate_int(gb_tree, "security", GB_read_security_write(gb_tree));
            tree_prot         = GB_search(gb_tree, "security", GB_INT);

            GBDATA *tree_rem = GB_search(gb_tree, "remark",   GB_STRING);
            aw_root->awar(AWAR_TREE_SECURITY)->map(tree_prot);
            aw_root->awar(AWAR_TREE_REM)     ->map(tree_rem);
        }

        // create default filename from tree-name:
        {
            char *suffix = aw_root->awar(AWAR_TREE_EXPORT_FILTER)->read_string();
            char *fname  = GBS_string_eval(treename, GBS_global_string("*=*1.%s:tree_*=*1", suffix));

            aw_root->awar(AWAR_TREE_EXPORT_NAME)->write_string(fname); // create default file name

            free(fname);
            free(suffix);
        }

        free(treename);
    }
}

static void update_default_treename_cb(AW_root *aw_root) {
    // update import tree name depending on file name
    GB_transaction ta(GLOBAL.gb_main);

    char *treename        = aw_root->awar(AWAR_TREE_IMPORT "/file_name")->read_string();
    char *treename_nopath = strrchr(treename, '/');

    if (treename_nopath) {
        ++treename_nopath;
    }
    else {
        treename_nopath = treename;
    }

    char *fname = GBS_string_eval(treename_nopath, "*.tree=tree_*1:*.ntree=tree_*1:*.xml=tree_*1:.=:-=_: =_");
    aw_root->awar(AWAR_TREE_IMPORT "/tree_name")->write_string(fname);

    free(fname);
    free(treename);
}

static void ad_tree_set_security(AW_root *aw_root) {
    if (GLOBAL.gb_main) {
        GB_transaction ta(GLOBAL.gb_main);

        char   *treename = aw_root->awar(AWAR_TREE_NAME)->read_string();
        GBDATA *gb_tree  = GBT_find_tree(GLOBAL.gb_main, treename);

        if (gb_tree) {
            long prot = aw_root->awar(AWAR_TREE_SECURITY)->read_int();
            long old  = GB_read_security_delete(gb_tree);

            GB_ERROR error = NULp;
            if (old != prot) {
                error             = GB_write_security_delete(gb_tree, prot);
                if (!error) error = GB_write_security_write(gb_tree, prot);
            }
            aw_message_if(error);
        }
        free(treename);
    }
}

enum ExportTreeType {
    AD_TREE_EXPORT_FORMAT_NEWICK,
    AD_TREE_EXPORT_FORMAT_XML,
    AD_TREE_EXPORT_FORMAT_NEWICK_PRETTY,
};

enum ExportNodeType { // careful: value saved in awar!
    AD_TREE_EXPORT_NODE_SPECIES_NAME,
    AD_TREE_EXPORT_NODE_NDS,
    AD_TREE_EXPORT_NODE_NDS_TRUNCATED
};

static void update_filter_cb(AW_root *root) {
    const char *filter_type = NULp;

    switch (ExportTreeType(root->awar(AWAR_TREE_EXPORT_FORMAT)->read_int())) {
        case AD_TREE_EXPORT_FORMAT_XML:
            filter_type = "xml";
            break;

        case AD_TREE_EXPORT_FORMAT_NEWICK:
        case AD_TREE_EXPORT_FORMAT_NEWICK_PRETTY:
            switch (ExportNodeType(root->awar(AWAR_TREE_EXPORT_NDS)->read_int())) {
                case AD_TREE_EXPORT_NODE_SPECIES_NAME:  filter_type = "tree"; break;
                case AD_TREE_EXPORT_NODE_NDS:
                case AD_TREE_EXPORT_NODE_NDS_TRUNCATED: filter_type = "ntree"; break;
            }
            break;

        default: nt_assert(0); break;
    }

    nt_assert(filter_type);
    root->awar(AWAR_TREE_EXPORT_FILTER)->write_string(filter_type);
}

void create_trees_var(AW_root *aw_root, AW_default aw_def) {
    AW_awar *awar_tree_name = aw_root->awar_string(AWAR_TREE_NAME, NULp, aw_def)->set_srt(SRT_AUTOCORRECT_TREENAME);

    aw_root->awar_pointer(AWAR_GROUP, NULp, aw_def);

    TreeAdmin::create_awars(aw_root, aw_def, true);

    aw_root->awar_int   (AWAR_TREE_SECURITY, 0,    aw_def);
    aw_root->awar_string(AWAR_TREE_REM,      NULp, aw_def);

    AW_create_fileselection_awars(aw_root, AWAR_TREE_EXPORT_FILEBASE, "", ".tree", "treefile");
    aw_root->awar_int(AWAR_TREE_EXPORT_FORMAT, AD_TREE_EXPORT_FORMAT_NEWICK, aw_def)-> add_callback(update_filter_cb);
    aw_root->awar_int(AWAR_TREE_EXPORT_NDS,  AD_TREE_EXPORT_NODE_SPECIES_NAME, aw_def)-> add_callback(update_filter_cb);

    aw_root->awar_int(AWAR_TREE_EXPORT_INCLUDE_BOOTSTRAPS, 0, aw_def);
    aw_root->awar_int(AWAR_TREE_EXPORT_INCLUDE_BRANCHLENS, 1, aw_def);
    aw_root->awar_int(AWAR_TREE_EXPORT_HIDE_FOLDED_GROUPS, 0, aw_def);
    aw_root->awar_int(AWAR_TREE_EXPORT_INCLUDE_GROUPNAMES, 1, aw_def);

    aw_root->awar_int(AWAR_TREE_EXPORT_QUOTEMODE, LABEL_SINGLE_QUOTES, aw_def); // old default behavior
    aw_root->awar_int(AWAR_TREE_EXPORT_NON_ASCII, 0,                   aw_def); // changes default behavior (=reject non-ASCII)
    aw_root->awar_int(AWAR_TREE_EXPORT_REPLACE,   0,                   aw_def); // old default behavior

    AW_create_fileselection_awars(aw_root, AWAR_TREE_IMPORT, "", ".tree", "treefile");

    aw_root->awar_string(AWAR_TREE_IMPORT "/tree_name", "tree_",    aw_def)->set_srt(SRT_AUTOCORRECT_TREENAME);

    aw_root->awar(AWAR_TREE_IMPORT "/file_name")->add_callback(update_default_treename_cb);
    awar_tree_name->add_callback(tree_vars_callback);
    awar_tree_name->map(AWAR_TREE);
    aw_root->awar(AWAR_TREE_SECURITY)->add_callback(ad_tree_set_security);

    aw_root->awar_int(AWAR_GROUPXFER_SOURCE,         XFER_ALL_GROUPS,        aw_def);
    aw_root->awar_int(AWAR_GROUPXFER_OVERWRITE_MODE, REMOVE_EXISTING_GROUPS, aw_def);

    aw_root->awar_float(AWAR_GROUPXFER_INGROUP_ABS,  1.0,    aw_def);
    aw_root->awar_float(AWAR_GROUPXFER_OUTGROUP_ABS, 1.0,    aw_def);
    aw_root->awar_float(AWAR_GROUPXFER_INGROUP_REL,  0.0,    aw_def);
    aw_root->awar_float(AWAR_GROUPXFER_OUTGROUP_REL, 0.0,    aw_def);
    aw_root->awar_float(AWAR_GROUPXFER_INGROUP_LIM,  0.0,    aw_def);
    aw_root->awar_float(AWAR_GROUPXFER_OUTGROUP_LIM, 100.0,  aw_def);
    aw_root->awar_float(AWAR_GROUPXFER_UNKNOWN_ABS,  0.0001, aw_def);
    aw_root->awar_float(AWAR_GROUPXFER_KEELING,      0.01,   aw_def);

    aw_root->awar_string(AWAR_GROUPXFER_ACI, "", aw_def);

    aw_root->awar_string(AWAR_TREE_CONSENSE_TREE, "tree_consensus", aw_def)->set_srt(SRT_AUTOCORRECT_TREENAME);
    AW_awar *ctree_awar = aw_root->awar_string(AWAR_TREE_CONSENSE_SELECTED, "", aw_def);
    AWT_registerTreeAwarSimple(ctree_awar);

    update_filter_cb(aw_root);
    tree_vars_callback(aw_root);
}

static void tree_save_cb(AW_window *aww) {
    AW_root  *aw_root   = aww->get_root();
    char     *tree_name = aw_root->awar(AWAR_TREE_NAME)->read_string();

    GB_ERROR error = NULp;

    if (!tree_name || !strlen(tree_name)) {
        error = "Please select a tree first";
    }
    else {
        char *fname   = aw_root->awar(AWAR_TREE_EXPORT_NAME)->read_string();
        char *db_name = aw_root->awar(AWAR_DB_NAME)->read_string();

        SmartPtr<TreeLabeler> labeler;
        switch (ExportNodeType(aw_root->awar(AWAR_TREE_EXPORT_NDS)->read_int())) {
            case AD_TREE_EXPORT_NODE_NDS:           labeler = new NDS_Labeler(NDS_OUTPUT_LEAFTEXT_UNLIMITED); break;
            case AD_TREE_EXPORT_NODE_NDS_TRUNCATED: labeler = new NDS_Labeler(NDS_OUTPUT_LEAFTEXT);           break;
            case AD_TREE_EXPORT_NODE_SPECIES_NAME:  labeler = new Node_ID_Labeler;                            break;
        }

        ExportTreeType exportType = static_cast<ExportTreeType>(aw_root->awar(AWAR_TREE_EXPORT_FORMAT)->read_int());
        switch (exportType) {
            case AD_TREE_EXPORT_FORMAT_XML:
                error = TREE_write_XML(GLOBAL.gb_main, db_name, tree_name, *labeler,
                                       aw_root->awar(AWAR_TREE_EXPORT_HIDE_FOLDED_GROUPS)->read_int(),
                                       fname);
                break;

            case AD_TREE_EXPORT_FORMAT_NEWICK:
            case AD_TREE_EXPORT_FORMAT_NEWICK_PRETTY:
                LabelQuoting quoteMode = LabelQuoting(aw_root->awar(AWAR_TREE_EXPORT_QUOTEMODE)->read_int());

                if (aw_root->awar(AWAR_TREE_EXPORT_REPLACE)  ->read_int()) quoteMode = LabelQuoting(quoteMode|LABEL_FORCE_REPLACE);
                if (aw_root->awar(AWAR_TREE_EXPORT_NON_ASCII)->read_int()) quoteMode = LabelQuoting(quoteMode|LABEL_ACCEPT_NON_ASCII);

                error = TREE_write_Newick(GLOBAL.gb_main, tree_name, *labeler,
                                          aw_root->awar(AWAR_TREE_EXPORT_INCLUDE_BRANCHLENS)->read_int(),
                                          aw_root->awar(AWAR_TREE_EXPORT_INCLUDE_BOOTSTRAPS)->read_int(),
                                          aw_root->awar(AWAR_TREE_EXPORT_INCLUDE_GROUPNAMES)->read_int(),
                                          exportType == AD_TREE_EXPORT_FORMAT_NEWICK_PRETTY,
                                          quoteMode,
                                          fname);
                break;
        }

        free(db_name);
        free(fname);
    }

    aww->hide_or_notify(error);
    free(tree_name);

    AW_refresh_fileselection(aw_root, AWAR_TREE_EXPORT_FILEBASE);
}

static AWT_config_mapping_def tree_export_config_mapping[] = {
    { AWAR_TREE_EXPORT_FORMAT,             "format" },
    { AWAR_TREE_EXPORT_NDS,                "nodetype" },
    { AWAR_TREE_EXPORT_INCLUDE_BRANCHLENS, "lengths" },
    { AWAR_TREE_EXPORT_INCLUDE_BOOTSTRAPS, "bootstraps" },
    { AWAR_TREE_EXPORT_INCLUDE_GROUPNAMES, "groupnames" },
    { AWAR_TREE_EXPORT_HIDE_FOLDED_GROUPS, "hidefolded" },
    { AWAR_TREE_EXPORT_QUOTEMODE,          "quotemode" },
    { AWAR_TREE_EXPORT_NON_ASCII,          "nonASCII" },
    { AWAR_TREE_EXPORT_REPLACE,            "replacechars" },

    { NULp, NULp }
};

static AW_window *create_tree_export_window(AW_root *root) {
    AW_window_simple *aws = new AW_window_simple;
    aws->init(root, "SAVETREE", "TREE SAVE");
    aws->load_xfig("tree_export.fig");

    aws->at("close");
    aws->callback(AW_POPDOWN);
    aws->create_button("CLOSE", "CLOSE", "C");

    aws->at("help");
    aws->callback(makeHelpCallback("tr_export.hlp"));
    aws->create_button("HELP", "HELP", "H");

    AW_create_standard_fileselection(aws, AWAR_TREE_EXPORT_FILEBASE);

    aws->at("format");
    aws->label("Tree format");
    aws->create_option_menu(AWAR_TREE_EXPORT_FORMAT);
    aws->insert_option("Newick tree",              "N", AD_TREE_EXPORT_FORMAT_NEWICK);
    aws->insert_option("Newick (pretty, but big)", "P", AD_TREE_EXPORT_FORMAT_NEWICK_PRETTY);
    aws->insert_option("XML tree (export only)",   "X", AD_TREE_EXPORT_FORMAT_XML);
    aws->update_option_menu();

    aws->at("labels");
    aws->label("Tree labels");
    aws->create_option_menu(AWAR_TREE_EXPORT_NDS);
    aws->insert_default_option("Species/group ID ('name')", "S", AD_TREE_EXPORT_NODE_SPECIES_NAME);
    aws->insert_option        ("NDS",                       "N", AD_TREE_EXPORT_NODE_NDS);
    aws->insert_option        ("NDS (truncated)",           "t", AD_TREE_EXPORT_NODE_NDS_TRUNCATED);
    aws->update_option_menu();

    aws->at("quote");
    aws->label("Label quoting (Newick only)");
    aws->create_option_menu(AWAR_TREE_EXPORT_QUOTEMODE);
    aws->insert_option("none",            "n", LABEL_DISALLOW_QUOTES);
    aws->insert_option("single",          "s", LABEL_SINGLE_QUOTES);
    aws->insert_option("double",          "d", LABEL_DOUBLE_QUOTES);
    aws->insert_option("single (forced)", "i", LABEL_SINGLE_QUOTES | LABEL_FORCE_QUOTES);
    aws->insert_option("double (forced)", "o", LABEL_DOUBLE_QUOTES | LABEL_FORCE_QUOTES);
    aws->update_option_menu();

    aws->at("ascii"); aws->label("Accept non-ASCII chars");        aws->create_toggle(AWAR_TREE_EXPORT_NON_ASCII);
    aws->at("repl");  aws->label("Replace problem chars");         aws->create_toggle(AWAR_TREE_EXPORT_REPLACE);
    aws->at("group"); aws->label("Save group names");              aws->create_toggle(AWAR_TREE_EXPORT_INCLUDE_GROUPNAMES);
    aws->at("hide");  aws->label("Hide folded groups (XML only)"); aws->create_toggle(AWAR_TREE_EXPORT_HIDE_FOLDED_GROUPS);
    aws->at("len");   aws->label("Save branch lengths");           aws->create_toggle(AWAR_TREE_EXPORT_INCLUDE_BRANCHLENS);
    aws->at("boot");  aws->label("Save bootstrap values");         aws->create_toggle(AWAR_TREE_EXPORT_INCLUDE_BOOTSTRAPS);

    aws->at("save");
    aws->button_length(10);
    aws->callback(tree_save_cb);
    aws->create_button("SAVE", "SAVE", "o");

    aws->at("cfg");
    AWT_insert_config_manager(aws, AW_ROOT_DEFAULT, "tree_export", tree_export_config_mapping);

    update_filter_cb(root);

    return aws;
}

static char *readXmlTree(char *fname) {
    // create a temp file
    char tempFile[]  = "newickXXXXXX";
    int createTempFile = mkstemp(tempFile);

    if (createTempFile) {
        GBS_strstruct buf(strlen(fname));

        // extract path from fname in order to place a copy of dtd file required to validate xml file
        {
            char *tmpFname = ARB_strdup(fname);
            for (char *tok = strtok(tmpFname, "/"); tok;) {
                char *tmp = tok;
                tok = strtok(NULp, "/");
                if (tok) {
                    buf.put('/');
                    buf.cat(tmp);
                }
            }
            free(tmpFname);
        }

        // linking arb_tree.dtd file to the Path from where xml file is loaded
        char *command = GBS_global_string_copy("ln -s %s/lib/dtd/arb_tree.dtd %s/.", GB_getenvARBHOME(), buf.get_data());
        ARB_system(command, XCmdType(XCMD_SYNC_WAIT_ON_ERROR, GLOBAL.gb_main));

        // execute xml2newick to convert xml format tree to newick format tree
        command = GBS_global_string_copy("xml2newick %s %s", fname, tempFile);
        ARB_system(command, XCmdType(XCMD_SYNC_WAIT_ON_ERROR, GLOBAL.gb_main));

        free(command);

        // return newick format tree file
        return ARB_strdup(tempFile);
    }
    else {
        printf("Failed to create Temporary File to Parse xml file!\n");
        return NULp;
    }
}

static void tree_load_cb(AW_window *aww) {
    GB_ERROR  error     = NULp;
    AW_root  *aw_root   = aww->get_root();
    char     *tree_name = aw_root->awar(AWAR_TREE_IMPORT "/tree_name")->read_string();

    {
        char *pcTreeFormat = aw_root->awar(AWAR_TREE_IMPORT "/filter")->read_string();
        char *fname        = aw_root->awar(AWAR_TREE_IMPORT "/file_name")->read_string();
        if (strcmp(pcTreeFormat, "xml") == 0) {
            char *tempFname = readXmlTree(fname);

            error = TREE_load_to_db(GLOBAL.gb_main, tempFname, tree_name);

            GB_unlink_or_warn(tempFname, NULp);
            free(tempFname);
        }
        else {
            error = TREE_load_to_db(GLOBAL.gb_main, fname, tree_name);
        }

        free(fname);
        free(pcTreeFormat);
    }

    aww->hide_or_notify(error);
    if (!error) aw_root->awar(AWAR_TREE)->write_string(tree_name); // show new tree

    free(tree_name);
}

static AW_window *create_tree_import_window(AW_root *root) {
    AW_window_simple *aws = new AW_window_simple;
    aws->init(root, "LOAD_TREE", "TREE LOAD");
    aws->load_xfig("sel_box_tree.fig");

    aws->at("close");
    aws->callback(AW_POPDOWN);
    aws->create_button("CLOSE", "CLOSE", "C");

    aws->at("help");
    aws->callback(makeHelpCallback("tr_import.hlp"));
    aws->create_button("HELP", "HELP", "H");

    aws->at("format");
    aws->create_option_menu(AWAR_TREE_IMPORT "/filter");
    aws->insert_default_option("Newick", "t", "tree");
    aws->insert_option("XML", "x", "xml");
    aws->update_option_menu();

    aws->at("user");
    aws->label("Tree name");
    aws->create_input_field(AWAR_TREE_IMPORT "/tree_name", 15);

    AW_create_standard_fileselection(aws, AWAR_TREE_IMPORT);

    aws->at("save2");
    aws->callback(tree_load_cb);
    aws->create_button("LOAD", "LOAD", "o");

    aws->window_fit();

    return aws;
}

static void ad_move_tree_info(AW_window *aww, bool transferGroups) {
    AW_root *awr = aww->get_root();

    char     *log_file = NULp;
    GB_ERROR  error    = NULp;

    GroupTransferMode mode = COMPARE_TOPOLOGY;
    GroupsToTransfer  what = XFER_ALL_GROUPS;

    if (transferGroups) {
        // log file is only written if transferring groups!
        char *log_name       = GB_unique_filename("arb_node", "log");
        log_file             = GB_create_tempfile(log_name);
        if (!log_file) error = GB_await_error();
        free(log_name);

        what = GroupsToTransfer(awr->awar(AWAR_GROUPXFER_SOURCE)->read_int());
        mode = GroupTransferMode(awr->awar(AWAR_GROUPXFER_OVERWRITE_MODE)->read_int());
    }

    if (!error) {
        char *src_tree = TreeAdmin::source_tree_awar(awr)->read_string();
        char *dst_tree = TreeAdmin::dest_tree_awar(awr)->read_string();
        char *aci      = awr->awar(AWAR_GROUPXFER_ACI)->read_string();

        NT_deselect_group(awr); // avoid crash (if group selected in target tree)

        GroupMatchScorer userScorer;
        if (transferGroups) {
            userScorer.setLimits(RatioLimits(awr->awar(AWAR_GROUPXFER_INGROUP_LIM)->read_float()/100, 1.0),
                                 RatioLimits(0.0, awr->awar(AWAR_GROUPXFER_OUTGROUP_LIM)->read_float()/100));

            userScorer.setPerErrorPenalties(awr->awar(AWAR_GROUPXFER_INGROUP_ABS)->read_float(),
                                            awr->awar(AWAR_GROUPXFER_OUTGROUP_ABS)->read_float(),
                                            awr->awar(AWAR_GROUPXFER_UNKNOWN_ABS)->read_float());

            userScorer.setRelativePenalties(awr->awar(AWAR_GROUPXFER_INGROUP_REL)->read_float(),
                                            awr->awar(AWAR_GROUPXFER_OUTGROUP_REL)->read_float());
        }

        error = NTREE_move_tree_info(GLOBAL.gb_main, src_tree, dst_tree, log_file, mode, what, userScorer, aci);

        if (mode == COMPARE_TOPOLOGY && !error) {
            // if tree is not shown -> provide hint
            TREE_canvas *canvas_showing_dest = NT_get_canvas_showing_tree(dst_tree, false);
            if (!canvas_showing_dest) {
                aw_message(GBS_global_string("Note: annotations added to tree '%s'\n"
                                             "Press the right 'Display' button to view that tree", dst_tree));
            }
        }

        if (log_file) {
            AW_edit(log_file);
            GB_remove_on_exit(log_file);
        }

        free(aci);
        free(dst_tree);
        free(src_tree);
    }

    aw_message_if(error);

    free(log_file);
}

static void swap_source_dest_cb(AW_window *aww) {
    AW_root *root = aww->get_root();

    AW_awar *s = TreeAdmin::source_tree_awar(root);
    AW_awar *d = TreeAdmin::dest_tree_awar(root);

    char *old_src = s->read_string();
    s->write_string(d->read_char_pntr());
    d->write_string(old_src);
    free(old_src);
}

static void copy_tree_awar_cb(UNFIXED, AW_awar *aw_source, AW_awar *aw_dest) {
    const char *tree = aw_source->read_char_pntr();
    if (tree && tree[0]) aw_dest->write_string(tree);
}

void NT_create_twoTreeSelection(AW_window *aws) {
    AW_root *root = aws->get_root();

    aws->auto_space(10, 3);

    aws->at("tree1");
    awt_create_TREE_selection_list(GLOBAL.gb_main, aws, TreeAdmin::source_tree_awar(root)->awar_name);
    aws->at("tree2");
    awt_create_TREE_selection_list(GLOBAL.gb_main, aws, TreeAdmin::dest_tree_awar(root)->awar_name);

    AW_awar *awar_displayed_tree = root->awar(AWAR_TREE_NAME);

    { // let source tree default to currently displayed tree:
        static bool firstCall = true;
        if (firstCall) {
            TreeAdmin::source_tree_awar(root)->write_string(awar_displayed_tree->read_char_pntr());
            firstCall = false;
        }
    }


    aws->at("select1");
    aws->callback(makeWindowCallback(copy_tree_awar_cb, awar_displayed_tree, TreeAdmin::source_tree_awar(root)));  aws->create_autosize_button("SELECT_DISPLAYED1", "Use shown");
    aws->callback(makeWindowCallback(copy_tree_awar_cb, TreeAdmin::source_tree_awar(root), awar_displayed_tree));  aws->create_autosize_button("DISPLAY_SELECTED1", "Display");

    aws->callback(swap_source_dest_cb);
    aws->create_autosize_button("SWAP", "Swap");

    aws->at("select2");
    aws->callback(makeWindowCallback(copy_tree_awar_cb, awar_displayed_tree, TreeAdmin::dest_tree_awar(root)));  aws->create_autosize_button("SELECT_DISPLAYED2", "Use shown");
    aws->callback(makeWindowCallback(copy_tree_awar_cb, TreeAdmin::dest_tree_awar(root), awar_displayed_tree));  aws->create_autosize_button("DISPLAY_SELECTED2", "Display");
}

static AW_window_simple *create_select_other_tree_window(AW_root *root, const char *winId, const char *winTitle, const char *helpFile, AW_awar *awar_displayed_tree) {
    AW_window_simple *aws = new AW_window_simple;
    aws->init(root, winId, winTitle);
    aws->load_xfig("ad_one_tree.fig");

    aws->at("close");
    aws->auto_space(10, 3);

    aws->callback(AW_POPDOWN);
    aws->create_button("CLOSE", "Close", "C");

    aws->at("help");
    aws->callback(makeHelpCallback(helpFile));
    aws->create_button("HELP", "Help", "H");

    AW_awar *awar_other_tree = TreeAdmin::dest_tree_awar(root);

    aws->at("tree");
    awt_create_TREE_selection_list(GLOBAL.gb_main, aws, awar_other_tree->awar_name);

    aws->at("select");
    aws->callback(makeWindowCallback(copy_tree_awar_cb, awar_displayed_tree, awar_other_tree));     aws->create_autosize_button("SELECT_DISPLAYED", "Use");
    aws->callback(makeWindowCallback(copy_tree_awar_cb, awar_other_tree,     awar_displayed_tree)); aws->create_autosize_button("DISPLAY_SELECTED", "Display");

    aws->at("user");

    return aws;
}

AW_window *NT_create_compareTopologies_window(AW_root *root) {
    AW_window_simple *aws = new AW_window_simple;
    aws->init(root, "CMP_TOPOLOGY", "Compare tree topologies");
    aws->load_xfig("compare_topo.fig");

    aws->at("close");
    aws->callback(AW_POPDOWN);
    aws->create_button("CLOSE", "Close", "C");

    aws->at("help");
    aws->callback(makeHelpCallback("compare_topo.hlp"));
    aws->create_button("HELP", "Help", "H");

    NT_create_twoTreeSelection(aws);

    aws->at("user");
    aws->callback(makeWindowCallback(ad_move_tree_info, false));
    aws->create_autosize_button("CMP_TOPOLOGY", "Compare topologies");

    return aws;
}

static AWT_config_mapping_def moveGroupInfo_mapping[] = {
    { AWAR_GROUPXFER_INGROUP_ABS,    "ingroup_abs" },
    { AWAR_GROUPXFER_INGROUP_REL,    "ingroup_rel" },
    { AWAR_GROUPXFER_OUTGROUP_ABS,   "outgroup_abs" },
    { AWAR_GROUPXFER_OUTGROUP_REL,   "outgroup_rel" },

    { AWAR_GROUPXFER_UNKNOWN_ABS,    "unknown_abs" },
    { AWAR_GROUPXFER_KEELING,        "keeling" },

    { AWAR_GROUPXFER_INGROUP_LIM,    "ingroup_lim" },
    { AWAR_GROUPXFER_OUTGROUP_LIM,   "outgroup_lim" },

    { AWAR_GROUPXFER_SOURCE,         "sourceGroups" },
    { AWAR_GROUPXFER_OVERWRITE_MODE, "overwriteGroups" },

    { AWAR_GROUPXFER_ACI,            "aci" },

    { NULp, NULp },
};

static AWT_predefined_config moveGroupInfo_predef[] = {
    { "*only_perfect_groups", "Only copy perfectly matching groups with\n * 100% ingroup ratio and\n * 0% outgroup ratio", "ingroup_lim='100';outgroup_lim='0'" },

    { "*maximize_ingroup_ratio", "Maximize ingroup ratio \n   over outgroup ratio.\n(Note: diff of factor 10 is maybe too strong)", "ingroup_abs='0';ingroup_rel='100';outgroup_abs='0';outgroup_rel='10'" },
    { "*minimize_outgroup_ratio", "Minimize outgroup ratio \n     over ingroup ratio.\n(Note: diff of factor 10 is maybe too strong)", "ingroup_abs='0';ingroup_rel='10';outgroup_abs='0';outgroup_rel='100'" },

    { "*report2name", "custom target group name:\n * add prefix \"XFRD_\" (allows to distinguish newly transferred from existing groups)\n * add suffix reporting penalty", "aci='\"XFRD_\";groupname;\" {penalty = \";penalty;\"}\"'" },

    { NULp, NULp, NULp },
};



AW_window *NT_create_moveGroupInfo_window(AW_root *root) {
    AW_window_simple *aws = new AW_window_simple;
    aws->init(root, "COPY_NODE_INFO_OF_TREE", "Move groups");
    aws->load_xfig("move_groups.fig");

    aws->button_length(11);

    aws->at("close");
    aws->callback(AW_POPDOWN);
    aws->create_button("CLOSE", "Close", "C");

    aws->at("help");
    aws->callback(makeHelpCallback("move_groups.hlp"));
    aws->create_button("HELP", "Help", "H");

    const int FLOAT_COLUMNS   = 10;
    const int PERCENT_COLUMNS = 5;

    aws->at("ipep"); aws->create_input_field(AWAR_GROUPXFER_INGROUP_ABS, FLOAT_COLUMNS);
    aws->at("irp");  aws->create_input_field(AWAR_GROUPXFER_INGROUP_REL, FLOAT_COLUMNS);
    aws->at("ilim"); aws->create_input_field(AWAR_GROUPXFER_INGROUP_LIM, PERCENT_COLUMNS);

    aws->at("opep"); aws->create_input_field(AWAR_GROUPXFER_OUTGROUP_ABS, FLOAT_COLUMNS);
    aws->at("orp");  aws->create_input_field(AWAR_GROUPXFER_OUTGROUP_REL, FLOAT_COLUMNS);
    aws->at("olim"); aws->create_input_field(AWAR_GROUPXFER_OUTGROUP_LIM, PERCENT_COLUMNS);

    aws->at("upep"); aws->create_input_field(AWAR_GROUPXFER_UNKNOWN_ABS, FLOAT_COLUMNS);
    aws->at("keel"); aws->create_input_field(AWAR_GROUPXFER_KEELING,     FLOAT_COLUMNS);

    aws->at("srcGrps");
    aws->create_option_menu(AWAR_GROUPXFER_SOURCE);
    aws->insert_option("all groups",         "a", XFER_ALL_GROUPS);
    aws->insert_option("groups with marked", "m", XFER_GROUPS_WITH_MARKED);
    aws->update_option_menu();

    aws->at("tgtGrps");
    aws->create_option_menu(AWAR_GROUPXFER_OVERWRITE_MODE);
    aws->insert_option("remove existing groups",          "r", REMOVE_EXISTING_GROUPS);
    aws->insert_option("keep \"newname [was: oldname]\"", "k", KEEP_OLD_NAMES);
    aws->update_option_menu();

    aws->at("aci");
    aws->create_input_field(AWAR_GROUPXFER_ACI);

    NT_create_twoTreeSelection(aws);

    aws->at("go");
    aws->callback(makeWindowCallback(ad_move_tree_info, true));
    aws->create_button("GO", "GO", "G");

    aws->at("cfg");
    AWT_insert_config_manager(aws, AW_ROOT_DEFAULT, "moveGroupInfo", moveGroupInfo_mapping, NULp, moveGroupInfo_predef);

    return aws;
}

static void reorder_trees_cb(AW_window *aww, awt_reorder_mode dest) {
    // moves the tree in the list of trees

    char     *tree_name = aww->get_root()->awar(AWAR_TREE_NAME)->read_string();
    GB_ERROR  error     = NULp;

    GB_transaction ta(GLOBAL.gb_main);
    GBDATA *gb_treedata   = GBT_get_tree_data(GLOBAL.gb_main);
    GBDATA *gb_moved_tree = GB_entry(gb_treedata, tree_name);

    if (!gb_moved_tree) {
        error = "No tree selected";
    }
    else {
        GBT_ORDER_MODE  move_mode;
        GBDATA         *gb_target_tree = NULp;

        switch (dest) {
            case ARM_UP:
                move_mode      = GBT_INFRONTOF;
                gb_target_tree = GBT_tree_infrontof(gb_moved_tree);
                if (gb_target_tree) break;
                FALLTHROUGH; // move top-tree up = move to bottom
            case ARM_BOTTOM:
                move_mode      = GBT_BEHIND;
                gb_target_tree = GBT_find_bottom_tree(GLOBAL.gb_main);
                break;

            case ARM_DOWN:
                move_mode      = GBT_BEHIND;
                gb_target_tree = GBT_tree_behind(gb_moved_tree);
                if (gb_target_tree) break;
                FALLTHROUGH; // move bottom-tree down = move to top
            case ARM_TOP:
                move_mode      = GBT_INFRONTOF;
                gb_target_tree = GBT_find_top_tree(GLOBAL.gb_main);
                break;
        }

        if (gb_target_tree && gb_target_tree != gb_moved_tree) {
            error = GBT_move_tree(gb_moved_tree, move_mode, gb_target_tree);
        }
    }

    if (error) aw_message(error);
    free(tree_name);
}

void popup_tree_admin_window(AW_window *awp) {
    static AW_window_simple *aws = NULp;

    if (!aws) {
        AW_root *aw_root = awp->get_root();

        aws = new AW_window_simple;
        aws->init(aw_root, "TREE_ADMIN", "TREE ADMIN");
        aws->load_xfig("ad_tree.fig");

        aws->callback(AW_POPDOWN);
        aws->at("close");
        aws->create_button("CLOSE", "CLOSE", "C");

        aws->callback(makeHelpCallback("treeadm.hlp"));
        aws->at("help");
        aws->create_button("HELP", "HELP", "H");

        aws->button_length(40);

        aws->at("sel");
        aws->create_button(NULp, AWAR_TREE_NAME, NULp, "+");

        aws->at("security");
        aws->create_option_menu(AWAR_TREE_SECURITY);
        aws->insert_option("0", "0", 0);
        aws->insert_option("1", "1", 1);
        aws->insert_option("2", "2", 2);
        aws->insert_option("3", "3", 3);
        aws->insert_option("4", "4", 4);
        aws->insert_option("5", "5", 5);
        aws->insert_default_option("6", "6", 6);
        aws->update_option_menu();

        aws->at("rem");
        aws->create_text_field(AWAR_TREE_REM);


        aws->button_length(20);

        static TreeAdmin::Spec spec(GLOBAL.gb_main, AWAR_TREE_NAME);

        aws->at("delete");
        aws->help_text("treeadm.hlp");
        aws->callback(makeWindowCallback(TreeAdmin::delete_tree_cb, &spec));
        aws->create_button("DELETE", "Delete", "D");

        aws->at("rename");
        aws->help_text("treeadm.hlp");
        aws->callback(makeCreateWindowCallback(TreeAdmin::create_rename_window, &spec));
        aws->create_button("RENAME", "Rename", "R");

        aws->at("copy");
        aws->help_text("treeadm.hlp");
        aws->callback(makeCreateWindowCallback(TreeAdmin::create_copy_window, &spec));
        aws->create_button("COPY", "Copy", "C");

        aws->at("export");
        aws->help_text("tr_export.hlp");
        aws->callback(create_tree_export_window);
        aws->create_button("EXPORT", "Export", "E");

        aws->at("import");
        aws->help_text("tr_import.hlp");
        aws->callback(create_tree_import_window);
        aws->create_button("IMPORT", "Import", "I");

        aws->button_length(0);

        aws->at("list");
        awt_create_TREE_selection_list(GLOBAL.gb_main, aws, AWAR_TREE_NAME);

        aws->at("sort");
        awt_create_order_buttons(aws, reorder_trees_cb);
    }

    aws->activate();
}

// -----------------------
//      consense tree


static void create_consense_tree_cb(AW_window *aww, AW_selection *selected_trees) {
    AW_root  *aw_root = aww->get_root();
    GB_ERROR  error   = NULp;

    const char *cons_tree_name = aw_root->awar(AWAR_TREE_CONSENSE_TREE)->read_char_pntr();
    if (!cons_tree_name || !cons_tree_name[0]) {
        error = "No name specified for the consensus tree";
    }
    else {
        StrArray tree_names;
        selected_trees->get_values(tree_names);

        if (tree_names.size()<2) {
            error = "Not enough trees selected (at least 2 needed)";
        }
        else {
            GBDATA *gb_main = GLOBAL.gb_main;
            GB_transaction ta(gb_main);

            {
                arb_progress progress("Building consensus tree");
                ConsensusTreeBuilder tree_builder;

                progress.subtitle("loading input trees");
                for (size_t t = 0; t<tree_names.size() && !error; ++t) {
                    TreeRoot      *root = new SizeAwareRoot; // will be deleted when tree gets deleted
                    SizeAwareTree *tree = DOWNCAST(SizeAwareTree*, GBT_read_tree(gb_main, tree_names[t], root));
                    if (!tree) {
                        error = GB_await_error();
                    }
                    else {
                        tree_builder.add(tree, tree_names[t], 1.0);
                    }
                }

                if (!error) {
                    size_t    species_count;
                    TreeNode *cons_tree = tree_builder.get(species_count, error); // triggers 2 implicit progress increments

                    if (!error && progress.aborted()) {
                        error = "user abort";
                    }

                    nt_assert(contradicted(cons_tree, error));
                    if (cons_tree) {
                        char *comment = tree_builder.get_tree_remark();
                        error         = GBT_write_tree_with_remark(gb_main, cons_tree_name, cons_tree, comment);
                        free(comment);
                        UNCOVERED();
                        destroy(cons_tree);
                    }
                }
                if (error) progress.done();
            }
            error = ta.close(error);
        }
    }

    if (!error) {
        aw_root->awar(AWAR_TREE_NAME)->write_string(cons_tree_name); // show in main window
    }

    aw_message_if(error);
}

static void use_selected_as_target_cb(AW_window *aww) {
    AW_root *aw_root = aww->get_root();
    aw_root->awar(AWAR_TREE_CONSENSE_TREE)->write_string(aw_root->awar(AWAR_TREE_CONSENSE_SELECTED)->read_char_pntr());
}

AW_window *NT_create_consense_window(AW_root *aw_root) {
    static AW_window_simple *aws = NULp;
    if (!aws) {
        aws = new AW_window_simple;
        aws->init(aw_root, "CONSENSE_TREE", "Consensus Tree");
        aws->load_xfig("ad_cons_tree.fig");

        aws->auto_space(10, 10);

        aws->callback(AW_POPDOWN);
        aws->at("close");
        aws->create_button("CLOSE", "CLOSE", "C");

        aws->callback(makeHelpCallback("consense_tree.hlp"));
        aws->at("help");
        aws->create_button("HELP", "HELP", "H");

        aws->at("list");
        AW_DB_selection *all_trees      = awt_create_TREE_selection_list(GLOBAL.gb_main, aws, AWAR_TREE_CONSENSE_SELECTED);
        AW_selection    *selected_trees = awt_create_subset_selection_list(aws, all_trees->get_sellist(), "selected", "add", "sort");

        aws->at("name");
        aws->create_input_field(AWAR_TREE_CONSENSE_TREE);

        aws->button_length(0);
        aws->callback(use_selected_as_target_cb);
        aws->create_button("USE_AS_TARGET", "#moveLeft.xpm");

        aws->at("build");
        aws->callback(makeWindowCallback(create_consense_tree_cb, selected_trees));
        aws->create_autosize_button("BUILD", "Build consensus tree", "B");
    }
    return aws;
}

class CombinedPosInfo {
    // combines relative positions of a subtree in 2 trees (source- and target-tree).
    // provides compare operations for SortByTopo

    TreeRelativePosition source; // in source tree ("ordering tree")
    TreeRelativePosition target; // in target tree ("modified tree")

public:

    CombinedPosInfo(const TreeRelativePosition& s, const TreeRelativePosition& t)
        : source(s),
          target(t)
    {
        nt_assert(target.is_known());
    }
    CombinedPosInfo(const CombinedPosInfo& c1, const CombinedPosInfo& c2)
        : source(c1.source, c2.source),
          target(c1.target, c2.target)
    {}

    int compare(const CombinedPosInfo &right) const {
        // result similar to strcmp(this, right)
        if (!source.is_known() || !right.source.is_known()) {
            // one subtree is completely unknown in source-tree
            // => keep target-tree order
            return target.compare(right.target);
        }
        return source.compare(right.source);
    }
};

class SortByTopo : virtual Noncopyable {
    TreePositionLookup        source_pos; // in ordering topology
    const TreePositionLookup *target_pos; // in target topology (used where source_pos does not provide order)

    CombinedPosInfo reorder_subtree_rec(TreeNode *node) { // similar to ../ARBDB/TreeNode.cxx@reorder_subtree
        static const char *smallest_leafname; // has to be set to the alphabetically smallest name (when function exits)

        if (node->is_leaf()) {
            smallest_leafname = node->name;
            return CombinedPosInfo(source_pos.relative(node->name),
                                   target_pos->relative(node->name));
        }

        CombinedPosInfo  leftInfo       = reorder_subtree_rec(node->get_leftson());
        const char      *smallest_left  = smallest_leafname;
        CombinedPosInfo  rightInfo      = reorder_subtree_rec(node->get_rightson());
        const char      *smallest_right = smallest_leafname;

        bool left_leafname_bigger = strcmp(smallest_left, smallest_right)>0;
        smallest_leafname         = left_leafname_bigger ? smallest_right : smallest_left;

        {
            int cmp = leftInfo.compare(rightInfo);
            if (cmp>0 || (cmp == 0 && left_leafname_bigger)) {
                node->swap_sons();
            }
        }

        return CombinedPosInfo(leftInfo, rightInfo);
    }
public:

    SortByTopo(const TreeNode *by)
        : source_pos(by),
          target_pos(NULp)
    {}

#if defined(UNIT_TESTS)
    TreeRelativePosition sourcePos(const char *name) { return source_pos.relative(name); }
#endif

    void reorder_subtree(TreeNode *tree) {
        TreePositionLookup tpos(tree);
        LocallyModify<const TreePositionLookup*> provide(target_pos, &tpos);
        reorder_subtree_rec(tree);
    }
};

static GB_ERROR sort_tree_by_other_tree(GBDATA *gb_main, TreeNode *tree, const char *other_tree) {
    GB_ERROR       error = NULp;
    GB_transaction ta(gb_main);

    TreeNode *otherTree   = GBT_read_tree(gb_main, other_tree, new SimpleRoot);
    if (!otherTree) error = GB_await_error();
    else {
        SortByTopo sorter(otherTree);
        destroy(otherTree);
        sorter.reorder_subtree(tree);
    }
    return error;
}

static bool sort_dtree_by_other_tree_cb(TreeNode *tree, GB_ERROR& error) {
    const char *other_tree = TreeAdmin::dest_tree_awar(AW_root::SINGLETON)->read_char_pntr();
    error = sort_tree_by_other_tree(GLOBAL.gb_main, tree, other_tree);
    return !error;
}

static void sort_tree_by_other_tree_cb(UNFIXED, TREE_canvas *ntw) {
    GB_ERROR error = NT_with_displayed_tree_do(ntw, sort_dtree_by_other_tree_cb);
    aw_message_if(error);
}

AW_window *NT_create_sort_tree_by_other_tree_window(AW_root *aw_root, TREE_canvas *ntw) {
    AW_window_simple *aws = create_select_other_tree_window(aw_root, ntw->aww->local_id("SORT_BY_OTHER"), "Sort tree by other tree", "resortbyother.hlp", ntw->get_awar_tree());

    aws->callback(makeWindowCallback(sort_tree_by_other_tree_cb, ntw));
    aws->create_autosize_button("RESORT", "Sort according to source tree");

    return aws;
}

// ---------------------------
//      multifurcate tree

#define AWAR_MFURC                    "tree/multifurc/"
#define AWAR_MFURC_CONSIDER_BOOTSTRAP AWAR_MFURC "use_bs"
#define AWAR_MFURC_CONSIDER_LENGTH    AWAR_MFURC "use_len"
#define AWAR_MFURC_CONSIDER_TERMINALS AWAR_MFURC "terminals"
#define AWAR_MFURC_LENGTH_LIMIT       AWAR_MFURC "len"
#define AWAR_MFURC_BOOTSTRAP_LIMIT    AWAR_MFURC "bs"

void NT_create_multifurcate_tree_awars(AW_root *aw_root, AW_default props) {
    aw_root->awar_int  (AWAR_MFURC_CONSIDER_BOOTSTRAP, 0,   props);
    aw_root->awar_int  (AWAR_MFURC_CONSIDER_LENGTH,    1,   props);
    aw_root->awar_int  (AWAR_MFURC_CONSIDER_TERMINALS, 0,   props);
    aw_root->awar_float(AWAR_MFURC_LENGTH_LIMIT,       0.1, props);
    aw_root->awar_float(AWAR_MFURC_BOOTSTRAP_LIMIT,    50,  props);
}
static void multifurcation_cb(UNFIXED, TREE_canvas *ntw) {
    AW_root *aw_root = ntw->aww->get_root();

    float below_bootstrap = 101.0;
    float below_length    = 1000000.0;
    bool  applyAtLeafs    = aw_root->awar(AWAR_MFURC_CONSIDER_TERMINALS)->read_int();

    if (aw_root->awar(AWAR_MFURC_CONSIDER_BOOTSTRAP)->read_int()) below_bootstrap = aw_root->awar(AWAR_MFURC_BOOTSTRAP_LIMIT)->read_float();
    if (aw_root->awar(AWAR_MFURC_CONSIDER_LENGTH)   ->read_int()) below_length    = aw_root->awar(AWAR_MFURC_LENGTH_LIMIT)   ->read_float();

    NT_multifurcate_tree(ntw, TreeNode::multifurc_limits(below_bootstrap, below_length, applyAtLeafs));
}
AW_window *NT_create_multifurcate_tree_window(AW_root *aw_root, TREE_canvas *ntw) {
    AW_window_simple *aws = new AW_window_simple;

    aws->init(aw_root, ntw->aww->local_id("multifurcate"), "Multifurcate tree");
    aws->at(10, 10);
    aws->auto_space(10, 10);

    aws->callback(AW_POPDOWN);
    aws->create_button("CLOSE", "CLOSE", "C");

    aws->callback(makeHelpCallback("multifurcate.hlp"));
    aws->create_button("HELP", "HELP", "H");

    const int LABEL_LENGTH = 46;
    aws->label_length(LABEL_LENGTH);

    aws->at_newline();
    aws->label("Multifurcate branches with branchlength below");
    aws->create_toggle(AWAR_MFURC_CONSIDER_LENGTH);
    aws->create_input_field(AWAR_MFURC_LENGTH_LIMIT, 10);

    aws->at_newline();
    aws->label("                          AND bootstrap below");
    aws->create_toggle(AWAR_MFURC_CONSIDER_BOOTSTRAP);
    aws->create_input_field(AWAR_MFURC_BOOTSTRAP_LIMIT, 10);

    aws->label_length(0);
    aws->at_newline();
    aws->label("Also apply to terminal branches");
    aws->create_toggle(AWAR_MFURC_CONSIDER_TERMINALS);

    aws->at_newline();
    aws->callback(makeWindowCallback(multifurcation_cb, ntw));
    aws->create_autosize_button("MULTIFURCATE", "Multifurcate", "M");

    return aws;
}

// --------------------------------------------------------------------------------

#ifdef UNIT_TESTS
#ifndef TEST_UNIT_H
#include <test_unit.h>
#endif

static const char *getTreeComment(GBDATA *gb_main, const char *treeName) {
    GB_transaction ta(gb_main);
    return GBT_tree_info_string(gb_main, treeName, -1);
}

#define TEST_EXPECT_TREE_COMMENT_CONTAINS(treeName,expected)               TEST_EXPECT_CONTAINS(getTreeComment(gb_main,treeName),expected)
#define TEST_EXPECT_TREE_COMMENT_DOESNT_CONTAIN(treeName,expected)         TEST_EXPECT_DOESNT_CONTAIN(getTreeComment(gb_main,treeName),expected)
#define TEST_EXPECT_TREE_COMMENT_DOESNT_CONTAIN__BROKEN(treeName,expected) TEST_EXPECT_DOESNT_CONTAIN__BROKEN(getTreeComment(gb_main,treeName),expected)

static GB_ERROR sort_namedtree_by_other_tree(GBDATA *gb_main, const char *tree, const char *other_tree) {
    GB_ERROR        error = NULp;
    GB_transaction  ta(gb_main);
    SizeAwareTree  *Tree  = DOWNCAST(SizeAwareTree*, GBT_read_tree(gb_main, tree, new SizeAwareRoot));
    if (!Tree) error      = GB_await_error();
    else {
        Tree->compute_tree();
        error             = sort_tree_by_other_tree(gb_main, Tree, other_tree);
        if (!error) error = GBT_write_tree(gb_main, tree, Tree);
    }
    destroy(Tree);
    return error;
}

void TEST_sort_tree_by_other_tree() {
    GB_shell  shell;
    GBDATA   *gb_main = GB_open("TEST_trees.arb", "rw");
    TEST_REJECT_NULL(gb_main);

    const char *topo_test   = "(((((((CloTyro3:1.046,CloTyro4:0.061):0.026,CloTyro2:0.017):0.017,CloTyrob:0.009):0.274,CloInnoc:0.371):0.057,CloBifer:0.388):0.124,(((CloButy2:0.009,CloButyr:0.000):0.564,CloCarni:0.120):0.010,CloPaste:0.179):0.131):0.081,((((CorAquat:0.084,CurCitre:0.058):0.103,CorGluta:0.522):0.053,CelBiazo:0.059):0.207,CytAquat:0.711):0.081);";
    const char *topo_center = "(((CloPaste:0.179,((CloButy2:0.009,CloButyr:0.000):0.564,CloCarni:0.120):0.010):0.131,((CloInnoc:0.371,((CloTyro2:0.017,(CloTyro3:1.046,CloTyro4:0.061):0.026):0.017,CloTyrob:0.009):0.274):0.057,CloBifer:0.388):0.124):0.081,((CelBiazo:0.059,((CorAquat:0.084,CurCitre:0.058):0.103,CorGluta:0.522):0.053):0.207,CytAquat:0.711):0.081);";
    const char *topo_bottom = "((CytAquat:0.711,(CelBiazo:0.059,(CorGluta:0.522,(CorAquat:0.084,CurCitre:0.058):0.103):0.053):0.207):0.081,((CloPaste:0.179,(CloCarni:0.120,(CloButy2:0.009,CloButyr:0.000):0.564):0.010):0.131,(CloBifer:0.388,(CloInnoc:0.371,(CloTyrob:0.009,(CloTyro2:0.017,(CloTyro3:1.046,CloTyro4:0.061):0.026):0.017):0.274):0.057):0.124):0.081);";

    const char *topo_vs_nj_bs = "(((((((CloTyro3:1.046,CloTyro4:0.061):0.026,CloTyro2:0.017):0.017,CloTyrob:0.009):0.274,CloInnoc:0.371):0.057,CloBifer:0.388):0.124,(((CloButyr:0.000,CloButy2:0.009):0.564,CloCarni:0.120):0.010,CloPaste:0.179):0.131):0.081,(((CorGluta:0.522,(CorAquat:0.084,CurCitre:0.058):0.103):0.053,CelBiazo:0.059):0.207,CytAquat:0.711):0.081);";

    TEST_EXPECT_DIFFERENT(topo_test,   topo_center);
    TEST_EXPECT_DIFFERENT(topo_test,   topo_bottom);
    TEST_EXPECT_DIFFERENT(topo_center, topo_bottom);

    // create sorted copies of tree_test
    {
        GB_transaction  ta(gb_main);
        SizeAwareTree  *tree = DOWNCAST(SizeAwareTree*, GBT_read_tree(gb_main, "tree_test", new SizeAwareRoot));
        TEST_REJECT_NULL(tree);
        TEST_EXPECT_NEWICK(nLENGTH, tree, topo_test);

        tree->reorder_tree(BIG_BRANCHES_TO_CENTER); TEST_EXPECT_NO_ERROR(GBT_write_tree(gb_main, "tree_sorted_center", tree)); TEST_EXPECT_NEWICK(nLENGTH, tree, topo_center);
        tree->reorder_tree(BIG_BRANCHES_TO_BOTTOM); TEST_EXPECT_NO_ERROR(GBT_write_tree(gb_main, "tree_sorted_bottom", tree)); TEST_EXPECT_NEWICK(nLENGTH, tree, topo_bottom);

        // test SortByTopo
        {
            SortByTopo   sbt(tree);
            const double EPSILON = 0.0001;

            TEST_EXPECT_SIMILAR(sbt.sourcePos("CytAquat").value(), 0.0, EPSILON); // leftmost species (in topo_bottom)
            TEST_EXPECT_SIMILAR(sbt.sourcePos("CloTyro4").value(), 1.0, EPSILON); // rightmost species

            TEST_EXPECT_SIMILAR(sbt.sourcePos("CurCitre").value(), 0.2857, EPSILON); // (5 of 15)
            TEST_EXPECT_SIMILAR(sbt.sourcePos("CloButy2").value(), 0.5,    EPSILON); // center species (8 of 15)
            TEST_EXPECT_SIMILAR(sbt.sourcePos("CloTyrob").value(), 0.7857, EPSILON); // (12 of 15)

            TEST_REJECT(sbt.sourcePos("Un-Known").is_known()); // unknown species
        }

        tree->reorder_tree(BIG_BRANCHES_TO_EDGE); TEST_EXPECT_NO_ERROR(GBT_write_tree(gb_main, "tree_work", tree));

        destroy(tree);
    }


    TEST_EXPECT_NO_ERROR(sort_namedtree_by_other_tree(gb_main, "tree_work", "tree_sorted_center")); TEST_EXPECT_SAVED_NEWICK(nLENGTH, gb_main, "tree_work", topo_center);
    TEST_EXPECT_NO_ERROR(sort_namedtree_by_other_tree(gb_main, "tree_work", "tree_sorted_bottom")); TEST_EXPECT_SAVED_NEWICK(nLENGTH, gb_main, "tree_work", topo_bottom);
    TEST_EXPECT_NO_ERROR(sort_namedtree_by_other_tree(gb_main, "tree_work", "tree_test"));          TEST_EXPECT_SAVED_NEWICK(nLENGTH, gb_main, "tree_work", topo_test);
    TEST_EXPECT_NO_ERROR(sort_namedtree_by_other_tree(gb_main, "tree_work", "tree_nj_bs"));         TEST_EXPECT_SAVED_NEWICK(nLENGTH, gb_main, "tree_work", topo_vs_nj_bs);

    // TEST_EXPECT_NO_ERROR(GB_save_as(gb_main, "TEST_trees_save.arb", "b")); // test-save db to examine saved trees (do not commit!)

    // ----------------------------------------------------------------------------------------------------
    // test high-level function TREE_load_to_db (see #701; placed here by laziness, not related to sorting trees)
    TEST_EXPECT_NO_ERROR(TREE_load_to_db(gb_main, "trees/test.tree", "tree_loaded")); // ../UNIT_TESTER/run/trees/test.tree
    TEST_EXPECT_ERROR_CLEAR();
    TEST_EXPECT_SAVED_NEWICK(nALL, gb_main, "tree_loaded", "(((s1:0.200,s2:0.400):0.600,(s3:0.300,s 4:0.100):0.100):0.000,(s5:0.020,s-6:0.040):0.060);");
    TEST_EXPECT_TREE_COMMENT_CONTAINS("tree_loaded", "covering most of tree reader code"); // test comment

    GB_close(gb_main);
}

void TEST_move_node_info() {
    GB_shell  shell;
    GBDATA   *gb_main = GB_open("TEST_trees.arb", "r");

    const char *treeTarget1 = "tree_removal";
    const char *treeTarget2 = "tree_test";
    const char *treeSortby1 = "tree_removal_copy";
    const char *treeSortby2 = "tree_test_copy";

    const char *treeSource1 = treeSortby2;   // contains 1 group ("test")
    const char *treeSource2 = "tree_tree2";  // contains 2 groups ("g2" + "outer")
    const char *treeSource3 = "tree_groups"; // contains 5 groups

#define GROUP_TEST         "(CloTyrob,(CloTyro2,(CloTyro3,CloTyro4)))"
#define GROUP_TEST_FLIPPED "(((CloTyro3,CloTyro4),CloTyro2),CloTyrob)"

#define NAMED_GROUP_TEST       GROUP_TEST "'test'"
#define OVERWRITTEN_GROUP_TEST GROUP_TEST "'g2 [was: test]'"

    const char *org_topo1 = "((CloInnoc," GROUP_TEST "),(CloBifer,((CloCarni,CurCitre),((CloPaste,(Zombie1,(CloButy2,CloButyr))),(CytAquat,(CelBiazo,(CorGluta,(CorAquat,Zombie2))))))));";
    const char *org_topo2 = "((((" GROUP_TEST_FLIPPED ",CloInnoc),CloBifer),(((CloButy2,CloButyr),CloCarni),CloPaste)),((((CorAquat,CurCitre),CorGluta),CelBiazo),CytAquat));";

    // (index convention := source target)
    const char *unwanted_topo11 = "((CytAquat,(CelBiazo,(CorGluta,(CorAquat,Zombie2)))),((CloPaste,(Zombie1,(CloButy2,CloButyr))),((CloCarni,CurCitre),(CloBifer,(CloInnoc," NAMED_GROUP_TEST ")))));";
    const char *unwanted_topo21 = "((CloButy2,CloButyr),(Zombie1,(CloPaste,((((CloInnoc," OVERWRITTEN_GROUP_TEST "),CloBifer),(CloCarni,CurCitre)),(CytAquat,(CelBiazo,(CorGluta,(CorAquat,Zombie2)))))))'outer');";

    const char *sorted_topo11 = "(((((CloInnoc," NAMED_GROUP_TEST "),CloBifer),(CloCarni,CurCitre)),(CloPaste,(Zombie1,(CloButy2,CloButyr)))),(CytAquat,(CelBiazo,(CorGluta,(CorAquat,Zombie2)))));";
    const char *sorted_topo21 = "(((((((CloInnoc," OVERWRITTEN_GROUP_TEST "),CloBifer),(CloCarni,CurCitre)),(CytAquat,(CelBiazo,(CorGluta,(CorAquat,Zombie2))))),CloPaste),Zombie1)'outer',(CloButy2,CloButyr));";
    const char *topo32        = "((CloButy2,CloButyr)'upper',(((((" GROUP_TEST_FLIPPED "'low2',CloInnoc),CloBifer),((((CorAquat,CurCitre),CorGluta),CelBiazo),CytAquat)'low1'),CloPaste),CloCarni));";
    const char *topo32_rc     = "((CloButy2,CloButyr)'upper',(((((" GROUP_TEST_FLIPPED "'low2',CloInnoc),CloBifer),((((CorAquat,CurCitre),CorGluta),CelBiazo),CytAquat)'low1'),CloPaste),CloCarni)'lower');"; // @@@ should be same as topo32 (see #451)
    const char *topo32_rel    = "((CloButy2,CloButyr)"     ",(((((" GROUP_TEST_FLIPPED "'low2 [p=0.250000;ir=100.0%;3->4]',CloInnoc),CloBifer)'low1 [p=0.232222;ir=100.0%;7->6]',((((CorAquat,CurCitre),CorGluta),CelBiazo),CytAquat)'upper [p=0.510000;ir=100.0%;5->5]'),CloPaste),CloCarni)'lower [p=0.230769;ir=100.0%;10->13]');"; // group 'upper' and 'low1' moved to different locations by relative scoring
    const char *topo32_li     = "((CloButy2,CloButyr)"     ",(((((" GROUP_TEST_FLIPPED "'low2',CloInnoc),CloBifer),((((CorAquat,CurCitre),CorGluta),CelBiazo),CytAquat)'low1'),CloPaste),CloCarni)'lower');"; // group 'upper' filtered by limits

    const char *compared_topo = "(((((((CloInnoc,(CloTyrob,(CloTyro2,(CloTyro3,CloTyro4)))),CloBifer),(CloCarni,CurCitre)'# 2')'# 2',(CytAquat,(CelBiazo,(CorGluta,(CorAquat,Zombie2)'# 1')'# 1')'# 1')'# 1')'# 1',CloPaste),Zombie1),(CloButy2,CloButyr));";

    const char *LOG = "move_node_info.log";

// #define TEST_AUTO_UPDATE // uncomment to auto-update expected log-files
#if defined(TEST_AUTO_UPDATE)
# define TEST_LOGS_EXPECTED(expected) TEST_COPY_FILE(LOG, expected)
#else
# define TEST_LOGS_EXPECTED(expected) TEST_EXPECT_TEXTFILES_EQUAL(expected, LOG)
#endif // TEST_AUTO_UPDATE

    // create copies of 'tree_removal' + 'tree_test'
    {
        GB_transaction ta(gb_main);

        // remove existing comments from trees (already contains some log-entries tested below)
        {
            const char  *resetComment = "<comment reset>";
            TEST_EXPECT_NO_ERROR(GBT_write_tree_remark(gb_main, treeTarget1, resetComment));
            TEST_EXPECT_NO_ERROR(GBT_write_tree_remark(gb_main, treeTarget2, resetComment));
        }

        TEST_EXPECT_NO_ERROR(GBT_copy_tree(gb_main, treeTarget1, treeSortby1));
        TEST_EXPECT_NO_ERROR(GBT_copy_tree(gb_main, treeTarget2, treeSortby2));

        TEST_EXPECT_SAVED_NEWICK(nSIMPLE, gb_main, treeTarget1, org_topo1);
        TEST_EXPECT_SAVED_NEWICK(nSIMPLE, gb_main, treeTarget2, org_topo2);
    }

    GroupMatchScorer defaultScorer;

    // move node info
    {
        const char *comment_added = "Copied node info from tree_test_copy";
        TEST_EXPECT_TREE_COMMENT_DOESNT_CONTAIN(treeTarget1, comment_added);

        TEST_EXPECT_NO_ERROR(NTREE_move_tree_info(gb_main, treeSource1, treeTarget1, LOG, REMOVE_EXISTING_GROUPS, XFER_ALL_GROUPS, defaultScorer, NULp));
        TEST_LOGS_EXPECTED("group_xfer_11.log.expected");

        TEST_EXPECT_SAVED_NEWICK__BROKEN(nSIMPLE, gb_main, treeTarget1, org_topo1); // @@@ moving node info modifies topology; caused by NT_tree_cmp.cxx@NAIVE_ROOTING
        TEST_EXPECT_SAVED_NEWICK(nGROUP, gb_main, treeTarget1, unwanted_topo11);
        TEST_EXPECT_TREE_COMMENT_CONTAINS(treeTarget1, comment_added);

        // @@@ when we have a function to set the root according to another tree (#449),
        // use that function here. sorting tree after that, should again result in 'org_topo1'!

        TEST_EXPECT_NO_ERROR(sort_namedtree_by_other_tree(gb_main, treeTarget1, treeSortby1));
        TEST_EXPECT_SAVED_NEWICK(nGROUP, gb_main, treeTarget1, sorted_topo11);
    }
    {
        const char *comment_added = "Copied node info from tree_groups";
        TEST_EXPECT_TREE_COMMENT_DOESNT_CONTAIN(treeTarget2, comment_added);

        TEST_EXPECT_NO_ERROR(NTREE_move_tree_info(gb_main, treeSource3, treeTarget2, LOG, REMOVE_EXISTING_GROUPS, XFER_ALL_GROUPS, defaultScorer, NULp));
        TEST_LOGS_EXPECTED("group_xfer_32.log.expected");

        TEST_EXPECT_SAVED_NEWICK__BROKEN(nSIMPLE, gb_main, treeTarget2, org_topo2); // @@@ moving node info modifies topology; caused by NT_tree_cmp.cxx@NAIVE_ROOTING
        TEST_EXPECT_TREE_COMMENT_CONTAINS(treeTarget2, comment_added);
        TEST_EXPECT_SAVED_NEWICK(nGROUP, gb_main, treeTarget2, topo32);

        // perform same group-xfer after 1st xfer changed root => inserts 4 instead of 3 groups (obviously caused by changed root position; see #451)
        TEST_EXPECT_NO_ERROR(NTREE_move_tree_info(gb_main, treeSource3, treeTarget2, LOG, REMOVE_EXISTING_GROUPS, XFER_ALL_GROUPS, defaultScorer, NULp));
        TEST_LOGS_EXPECTED("group_xfer_32_rc.log.expected");
        TEST_EXPECT_SAVED_NEWICK(nGROUP, gb_main, treeTarget2, topo32_rc);

        {
            GroupMatchScorer relativeScorer;
            relativeScorer.setPerErrorPenalties(0.0, 0.0, 0.0001); // remove absolute penalties for in-/outgroup
            relativeScorer.setRelativePenalties(1.0, 1.0);         // set relative penalties for in-/outgroup

            TEST_EXPECT_NO_ERROR(NTREE_move_tree_info(gb_main, treeSource3, treeTarget2, LOG, REMOVE_EXISTING_GROUPS, XFER_ALL_GROUPS, relativeScorer,
                                                      "groupname;\" [p=\";penalty;\";ir=\";ingroup;\";\";oldsize;\"->\";newsize;\"]\""));
            TEST_LOGS_EXPECTED("group_xfer_32_rel.log.expected");
            TEST_EXPECT_SAVED_NEWICK(nGROUP, gb_main, treeTarget2, topo32_rel);
        }

        // again perform same group-xfer using ingroup- and outgroup-limit
        {
            GroupMatchScorer limitedScorer;
            // limitedScorer.setLimits(RatioLimits(1.0, 1.0), RatioLimits(0.0, 0.0)); // filters all groups (upper, low2, low1 + lower)
            // limitedScorer.setLimits(RatioLimits(0.0, 1.0), RatioLimits(0.0, 1.0)); // filters no group (by definition)
            // limitedScorer.setLimits(RatioLimits(0.5, 1.0), RatioLimits(0.0, 1.0)); // group 'upper' placed at position with higher absolute penalty
            // limitedScorer.setLimits(RatioLimits(0.75, 1.0), RatioLimits(0.0, 1.0)); // weird (does keel groups)
            // limitedScorer.setLimits(RatioLimits(0.9, 1.0), RatioLimits(0.0, 1.0)); // removes group 'upper'
            // limitedScorer.setLimits(RatioLimits(0.0, 1.0), RatioLimits(0.0, 0.5)); // filters no group
            // limitedScorer.setLimits(RatioLimits(0.0, 1.0), RatioLimits(0.0, 0.1)); // filters groups 'twoleafs' + 'low2' (group 'lower' superseeded by 'low1')
            // limitedScorer.setLimits(RatioLimits(0.0, 1.0), RatioLimits(0.0, 0.3)); // filters group 'twoleafs'
            // limitedScorer.setLimits(RatioLimits(0.9, 1.0), RatioLimits(0.0, 0.1)); // filters all groups (weird)
            limitedScorer.setLimits(RatioLimits(0.7, 1.0), RatioLimits(0.0, 0.3)); // filters group 'upper' + group 'twoleafs'
            limitedScorer.setPerErrorPenalties(2.0, 2.0, 0.0002); // all values are 2*default -> result is same, scores are doubled!

            TEST_EXPECT_NO_ERROR(NTREE_move_tree_info(gb_main, treeSource3, treeTarget2, LOG, REMOVE_EXISTING_GROUPS, XFER_ALL_GROUPS, limitedScorer, "")); // test empty ACI does same as passing NULp
            TEST_LOGS_EXPECTED("group_xfer_32_li.log.expected");
            TEST_EXPECT_SAVED_NEWICK(nGROUP, gb_main, treeTarget2, topo32_li);
        }
    }

    // add node info
    {
        const char *comment_added = "Added node info from tree_tree2";
        TEST_EXPECT_TREE_COMMENT_DOESNT_CONTAIN(treeTarget1, comment_added);

        TEST_EXPECT_NO_ERROR(NTREE_move_tree_info(gb_main, treeSource2, treeTarget1, LOG, KEEP_OLD_NAMES, XFER_ALL_GROUPS, defaultScorer, NULp));
        TEST_LOGS_EXPECTED("group_xfer_21.log.expected");

        TEST_EXPECT_SAVED_NEWICK__BROKEN(nSIMPLE, gb_main, treeTarget1, org_topo1); // @@@ moving node info modifies topology; caused by NT_tree_cmp.cxx@NAIVE_ROOTING
        TEST_EXPECT_SAVED_NEWICK(nGROUP, gb_main, treeTarget1, unwanted_topo21);
        TEST_EXPECT_TREE_COMMENT_CONTAINS(treeTarget1, comment_added);

        // @@@ when we have a function to set the root according to another tree (#449),
        // use that function here. sorting tree after that, should again result in 'org_topo1'!

        TEST_EXPECT_NO_ERROR(sort_namedtree_by_other_tree(gb_main, treeTarget1, treeSortby1));
        TEST_EXPECT_SAVED_NEWICK(nGROUP, gb_main, treeTarget1, sorted_topo21);
    }

    // compare node info
    {
        const char *comment_added = "Compared topology with tree_test";
        TEST_EXPECT_TREE_COMMENT_DOESNT_CONTAIN(treeTarget1, comment_added);

        TEST_EXPECT_NO_ERROR(NTREE_move_tree_info(gb_main, treeSource1, treeTarget1, NULp, COMPARE_TOPOLOGY, XFER_ALL_GROUPS, defaultScorer, NULp));
        TEST_EXPECT_SAVED_NEWICK(nREMARK, gb_main, treeTarget1, compared_topo);
        TEST_EXPECT_TREE_COMMENT_CONTAINS(treeTarget1, comment_added);
    }

    // test error cases:
    {
#define DOESNT_MATTER_ARGS gb_main,treeSource2,treeTarget1,LOG,REMOVE_EXISTING_GROUPS,XFER_ALL_GROUPS

        GroupMatchScorer invalidScoring;

        invalidScoring.setPerErrorPenalties(1.0, 0.0, 0.0001);
        TEST_EXPECT_ERROR_CONTAINS(NTREE_move_tree_info(DOESNT_MATTER_ARGS, invalidScoring, NULp), "one outgroup penalty has to be different from zero");

        invalidScoring.setPerErrorPenalties(0.0, 1.0, 0.0001);
        TEST_EXPECT_ERROR_CONTAINS(NTREE_move_tree_info(DOESNT_MATTER_ARGS, invalidScoring, NULp), "one ingroup penalty has to be different from zero");

        invalidScoring.setPerErrorPenalties(-1.0, 1.0, 0.0001);
        TEST_EXPECT_ERROR_CONTAINS(NTREE_move_tree_info(DOESNT_MATTER_ARGS, invalidScoring, NULp), "invalid negative in/outgroup penalty");

        invalidScoring.setPerErrorPenalties(1.0, 1.0, 0.0001);
        invalidScoring.setRelativePenalties(100.0, -100.0);
        TEST_EXPECT_ERROR_CONTAINS(NTREE_move_tree_info(DOESNT_MATTER_ARGS, invalidScoring, NULp), "invalid negative in/outgroup penalty");

#undef DOESNT_MATTER_ARGS
    }

    GB_unlink(LOG);
    GB_close(gb_main);
}

__ATTR__REDUCED_OPTIMIZE void TEST_edges() {
    GB_shell  shell;
    GBDATA   *gb_main = GB_open("TEST_trees.arb", "rw");
    TEST_REJECT_NULL(gb_main);

    {
        GB_transaction  ta(gb_main);
        TreeNode       *tree = GBT_read_tree(gb_main, "tree_test", new SizeAwareRoot);

        TreeNode *left  = tree->findLeafNamed("CloTyro3"); TEST_REJECT_NULL(left);
        TreeNode *node  = left->get_father();              TEST_REJECT_NULL(node);
        TreeNode *right = node->findLeafNamed("CloTyro4"); TEST_REJECT_NULL(right);

        TEST_EXPECT(node == right->get_father());
        TEST_EXPECT(node->get_leftson()  == left);
        TEST_EXPECT(node->get_rightson() == right);

        TreeNode *parent  = node->get_father();                TEST_REJECT_NULL(parent);
        TreeNode *brother = parent->findLeafNamed("CloTyro2"); TEST_REJECT_NULL(brother);

        TEST_EXPECT(node->get_brother() == brother);

        TreeNode *grandpa  = parent->get_father(); TEST_REJECT_NULL(grandpa);

        // topology:
        //
        //            grandpa
        //              /
        //             /
        //            /
        //          parent
        //           /\              .
        //          /  \             .
        //         /    \            .
        //       node  brother
        //        /\                 .
        //       /  \                .
        //      /    \               .
        //    left right

        // test next() and otherNext() for inner edge 'node->parent'
        {
            ARB_edge nodeUp = parentEdge(node);

            TEST_EXPECT(node->is_leftson());                      // if child is left son..
            TEST_EXPECT(nodeUp.next().dest()         == grandpa); // .. next() continues rootwards
            TEST_EXPECT(nodeUp.counter_next().dest() == brother);

            ARB_edge brotherUp = parentEdge(brother);

            TEST_EXPECT(brother->is_rightson());                  // if child is right son..
            TEST_EXPECT(brotherUp.next().dest()         == node); // .. next() continues with other son
            TEST_EXPECT(brotherUp.counter_next().dest() == grandpa);

            ARB_edge down = nodeUp.inverse();

            TEST_EXPECT(down.next().dest()         == right); // next descends into right son
            TEST_EXPECT(down.counter_next().dest() == left);

            TEST_EXPECT(nodeUp.previous().source()         == left);
            TEST_EXPECT(nodeUp.counter_previous().source() == right);

            ARB_edge toLeaf(node, left);
            TEST_EXPECT(toLeaf.is_edge_to_leaf());

            // all iterators should turn around at leaf:
            TEST_EXPECT(toLeaf.next().dest()         == node);
            TEST_EXPECT(toLeaf.counter_next().dest() == node);

            ARB_edge fromLeaf(left, node);
            TEST_EXPECT(fromLeaf.previous().dest()         == left);
            TEST_EXPECT(fromLeaf.counter_previous().dest() == left);

            ARB_edge rootEdge(tree->get_leftson(), tree->get_rightson());

            TEST_EXPECT(rootEdge.get_type() == ROOT_EDGE);
            TEST_EXPECT(nodeUp.get_type()   == EDGE_TO_ROOT);
            TEST_EXPECT(fromLeaf.get_type() == EDGE_TO_ROOT);
            TEST_EXPECT(down.get_type()     == EDGE_TO_LEAF);
            TEST_EXPECT(toLeaf.get_type()   == EDGE_TO_LEAF);

            // test iterators are inverse functions
            {
                ARB_edge e[] = { nodeUp, down, toLeaf, fromLeaf, rootEdge };
                const int EDGES = ARRAY_ELEMS(e);
                for (int i = 0; i<EDGES; ++i) {
                    TEST_ANNOTATE(GBS_global_string("i=%i", i));

                    TEST_EXPECT(e[i].next().previous() == e[i]);
                    TEST_EXPECT(e[i].previous().next() == e[i]);

                    TEST_EXPECT(e[i].counter_next().counter_previous() == e[i]);
                    TEST_EXPECT(e[i].counter_previous().counter_next() == e[i]);

                    ARB_edge inv(e[i].inverse());

                    TEST_EXPECT(e[i].counter_next().inverse().next()         == inv);
                    TEST_EXPECT(e[i].counter_previous().inverse().previous() == inv);
                    TEST_EXPECT(e[i].next().inverse().counter_next()         == inv);
                    TEST_EXPECT(e[i].previous().inverse().counter_previous() == inv);
                }
            }

            // test adjacent_distance
            const double EPSILON = 0.000001;

            const double NLEN = 0.025806;
            const double BLEN = 0.017316;
            const double PLEN = 0.017167;
            const double LLEN = 1.045690;
            const double RLEN = 0.060606;

            TEST_EXPECT_SIMILAR(node->get_branchlength(),             NLEN, EPSILON);
            TEST_EXPECT_SIMILAR(nodeUp.length(),                      NLEN, EPSILON);
            TEST_EXPECT_SIMILAR(down.length(),                        NLEN, EPSILON);
            TEST_EXPECT_SIMILAR(nodeUp.length_or_adjacent_distance(), NLEN, EPSILON);
            TEST_EXPECT_SIMILAR(down.length_or_adjacent_distance(),   NLEN, EPSILON);

            TEST_EXPECT_SIMILAR(brother->get_branchlength(), BLEN,      EPSILON);
            TEST_EXPECT_SIMILAR(parent ->get_branchlength(), PLEN,      EPSILON);
            TEST_EXPECT_SIMILAR(nodeUp.adjacent_distance(),  BLEN+PLEN, EPSILON);

            TEST_EXPECT_SIMILAR(left ->get_branchlength(), LLEN,      EPSILON);
            TEST_EXPECT_SIMILAR(right->get_branchlength(), RLEN,      EPSILON);
            TEST_EXPECT_SIMILAR(down.adjacent_distance(),  LLEN+RLEN, EPSILON);

            // modify lengths
            const double MOD_NLEN = 0.123456;
            const double MOD_LLEN = 0.246802;

            toLeaf.set_length(MOD_LLEN);
            nodeUp.set_length(MOD_NLEN);

            TEST_EXPECT_SIMILAR(toLeaf.length(), MOD_LLEN, EPSILON);
            TEST_EXPECT_SIMILAR(nodeUp.length(), MOD_NLEN, EPSILON);
            TEST_EXPECT_SIMILAR(down.length(),   MOD_NLEN, EPSILON);
        }

        destroy(tree);
    }

    GB_close(gb_main);
}

void TEST_remove_bootstraps() {
    GB_shell  shell;
    GBDATA   *gb_main = GB_open("TEST_trees.arb", "rw");
    TEST_REJECT_NULL(gb_main);

    {
        GB_transaction  ta(gb_main);
        TreeNode       *tree = GBT_read_tree(gb_main, "tree_test", new SizeAwareRoot);
        TEST_REJECT_NULL(tree);

        const char *topo_org   = "(((((((CloTyro3,CloTyro4)'40%',CloTyro2)'0%',CloTyrob)'97%',CloInnoc)'0%',CloBifer)'53%',(((CloButy2,CloButyr),CloCarni)'33%',CloPaste)'97%'),((((CorAquat,CurCitre),CorGluta)'17%',CelBiazo)'40%',CytAquat));";
        const char *topo_rem   = "(((((((CloTyro3,CloTyro4)"   ",CloTyro2)"  ",CloTyrob)"   ",CloInnoc)"  ",CloBifer)"   ",(((CloButy2,CloButyr),CloCarni)"   ",CloPaste)"   "),((((CorAquat,CurCitre),CorGluta)"   ",CelBiazo)"   ",CytAquat));";

        TEST_EXPECT_NEWICK(nREMARK, tree, topo_org);

        tree->remove_bootstrap();
        TEST_EXPECT_NEWICK(nREMARK, tree, topo_rem);

        destroy(tree);
    }

    GB_close(gb_main);
}

void TEST_multifurcate_tree() {
    GB_shell  shell;
    GBDATA   *gb_main = GB_open("TEST_trees.arb", "rw");
    TEST_REJECT_NULL(gb_main);

    const char *topo_test               = "(((((((CloTyro3:1.046,CloTyro4:0.061)'40%':0.026,CloTyro2:0.017)'0%':0.017,CloTyrob:0.009)'97%:test':0.274,CloInnoc:0.371)'0%':0.057,CloBifer:0.388)'53%':0.124,(((CloButy2:0.009,CloButyr:0.000):0.564,CloCarni:0.120)'33%':0.010,CloPaste:0.179)'97%':0.131):0.081,((((CorAquat:0.084,CurCitre:0.058):0.103,CorGluta:0.522)'17%':0.053,CelBiazo:0.059)'40%':0.207,CytAquat:0.711):0.081);";
    // changes                          = "                                                                                                    +0.307         -0.371     +0.064 "
    const char *topo_single             = "(((((((CloTyro3:1.046,CloTyro4:0.061)'40%':0.026,CloTyro2:0.017)'0%':0.017,CloTyrob:0.009)'97%:test':0.581,CloInnoc:0.000)'0%':0.121,CloBifer:0.388)'53%':0.124,(((CloButy2:0.009,CloButyr:0.000):0.564,CloCarni:0.120)'33%':0.010,CloPaste:0.179)'97%':0.131):0.081,((((CorAquat:0.084,CurCitre:0.058):0.103,CorGluta:0.522)'17%':0.053,CelBiazo:0.059)'40%':0.207,CytAquat:0.711):0.081);";
    const char *topo_bs_less_101_005    = "(((((((CloTyro3:1.098,CloTyro4:0.064)"   ":0.000,CloTyro2:0.000)"  ":0.000,CloTyrob:0.000)'97%:test':0.287,CloInnoc:0.371)'0%':0.057,CloBifer:0.388)'53%':0.124,(((CloButy2:0.000,CloButyr:0.000):0.578,CloCarni:0.121)"   ":0.000,CloPaste:0.181)'97%':0.132):0.081,((((CorAquat:0.084,CurCitre:0.058):0.103,CorGluta:0.522)'17%':0.053,CelBiazo:0.059)'40%':0.207,CytAquat:0.711):0.081);";
    const char *topo_bs_less_101_005_NT = "(((((((CloTyro3:1.078,CloTyro4:0.062)"   ":0.000,CloTyro2:0.018)"  ":0.000,CloTyrob:0.009)'97%:test':0.282,CloInnoc:0.371)'0%':0.057,CloBifer:0.388)'53%':0.124,(((CloButy2:0.009,CloButyr:0.000):0.570,CloCarni:0.121)"   ":0.000,CloPaste:0.181)'97%':0.132):0.081,((((CorAquat:0.084,CurCitre:0.058):0.103,CorGluta:0.522)'17%':0.053,CelBiazo:0.059)'40%':0.207,CytAquat:0.711):0.081);";
    const char *topo_bs_less_30_005     = "(((((((CloTyro3:1.046,CloTyro4:0.061)'40%':0.027,CloTyro2:0.018)"  ":0.000,CloTyrob:0.009)'97%:test':0.288,CloInnoc:0.371)'0%':0.057,CloBifer:0.388)'53%':0.124,(((CloButy2:0.009,CloButyr:0.000):0.564,CloCarni:0.120)'33%':0.010,CloPaste:0.179)'97%':0.131):0.081,((((CorAquat:0.084,CurCitre:0.058):0.103,CorGluta:0.522)'17%':0.053,CelBiazo:0.059)'40%':0.207,CytAquat:0.711):0.081);";
    const char *topo_bs_less_30         = "(((((((CloTyro3:1.046,CloTyro4:0.061)'40%':0.027,CloTyro2:0.018)"  ":0.000,CloTyrob:0.009)'97%:test':0.302,CloInnoc:0.390)"  ":0.000,CloBifer:0.407)'53%':0.131,(((CloButy2:0.009,CloButyr:0.000):0.564,CloCarni:0.120)'33%':0.010,CloPaste:0.179)'97%':0.131):0.081,((((CorAquat:0.084,CurCitre:0.058):0.109,CorGluta:0.554)"   ":0.000,CelBiazo:0.062)'40%':0.220,CytAquat:0.711):0.081);";
    const char *topo_all                = "(((((((CloTyro3:0.000,CloTyro4:0.000)"   ":0.000,CloTyro2:0.000)"  ":0.000,CloTyrob:0.000)'"  "test':0.000,CloInnoc:0.000)"  ":0.000,CloBifer:0.000)"   ":0.000,(((CloButy2:0.000,CloButyr:0.000):0.000,CloCarni:0.000)"   ":0.000,CloPaste:0.000)"   ":0.000):0.000,((((CorAquat:0.000,CurCitre:0.000):0.000,CorGluta:0.000)"   ":0.000,CelBiazo:0.000)"   ":0.000,CytAquat:0.000):0.000);";

    const double STABLE_LENGTH = 5.362750;
    const double EPSILON       = 0.000001;

    for (int test = 1; test<=6; ++test) {
        GB_transaction  ta(gb_main);
        TreeNode       *tree = GBT_read_tree(gb_main, "tree_test", new SizeAwareRoot);

        TEST_REJECT_NULL(tree);
        if (test == 1) {
            TEST_EXPECT_NEWICK(nALL, tree, topo_test);
            TEST_EXPECT_SIMILAR(tree->sum_child_lengths(), STABLE_LENGTH, EPSILON);
        }

        switch (test) {
            case 1:
                tree->multifurcate_whole_tree(TreeNode::multifurc_limits(101, 0.05, true));
                TEST_EXPECT_NEWICK(nALL, tree, topo_bs_less_101_005);
                TEST_EXPECT_SIMILAR(tree->sum_child_lengths(), STABLE_LENGTH, EPSILON);
                break;
            case 6:
                tree->multifurcate_whole_tree(TreeNode::multifurc_limits(101, 0.05, false));
                TEST_EXPECT_NEWICK(nALL, tree, topo_bs_less_101_005_NT);
                TEST_EXPECT_SIMILAR(tree->sum_child_lengths(), STABLE_LENGTH, EPSILON);
                break;
            case 2:
                tree->multifurcate_whole_tree(TreeNode::multifurc_limits(30, 0.05, true));
                TEST_EXPECT_NEWICK(nALL, tree, topo_bs_less_30_005);
                TEST_EXPECT_SIMILAR(tree->sum_child_lengths(), STABLE_LENGTH, EPSILON);
                break;
            case 3:
                tree->multifurcate_whole_tree(TreeNode::multifurc_limits(30, 1000, true));
                TEST_EXPECT_NEWICK(nALL, tree, topo_bs_less_30);
                TEST_EXPECT_SIMILAR(tree->sum_child_lengths(), STABLE_LENGTH, EPSILON);
                break;
            case 4:
                tree->multifurcate_whole_tree(TreeNode::multifurc_limits(101, 1000, true)); // multifurcate all
                TEST_EXPECT_NEWICK(nALL, tree, topo_all);
                TEST_EXPECT_SIMILAR(tree->sum_child_lengths(), 0.0, EPSILON);
                break;
            case 5: {
                TreeNode *CloInnoc = tree->findLeafNamed("CloInnoc");
                TEST_REJECT_NULL(CloInnoc);

                parentEdge(CloInnoc).multifurcate();
                TEST_EXPECT_NEWICK(nALL, tree, topo_single);

                TEST_EXPECT_SIMILAR(tree->sum_child_lengths(), STABLE_LENGTH, EPSILON);
                break;
            }
            default:
                nt_assert(0);
                break;
        }

        destroy(tree);
    }

    GB_close(gb_main);
}

void TEST_TreeNode_attributes() {
    // -> ../UNIT_TESTER/run/trees/bg_exp_p__0.tree
    TreeNode *tree = TREE_load("trees/bg_exp_p__0.tree", new SimpleRoot, NULp, false, NULp);

    TreeNode *MabPelag = tree->findLeafNamed("MabPelag");
    TreeNode *MabSalin = tree->findLeafNamed("MabSalin");
    TreeNode *PaoMaris = tree->findLeafNamed("PaoMaris");

    TEST_EXPECT(MabPelag->father == MabSalin->father); // are brothers

    TreeNode *Mabs    = MabPelag->father;
    TreeNode *PaoMabs = PaoMaris->father;

    // ((MabPelag, MabSalin), PaoMaris)
    //  -------- Mabs ------
    // -------------- PaoMabs ---------

    TEST_EXPECT(Mabs->father == PaoMabs);

    // is_son_of
    TEST_EXPECT(MabPelag->is_son_of(Mabs));
    TEST_EXPECT(MabSalin->is_son_of(Mabs));
    TEST_EXPECT(Mabs->is_son_of(PaoMabs));
    TEST_EXPECT(PaoMaris->is_son_of(PaoMabs));

    // is_inside
    TEST_EXPECT(MabPelag->is_inside(Mabs));     // leaf in father
    TEST_EXPECT(Mabs->is_inside(PaoMabs));      // node in father
    TEST_EXPECT(MabPelag->is_inside(PaoMabs));  // leaf in grandfather
    TEST_EXPECT(MabPelag->is_inside(MabPelag)); // self-containment
    TEST_REJECT(Mabs->is_inside(MabPelag));     // not: father in child
    TEST_REJECT(MabPelag->is_inside(MabSalin)); // not: node in brother

    // is_ancestor_of
    TEST_EXPECT(Mabs->is_ancestor_of(MabPelag));
    TEST_EXPECT(Mabs->is_ancestor_of(MabSalin));
    TEST_REJECT(Mabs->is_ancestor_of(PaoMaris)); // brother is no ancestor
    TEST_REJECT(Mabs->is_ancestor_of(Mabs));     // node never is ancestor of itself
    TEST_REJECT(Mabs->is_ancestor_of(PaoMabs));  // child cannot be ancestor

    TEST_EXPECT(PaoMabs->is_ancestor_of(MabPelag)); // root of subtree (PaoMabs) is ancestor of all members..
    TEST_EXPECT(PaoMabs->is_ancestor_of(MabSalin));
    TEST_EXPECT(PaoMabs->is_ancestor_of(PaoMaris));
    TEST_EXPECT(PaoMabs->is_ancestor_of(Mabs));
    TEST_REJECT(PaoMabs->is_ancestor_of(PaoMabs));  // .. despite itself

    // in_same_branch_as / in_other_branch_than
    TEST_EXPECT(MabPelag->in_same_branch_as(MabPelag));
    TEST_EXPECT(MabPelag->in_other_branch_than(MabSalin));
    TEST_EXPECT(MabPelag->in_other_branch_than(PaoMaris));
    TEST_EXPECT(MabPelag->in_same_branch_as(Mabs));
    TEST_EXPECT(MabPelag->in_same_branch_as(PaoMabs));

    TEST_EXPECT(PaoMabs->in_same_branch_as(MabPelag));
    TEST_EXPECT(PaoMabs->in_same_branch_as(MabSalin));
    TEST_EXPECT(PaoMabs->in_same_branch_as(PaoMaris));
    TEST_EXPECT(PaoMabs->in_same_branch_as(Mabs));
    TEST_EXPECT(PaoMabs->in_same_branch_as(PaoMabs));

    TEST_EXPECT(Mabs->in_same_branch_as(MabPelag));
    TEST_EXPECT(Mabs->in_same_branch_as(MabSalin));
    TEST_EXPECT(Mabs->in_other_branch_than(PaoMaris));
    TEST_EXPECT(Mabs->in_same_branch_as(Mabs));
    TEST_EXPECT(Mabs->in_same_branch_as(PaoMabs));

    // ancestor_common_with
    TEST_EXPECT(MabPelag->ancestor_common_with(MabSalin) == Mabs);
    TEST_EXPECT(MabSalin->ancestor_common_with(MabPelag) == Mabs);
    TEST_EXPECT(PaoMaris->ancestor_common_with(MabPelag) == PaoMabs);
    TEST_EXPECT(PaoMabs->ancestor_common_with(Mabs)      == PaoMabs);
    TEST_EXPECT(MabPelag->ancestor_common_with(PaoMabs)  == PaoMabs);

    destroy(tree);
}

#endif // UNIT_TESTS

// --------------------------------------------------------------------------------