NT_syncroot.cxx

Go to the documentation of this file.

// ========================================================= //
//                                                           //
//   File      : NT_syncroot.cxx                             //
//   Purpose   : GUI + tests for root synchronization        //
//                                                           //
//   Coded by Ralf Westram (coder@reallysoft.de) in May 20   //
//   http://www.arb-home.de/                                 //
//                                                           //
// ========================================================= //

#include <SyncRoot.hxx>
#include <TreeRead.h>

#include <aw_window.hxx>
#include <aw_msg.hxx>
#include <aw_root.hxx>
#include <aw_select.hxx>
#include <aw_awar.hxx>
#include <awt_sel_boxes.hxx>

#include <arb_global_defs.h>

using namespace std;

#define TREE_SYNCROOT_AWAR_BASE     "tree/syncroot/"
#define TREE_SYNCROOT_TEMP_BASE     "tmp/" TREE_SYNCROOT_AWAR_BASE
#define AWAR_TREE_SYNCROOT_SELECTED TREE_SYNCROOT_TEMP_BASE "selected"

static GB_ERROR load_and_add_tree(GBDATA *gb_main, const char *treename, RootSynchronizer& addTo) {
    GB_transaction  ta(gb_main);
    SizeAwareTree  *satree = DOWNCAST(SizeAwareTree*, GBT_read_tree(gb_main, treename, new SizeAwareRoot));
    GB_ERROR        error  = NULp;
    if (!satree) {
        error = GB_await_error();
    }
    else {
        addTo.add(satree, treename);
    }
    return error;
}

static ARB_ERROR adjustTreeRoot(ConstSizeAwareTreePtr newRootEdge, RootSynchronizer& rsync, size_t t, GBDATA *gb_main, const char *distInfo, int rt) {
    ARB_ERROR        error;
    SizeAwareTree   *resultTree = rsync.take_tree(t); // retrieve tree from RootSynchronizer (takes ownership!)
    const TreeInfo&  treeInfo   = rsync.get_tree_info(t);

    arb_assert(newRootEdge->is_inside(resultTree));
    if (newRootEdge->is_son_of_root()) { // -> do NOT set root (just drop a note)
        const char *what = rt<0 ? "best found" : "optimal";
        aw_message(GBS_global_string("%s: root already at %s position (%s)", treeInfo.name(), what, distInfo));
    }
    else {
        SizeAwareTree *newRootEdge_nc = const_cast<SizeAwareTree*>(&*newRootEdge); // safe ('resultTree' is owned)
        newRootEdge_nc->set_root();                                                // set root to 'edge'

        aw_message(GBS_global_string("%s: set root (%s)", treeInfo.name(), distInfo));

        // store tree in DB:
        {
            GB_transaction  ta(gb_main);
            GBDATA         *gb_tree = GBT_find_tree(gb_main, treeInfo.name());
            if (!gb_tree) {
                error = GBS_global_string("no such tree '%s' - cannot overwrite", treeInfo.name());
            }
            else {
                error = GBT_overwrite_tree(gb_tree, resultTree);
                if (!error) {
                    string entry;
                    if (rt<0) { // multiroot optimization
                        entry = GBS_global_string("Multiroot optimization (%s)", distInfo);
                    }
                    else { // sync vs ref tree
                        entry = GBS_global_string("Adjusted root versus '%s' (%s)", rsync.get_tree_info(rt).name(), distInfo);
                    }
                    error = GBT_log_to_tree_remark(gb_tree, entry.c_str(), true);
                }
            }
            error = ta.close(error);
        }
    }

    return error;
}
static ARB_ERROR adjustTreeRoot(ErrorOrSizeAwareTreePtr bestEdge, RootSynchronizer& rsync, size_t t, GBDATA *gb_main, const char *distInfo, int rt) {
    return bestEdge.hasError()
        ? bestEdge.getError()
        : adjustTreeRoot(bestEdge.getValue(), rsync, t, gb_main, distInfo, rt);
}

static void rootsync_subsetTrees_vs_selected(AW_window *aws, GBDATA *gb_main, AW_selection *tosync_trees_selection) {
    StrArray tosync_tree;
    tosync_trees_selection->get_values(tosync_tree);

    if (tosync_tree.empty()) {
        aw_message("List of trees to synchronize is empty (left list). Nothing to do.");
    }
    else {
        AW_root    *awr           = aws->get_root();
        const char *ref_tree_name = awr->awar(AWAR_TREE_SYNCROOT_SELECTED)->read_char_pntr();

        if (strcmp(ref_tree_name, NO_TREE_SELECTED) == 0) {
            aw_message("No reference tree selected (in right list)");
        }
        else {
            arb_progress progress("Adjusting root of tree");
            progress.subtitle("Loading trees..");

            RootSynchronizer rsync;
            ARB_ERROR        error   = load_and_add_tree(gb_main, ref_tree_name, rsync); // load reference tree first -> index==0
            const int        REF_IDX = 0;

            for (int i = 0; tosync_tree[i] && !error; ++i) {
                if (strcmp(tosync_tree[i], ref_tree_name) == 0) {
                    aw_message(GBS_global_string("%s: won't synchronize (same as reference tree)", tosync_tree[i]));
                }
                else {
                    error = load_and_add_tree(gb_main, tosync_tree[i], rsync);
                }
            }

            if (!error) {
                size_t toSyncCount = rsync.get_tree_count()-1;

                if (!toSyncCount) {
                    error = "nothing to synchronize";
                }
                else {
                    arb_progress progress2(toSyncCount);

                    for (size_t t = 1; t<=toSyncCount && !error; ++t) {
                        int                     lowestDist;
                        ErrorOrSizeAwareTreePtr bestEdge = rsync.find_best_root_candidate(t, REF_IDX, lowestDist, true);
                        string                  distInfo = lowestDist ? GBS_global_string("distance: %i", lowestDist) : "perfect match";

                        error = adjustTreeRoot(bestEdge, rsync, t, gb_main, distInfo.c_str(), REF_IDX);

                        progress2.inc_and_check_user_abort(error);
                    }
                }
            }

            aw_message_if(error);
        }
    }
}

const int MULTIROOT_SEARCH_DEPTH = 1; // 2 already causes far to deep recursion

static void multiroot_sync_subsetTrees(AW_window*, GBDATA *gb_main, AW_selection *tosync_trees_selection) {
    StrArray tosync_tree;
    tosync_trees_selection->get_values(tosync_tree);

    if (tosync_tree.size()<2) {
        aw_message("Need at least two trees to synchronize (in left list).");
    }
    else {
        RootSynchronizer rsync;
        ARB_ERROR        error;

        for (int i = 0; tosync_tree[i] && !error; ++i) {
            error = load_and_add_tree(gb_main, tosync_tree[i], rsync);
        }

        if (!error) {
            error = rsync.deconstruct_all_trees(true);
        }

        if (!error) {
            ErrorOrMultirootPtr mrStart_orError = rsync.get_current_roots();
            if (mrStart_orError.hasError()) {
                error = mrStart_orError.getError();
            }
            else {
                MultirootPtr mrStart = mrStart_orError.getValue();
                aw_message(GBS_global_string("Starting at root-combination with distance %i", mrStart->distanceSum(rsync)));
            }
        }
        if (!error) {
            arb_progress progress("Multi root optimize (abort to stop early)");
            ErrorOrMultirootPtr mroot_orError = rsync.find_good_roots_for_trees(MULTIROOT_SEARCH_DEPTH, &progress);
            if (mroot_orError.hasError()) {
                error = mroot_orError.getError();
            }
            else {
                MultirootPtr mroot          = mroot_orError.getValue();
                int          overallDistSum = mroot->distanceSum(rsync);
                aw_message(GBS_global_string("Found root-combination with distance %i", overallDistSum));
                if (progress.aborted()) aw_message("[search aborted by user -> using best result so far]");

                for (size_t t = 0; t<rsync.get_tree_count() && !error; ++t) {
                    ConstSizeAwareTreePtr newRootEdge = mroot->get_node(t);
                    int                   treeDistSum = mroot->singleTreeDistanceSum(rsync, t);
                    string                distInfo    = GBS_global_string("distance to other trees: %i/%i", treeDistSum, overallDistSum);

                    error = adjustTreeRoot(newRootEdge, rsync, t, gb_main, distInfo.c_str(), -1);
                }
            }
        }

        aw_message_if(error);
    }
}

static void create_syncroot_awars(AW_root *awr) {
    awr->awar_string(AWAR_TREE_SYNCROOT_SELECTED, NO_TREE_SELECTED, AW_ROOT_DEFAULT);
}

AW_window *NT_create_syncroot_window(AW_root *awr, GBDATA *gb_main) {
    static AW_window_simple *aws = NULp;

    if (!aws) {
        create_syncroot_awars(awr);

        aws = new AW_window_simple;
        aws->init(awr, "SYNCROOT", "Adjust roots of trees");
        aws->load_xfig("syncroot.fig");

        aws->auto_space(10, 10);

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

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

        aws->at("list");
        AW_DB_selection *all_trees    = awt_create_TREE_selection_list(gb_main, aws, AWAR_TREE_SYNCROOT_SELECTED);
        AW_selection    *tosync_trees = awt_create_subset_selection_list(aws, all_trees->get_sellist(), "tosync", "add", NULp);

        aws->at("all");
        aws->callback(makeWindowCallback(multiroot_sync_subsetTrees, gb_main, tosync_trees));
        aws->create_autosize_button("SYNC_ALL_TREES", "to find common optima for all.", "a");

        aws->at("sel");
        aws->callback(makeWindowCallback(rootsync_subsetTrees_vs_selected, gb_main, tosync_trees));
        aws->create_autosize_button("SYNC_TO_ONE", "to tree selected in the right list", "r");
    }
    return aws;
}

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

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

static const char *custom_tree_name(int dir, const char *name) { return GBS_global_string("syncroot/%i/%s.tree", dir, name); }

static SizeAwareTree *loadTree(const char *treefile, GB_ERROR& error) {
    arb_assert(!error);

    char *warnings = NULp;

    TreeRoot      *root = new SizeAwareRoot;
    SizeAwareTree *tree = DOWNCAST(SizeAwareTree*, TREE_load(treefile, root, NULp, true, &warnings));

    if (!tree) {
        error = GBS_global_string("Failed to load tree '%s' (Reason: %s)", treefile, GB_await_error());
    }
    else if (warnings) {
        GB_warningf("while loading tree '%s':\n%s", treefile, warnings);
        free(warnings);
    }

    return tree;
}

static string wayFromTo_internal(const TreeNode *ancestor, const TreeNode *successor) {
    if (successor == ancestor) return "";

    const TreeNode *father      = successor->get_father();
    string          wayToFather = wayFromTo_internal(ancestor, father);

    return wayToFather+(successor->is_leftson() ? 'l' : 'r');
}
static string wayFromTo(const TreeNode *ancestor, const TreeNode *successor) {
    arb_assert(ancestor);
    arb_assert(successor);

    if (successor->is_inside(ancestor)) {
        return wayFromTo_internal(ancestor, successor);
    }
    if (ancestor->get_tree_root() != successor->get_tree_root()) {
        return "<not same tree>";
    }
    if (ancestor->is_inside(successor)) {
        return "<wrong order>";
    }

    if (ancestor->is_son_of_root()) {
        const TreeNode *brother = ancestor->get_brother();
        if (successor->is_inside(brother)) {
            return "!"+wayFromTo_internal(brother, successor);
        }
    }

    const TreeNode *root = ancestor->get_tree_root()->get_root_node();
    arb_assert(successor->get_tree_root()->get_root_node() == root);

    arb_assert(ancestor->is_inside(root));
    arb_assert(successor->is_inside(root));

    return wayFromTo_internal(root, ancestor) + "-" + wayFromTo_internal(root, successor);
}

template<class TREECONT>
int loadTreeAndAddTo(int dir, const char *name, TREECONT& container) {
    GB_ERROR       error = NULp;
    SizeAwareTree *tree  = loadTree(custom_tree_name(dir, name), error);
    TEST_EXPECT_NO_ERROR(error);
    TEST_REJECT_NULL(tree);
    return container.add(tree, name);
}

void TEST_part_node_linkage() {
    GB_ERROR error = NULp;

    TreeContainer tc;
    loadTreeAndAddTo(1, "ref", tc); // -> ../UNIT_TESTER/run/syncroot/1/ref.tree

    for (int partial = 0; partial<=1; ++partial) {
        TEST_ANNOTATE(GBS_global_string("partial=%i", partial));
        if (partial == 1) {
            loadTreeAndAddTo(1, "overlap", tc); // may be any tree that introduces additional species into namespace
        }

        ConstStrArray names;
        tc.get_species_names(names);

        SpeciesSpace      specSpace(names);
        DeconstructedTree dtree(specSpace);

        const SizeAwareTree *root = tc.get_tree(0);

        {
            TreeParts tparts(specSpace, tc);
            error = dtree.deconstruct_weighted(root, tparts.get_tree_PART(0), root->get_leaf_count(), 1.0, false, specSpace.get_allSpecies(), DMODE_ROOTSYNC);
            TEST_EXPECT_NO_ERROR(error);
        }

        dtree.start_sorted_retrieval();

        const int LEAFS = 6;
        const int PARTS = leafs_2_edges(LEAFS, UNROOTED); // expect one partition for each edge

        TEST_EXPECT_EQUAL(root->get_leaf_count(), LEAFS);
        TEST_EXPECT_EQUAL(dtree.get_part_count(), PARTS);

        const PART *rootPART = dtree.find_part(root);
        TEST_EXPECT_NULL(rootPART); // the root node is not attached to any edge -> does not define any partition

        const SizeAwareTree *leftRootSon  = root->get_leftson();
        const SizeAwareTree *rightRootSon = root->get_rightson();

        const PART *leftRootPART  = dtree.find_part(leftRootSon);
        const PART *rightRootPART = dtree.find_part(rightRootSon);

        TEST_REJECT_NULL(leftRootPART);
        TEST_REJECT_NULL(rightRootPART);
        TEST_EXPECT_EQUAL(leftRootPART, rightRootPART); // returns SAME part for both sons of root!

        using namespace PART_FWD;
        TEST_EXPECT_EQUAL(get_origin(leftRootPART), leftRootSon);  // expect reverse linkage
        TEST_EXPECT_EQUAL(get_origin(rightRootPART), leftRootSon); // reverse linkage not fully consistent at one son of root-edge

        // check correct linkage for all other nodes in tree:
        {
            std::vector<const SizeAwareTree*> toTest;
            toTest.push_back(leftRootSon->get_leftson());
            toTest.push_back(leftRootSon->get_rightson());
            toTest.push_back(rightRootSon->get_leftson());
            toTest.push_back(rightRootSon->get_rightson());

            while (!toTest.empty()) {
                const SizeAwareTree *node = toTest.back();
                toTest.pop_back();

                const PART *nodePART = dtree.find_part(node);

                TEST_REJECT_NULL(nodePART);
                TEST_EXPECT_EQUAL(get_origin(nodePART), node);

                if (!node->is_leaf()) { // push sons
                    toTest.push_back(node->get_leftson());
                    toTest.push_back(node->get_rightson());
                }
            }
        }
    }
}

inline const DeconstructedTree& EXPECT_DECONSTRUCTED(ErrorOrDeconstructedTreePtr eodtp) {
    TEST_REJECT(eodtp.hasError());
    return *eodtp.getValue();
}

void TEST_part_distance() {
    RootSynchronizer rs;

    const int tosync_idx = loadTreeAndAddTo(1, "tosync",   rs); // -> ../UNIT_TESTER/run/syncroot/1/tosync.tree
    const int ref_idx    = loadTreeAndAddTo(1, "ref",      rs); // -> ../UNIT_TESTER/run/syncroot/1/ref.tree
    const int disj_idx   = loadTreeAndAddTo(1, "disjunct", rs); // -> ../UNIT_TESTER/run/syncroot/1/disjunct.tree
    const int over_idx   = loadTreeAndAddTo(1, "overlap", rs);  // -> ../UNIT_TESTER/run/syncroot/1/overlap.tree

    TEST_EXPECT_EQUAL(tosync_idx, 0);
    TEST_EXPECT_EQUAL(ref_idx,    1);
    TEST_EXPECT_EQUAL(disj_idx,   2);
    TEST_EXPECT_EQUAL(over_idx,   3);

    rs.beginDeconstructionPhase();

    const SpeciesSpace& specSpace  = rs.get_SpeciesSpace();
    const int           SPACE_SIZE = 12;
    TEST_EXPECT_EQUAL(rs.get_species_count(), SPACE_SIZE);                            // via TreeContainer
    TEST_EXPECT_EQUAL(PART_FWD::get_members(specSpace.get_allSpecies()), SPACE_SIZE); // via SpeciesSpace

    const SizeAwareTree *tosync_root = rs.get_tree(tosync_idx);
    const SizeAwareTree *ref_root    = rs.get_tree(ref_idx);
    const SizeAwareTree *disj_root   = rs.get_tree(disj_idx);
    const SizeAwareTree *over_root   = rs.get_tree(over_idx);

    TEST_REJECT_NULL(tosync_root);
    TEST_REJECT_NULL(ref_root);
    TEST_REJECT_NULL(disj_root);
    TEST_REJECT_NULL(over_root);

    {
        const PART *tosync_wholeTree_PART = rs.get_tree_PART(tosync_idx);
        const PART *ref_wholeTree_PART    = rs.get_tree_PART(ref_idx);
        const PART *disj_wholeTree_PART   = rs.get_tree_PART(disj_idx);
        const PART *over_wholeTree_PART   = rs.get_tree_PART(over_idx);

        TEST_EXPECT_EQUAL(PART_FWD::get_members(tosync_wholeTree_PART), 6);
        TEST_EXPECT_EQUAL(PART_FWD::get_members(ref_wholeTree_PART),    6);
        TEST_EXPECT_EQUAL(PART_FWD::get_members(disj_wholeTree_PART),   6);
        TEST_EXPECT_EQUAL(PART_FWD::get_members(over_wholeTree_PART),   6);

        const int DISJUNCT_DIST = 12; // =sum of sizes of 2 trees

        const DeconstructedTree& tosync_dtree = EXPECT_DECONSTRUCTED(rs.get_DeconstructedTree(tosync_idx));
        const DeconstructedTree& disj_dtree   = EXPECT_DECONSTRUCTED(rs.get_DeconstructedTree(disj_idx));
        const DeconstructedTree& over_dtree   = EXPECT_DECONSTRUCTED(rs.get_DeconstructedTree(over_idx));
        const DeconstructedTree& ref_dtree    = EXPECT_DECONSTRUCTED(rs.get_DeconstructedTree(ref_idx));

        // test single part distances at beginning:
        {
            const SizeAwareTree *tosync_rightson      = tosync_root->get_rightson();             TEST_REJECT_NULL(tosync_rightson);
            const PART          *tosync_rightson_PART = tosync_dtree.find_part(tosync_rightson); TEST_REJECT_NULL(tosync_rightson_PART);

            // compare PART of tosync_rightson with self -> shall report no distance:
            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(tosync_rightson_PART, tosync_rightson_PART, tosync_wholeTree_PART, tosync_wholeTree_PART), 0);

            TEST_REJECT(tosync_rightson->is_leaf()); // want to descent further..

            const SizeAwareTree *tosync_grandson      = tosync_rightson->get_rightson();         TEST_REJECT_NULL(tosync_grandson);
            const PART          *tosync_grandson_PART = tosync_dtree.find_part(tosync_grandson); TEST_REJECT_NULL(tosync_grandson_PART);

            int RIGHT_GRAND_DIST = 4;
            // compare PART of tosync_rightson with tosync_grandson -> shall report some distance:
            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(tosync_rightson_PART, tosync_grandson_PART, tosync_wholeTree_PART, tosync_wholeTree_PART), RIGHT_GRAND_DIST);

            // test distance does not depend on direction:
            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(tosync_grandson_PART, tosync_rightson_PART, tosync_wholeTree_PART, tosync_wholeTree_PART), RIGHT_GRAND_DIST);

            {
                // this subtree changes the partition side (between tosync_rightson_PART and tosync_grandson_PART):
                const SizeAwareTree *tosync_othergrandson = tosync_grandson->get_brother(); TEST_REJECT_NULL(tosync_othergrandson);
                TEST_EXPECT_EQUAL(tosync_othergrandson->get_leaf_count(), RIGHT_GRAND_DIST); // the subtree size is the same as the calculated distance between these PARTS. seems reasonable! :)
            }


            // test distance to edges from disjunct tree (distance should always be same):
            const SizeAwareTree *disj_leftson  = disj_root->get_leftson ();                TEST_REJECT_NULL(disj_leftson);
            const SizeAwareTree *disj_grandson = disj_root->get_rightson()->get_leftson(); TEST_REJECT_NULL(disj_grandson);

            const PART *disj_leftson_PART  = disj_dtree.find_part(disj_leftson);  TEST_REJECT_NULL(disj_leftson_PART);
            const PART *disj_grandson_PART = disj_dtree.find_part(disj_grandson); TEST_REJECT_NULL(disj_grandson_PART);

            // distance between edges of disjunct trees is the same (for any edge):
            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(tosync_grandson_PART, disj_leftson_PART, tosync_wholeTree_PART, disj_wholeTree_PART), DISJUNCT_DIST);
            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(tosync_grandson_PART, disj_grandson_PART, tosync_wholeTree_PART, disj_wholeTree_PART), DISJUNCT_DIST);

            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(disj_leftson_PART, disj_grandson_PART, disj_wholeTree_PART, disj_wholeTree_PART), 2); // shows that different edges (used from tree 'disjunct') actually differ


            // test distance between partly overlapping trees:
            const SizeAwareTree *over_leftson      = over_root->get_leftson();           TEST_REJECT_NULL(over_leftson);
            const PART          *over_leftson_PART = over_dtree.find_part(over_leftson); TEST_REJECT_NULL(over_leftson_PART);

            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(over_leftson_PART, tosync_grandson_PART, over_wholeTree_PART, tosync_wholeTree_PART), 6); // no distance in overlapping region -> only counts disjunct parts

            const SizeAwareTree *over_somenode      = over_leftson->get_leftson();              TEST_REJECT_NULL(over_somenode);
            const PART          *over_somenode_PART = over_dtree.find_part    (over_somenode); TEST_REJECT_NULL(over_somenode_PART);

            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(over_somenode_PART, tosync_grandson_PART, over_wholeTree_PART, tosync_wholeTree_PART), 8);
        }

        // The trees 'ref' and 'tosync' have same topology - only root position differs.
        // => each branch in one tree should perfectly match another branch in other tree.

        bool reverseSearchFound_identicalIndex = false;
        bool reverseSearchFound_duplicateIndex = false;
        bool selfSearchFound_identicalIndex    = false;
        bool selfSearchFound_duplicateIndex    = false;

        for (size_t pr = 0; pr<ref_dtree.get_part_count(); ++pr) {
            const PART *ref_PART = ref_dtree.peek_part(pr);
            TEST_REJECT_NULL(ref_PART);

            if (!represents_existing_edge(ref_PART)) continue;

            int best_dist;
            int best_idx;

            RootSynchronizer::find_best_matching_PART_in(best_dist, best_idx, ref_PART, tosync_dtree, ref_wholeTree_PART, tosync_wholeTree_PART, false);

            TEST_REJECT(best_idx == -1);     // expect some PART is "best match"
            TEST_EXPECT_EQUAL(best_dist, 0); // should find a perfect match for each branch!

            // perform reverse search
            {
                const PART *tosync_PART = tosync_dtree.peek_part(best_idx);
                TEST_REJECT_NULL(tosync_PART);

                arb_assert(represents_existing_edge(tosync_PART));

                RootSynchronizer::find_best_matching_PART_in(best_dist, best_idx, tosync_PART, ref_dtree, tosync_wholeTree_PART, ref_wholeTree_PART, false);

                TEST_REJECT(best_idx == -1);     // expect some PART is "best match"
                TEST_EXPECT_EQUAL(best_dist, 0); // should find a perfect match for each branch!

                // expect reverse search matches original PART:
                TEST_EXPECT_EQUAL(PART_FWD::get_origin(ref_dtree.peek_part(best_idx)), PART_FWD::get_origin(ref_PART));
                TEST_EXPECT_EQUAL(ref_dtree.peek_part(best_idx), ref_PART);
                TEST_EXPECT_EQUAL(best_idx, pr);
                if (size_t(best_idx) == pr) reverseSearchFound_identicalIndex = true;
                else                        reverseSearchFound_duplicateIndex = true;
            }

            // search self:
            RootSynchronizer::find_best_matching_PART_in(best_dist, best_idx, ref_PART, ref_dtree, ref_wholeTree_PART, ref_wholeTree_PART, false);

            // each PART should perfectly match to itself:
            TEST_EXPECT_EQUAL(PART_FWD::get_origin(ref_dtree.peek_part(best_idx)), PART_FWD::get_origin(ref_PART));
            TEST_EXPECT_EQUAL(ref_dtree.peek_part(best_idx), ref_PART); // each PART should perfectly match to itself
            TEST_EXPECT_EQUAL(best_idx, pr);
            if (size_t(best_idx) == pr) selfSearchFound_identicalIndex = true;
            else                        selfSearchFound_duplicateIndex = true;
        }

        TEST_EXPECT(reverseSearchFound_identicalIndex);
        TEST_REJECT(reverseSearchFound_duplicateIndex);
        TEST_EXPECT(selfSearchFound_identicalIndex);
        TEST_REJECT(selfSearchFound_duplicateIndex);

        // compare PARTs of disjunct trees:
        //  - all distances are expected to be the same ("comparing apples and oranges")

        for (size_t pd = 0; pd<disj_dtree.get_part_count(); ++pd) {
            const PART *disj_PART = disj_dtree.peek_part(pd);
            TEST_REJECT_NULL(disj_PART);

            if (!represents_existing_edge(disj_PART)) continue;

            for (size_t pr = 0; pr<ref_dtree.get_part_count(); ++pr) {
                const PART *ref_PART = ref_dtree.peek_part(pr);
                TEST_REJECT_NULL(ref_PART);

                if (!represents_existing_edge(ref_PART)) continue;

                TEST_EXPECT_EQUAL(PART_FWD::calcDistance(ref_PART, disj_PART, ref_wholeTree_PART, disj_wholeTree_PART), DISJUNCT_DIST);
            }
        }

        // compare PARTs of overlap tree with other trees:
        for (size_t po = 0; po<over_dtree.get_part_count(); ++po) {
            const PART *over_PART = over_dtree.peek_part(po);
            TEST_REJECT_NULL(over_PART);

            if (!represents_existing_edge(over_PART)) continue;

            int best_dist, best_idx;
            int worst_dist, worst_idx;

            // compare with tosync:
            RootSynchronizer::find_best_matching_PART_in(best_dist, best_idx, over_PART, tosync_dtree, over_wholeTree_PART, tosync_wholeTree_PART, false);
            TEST_REJECT(best_idx == -1);     // expect some PART is "best match"
            TEST_EXPECT_EQUAL(best_dist, 6); // 6 = perfect match in overlap + 2*3 not overlapping parts

            RootSynchronizer::find_worst_matching_PART_in(worst_dist, worst_idx, over_PART, tosync_dtree, over_wholeTree_PART, tosync_wholeTree_PART);
            TEST_REJECT(worst_idx == -1);     // expect some PART is "worst match"
            TEST_EXPECT_EQUAL(worst_dist, 8); // 8 = worst match in overlap (=2) + 2*3 not overlapping parts; 3 diffs in overlap not possible (would use inverse)

            // compare with disjunct:
            RootSynchronizer::find_best_matching_PART_in(best_dist, best_idx, over_PART, disj_dtree, over_wholeTree_PART, disj_wholeTree_PART, false);
            TEST_REJECT(best_idx == -1);     // expect some PART is "best match"
            TEST_EXPECT_EQUAL(best_dist, 6); // see above

            RootSynchronizer::find_worst_matching_PART_in(worst_dist, worst_idx, over_PART, disj_dtree, over_wholeTree_PART, disj_wholeTree_PART);
            TEST_REJECT(worst_idx == -1);     // expect some PART is "worst match"
            TEST_EXPECT_EQUAL(worst_dist, 8); // see above
        }
    }
}

const int DEPTH = 0; // 0 means: perform 1 move per tree only

void TEST_RootSynchronizer() {
    RootSynchronizer rsync1;

    int tosync_idx = loadTreeAndAddTo(1, "tosync", rsync1); // -> ../UNIT_TESTER/run/syncroot/1/tosync.tree
    int ref_idx    = loadTreeAndAddTo(1, "ref",    rsync1); // -> ../UNIT_TESTER/run/syncroot/1/ref.tree

    ConstSizeAwareTreePtr newRoot = NULp;
    int                   foundDist;

    // access invalid idx => test error is reported:
    {
        ErrorOrSizeAwareTreePtr erc = rsync1.find_best_root_candidate(tosync_idx, 7, foundDist, false);
        TEST_EXPECT(erc.hasError());
        TEST_EXPECT_CONTAINS(erc.getError().deliver(), "invalid tree index 7");
    }

    // test finding best candidate for root in 'tosync':
    {
        ErrorOrSizeAwareTreePtr erc1 = rsync1.find_best_root_candidate(tosync_idx, ref_idx, foundDist, false);
        TEST_REJECT(erc1.hasError());

        newRoot = erc1.getValue();
        TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(tosync_idx), newRoot), "rlr");
        TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(ref_idx), newRoot), "<not same tree>"); // (newRoot is not member of 'ref')

        TEST_EXPECT_EQUAL(foundDist, 0); // =exact match

        TEST_EXPECT_EQUAL(rsync1.calcTreeDistance(ref_idx, tosync_idx), 0);
        TEST_EXPECT_EQUAL(rsync1.minDistanceSum(), 0);
    }

    // test opposite detection:
    {
        ErrorOrSizeAwareTreePtr erc2 = rsync1.find_best_root_candidate(ref_idx, tosync_idx, foundDist, false);
        TEST_REJECT(erc2.hasError());

        ConstSizeAwareTreePtr newRoot2 = erc2.getValue();
        TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(tosync_idx), newRoot2), "<not same tree>"); // (newRoot2 is not member of 'tosync')
        TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(ref_idx), newRoot2), "rrl");

        TEST_EXPECT_EQUAL(foundDist, 0); // =exact match
    }

    // test basics of synchronizing multiple roots:
    {
        ErrorOrMultirootPtr emr0 = rsync1.get_current_roots();
        TEST_REJECT(emr0.hasError());

        MultirootPtr mr0 = emr0.getValue();
        TEST_EXPECT(mr0.isSet());
        TEST_EXPECT_EQUAL(mr0->size(), 2);

        // access nodes:
        {
            ConstSizeAwareTreePtr r1 = mr0->get_node(0);
            TEST_REJECT_NULL(r1.plain_pointer());

            ConstSizeAwareTreePtr r2 = mr0->get_node(1);
            TEST_REJECT_NULL(r2.plain_pointer());

            ConstSizeAwareTreePtr r3 = mr0->get_node(2); // should not exist
            TEST_EXPECT_NULL(r3.plain_pointer());
        }

        const int distSum0    = mr0->distanceSum(rsync1);
        const int distCenter0 = mr0->distanceToCenterSum(rsync1);
        TEST_EXPECT_EQUAL(distSum0, 4);
        TEST_EXPECT_EQUAL(distCenter0, 2);

        {
            MultirootPtr mr2 = new Multiroot(*mr0); // clone ..
            TEST_EXPECT_EQUAL(mr2->distanceSum(rsync1), distSum0); // .. reports same distance as original ..
            TEST_EXPECT_EQUAL(mr2->distanceToCenterSum(rsync1), distCenter0); // .. and same distance to center

            const int idx = 1;

            // replacing a node with its son should (normally) change distance and center-distance:
            ConstSizeAwareTreePtr node    = mr2->get_node(idx);
            ConstSizeAwareTreePtr newNode = node->get_rightson();
            arb_assert(newNode);
            mr2->replace_node(idx, newNode);

            {
                int distSum2    = mr2->distanceSum(rsync1);
                int distCenter2 = mr2->distanceToCenterSum(rsync1);

                TEST_EXPECT_DIFFERENT(distSum2,    distSum0);    TEST_EXPECT_EQUAL(distSum2,    6);
                TEST_EXPECT_DIFFERENT(distCenter2, distCenter0); TEST_EXPECT_EQUAL(distCenter2, 3);
            }

            newNode = node->get_leftson();
            arb_assert(newNode);
            mr2->replace_node(idx, newNode);

            {
                int distSum2    = mr2->distanceSum(rsync1);
                int distCenter2 = mr2->distanceToCenterSum(rsync1);

                TEST_EXPECT_EQUAL(distSum2, distSum0);           // no difference for leftson (not normal, but obviously possible. assuming its a special case)
                TEST_EXPECT_DIFFERENT(distCenter2, distCenter0); // nevertheless we got different distance to center
                TEST_EXPECT_EQUAL(distCenter2, 4);
            }
        }

        // find optimal roots for all trees:
        {
            ErrorOrMultirootPtr emr1 = rsync1.find_good_roots_for_trees(DEPTH);
            TEST_REJECT(emr1.hasError());

            MultirootPtr mr1 = emr1.getValue();
            TEST_EXPECT(mr1.isSet());
            TEST_EXPECT_EQUAL(mr1->size(), 2);

            TEST_EXPECT_EQUAL(mr1->distanceSum(rsync1), 0);
            TEST_EXPECT_EQUAL(mr1->distanceToCenterSum(rsync1), 0);

            // test positions of resulting root-nodes in original trees (shows how roots will move):
            TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(ref_idx),    mr1->get_node(ref_idx)),    "l");
            TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(tosync_idx), mr1->get_node(tosync_idx)), "rlr");
        }
    }

    {
        // test releasing a tree:
        SizeAwareTree *tosync_released = rsync1.take_tree(tosync_idx);

        // attempt to use a "released tree" should fail:
        {
            ErrorOrSizeAwareTreePtr erc2 = rsync1.find_best_root_candidate(tosync_idx, ref_idx, foundDist, false);
            TEST_EXPECT(erc2.hasError());
            TEST_EXPECT_ERROR_CONTAINS(erc2.getError(), "tree at index #0 vanished");

            TEST_EXPECT_EQUAL(foundDist, INT_MAX); // =no match
        }

        // change root of 'tosync_released' to 'newRoot':
        {
            arb_assert(newRoot->is_inside(tosync_released));                   // when newRoot is member of tosync_released ..
            SizeAwareTree *newRoot_nc = const_cast<SizeAwareTree*>(&*newRoot); // .. casting away const is ok (because we own the tree atm)

            arb_assert(newRoot_nc != tosync_released);
            arb_assert(tosync_released->is_root_node());
            newRoot_nc->set_root(); // set new root
            arb_assert(tosync_released->is_root_node()); // virtual root node remains valid (it is moved to new root)
        }
        {
            // create new RootSynchronizer and add tree with changed root:
            RootSynchronizer rsync2;
            tosync_idx = rsync2.add(tosync_released, "tosync");

            // also move "ref" tree from 'rsync1' -> 'rsync2':
            {
                SizeAwareTree *ref_released = rsync1.take_tree(ref_idx);
                ref_idx = rsync2.add(ref_released, "ref");
            }

            // test find_best_root_candidate with these trees (root should be same -> should report son-of-root as best match)
            {
                int tr_dist, rt_dist;
                ErrorOrSizeAwareTreePtr tosync_erc = rsync2.find_best_root_candidate(tosync_idx, ref_idx, tr_dist, false);
                ErrorOrSizeAwareTreePtr ref_erc    = rsync2.find_best_root_candidate(ref_idx, tosync_idx, rt_dist, false);

                TEST_REJECT(tosync_erc.hasError());
                TEST_REJECT(ref_erc.hasError());

                TEST_EXPECT_EQUAL(rsync2.calcTreeDistance(ref_idx, tosync_idx), 0);
                TEST_EXPECT_EQUAL(rsync2.minDistanceSum(), 0);

                TEST_EXPECT_EQUAL(tr_dist, 0); // =exact match
                TEST_EXPECT_EQUAL(rt_dist, 0); // =exact match

                ConstSizeAwareTreePtr tosync_rc = tosync_erc.getValue();
                ConstSizeAwareTreePtr ref_rc    = ref_erc.getValue();

                TEST_EXPECT(tosync_rc->is_son_of_root());
                TEST_EXPECT(ref_rc->is_son_of_root());

                TEST_EXPECT_EQUAL(wayFromTo(rsync2.get_tree(tosync_idx), tosync_rc), "l");
                TEST_EXPECT_EQUAL(wayFromTo(rsync2.get_tree(ref_idx),    ref_rc),    "l");
            }
        }
    }

    // test some error cases:
    {
        RootSynchronizer rsync3;
        loadTreeAndAddTo(1, "tosync", rsync3); // -> ../UNIT_TESTER/run/syncroot/1/tosync.tree

        ErrorOrMultirootPtr emr2 = rsync3.find_good_roots_for_trees(DEPTH);
        TEST_EXPECT(emr2.hasError());
        TEST_EXPECT_ERROR_CONTAINS(emr2.getError().deliver(), "Need at least two trees");
    }
}

void TEST_sync_more_trees() {
    {
        RootSynchronizer rsync;

        const int ref_idx      = loadTreeAndAddTo(1, "ref",      rsync); // -> ../UNIT_TESTER/run/syncroot/1/ref.tree
        const int disjunct_idx = loadTreeAndAddTo(1, "disjunct", rsync); // -> ../UNIT_TESTER/run/syncroot/1/disjunct.tree

        ErrorOrMultirootPtr startOrErr  = rsync.get_current_roots();              TEST_REJECT(startOrErr.hasError());
        ErrorOrMultirootPtr syncedOrErr = rsync.find_good_roots_for_trees(DEPTH); TEST_REJECT(syncedOrErr.hasError());

        MultirootPtr innermost = rsync.get_innermost_edges(); TEST_REJECT(innermost.isNull());
        MultirootPtr start     = startOrErr.getValue ();      TEST_REJECT(start.isNull());
        MultirootPtr synced    = syncedOrErr.getValue();      TEST_REJECT(synced.isNull());

        // Note: find_good_roots_for_trees keeps status quo here (did not find better root-combination for disjunct trees):
        const int DISTSUM = 12;
        TEST_EXPECT_EQUAL(start->distanceSum (rsync), DISTSUM);
        TEST_EXPECT_EQUAL(synced->distanceSum(rsync), DISTSUM);
        TEST_EXPECT_EQUAL(start->distanceToCenterSum (rsync), 8);
        TEST_EXPECT_EQUAL(synced->distanceToCenterSum(rsync), 5);    // synced roots are nearer to center (of species set).
        TEST_EXPECT_EQUAL(innermost->distanceToCenterSum(rsync), 5); // [did not understand that value]

        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(ref_idx, disjunct_idx), DISTSUM);
        TEST_EXPECT_EQUAL(rsync.minDistanceSum(), DISTSUM);

        // compare 'start' with 'synced' (did nodes change?):
        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(ref_idx),      synced->get_node(ref_idx)),      "");   // node of ref-tree was not really modified
        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(disjunct_idx), synced->get_node(disjunct_idx)), "!l"); // node of disjunct-tree now slightly modified (acceptable)
    }

    // test 3 trees:
    {
        RootSynchronizer rsync;

        const int tosync_idx   = loadTreeAndAddTo(1, "tosync",    rsync); // -> ../UNIT_TESTER/run/syncroot/1/tosync.tree
        const int disjunct_idx = loadTreeAndAddTo(1, "disjunct",  rsync); // -> ../UNIT_TESTER/run/syncroot/1/disjunct.tree
        const int overa_idx    = loadTreeAndAddTo(1, "overlap_A", rsync); // -> ../UNIT_TESTER/run/syncroot/1/overlap_A.tree

        ErrorOrMultirootPtr startOrErr  = rsync.get_current_roots();          TEST_REJECT(startOrErr.hasError());
        ErrorOrMultirootPtr syncedOrErr = rsync.find_good_roots_for_trees(1); TEST_REJECT(syncedOrErr.hasError()); // need depth higher than 0 to reach optimum here

        MultirootPtr innermost = rsync.get_innermost_edges(); TEST_REJECT(innermost.isNull());
        MultirootPtr start     = startOrErr.getValue();       TEST_REJECT(start.isNull());
        MultirootPtr synced    = syncedOrErr.getValue();      TEST_REJECT(synced.isNull());

        const int OPTIMAL_DIST = 24;

        TEST_EXPECT_EQUAL(start->distanceSum (rsync), 28);
        TEST_EXPECT_EQUAL(synced->distanceSum(rsync), OPTIMAL_DIST); // 24 is possible (and wanted) optimum for these 3 trees (12 between disjunct+tosync; 6 between the other 2 pairings)
        TEST_EXPECT_EQUAL(start->distanceToCenterSum (rsync), 15);
        TEST_EXPECT_EQUAL(synced->distanceToCenterSum(rsync), 8);
        TEST_EXPECT_EQUAL(innermost->distanceToCenterSum(rsync), 6); // [did not understand that value]

        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(tosync_idx, disjunct_idx), 12);
        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(overa_idx,  disjunct_idx), 6);
        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(overa_idx,  tosync_idx),   6);
        TEST_EXPECT_EQUAL(rsync.minDistanceSum(), OPTIMAL_DIST);

        // compare 'start' with 'synced' (did nodes change?):
        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(tosync_idx),   synced->get_node(tosync_idx)),   "!l"); // '!' indicates: start node at one son of root + resulting node inside other son
        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(disjunct_idx), synced->get_node(disjunct_idx)), "!l");
        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(overa_idx),    synced->get_node(overa_idx)),    "!lrr");
    }

    // test 4 trees:
    {
        RootSynchronizer rsync;

        const int tosync_idx = loadTreeAndAddTo(1, "tosync",    rsync); // -> ../UNIT_TESTER/run/syncroot/1/tosync.tree
        const int ref_idx    = loadTreeAndAddTo(1, "ref",       rsync); // -> ../UNIT_TESTER/run/syncroot/1/ref.tree
        const int over_idx   = loadTreeAndAddTo(1, "overlap",   rsync); // -> ../UNIT_TESTER/run/syncroot/1/overlap.tree
        const int overa_idx  = loadTreeAndAddTo(1, "overlap_A", rsync); // -> ../UNIT_TESTER/run/syncroot/1/overlap_A.tree

        ErrorOrMultirootPtr startOrErr  = rsync.get_current_roots();              TEST_REJECT(startOrErr.hasError());
        ErrorOrMultirootPtr syncedOrErr = rsync.find_good_roots_for_trees(DEPTH); TEST_REJECT(syncedOrErr.hasError());

        MultirootPtr innermost = rsync.get_innermost_edges(); TEST_REJECT(innermost.isNull());
        MultirootPtr start     = startOrErr.getValue ();      TEST_REJECT(start.isNull());
        MultirootPtr synced    = syncedOrErr.getValue();      TEST_REJECT(synced.isNull());

        const int OPTIMAL_DIST = 24;

        TEST_EXPECT_EQUAL(start->distanceSum (rsync), 36);
        TEST_EXPECT_EQUAL(synced->distanceSum(rsync), OPTIMAL_DIST); // 24 is possible optimum for these 4 trees (0 between tosync+ref and overlap+overlap_A; 6 between any of the other 4 pairings)
        TEST_EXPECT_EQUAL(start->distanceToCenterSum (rsync), 9);
        TEST_EXPECT_EQUAL(synced->distanceToCenterSum(rsync), 5);    // center distance now gets reduced.
        TEST_EXPECT_EQUAL(innermost->distanceToCenterSum(rsync), 3); // [did not understand that value]

        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(tosync_idx, ref_idx),   0);
        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(tosync_idx, over_idx),  6);
        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(tosync_idx, overa_idx), 6);
        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(ref_idx,    over_idx),  6);
        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(ref_idx,    overa_idx), 6);
        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(over_idx,   overa_idx), 0);
        TEST_EXPECT_EQUAL(rsync.minDistanceSum(), OPTIMAL_DIST);

        // compare 'start' with 'synced' (did nodes change?):
        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(tosync_idx),   synced->get_node(tosync_idx)),   "!lr"); // '!' indicates: start node at one son of root + resulting node inside other son
        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(ref_idx),      synced->get_node(ref_idx)),      "");
        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(over_idx),     synced->get_node(over_idx)),     "");
        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(overa_idx),    synced->get_node(overa_idx)),    "!lr");
    }
}

#endif // UNIT_TESTS

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