source: trunk/CONSENSUS_TREE/SyncRoot.hxx

// ========================================================= //
//                                                           //
//   File      : SyncRoot.hxx                                //
//   Purpose   : Sync roots of trees                         //
//                                                           //
//   Coded by Ralf Westram (coder@reallysoft.de) in May 20   //
//   http://www.arb-home.de/                                 //
//                                                           //
// ========================================================= //

#ifndef SYNCROOT_HXX
#define SYNCROOT_HXX

#ifndef CT_COMMON_HXX
#include "CT_common.hxx"
#endif
#ifndef _GLIBCXX_VECTOR
#include <vector>
#endif
#ifndef ERRORORTYPE_H
#include <ErrorOrType.h>
#endif
#ifndef MATRIX_H
#include <matrix.h>
#endif

typedef SmartPtr<DeconstructedTree> DeconstructedTreePtr;

typedef RefPtr<const SizeAwareTree>     ConstSizeAwareTreePtr;
typedef RefPtr<const DeconstructedTree> ConstDeconstructedTreePtr;

typedef ErrorOr<ConstSizeAwareTreePtr>     ErrorOrSizeAwareTreePtr;
typedef ErrorOr<ConstDeconstructedTreePtr> ErrorOrDeconstructedTreePtr;

class RootSynchronizer;

typedef std::vector<ConstSizeAwareTreePtr> ConstSizeAwareTreeVector;

class Multiroot {
    ConstSizeAwareTreeVector      node;
    mutable symmetric_matrix<int> distance; // pairwise

#if defined(ASSERTION_USED)
    bool is_valid() const {
        if (size()<2) return false; // too small
        for (int i = 0; i<size(); ++i) {
            if (!node[i]) return false;
            if (node[i]->is_root_node()) return false;
        }
        return true;
    }
#endif

    int lazy_eval_distance(const RootSynchronizer& rsync, int i, int j) const;

public:
    static const int UNKNOWN_DISTANCE = -1;

    Multiroot(const TreeContainer& trees) :
        node(trees.get_tree_count(), NULp),
        distance(trees.get_tree_count())
    {
        for (int i = 0; i<size(); ++i) {
            node[i] = trees.get_tree(i)->get_leftson(); // take any son
            for (int j = 0; j<i; ++j) {
                distance.set(i, j, UNKNOWN_DISTANCE);
            }
        }
        arb_assert(is_valid());
    }
    Multiroot(const Multiroot& other) :
        node(other.node),
        distance(other.size())
    {
        for (int i = 0; i<size(); ++i) {
            for (int j = 0; j<i; ++j) {
                distance.set(i, j, other.distance.get(i, j));
            }
        }
    }

    int size() const { return distance.size(); }
    int distanceSum(const RootSynchronizer& rsync) const;
    int distanceToCenterSum(const RootSynchronizer& rsync) const;
    int singleTreeDistanceSum(const RootSynchronizer& rsync, int idx);

    ConstSizeAwareTreePtr get_node(int idx) const {
        if (idx<0 || size_t(idx)>=node.size()) {
            return NULp;
        }
        return node[idx];
    }

    void replace_node(int idx, ConstSizeAwareTreePtr newNode);
};

typedef SmartPtr<Multiroot>   MultirootPtr;
typedef ErrorOr<MultirootPtr> ErrorOrMultirootPtr;

class RootSynchronizer : public TreeContainer {
    ConstStrArray          species_names;
    SmartPtr<SpeciesSpace> speciesSpacePtr;
    SmartPtr<TreeParts>    treePartsPtr;

    std::vector<DeconstructedTreePtr> dtree; // all involved trees

    GB_ERROR deconstructTree(int treeIdx, bool provideProgress);

    bool has_deconstructed_tree(int idx) const {
        return valid_tree_index(idx) && dtree.size()>size_t(idx) && dtree[idx].isSet();
    }

    MultirootPtr find_better_multiroot(const Multiroot& start, int best_distSum, int best_centerDist, int *movesPerTree, arb_progress *progress = NULp);

public:
    RootSynchronizer() {}

    int add(SizeAwareTree*& tree, const char *treename) {
        arb_assert(!deconstructionPhase()); // now its too late to add new trees
        return TreeContainer::add(tree, treename);
    }
    SizeAwareTree *take_tree(int idx) {
        SizeAwareTree *t = TreeContainer::take_tree(idx);
        if (deconstructionPhase()) {
            dtree[idx].setNull();
        }
        return t;
    }

    void beginDeconstructionPhase();
    bool deconstructionPhase() const {
        return speciesSpacePtr.isSet();
    }
    GB_ERROR deconstruct_all_trees(bool provideProgress);
    bool allTreesDeconstructed() const {
        arb_assert(deconstructionPhase());
        const int treeCount = get_tree_count();
        for (int t = 0; t<treeCount; ++t) if (!has_deconstructed_tree(t)) return false;
        return true;
    }

    ErrorOrSizeAwareTreePtr find_best_root_candidate(int inTree, int accordingToTree, int& best_dist, bool provideProgress); // find root in 'inTree' with best match to root of tree 'accordingToTree'

    MultirootPtr        get_innermost_edges() const;
    ErrorOrMultirootPtr get_current_roots() const;
    ErrorOrMultirootPtr find_good_roots_for_trees(const int MAX_DEPTH, arb_progress *progress = NULp);

    // some helper methods (used to port TEST_part_distance to RootSynchronizer):
    const SpeciesSpace& get_SpeciesSpace() const {
        arb_assert(deconstructionPhase());
        return *speciesSpacePtr;
    }
    ErrorOrDeconstructedTreePtr get_DeconstructedTree(int treeIdx) {
        GB_ERROR error = deconstructTree(treeIdx, false); // lazy eval
        return ErrorOrDeconstructedTreePtr(error, &*dtree[treeIdx]);
    }
    const PART *get_tree_PART(int treeIdx) const {
        arb_assert(deconstructionPhase());
        return treePartsPtr->get_tree_PART(treeIdx);
    }
    const PART *get_edge_PART(int treeIdx, const SizeAwareTree *sonOfEdge) const {
        arb_assert(allTreesDeconstructed()); // otherwise dtree contains nothing yet
        arb_assert(valid_tree_index(treeIdx));
        arb_assert(!sonOfEdge->is_root_node());
        return dtree[treeIdx]->find_part(sonOfEdge);
    }

    int calcEdgeDistance(int i1, const SizeAwareTree *n1, int i2, const SizeAwareTree *n2) const;
    int calcTreeDistance(int i1, int i2) const; // minimal possible distance between (any edges) of two trees
    int minDistanceSum() const; // sum of pairwise distances between all trees

    static void find_best_matching_PART_in(int& best_dist, int &best_idx, const PART *part, const DeconstructedTree& in, const PART *tree_part, const PART *tree_in, bool provideProgress);
    static void find_worst_matching_PART_in(int& worst_dist, int &worst_idx, const PART *part, const DeconstructedTree& in, const PART *tree_part, const PART *tree_in);
};

#else
#error SyncRoot.hxx included twice
#endif // SYNCROOT_HXX