source: branches/stable/CONSENSUS_TREE/CT_common.hxx

// ========================================================= //
//                                                           //
//   File      : CT_common.hxx                               //
//   Purpose   : provides common code used by public headers //
//                                                           //
//   Coded by Ralf Westram (coder@reallysoft.de) in May 20   //
//   http://www.arb-home.de/                                 //
//                                                           //
// ========================================================= //



#ifndef CT_COMMON_HXX
#define CT_COMMON_HXX

#ifndef TREENODE_H
#include <TreeNode.h>
#endif
#ifndef ARB_STRARRAY_H
#include <arb_strarray.h>
#endif
#ifndef ARB_PROGRESS_H
#include <arb_progress.h>
#endif
#ifndef _GLIBCXX_MAP
#include <map>
#endif
#ifndef _GLIBCXX_VECTOR
#include <vector>
#endif
#ifndef _GLIBCXX_STRING
#include <string>
#endif

// -----------------------
//      SizeAwareTree

struct SizeAwareRoot : public TreeRoot {
    inline SizeAwareRoot();
    inline TreeNode *makeNode() const OVERRIDE;
    inline void destroyNode(TreeNode *node) const OVERRIDE;
};

class SizeAwareTree FINAL_TYPE : public TreeNode {
    // simple size-aware tree
    unsigned leaf_count;
protected:
    ~SizeAwareTree() OVERRIDE {}
    friend class SizeAwareRoot; // allowed to call dtor
public:
    SizeAwareTree(TreeRoot *root) : TreeNode(root) {}

    DEFINE_TREE_RELATIVES_ACCESSORS(SizeAwareTree);

    unsigned get_leaf_count() const OVERRIDE {
        return leaf_count;
    }
    void compute_tree() OVERRIDE {
        if (is_leaf()) {
            leaf_count = 1;
        }
        else {
            get_leftson()->compute_tree();
            get_rightson()->compute_tree();
            leaf_count = get_leftson()->get_leaf_count()+get_rightson()->get_leaf_count();
        }
    }
};

SizeAwareRoot::SizeAwareRoot() : TreeRoot(true) {}
inline TreeNode *SizeAwareRoot::makeNode() const { return new SizeAwareTree(const_cast<SizeAwareRoot*>(this)); }
inline void SizeAwareRoot::destroyNode(TreeNode *node) const { delete DOWNCAST(SizeAwareTree*,node); }


class TreeInfo {
    std::string Name;
    size_t      specCount;

public:
    explicit TreeInfo(const char *Name_, size_t specCount_)
        : Name(Name_),
          specCount(specCount_)
    {}

    const char *name() const { return Name.c_str(); }
    size_t species_count() const { return specCount; }
};

class TreeContainer {
    // owns multiple loaded trees.
    // maintains overall set of species occurring in these trees.

    typedef std::map<std::string, size_t> OccurCount;
    OccurCount species_occurred;

    typedef std::vector<SizeAwareTree*> Trees;
    Trees                               trees;
    std::vector<TreeInfo>               tree_info;

public:
    ~TreeContainer() {
        for (size_t i = 0; i<trees.size(); ++i) {
            destroy(trees[i]);
        }
    }

    size_t get_tree_count() const { arb_assert(trees.size() == tree_info.size()); return tree_info.size(); }
    bool valid_tree_index(int idx) const { return idx>=0 && size_t(idx)<get_tree_count(); }

    const TreeInfo& get_tree_info(int idx) const { arb_assert(valid_tree_index(idx)); return tree_info[idx]; }
    const SizeAwareTree *get_tree(int idx) const { arb_assert(valid_tree_index(idx)); return trees[idx]; }
    SizeAwareTree *take_tree(int idx) {
        arb_assert(valid_tree_index(idx));
        arb_assert(trees[idx]);
        SizeAwareTree *t = trees[idx];
        trees[idx] = NULp;
        return t;
    }

    void get_species_names(ConstStrArray& species_names) const {
        // fills names into 'species_names'
        for (OccurCount::const_iterator s = species_occurred.begin(); s != species_occurred.end(); ++s) {
            species_names.put(s->first.c_str());
        }
    }

    size_t get_species_count() const { return species_occurred.size(); }

    int add(SizeAwareTree*& tree, const char *treename) {
        /*! add 'tree' with 'name'
         * @return index that can be used for get_tree() and get_tree_info()
         */

        tree->compute_tree();

        trees.push_back(tree);
        int added_at_idx = trees.size()-1;

        size_t   name_count;
        GB_CSTR *names = GBT_get_names_of_species_in_tree(tree, &name_count);

        for (size_t n = 0; n<name_count; ++n) {
            const char *name = names[n];
            if (species_occurred.find(name) == species_occurred.end()) {
                species_occurred[name] = 1;
            }
            else {
                species_occurred[name]++;
            }
        }

        tree_info.push_back(TreeInfo(treename, name_count));
        arb_assert(tree_info.size() == trees.size());

        free(names);
        tree = NULp;

        return added_at_idx;
    }

};

class PART;
class PartitionSize;

class SpeciesSpace : virtual Noncopyable {
    const CharPtrArray& names;

    GB_HASH       *Name_hash;
    PartitionSize *psize;
    PART          *allSpecies;

    void add_tree_to_PART(const TreeNode *tree, PART& part) const;

public:
    SpeciesSpace(const CharPtrArray& names_);
    ~SpeciesSpace();

    int get_species_index(const char *name) const {
        int idx = GBS_read_hash(Name_hash, name);
        arb_assert(idx>0); // given 'name' is unknown
        return idx-1;
    }
    const char *get_species_name(int idx) const { return names[idx]; }
    const CharPtrArray& get_names() const { return names; }
    const PartitionSize *get_PartitionSize() const { return psize; }
    const PART *get_allSpecies() const { return allSpecies; }

    PART *create_tree_PART(const TreeNode *tree, const double& weight) const;
};

class PartRegistry;

enum DeconstructionMode {
    DMODE_CONSENSUS_TREE, // inserts PARTs from partial trees twice (once with outgroup on each PARTs side)
    DMODE_ROOTSYNC,       // inserts PARTs from partial trees once  (values of outgroup member are irrelevant)
};

class DeconstructedTree : virtual Noncopyable {
    // for ConsensusTree:    use one DeconstructedTree for all trees
    // for RootSynchronizer: use one DeconstructedTree for each tree

    const SpeciesSpace&  specSpace; // union of all species of all involved trees
    PartRegistry        *registry;  // contains deconstructed tree(s), i.e. its/their edges
    double               overall_weight;

    PART *deconstruct_full_subtree(const TreeNode *tree, const GBT_LEN& len, const double& weight, arb_progress *insertProgress);
    PART *deconstruct_partial_subtree(const TreeNode *tree, const GBT_LEN& len, const double& weight, const PART *partialTree, arb_progress *insertProgress);

    void deconstruct_full_rootnode(const TreeNode *tree, const double& weight, arb_progress *insertProgress);
    void deconstruct_partial_rootnode(const TreeNode *tree, const double& weight, const PART *partialTree, arb_progress *insertProgress);

    const PART *part_with_origin(const TreeNode *node) const;

public:
    DeconstructedTree(const SpeciesSpace& specSpace_);
    ~DeconstructedTree();

    __ATTR__USERESULT GB_ERROR deconstruct_weighted(const TreeNode *tree, const PART *wholeTree, int leafs, double weight, bool provideProgress, const PART *allSpecies, DeconstructionMode mode);

    void start_sorted_retrieval();

    size_t get_part_count() const;
    PART *get_part();

    const PART *peek_part(int idx) const;
    const PART *find_part(const TreeNode *node) const;

    const PART *find_innermost_part() const;
};

namespace PART_FWD { // provide access to some methods of PART
    const TreeNode *get_origin(const PART *part);

    int  get_members(const PART *part);
    void destroy_part(PART* part);

    int calcDistance(const PART *e1, const PART *e2, const PART *t1, const PART *t2);
};

inline bool represents_existing_edge(const PART *p) {
    // This function is not safe!
    // Adding a PART twice into PartRegistry will erase the origin (see addWeightAndLength).
    return PART_FWD::get_origin(p);
}

typedef SmartCustomPtr(PART, PART_FWD::destroy_part) PART_Ptr;

class TreeParts {
    const SpeciesSpace&  specSpace;
    const TreeContainer& trees;

    mutable std::vector<PART_Ptr> whole_tree_parts; // cache

public:
    TreeParts(const SpeciesSpace& specSpace_, const TreeContainer& trees_) :
        specSpace(specSpace_),
        trees(trees_)
    {
        whole_tree_parts.resize(trees.get_tree_count());
    }

    const PART *get_tree_PART(int idx) const {
        arb_assert(trees.valid_tree_index(idx));

        PART_Ptr& wt = whole_tree_parts[idx];
        if (wt.isNull()) {
            wt = specSpace.create_tree_PART(trees.get_tree(idx), 0.0); // weight does/should not matter for wholeTree PARTs
        }
        arb_assert(wt.isSet());
        return wt.content();
    }
};


#else
#error CT_common.hxx included twice
#endif // CT_COMMON_HXX