source: trunk/NTREE/NT_syncroot.cxx

Last change on this file was 19536, checked in by westram, 5 days ago
  • mark test as "slow" (to avoid warnings).
  • fix warning introduced with 'track-ali-changes'.
File size: 42.5 KB
Line 
1// ========================================================= //
2//                                                           //
3//   File      : NT_syncroot.cxx                             //
4//   Purpose   : GUI + tests for root synchronization        //
5//                                                           //
6//   Coded by Ralf Westram (coder@reallysoft.de) in May 20   //
7//   http://www.arb-home.de/                                 //
8//                                                           //
9// ========================================================= //
10
11#include <SyncRoot.hxx>
12#include <TreeRead.h>
13
14#include <aw_window.hxx>
15#include <aw_msg.hxx>
16#include <aw_root.hxx>
17#include <aw_select.hxx>
18#include <aw_awar.hxx>
19#include <awt_sel_boxes.hxx>
20
21#include <arb_global_defs.h>
22
23using namespace std;
24
25#define TREE_SYNCROOT_AWAR_BASE     "tree/syncroot/"
26#define TREE_SYNCROOT_TEMP_BASE     "tmp/" TREE_SYNCROOT_AWAR_BASE
27#define AWAR_TREE_SYNCROOT_SELECTED TREE_SYNCROOT_TEMP_BASE "selected"
28
29static GB_ERROR load_and_add_tree(GBDATA *gb_main, const char *treename, RootSynchronizer& addTo) {
30    GB_transaction  ta(gb_main);
31    SizeAwareTree  *satree = DOWNCAST(SizeAwareTree*, GBT_read_tree(gb_main, treename, new SizeAwareRoot));
32    GB_ERROR        error  = NULp;
33    if (!satree) {
34        error = GB_await_error();
35    }
36    else {
37        addTo.add(satree, treename);
38    }
39    return error;
40}
41
42static ARB_ERROR adjustTreeRoot(ConstSizeAwareTreePtr newRootEdge, RootSynchronizer& rsync, size_t t, GBDATA *gb_main, const char *distInfo, int rt) {
43    /*! save tree to DB (if 'bestEdge' not already is the root edge).
44     * logs into tree comment + prints info message to gui.
45     *
46     * @param newRootEdge son node of edge wanted as root edge.
47     * @param rsync synchronizer used to find 'bestEdge'.
48     * @param t index of tree in 'rsync' (tree has to contain 'bestEdge')
49     * @param gb_main the database
50     * @param distInfo information about distance. gets added to message and/or log entries.
51     * @param rt index of reference tree (or -1 when multiroot optimization is performed)
52     * @return error
53     */
54
55    ARB_ERROR        error;
56    SizeAwareTree   *resultTree = rsync.take_tree(t); // retrieve tree from RootSynchronizer (takes ownership!)
57    const TreeInfo&  treeInfo   = rsync.get_tree_info(t);
58
59    arb_assert(newRootEdge->is_inside(resultTree));
60    if (newRootEdge->is_son_of_root()) { // -> do NOT set root (just drop a note)
61        const char *what = rt<0 ? "best found" : "optimal";
62        aw_message(GBS_global_string("%s: root already at %s position (%s)", treeInfo.name(), what, distInfo));
63    }
64    else {
65        SizeAwareTree *newRootEdge_nc = const_cast<SizeAwareTree*>(&*newRootEdge); // safe ('resultTree' is owned)
66        newRootEdge_nc->set_root();                                                // set root to 'edge'
67
68        aw_message(GBS_global_string("%s: set root (%s)", treeInfo.name(), distInfo));
69
70        // store tree in DB:
71        {
72            GB_transaction  ta(gb_main);
73            GBDATA         *gb_tree = GBT_find_tree(gb_main, treeInfo.name());
74            if (!gb_tree) {
75                error = GBS_global_string("no such tree '%s' - cannot overwrite", treeInfo.name());
76            }
77            else {
78                error = GBT_overwrite_tree(gb_tree, resultTree);
79                if (!error) {
80                    string entry;
81                    if (rt<0) { // multiroot optimization
82                        entry = GBS_global_string("Multiroot optimization (%s)", distInfo);
83                    }
84                    else { // sync vs ref tree
85                        entry = GBS_global_string("Adjusted root versus '%s' (%s)", rsync.get_tree_info(rt).name(), distInfo);
86                    }
87                    error = GBT_log_to_tree_remark(gb_tree, entry.c_str(), true);
88                }
89            }
90            error = ta.close(error);
91        }
92    }
93
94    return error;
95}
96static ARB_ERROR adjustTreeRoot(ErrorOrSizeAwareTreePtr bestEdge, RootSynchronizer& rsync, size_t t, GBDATA *gb_main, const char *distInfo, int rt) {
97    return bestEdge.hasError()
98        ? bestEdge.getError()
99        : adjustTreeRoot(bestEdge.getValue(), rsync, t, gb_main, distInfo, rt);
100}
101
102static void rootsync_subsetTrees_vs_selected(AW_window *aws, GBDATA *gb_main, AW_selection *tosync_trees_selection) {
103    StrArray tosync_tree;
104    tosync_trees_selection->get_values(tosync_tree);
105
106    if (tosync_tree.empty()) {
107        aw_message("List of trees to synchronize is empty (left list). Nothing to do.");
108    }
109    else {
110        AW_root    *awr           = aws->get_root();
111        const char *ref_tree_name = awr->awar(AWAR_TREE_SYNCROOT_SELECTED)->read_char_pntr();
112
113        if (strcmp(ref_tree_name, NO_TREE_SELECTED) == 0) {
114            aw_message("No reference tree selected (in right list)");
115        }
116        else {
117            arb_progress progress("Adjusting root of tree");
118            progress.subtitle("Loading trees..");
119
120            RootSynchronizer rsync;
121            ARB_ERROR        error   = load_and_add_tree(gb_main, ref_tree_name, rsync); // load reference tree first -> index==0
122            const int        REF_IDX = 0;
123
124            for (int i = 0; tosync_tree[i] && !error; ++i) {
125                if (strcmp(tosync_tree[i], ref_tree_name) == 0) {
126                    aw_message(GBS_global_string("%s: won't synchronize (same as reference tree)", tosync_tree[i]));
127                }
128                else {
129                    error = load_and_add_tree(gb_main, tosync_tree[i], rsync);
130                }
131            }
132
133            if (!error) {
134                size_t toSyncCount = rsync.get_tree_count()-1;
135
136                if (!toSyncCount) {
137                    error = "nothing to synchronize";
138                }
139                else {
140                    arb_progress progress2(toSyncCount);
141
142                    for (size_t t = 1; t<=toSyncCount && !error; ++t) {
143                        int                     lowestDist;
144                        ErrorOrSizeAwareTreePtr bestEdge = rsync.find_best_root_candidate(t, REF_IDX, lowestDist, true);
145                        string                  distInfo = lowestDist ? GBS_global_string("distance: %i", lowestDist) : "perfect match";
146
147                        error = adjustTreeRoot(bestEdge, rsync, t, gb_main, distInfo.c_str(), REF_IDX);
148
149                        progress2.inc_and_check_user_abort(error);
150                    }
151                }
152            }
153
154            aw_message_if(error);
155        }
156    }
157}
158
159const int MULTIROOT_SEARCH_DEPTH = 1; // 2 already causes far to deep recursion
160
161static void multiroot_sync_subsetTrees(AW_window*, GBDATA *gb_main, AW_selection *tosync_trees_selection) {
162    StrArray tosync_tree;
163    tosync_trees_selection->get_values(tosync_tree);
164
165    if (tosync_tree.size()<2) {
166        aw_message("Need at least two trees to synchronize (in left list).");
167    }
168    else {
169        RootSynchronizer rsync;
170        ARB_ERROR        error;
171
172        for (int i = 0; tosync_tree[i] && !error; ++i) {
173            error = load_and_add_tree(gb_main, tosync_tree[i], rsync);
174        }
175
176        if (!error) {
177            error = rsync.deconstruct_all_trees(true);
178        }
179
180        if (!error) {
181            ErrorOrMultirootPtr mrStart_orError = rsync.get_current_roots();
182            if (mrStart_orError.hasError()) {
183                error = mrStart_orError.getError();
184            }
185            else {
186                MultirootPtr mrStart = mrStart_orError.getValue();
187                aw_message(GBS_global_string("Starting at root-combination with distance %i", mrStart->distanceSum(rsync)));
188            }
189        }
190        if (!error) {
191            arb_progress progress("Multi root optimize (abort to stop early)");
192            ErrorOrMultirootPtr mroot_orError = rsync.find_good_roots_for_trees(MULTIROOT_SEARCH_DEPTH, &progress);
193            if (mroot_orError.hasError()) {
194                error = mroot_orError.getError();
195            }
196            else {
197                MultirootPtr mroot          = mroot_orError.getValue();
198                int          overallDistSum = mroot->distanceSum(rsync);
199                aw_message(GBS_global_string("Found root-combination with distance %i", overallDistSum));
200                if (progress.aborted()) aw_message("[search aborted by user -> using best result so far]");
201
202                for (size_t t = 0; t<rsync.get_tree_count() && !error; ++t) {
203                    ConstSizeAwareTreePtr newRootEdge = mroot->get_node(t);
204                    int                   treeDistSum = mroot->singleTreeDistanceSum(rsync, t);
205                    string                distInfo    = GBS_global_string("distance to other trees: %i/%i", treeDistSum, overallDistSum);
206
207                    error = adjustTreeRoot(newRootEdge, rsync, t, gb_main, distInfo.c_str(), -1);
208                }
209            }
210        }
211
212        aw_message_if(error);
213    }
214}
215
216static void create_syncroot_awars(AW_root *awr) {
217    awr->awar_string(AWAR_TREE_SYNCROOT_SELECTED, NO_TREE_SELECTED, AW_ROOT_DEFAULT);
218}
219
220AW_window *NT_create_syncroot_window(AW_root *awr, GBDATA *gb_main) {
221    static AW_window_simple *aws = NULp;
222
223    if (!aws) {
224        create_syncroot_awars(awr);
225
226        aws = new AW_window_simple;
227        aws->init(awr, "SYNCROOT", "Adjust roots of trees");
228        aws->load_xfig("syncroot.fig");
229
230        aws->auto_space(10, 10);
231
232        aws->callback(AW_POPDOWN);
233        aws->at("close");
234        aws->create_button("CLOSE", "CLOSE", "C");
235
236        aws->callback(makeHelpCallback("syncroots.hlp"));
237        aws->at("help");
238        aws->create_button("HELP", "HELP", "H");
239
240        aws->at("list");
241        AW_DB_selection *all_trees    = awt_create_TREE_selection_list(gb_main, aws, AWAR_TREE_SYNCROOT_SELECTED);
242        AW_selection    *tosync_trees = awt_create_subset_selection_list(aws, all_trees->get_sellist(), "tosync", "add", NULp);
243
244        aws->at("all");
245        aws->callback(makeWindowCallback(multiroot_sync_subsetTrees, gb_main, tosync_trees));
246        aws->create_autosize_button("SYNC_ALL_TREES", "to find common optima for all.", "a");
247
248        aws->at("sel");
249        aws->callback(makeWindowCallback(rootsync_subsetTrees_vs_selected, gb_main, tosync_trees));
250        aws->create_autosize_button("SYNC_TO_ONE", "to tree selected in the right list", "r");
251    }
252    return aws;
253}
254
255// --------------------------------------------------------------------------------
256
257#ifdef UNIT_TESTS
258#ifndef TEST_UNIT_H
259#include <test_unit.h>
260#endif
261
262static const char *custom_tree_name(int dir, const char *name) { return GBS_global_string("syncroot/%i/%s.tree", dir, name); }
263
264static SizeAwareTree *loadTree(const char *treefile, GB_ERROR& error) {
265    arb_assert(!error);
266
267    char *warnings = NULp;
268
269    TreeRoot      *root = new SizeAwareRoot;
270    SizeAwareTree *tree = DOWNCAST(SizeAwareTree*, TREE_load(treefile, root, NULp, true, &warnings));
271
272    if (!tree) {
273        error = GBS_global_string("Failed to load tree '%s' (Reason: %s)", treefile, GB_await_error());
274    }
275    else if (warnings) {
276        GB_warningf("while loading tree '%s':\n%s", treefile, warnings);
277        free(warnings);
278    }
279
280    return tree;
281}
282
283static string wayFromTo_internal(const TreeNode *ancestor, const TreeNode *successor) {
284    if (successor == ancestor) return "";
285
286    const TreeNode *father      = successor->get_father();
287    string          wayToFather = wayFromTo_internal(ancestor, father);
288
289    return wayToFather+(successor->is_leftson() ? 'l' : 'r');
290}
291static string wayFromTo(const TreeNode *ancestor, const TreeNode *successor) {
292    arb_assert(ancestor);
293    arb_assert(successor);
294
295    if (successor->is_inside(ancestor)) {
296        return wayFromTo_internal(ancestor, successor);
297    }
298    if (ancestor->get_tree_root() != successor->get_tree_root()) {
299        return "<not same tree>";
300    }
301    if (ancestor->is_inside(successor)) {
302        return "<wrong order>";
303    }
304
305    if (ancestor->is_son_of_root()) {
306        const TreeNode *brother = ancestor->get_brother();
307        if (successor->is_inside(brother)) {
308            return "!"+wayFromTo_internal(brother, successor);
309        }
310    }
311
312    const TreeNode *root = ancestor->get_tree_root()->get_root_node();
313    arb_assert(successor->get_tree_root()->get_root_node() == root);
314
315    arb_assert(ancestor->is_inside(root));
316    arb_assert(successor->is_inside(root));
317
318    return wayFromTo_internal(root, ancestor) + "-" + wayFromTo_internal(root, successor);
319}
320
321template<class TREECONT>
322int loadTreeAndAddTo(int dir, const char *name, TREECONT& container) {
323    GB_ERROR       error = NULp;
324    SizeAwareTree *tree  = loadTree(custom_tree_name(dir, name), error);
325    TEST_EXPECT_NO_ERROR(error);
326    TEST_REJECT_NULL(tree);
327    return container.add(tree, name);
328}
329
330void TEST_part_node_linkage() {
331    GB_ERROR error = NULp;
332
333    TreeContainer tc;
334    loadTreeAndAddTo(1, "ref", tc); // -> ../UNIT_TESTER/run/syncroot/1/ref.tree
335
336    for (int partial = 0; partial<=1; ++partial) {
337        TEST_ANNOTATE(GBS_global_string("partial=%i", partial));
338        if (partial == 1) {
339            loadTreeAndAddTo(1, "overlap", tc); // may be any tree that introduces additional species into namespace
340        }
341
342        ConstStrArray names;
343        tc.get_species_names(names);
344
345        SpeciesSpace      specSpace(names);
346        DeconstructedTree dtree(specSpace);
347
348        const SizeAwareTree *root = tc.get_tree(0);
349
350        {
351            TreeParts tparts(specSpace, tc);
352            error = dtree.deconstruct_weighted(root, tparts.get_tree_PART(0), root->get_leaf_count(), 1.0, false, specSpace.get_allSpecies(), DMODE_ROOTSYNC);
353            TEST_EXPECT_NO_ERROR(error);
354        }
355
356        dtree.start_sorted_retrieval();
357
358        const int LEAFS = 6;
359        const int PARTS = leafs_2_edges(LEAFS, UNROOTED); // expect one partition for each edge
360
361        TEST_EXPECT_EQUAL(root->get_leaf_count(), LEAFS);
362        TEST_EXPECT_EQUAL(dtree.get_part_count(), PARTS);
363
364        const PART *rootPART = dtree.find_part(root);
365        TEST_EXPECT_NULL(rootPART); // the root node is not attached to any edge -> does not define any partition
366
367        const SizeAwareTree *leftRootSon  = root->get_leftson();
368        const SizeAwareTree *rightRootSon = root->get_rightson();
369
370        const PART *leftRootPART  = dtree.find_part(leftRootSon);
371        const PART *rightRootPART = dtree.find_part(rightRootSon);
372
373        TEST_REJECT_NULL(leftRootPART);
374        TEST_REJECT_NULL(rightRootPART);
375        TEST_EXPECT_EQUAL(leftRootPART, rightRootPART); // returns SAME part for both sons of root!
376
377        using namespace PART_FWD;
378        TEST_EXPECT_EQUAL(get_origin(leftRootPART), leftRootSon);  // expect reverse linkage
379        TEST_EXPECT_EQUAL(get_origin(rightRootPART), leftRootSon); // reverse linkage not fully consistent at one son of root-edge
380
381        // check correct linkage for all other nodes in tree:
382        {
383            std::vector<const SizeAwareTree*> toTest;
384            toTest.push_back(leftRootSon->get_leftson());
385            toTest.push_back(leftRootSon->get_rightson());
386            toTest.push_back(rightRootSon->get_leftson());
387            toTest.push_back(rightRootSon->get_rightson());
388
389            while (!toTest.empty()) {
390                const SizeAwareTree *node = toTest.back();
391                toTest.pop_back();
392
393                const PART *nodePART = dtree.find_part(node);
394
395                TEST_REJECT_NULL(nodePART);
396                TEST_EXPECT_EQUAL(get_origin(nodePART), node);
397
398                if (!node->is_leaf()) { // push sons
399                    toTest.push_back(node->get_leftson());
400                    toTest.push_back(node->get_rightson());
401                }
402            }
403        }
404    }
405}
406
407inline const DeconstructedTree& EXPECT_DECONSTRUCTED(ErrorOrDeconstructedTreePtr eodtp) {
408    TEST_REJECT(eodtp.hasError());
409    return *eodtp.getValue();
410}
411
412void TEST_part_distance() {
413    RootSynchronizer rs;
414
415    const int tosync_idx = loadTreeAndAddTo(1, "tosync",   rs); // -> ../UNIT_TESTER/run/syncroot/1/tosync.tree
416    const int ref_idx    = loadTreeAndAddTo(1, "ref",      rs); // -> ../UNIT_TESTER/run/syncroot/1/ref.tree
417    const int disj_idx   = loadTreeAndAddTo(1, "disjunct", rs); // -> ../UNIT_TESTER/run/syncroot/1/disjunct.tree
418    const int over_idx   = loadTreeAndAddTo(1, "overlap", rs);  // -> ../UNIT_TESTER/run/syncroot/1/overlap.tree
419
420    TEST_EXPECT_EQUAL(tosync_idx, 0);
421    TEST_EXPECT_EQUAL(ref_idx,    1);
422    TEST_EXPECT_EQUAL(disj_idx,   2);
423    TEST_EXPECT_EQUAL(over_idx,   3);
424
425    rs.beginDeconstructionPhase();
426
427    const SpeciesSpace& specSpace  = rs.get_SpeciesSpace();
428    const int           SPACE_SIZE = 12;
429    TEST_EXPECT_EQUAL(rs.get_species_count(), SPACE_SIZE);                            // via TreeContainer
430    TEST_EXPECT_EQUAL(PART_FWD::get_members(specSpace.get_allSpecies()), SPACE_SIZE); // via SpeciesSpace
431
432    const SizeAwareTree *tosync_root = rs.get_tree(tosync_idx);
433    const SizeAwareTree *ref_root    = rs.get_tree(ref_idx);
434    const SizeAwareTree *disj_root   = rs.get_tree(disj_idx);
435    const SizeAwareTree *over_root   = rs.get_tree(over_idx);
436
437    TEST_REJECT_NULL(tosync_root);
438    TEST_REJECT_NULL(ref_root);
439    TEST_REJECT_NULL(disj_root);
440    TEST_REJECT_NULL(over_root);
441
442    {
443        const PART *tosync_wholeTree_PART = rs.get_tree_PART(tosync_idx);
444        const PART *ref_wholeTree_PART    = rs.get_tree_PART(ref_idx);
445        const PART *disj_wholeTree_PART   = rs.get_tree_PART(disj_idx);
446        const PART *over_wholeTree_PART   = rs.get_tree_PART(over_idx);
447
448        TEST_EXPECT_EQUAL(PART_FWD::get_members(tosync_wholeTree_PART), 6);
449        TEST_EXPECT_EQUAL(PART_FWD::get_members(ref_wholeTree_PART),    6);
450        TEST_EXPECT_EQUAL(PART_FWD::get_members(disj_wholeTree_PART),   6);
451        TEST_EXPECT_EQUAL(PART_FWD::get_members(over_wholeTree_PART),   6);
452
453        const int DISJUNCT_DIST = 12; // =sum of sizes of 2 trees
454
455        const DeconstructedTree& tosync_dtree = EXPECT_DECONSTRUCTED(rs.get_DeconstructedTree(tosync_idx));
456        const DeconstructedTree& disj_dtree   = EXPECT_DECONSTRUCTED(rs.get_DeconstructedTree(disj_idx));
457        const DeconstructedTree& over_dtree   = EXPECT_DECONSTRUCTED(rs.get_DeconstructedTree(over_idx));
458        const DeconstructedTree& ref_dtree    = EXPECT_DECONSTRUCTED(rs.get_DeconstructedTree(ref_idx));
459
460        // test single part distances at beginning:
461        {
462            const SizeAwareTree *tosync_rightson      = tosync_root->get_rightson();             TEST_REJECT_NULL(tosync_rightson);
463            const PART          *tosync_rightson_PART = tosync_dtree.find_part(tosync_rightson); TEST_REJECT_NULL(tosync_rightson_PART);
464
465            // compare PART of tosync_rightson with self -> shall report no distance:
466            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(tosync_rightson_PART, tosync_rightson_PART, tosync_wholeTree_PART, tosync_wholeTree_PART), 0);
467
468            TEST_REJECT(tosync_rightson->is_leaf()); // want to descent further..
469
470            const SizeAwareTree *tosync_grandson      = tosync_rightson->get_rightson();         TEST_REJECT_NULL(tosync_grandson);
471            const PART          *tosync_grandson_PART = tosync_dtree.find_part(tosync_grandson); TEST_REJECT_NULL(tosync_grandson_PART);
472
473            int RIGHT_GRAND_DIST = 4;
474            // compare PART of tosync_rightson with tosync_grandson -> shall report some distance:
475            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(tosync_rightson_PART, tosync_grandson_PART, tosync_wholeTree_PART, tosync_wholeTree_PART), RIGHT_GRAND_DIST);
476
477            // test distance does not depend on direction:
478            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(tosync_grandson_PART, tosync_rightson_PART, tosync_wholeTree_PART, tosync_wholeTree_PART), RIGHT_GRAND_DIST);
479
480            {
481                // this subtree changes the partition side (between tosync_rightson_PART and tosync_grandson_PART):
482                const SizeAwareTree *tosync_othergrandson = tosync_grandson->get_brother(); TEST_REJECT_NULL(tosync_othergrandson);
483                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! :)
484            }
485
486
487            // test distance to edges from disjunct tree (distance should always be same):
488            const SizeAwareTree *disj_leftson  = disj_root->get_leftson ();                TEST_REJECT_NULL(disj_leftson);
489            const SizeAwareTree *disj_grandson = disj_root->get_rightson()->get_leftson(); TEST_REJECT_NULL(disj_grandson);
490
491            const PART *disj_leftson_PART  = disj_dtree.find_part(disj_leftson);  TEST_REJECT_NULL(disj_leftson_PART);
492            const PART *disj_grandson_PART = disj_dtree.find_part(disj_grandson); TEST_REJECT_NULL(disj_grandson_PART);
493
494            // distance between edges of disjunct trees is the same (for any edge):
495            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(tosync_grandson_PART, disj_leftson_PART, tosync_wholeTree_PART, disj_wholeTree_PART), DISJUNCT_DIST);
496            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(tosync_grandson_PART, disj_grandson_PART, tosync_wholeTree_PART, disj_wholeTree_PART), DISJUNCT_DIST);
497
498            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
499
500
501            // test distance between partly overlapping trees:
502            const SizeAwareTree *over_leftson      = over_root->get_leftson();           TEST_REJECT_NULL(over_leftson);
503            const PART          *over_leftson_PART = over_dtree.find_part(over_leftson); TEST_REJECT_NULL(over_leftson_PART);
504
505            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
506
507            const SizeAwareTree *over_somenode      = over_leftson->get_leftson();              TEST_REJECT_NULL(over_somenode);
508            const PART          *over_somenode_PART = over_dtree.find_part    (over_somenode); TEST_REJECT_NULL(over_somenode_PART);
509
510            TEST_EXPECT_EQUAL(PART_FWD::calcDistance(over_somenode_PART, tosync_grandson_PART, over_wholeTree_PART, tosync_wholeTree_PART), 8);
511        }
512
513        // The trees 'ref' and 'tosync' have same topology - only root position differs.
514        // => each branch in one tree should perfectly match another branch in other tree.
515
516        bool reverseSearchFound_identicalIndex = false;
517        bool reverseSearchFound_duplicateIndex = false;
518        bool selfSearchFound_identicalIndex    = false;
519        bool selfSearchFound_duplicateIndex    = false;
520
521        for (size_t pr = 0; pr<ref_dtree.get_part_count(); ++pr) {
522            const PART *ref_PART = ref_dtree.peek_part(pr);
523            TEST_REJECT_NULL(ref_PART);
524
525            if (!represents_existing_edge(ref_PART)) continue;
526
527            int best_dist;
528            int best_idx;
529
530            RootSynchronizer::find_best_matching_PART_in(best_dist, best_idx, ref_PART, tosync_dtree, ref_wholeTree_PART, tosync_wholeTree_PART, false);
531
532            TEST_REJECT(best_idx == -1);     // expect some PART is "best match"
533            TEST_EXPECT_EQUAL(best_dist, 0); // should find a perfect match for each branch!
534
535            // perform reverse search
536            {
537                const PART *tosync_PART = tosync_dtree.peek_part(best_idx);
538                TEST_REJECT_NULL(tosync_PART);
539
540                arb_assert(represents_existing_edge(tosync_PART));
541
542                RootSynchronizer::find_best_matching_PART_in(best_dist, best_idx, tosync_PART, ref_dtree, tosync_wholeTree_PART, ref_wholeTree_PART, false);
543
544                TEST_REJECT(best_idx == -1);     // expect some PART is "best match"
545                TEST_EXPECT_EQUAL(best_dist, 0); // should find a perfect match for each branch!
546
547                // expect reverse search matches original PART:
548                TEST_EXPECT_EQUAL(PART_FWD::get_origin(ref_dtree.peek_part(best_idx)), PART_FWD::get_origin(ref_PART));
549                TEST_EXPECT_EQUAL(ref_dtree.peek_part(best_idx), ref_PART);
550                TEST_EXPECT_EQUAL(best_idx, pr);
551                if (size_t(best_idx) == pr) reverseSearchFound_identicalIndex = true;
552                else                        reverseSearchFound_duplicateIndex = true;
553            }
554
555            // search self:
556            RootSynchronizer::find_best_matching_PART_in(best_dist, best_idx, ref_PART, ref_dtree, ref_wholeTree_PART, ref_wholeTree_PART, false);
557
558            // each PART should perfectly match to itself:
559            TEST_EXPECT_EQUAL(PART_FWD::get_origin(ref_dtree.peek_part(best_idx)), PART_FWD::get_origin(ref_PART));
560            TEST_EXPECT_EQUAL(ref_dtree.peek_part(best_idx), ref_PART); // each PART should perfectly match to itself
561            TEST_EXPECT_EQUAL(best_idx, pr);
562            if (size_t(best_idx) == pr) selfSearchFound_identicalIndex = true;
563            else                        selfSearchFound_duplicateIndex = true;
564        }
565
566        TEST_EXPECT(reverseSearchFound_identicalIndex);
567        TEST_REJECT(reverseSearchFound_duplicateIndex);
568        TEST_EXPECT(selfSearchFound_identicalIndex);
569        TEST_REJECT(selfSearchFound_duplicateIndex);
570
571        // compare PARTs of disjunct trees:
572        //  - all distances are expected to be the same ("comparing apples and oranges")
573
574        for (size_t pd = 0; pd<disj_dtree.get_part_count(); ++pd) {
575            const PART *disj_PART = disj_dtree.peek_part(pd);
576            TEST_REJECT_NULL(disj_PART);
577
578            if (!represents_existing_edge(disj_PART)) continue;
579
580            for (size_t pr = 0; pr<ref_dtree.get_part_count(); ++pr) {
581                const PART *ref_PART = ref_dtree.peek_part(pr);
582                TEST_REJECT_NULL(ref_PART);
583
584                if (!represents_existing_edge(ref_PART)) continue;
585
586                TEST_EXPECT_EQUAL(PART_FWD::calcDistance(ref_PART, disj_PART, ref_wholeTree_PART, disj_wholeTree_PART), DISJUNCT_DIST);
587            }
588        }
589
590        // compare PARTs of overlap tree with other trees:
591        for (size_t po = 0; po<over_dtree.get_part_count(); ++po) {
592            const PART *over_PART = over_dtree.peek_part(po);
593            TEST_REJECT_NULL(over_PART);
594
595            if (!represents_existing_edge(over_PART)) continue;
596
597            int best_dist, best_idx;
598            int worst_dist, worst_idx;
599
600            // compare with tosync:
601            RootSynchronizer::find_best_matching_PART_in(best_dist, best_idx, over_PART, tosync_dtree, over_wholeTree_PART, tosync_wholeTree_PART, false);
602            TEST_REJECT(best_idx == -1);     // expect some PART is "best match"
603            TEST_EXPECT_EQUAL(best_dist, 6); // 6 = perfect match in overlap + 2*3 not overlapping parts
604
605            RootSynchronizer::find_worst_matching_PART_in(worst_dist, worst_idx, over_PART, tosync_dtree, over_wholeTree_PART, tosync_wholeTree_PART);
606            TEST_REJECT(worst_idx == -1);     // expect some PART is "worst match"
607            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)
608
609            // compare with disjunct:
610            RootSynchronizer::find_best_matching_PART_in(best_dist, best_idx, over_PART, disj_dtree, over_wholeTree_PART, disj_wholeTree_PART, false);
611            TEST_REJECT(best_idx == -1);     // expect some PART is "best match"
612            TEST_EXPECT_EQUAL(best_dist, 6); // see above
613
614            RootSynchronizer::find_worst_matching_PART_in(worst_dist, worst_idx, over_PART, disj_dtree, over_wholeTree_PART, disj_wholeTree_PART);
615            TEST_REJECT(worst_idx == -1);     // expect some PART is "worst match"
616            TEST_EXPECT_EQUAL(worst_dist, 8); // see above
617        }
618    }
619}
620
621const int DEPTH = 0; // 0 means: perform 1 move per tree only
622
623void TEST_RootSynchronizer() {
624    RootSynchronizer rsync1;
625
626    int tosync_idx = loadTreeAndAddTo(1, "tosync", rsync1); // -> ../UNIT_TESTER/run/syncroot/1/tosync.tree
627    int ref_idx    = loadTreeAndAddTo(1, "ref",    rsync1); // -> ../UNIT_TESTER/run/syncroot/1/ref.tree
628
629    ConstSizeAwareTreePtr newRoot = NULp;
630    int                   foundDist;
631
632    // access invalid idx => test error is reported:
633    {
634        ErrorOrSizeAwareTreePtr erc = rsync1.find_best_root_candidate(tosync_idx, 7, foundDist, false);
635        TEST_EXPECT(erc.hasError());
636        TEST_EXPECT_CONTAINS(erc.getError().deliver(), "invalid tree index 7");
637    }
638
639    // test finding best candidate for root in 'tosync':
640    {
641        ErrorOrSizeAwareTreePtr erc1 = rsync1.find_best_root_candidate(tosync_idx, ref_idx, foundDist, false);
642        TEST_REJECT(erc1.hasError());
643
644        newRoot = erc1.getValue();
645        TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(tosync_idx), newRoot), "rlr");
646        TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(ref_idx), newRoot), "<not same tree>"); // (newRoot is not member of 'ref')
647
648        TEST_EXPECT_EQUAL(foundDist, 0); // =exact match
649
650        TEST_EXPECT_EQUAL(rsync1.calcTreeDistance(ref_idx, tosync_idx), 0);
651        TEST_EXPECT_EQUAL(rsync1.minDistanceSum(), 0);
652    }
653
654    // test opposite detection:
655    {
656        ErrorOrSizeAwareTreePtr erc2 = rsync1.find_best_root_candidate(ref_idx, tosync_idx, foundDist, false);
657        TEST_REJECT(erc2.hasError());
658
659        ConstSizeAwareTreePtr newRoot2 = erc2.getValue();
660        TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(tosync_idx), newRoot2), "<not same tree>"); // (newRoot2 is not member of 'tosync')
661        TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(ref_idx), newRoot2), "rrl");
662
663        TEST_EXPECT_EQUAL(foundDist, 0); // =exact match
664    }
665
666    // test basics of synchronizing multiple roots:
667    {
668        ErrorOrMultirootPtr emr0 = rsync1.get_current_roots();
669        TEST_REJECT(emr0.hasError());
670
671        MultirootPtr mr0 = emr0.getValue();
672        TEST_EXPECT(mr0.isSet());
673        TEST_EXPECT_EQUAL(mr0->size(), 2);
674
675        // access nodes:
676        {
677            ConstSizeAwareTreePtr r1 = mr0->get_node(0);
678            TEST_REJECT_NULL(r1.plain_pointer());
679
680            ConstSizeAwareTreePtr r2 = mr0->get_node(1);
681            TEST_REJECT_NULL(r2.plain_pointer());
682
683            ConstSizeAwareTreePtr r3 = mr0->get_node(2); // should not exist
684            TEST_EXPECT_NULL(r3.plain_pointer());
685        }
686
687        const int distSum0    = mr0->distanceSum(rsync1);
688        const int distCenter0 = mr0->distanceToCenterSum(rsync1);
689        TEST_EXPECT_EQUAL(distSum0, 4);
690        TEST_EXPECT_EQUAL(distCenter0, 2);
691
692        {
693            MultirootPtr mr2 = new Multiroot(*mr0); // clone ..
694            TEST_EXPECT_EQUAL(mr2->distanceSum(rsync1), distSum0); // .. reports same distance as original ..
695            TEST_EXPECT_EQUAL(mr2->distanceToCenterSum(rsync1), distCenter0); // .. and same distance to center
696
697            const int idx = 1;
698
699            // replacing a node with its son should (normally) change distance and center-distance:
700            ConstSizeAwareTreePtr node    = mr2->get_node(idx);
701            ConstSizeAwareTreePtr newNode = node->get_rightson();
702            arb_assert(newNode);
703            mr2->replace_node(idx, newNode);
704
705            {
706                int distSum2    = mr2->distanceSum(rsync1);
707                int distCenter2 = mr2->distanceToCenterSum(rsync1);
708
709                TEST_EXPECT_DIFFERENT(distSum2,    distSum0);    TEST_EXPECT_EQUAL(distSum2,    6);
710                TEST_EXPECT_DIFFERENT(distCenter2, distCenter0); TEST_EXPECT_EQUAL(distCenter2, 3);
711            }
712
713            newNode = node->get_leftson();
714            arb_assert(newNode);
715            mr2->replace_node(idx, newNode);
716
717            {
718                int distSum2    = mr2->distanceSum(rsync1);
719                int distCenter2 = mr2->distanceToCenterSum(rsync1);
720
721                TEST_EXPECT_EQUAL(distSum2, distSum0);           // no difference for leftson (not normal, but obviously possible. assuming its a special case)
722                TEST_EXPECT_DIFFERENT(distCenter2, distCenter0); // nevertheless we got different distance to center
723                TEST_EXPECT_EQUAL(distCenter2, 4);
724            }
725        }
726
727        // find optimal roots for all trees:
728        {
729            ErrorOrMultirootPtr emr1 = rsync1.find_good_roots_for_trees(DEPTH);
730            TEST_REJECT(emr1.hasError());
731
732            MultirootPtr mr1 = emr1.getValue();
733            TEST_EXPECT(mr1.isSet());
734            TEST_EXPECT_EQUAL(mr1->size(), 2);
735
736            TEST_EXPECT_EQUAL(mr1->distanceSum(rsync1), 0);
737            TEST_EXPECT_EQUAL(mr1->distanceToCenterSum(rsync1), 0);
738
739            // test positions of resulting root-nodes in original trees (shows how roots will move):
740            TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(ref_idx),    mr1->get_node(ref_idx)),    "l");
741            TEST_EXPECT_EQUAL(wayFromTo(rsync1.get_tree(tosync_idx), mr1->get_node(tosync_idx)), "rlr");
742        }
743    }
744
745    {
746        // test releasing a tree:
747        SizeAwareTree *tosync_released = rsync1.take_tree(tosync_idx);
748
749        // attempt to use a "released tree" should fail:
750        {
751            ErrorOrSizeAwareTreePtr erc2 = rsync1.find_best_root_candidate(tosync_idx, ref_idx, foundDist, false);
752            TEST_EXPECT(erc2.hasError());
753            TEST_EXPECT_ERROR_CONTAINS(erc2.getError(), "tree at index #0 vanished");
754
755            TEST_EXPECT_EQUAL(foundDist, INT_MAX); // =no match
756        }
757
758        // change root of 'tosync_released' to 'newRoot':
759        {
760            arb_assert(newRoot->is_inside(tosync_released));                   // when newRoot is member of tosync_released ..
761            SizeAwareTree *newRoot_nc = const_cast<SizeAwareTree*>(&*newRoot); // .. casting away const is ok (because we own the tree atm)
762
763            arb_assert(newRoot_nc != tosync_released);
764            arb_assert(tosync_released->is_root_node());
765            newRoot_nc->set_root(); // set new root
766            arb_assert(tosync_released->is_root_node()); // virtual root node remains valid (it is moved to new root)
767        }
768        {
769            // create new RootSynchronizer and add tree with changed root:
770            RootSynchronizer rsync2;
771            tosync_idx = rsync2.add(tosync_released, "tosync");
772
773            // also move "ref" tree from 'rsync1' -> 'rsync2':
774            {
775                SizeAwareTree *ref_released = rsync1.take_tree(ref_idx);
776                ref_idx = rsync2.add(ref_released, "ref");
777            }
778
779            // test find_best_root_candidate with these trees (root should be same -> should report son-of-root as best match)
780            {
781                int tr_dist, rt_dist;
782                ErrorOrSizeAwareTreePtr tosync_erc = rsync2.find_best_root_candidate(tosync_idx, ref_idx, tr_dist, false);
783                ErrorOrSizeAwareTreePtr ref_erc    = rsync2.find_best_root_candidate(ref_idx, tosync_idx, rt_dist, false);
784
785                TEST_REJECT(tosync_erc.hasError());
786                TEST_REJECT(ref_erc.hasError());
787
788                TEST_EXPECT_EQUAL(rsync2.calcTreeDistance(ref_idx, tosync_idx), 0);
789                TEST_EXPECT_EQUAL(rsync2.minDistanceSum(), 0);
790
791                TEST_EXPECT_EQUAL(tr_dist, 0); // =exact match
792                TEST_EXPECT_EQUAL(rt_dist, 0); // =exact match
793
794                ConstSizeAwareTreePtr tosync_rc = tosync_erc.getValue();
795                ConstSizeAwareTreePtr ref_rc    = ref_erc.getValue();
796
797                TEST_EXPECT(tosync_rc->is_son_of_root());
798                TEST_EXPECT(ref_rc->is_son_of_root());
799
800                TEST_EXPECT_EQUAL(wayFromTo(rsync2.get_tree(tosync_idx), tosync_rc), "l");
801                TEST_EXPECT_EQUAL(wayFromTo(rsync2.get_tree(ref_idx),    ref_rc),    "l");
802            }
803        }
804    }
805
806    // test some error cases:
807    {
808        RootSynchronizer rsync3;
809        loadTreeAndAddTo(1, "tosync", rsync3); // -> ../UNIT_TESTER/run/syncroot/1/tosync.tree
810
811        ErrorOrMultirootPtr emr2 = rsync3.find_good_roots_for_trees(DEPTH);
812        TEST_EXPECT(emr2.hasError());
813        TEST_EXPECT_ERROR_CONTAINS(emr2.getError().deliver(), "Need at least two trees");
814    }
815}
816
817void TEST_SLOW_sync_more_trees() {
818    {
819        RootSynchronizer rsync;
820
821        const int ref_idx      = loadTreeAndAddTo(1, "ref",      rsync); // -> ../UNIT_TESTER/run/syncroot/1/ref.tree
822        const int disjunct_idx = loadTreeAndAddTo(1, "disjunct", rsync); // -> ../UNIT_TESTER/run/syncroot/1/disjunct.tree
823
824        ErrorOrMultirootPtr startOrErr  = rsync.get_current_roots();              TEST_REJECT(startOrErr.hasError());
825        ErrorOrMultirootPtr syncedOrErr = rsync.find_good_roots_for_trees(DEPTH); TEST_REJECT(syncedOrErr.hasError());
826
827        MultirootPtr innermost = rsync.get_innermost_edges(); TEST_REJECT(innermost.isNull());
828        MultirootPtr start     = startOrErr.getValue ();      TEST_REJECT(start.isNull());
829        MultirootPtr synced    = syncedOrErr.getValue();      TEST_REJECT(synced.isNull());
830
831        // Note: find_good_roots_for_trees keeps status quo here (did not find better root-combination for disjunct trees):
832        const int DISTSUM = 12;
833        TEST_EXPECT_EQUAL(start->distanceSum (rsync), DISTSUM);
834        TEST_EXPECT_EQUAL(synced->distanceSum(rsync), DISTSUM);
835        TEST_EXPECT_EQUAL(start->distanceToCenterSum (rsync), 8);
836        TEST_EXPECT_EQUAL(synced->distanceToCenterSum(rsync), 5);    // synced roots are nearer to center (of species set).
837        TEST_EXPECT_EQUAL(innermost->distanceToCenterSum(rsync), 5); // [did not understand that value]
838
839        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(ref_idx, disjunct_idx), DISTSUM);
840        TEST_EXPECT_EQUAL(rsync.minDistanceSum(), DISTSUM);
841
842        // compare 'start' with 'synced' (did nodes change?):
843        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(ref_idx),      synced->get_node(ref_idx)),      "");   // node of ref-tree was not really modified
844        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(disjunct_idx), synced->get_node(disjunct_idx)), "!l"); // node of disjunct-tree now slightly modified (acceptable)
845    }
846
847    // test 3 trees:
848    {
849        RootSynchronizer rsync;
850
851        const int tosync_idx   = loadTreeAndAddTo(1, "tosync",    rsync); // -> ../UNIT_TESTER/run/syncroot/1/tosync.tree
852        const int disjunct_idx = loadTreeAndAddTo(1, "disjunct",  rsync); // -> ../UNIT_TESTER/run/syncroot/1/disjunct.tree
853        const int overa_idx    = loadTreeAndAddTo(1, "overlap_A", rsync); // -> ../UNIT_TESTER/run/syncroot/1/overlap_A.tree
854
855        ErrorOrMultirootPtr startOrErr  = rsync.get_current_roots();          TEST_REJECT(startOrErr.hasError());
856        ErrorOrMultirootPtr syncedOrErr = rsync.find_good_roots_for_trees(1); TEST_REJECT(syncedOrErr.hasError()); // need depth higher than 0 to reach optimum here
857
858        MultirootPtr innermost = rsync.get_innermost_edges(); TEST_REJECT(innermost.isNull());
859        MultirootPtr start     = startOrErr.getValue();       TEST_REJECT(start.isNull());
860        MultirootPtr synced    = syncedOrErr.getValue();      TEST_REJECT(synced.isNull());
861
862        const int OPTIMAL_DIST = 24;
863
864        TEST_EXPECT_EQUAL(start->distanceSum (rsync), 28);
865        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)
866        TEST_EXPECT_EQUAL(start->distanceToCenterSum (rsync), 15);
867        TEST_EXPECT_EQUAL(synced->distanceToCenterSum(rsync), 8);
868        TEST_EXPECT_EQUAL(innermost->distanceToCenterSum(rsync), 6); // [did not understand that value]
869
870        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(tosync_idx, disjunct_idx), 12);
871        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(overa_idx,  disjunct_idx), 6);
872        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(overa_idx,  tosync_idx),   6);
873        TEST_EXPECT_EQUAL(rsync.minDistanceSum(), OPTIMAL_DIST);
874
875        // compare 'start' with 'synced' (did nodes change?):
876        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
877        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(disjunct_idx), synced->get_node(disjunct_idx)), "!l");
878        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(overa_idx),    synced->get_node(overa_idx)),    "!lrr");
879    }
880
881    // test 4 trees:
882    {
883        RootSynchronizer rsync;
884
885        const int tosync_idx = loadTreeAndAddTo(1, "tosync",    rsync); // -> ../UNIT_TESTER/run/syncroot/1/tosync.tree
886        const int ref_idx    = loadTreeAndAddTo(1, "ref",       rsync); // -> ../UNIT_TESTER/run/syncroot/1/ref.tree
887        const int over_idx   = loadTreeAndAddTo(1, "overlap",   rsync); // -> ../UNIT_TESTER/run/syncroot/1/overlap.tree
888        const int overa_idx  = loadTreeAndAddTo(1, "overlap_A", rsync); // -> ../UNIT_TESTER/run/syncroot/1/overlap_A.tree
889
890        ErrorOrMultirootPtr startOrErr  = rsync.get_current_roots();              TEST_REJECT(startOrErr.hasError());
891        ErrorOrMultirootPtr syncedOrErr = rsync.find_good_roots_for_trees(DEPTH); TEST_REJECT(syncedOrErr.hasError());
892
893        MultirootPtr innermost = rsync.get_innermost_edges(); TEST_REJECT(innermost.isNull());
894        MultirootPtr start     = startOrErr.getValue ();      TEST_REJECT(start.isNull());
895        MultirootPtr synced    = syncedOrErr.getValue();      TEST_REJECT(synced.isNull());
896
897        const int OPTIMAL_DIST = 24;
898
899        TEST_EXPECT_EQUAL(start->distanceSum (rsync), 36);
900        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)
901        TEST_EXPECT_EQUAL(start->distanceToCenterSum (rsync), 9);
902        TEST_EXPECT_EQUAL(synced->distanceToCenterSum(rsync), 5);    // center distance now gets reduced.
903        TEST_EXPECT_EQUAL(innermost->distanceToCenterSum(rsync), 3); // [did not understand that value]
904
905        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(tosync_idx, ref_idx),   0);
906        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(tosync_idx, over_idx),  6);
907        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(tosync_idx, overa_idx), 6);
908        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(ref_idx,    over_idx),  6);
909        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(ref_idx,    overa_idx), 6);
910        TEST_EXPECT_EQUAL(rsync.calcTreeDistance(over_idx,   overa_idx), 0);
911        TEST_EXPECT_EQUAL(rsync.minDistanceSum(), OPTIMAL_DIST);
912
913        // compare 'start' with 'synced' (did nodes change?):
914        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
915        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(ref_idx),      synced->get_node(ref_idx)),      "");
916        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(over_idx),     synced->get_node(over_idx)),     "");
917        TEST_EXPECT_EQUAL(wayFromTo(start->get_node(overa_idx),    synced->get_node(overa_idx)),    "!lr");
918    }
919}
920
921#endif // UNIT_TESTS
922
923// --------------------------------------------------------------------------------
924
Note: See TracBrowser for help on using the repository browser.