4.1 Create the `TreeManip` class

(Linux version)

< 4.0 | 4.1 | 4.2 >

There are benefits to keeping the Tree and Node classes simple, so in this step we will create a TreeManip class that will own, manage and manipulate a Tree object.

Rather than call the createTestTree() function of Tree, we will move that function to TreeManip. TreeManip will also eventually have functions to create a standard Newick description string, build a Tree from a Newick description, and perform modifications to a Tree needed during Metropolis (MCMC) proposals.

First, create the TreeManip class by creating a new header file named tree_manip.hpp and populating it with the following code:

#pragma once	

#include &lt;cassert&gt;
#include &lt;memory&gt;
#include "tree.hpp"

namespace strom {

    class TreeManip {
        public:
                                        TreeManip();
                                        TreeManip(Tree::SharedPtr t);
                                        ~TreeManip();

            void                        setTree(Tree::SharedPtr t);
            Tree::SharedPtr             getTree();

            double                      calcTreeLength() const;
            unsigned                    countEdges() const;
            void                        scaleAllEdgeLengths(double scaler);

            void                        createTestTree();
            void                        clear();

        private:

            Tree::SharedPtr             _tree;

        public:

            typedef std::shared_ptr&lt; TreeManip &gt; SharedPtr;
    };

    // This is where function bodies go


} 

Class declarations like this should look familiar because there are many similarities of this class declaration to those we created for Tree and Node. Inside the strom namespace, we have created a class named TreeManip that has two constructors, a destructor, four public member functions, a private data member named _tree, and a type definition that will allow us to create shared pointers to TreeManip objects.

Two constructors and a destructor

We still need to define bodies for each of the functions in the class declaration above. Here are the bodies for the two constructors and the destructor. These functions currently do little more than announce that a TreeManip object is being created or destroyed, except that the constructor that takes a tree shared pointer argument calls the member function setTree, which is defined below. These three member function definitions should go after the semicolon (;) ending the class declaration but before the curly bracket (}) that closes the namespace.

    inline TreeManip::TreeManip() {  
        std::cout &lt;&lt; "Constructing a TreeManip" &lt;&lt; std::endl;
        clear();
    }

    inline TreeManip::TreeManip(Tree::SharedPtr t) {
        std::cout &lt;&lt; "Constructing a TreeManip with a supplied tree" &lt;&lt; std::endl;
        clear();
        setTree(t);
    } 

    inline TreeManip::~TreeManip() {
        std::cout &lt;&lt; "Destroying a TreeManip" &lt;&lt; std::endl;
    }  

The clear function

This function resets the _tree data member. Resetting a shared pointer causes it to no longer point to any object. If this shared pointer was still pointing to a Tree object, and if this was the last shared pointer holding onto that Tree object, the Tree object would be deleted (and the destructor function will report that it has been called).

    inline void TreeManip::clear() {  
        _tree.reset();
    }  

The setTree function

This function sets the data member _tree to point to the supplied tree t, and is used by the second contructor function. This second, extra constructor is not essential: we could use the default constructor (the one that takes no arguments) and then call setTree immediately afterwards and accomplish the same thing. The extra constructor just makes it possible to accomplish both actions (creating the TreeManip object and assigning a tree to it) in the same line of code.

    inline void TreeManip::setTree(Tree::SharedPtr t) {  
        assert(t);
        _tree = t;
    }  

The getTree function

This function simply returns a shared pointer to the Tree object being managed by this TreeManip object.

    inline Tree::SharedPtr TreeManip::getTree() {  
        return _tree;
    }  

The calcTreeLength function

We will not need this function for a while, but given that it is a small, easily understood function, we might as well go ahead and add it to the class now. This function simply adds up the lengths of all edges in its tree and returns the sum (tree length). The function first sets the value of the local variable TL to zero. It then iterates through all nodes in the tree by setting the local variable nd to each element of the _tree->_preorder vector in turn and adding its _edge_length to the current value of TL. The auto keyword forces the compiler to figure out the type of the local variable nd. This makes the code easier to write and read. In this case, the type of nd is Node * (pointer to Node).

    inline double TreeManip::calcTreeLength() const {  
        double TL = 0.0;
        for (auto nd : _tree-&gt;_preorder) {
            TL += nd-&gt;_edge_length;
        } 
        return TL;
    }  

The countEdges function

Another function that will not be needed for awhile. This function returns the length of the managed Tree’s _preorder vector, which will always be equal to the number of edges in the tree.

    inline unsigned TreeManip::countEdges() const { 
        return (unsigned)_tree-&gt;_preorder.size();
    } 

The scaleAllEdgeLengths function

This function, like calcTreeLength and countEdges, will not be needed for some time, but it is easy to add now so it will be in place later when we need to scale all edge lengths in the tree up or down. This function simply scales all edge lengths in the tree by multiplying each by the supplied value scaler.

    inline void TreeManip::scaleAllEdgeLengths(double scaler) {  
        for (auto nd : _tree-&gt;_preorder) {
            nd-&gt;setEdgeLength(scaler*nd-&gt;_edge_length);
        }
    }  

The createTestTree function

This function is nearly identical to the function of the same name in the Tree class. One difference is that we must create a Tree first, and data members of the Tree class (such as _nodes, _preorder, and _is_rooted) must be accessed through the TreeManip object’s _tree pointer.

    inline void TreeManip::createTestTree() {  
        clear();
        _tree = Tree::SharedPtr(new Tree());
        _tree-&gt;_nodes.resize(6);

        Node * root_node       = &_tree-&gt;_nodes[0];
        Node * first_internal  = &_tree-&gt;_nodes[1];
        Node * second_internal = &_tree-&gt;_nodes[2];
        Node * first_leaf      = &_tree-&gt;_nodes[3];
        Node * second_leaf     = &_tree-&gt;_nodes[4];
        Node * third_leaf      = &_tree-&gt;_nodes[5];

        // Here is the structure of the tree (numbers in
        // parentheses are node numbers, other numbers
        // are edge lengths):
        //
        // first_leaf (0)   second_leaf (1)   third_leaf (2)
        //      \              /                  /
        //       \ 0.1        / 0.1              /
        //        \          /                  /
        //     second_internal (3)             / 0.2
        //             \                      /
        //              \ 0.1                /
        //               \                  /
        //                first_internal (4)
        //                        |
        //                        | 0.1
        //                        |
        //                    root_node (5)
        //
        root_node-&gt;_parent = 0;
        root_node-&gt;_left_child = first_internal;
        root_node-&gt;_right_sib = 0;
        root_node-&gt;_number = 5;
        root_node-&gt;_name = "root_node";
        root_node-&gt;_edge_length = 0.0;

        first_internal-&gt;_parent = root_node;
        first_internal-&gt;_left_child = second_internal;
        first_internal-&gt;_right_sib = 0;
        first_internal-&gt;_number = 4;
        first_internal-&gt;_name = "first_internal_node";
        first_internal-&gt;_edge_length = 0.1;

        second_internal-&gt;_parent = first_internal;
        second_internal-&gt;_left_child = first_leaf;
        second_internal-&gt;_right_sib = third_leaf;
        second_internal-&gt;_number = 3;
        second_internal-&gt;_name = "second_internal_node";
        second_internal-&gt;_edge_length = 0.1;

        first_leaf-&gt;_parent = second_internal;
        first_leaf-&gt;_left_child = 0;
        first_leaf-&gt;_right_sib = second_leaf;
        first_leaf-&gt;_number = 0;
        first_leaf-&gt;_name = "first_leaf";
        first_leaf-&gt;_edge_length = 0.1;

        second_leaf-&gt;_parent = second_internal;
        second_leaf-&gt;_left_child = 0;
        second_leaf-&gt;_right_sib = 0;
        second_leaf-&gt;_number = 1;
        second_leaf-&gt;_name = "second_leaf";
        second_leaf-&gt;_edge_length = 0.1;

        third_leaf-&gt;_parent = first_internal;
        third_leaf-&gt;_left_child = 0;
        third_leaf-&gt;_right_sib = 0;
        third_leaf-&gt;_number = 2;
        third_leaf-&gt;_name = "third_leaf";
        third_leaf-&gt;_edge_length = 0.2;

        _tree-&gt;_is_rooted = true;
        _tree-&gt;_root = root_node;
        _tree-&gt;_nleaves = 3;

        // Note that root node is not included in _preorder
        _tree-&gt;_preorder.push_back(first_internal);
        _tree-&gt;_preorder.push_back(second_internal);
        _tree-&gt;_preorder.push_back(first_leaf);
        _tree-&gt;_preorder.push_back(second_leaf);
        _tree-&gt;_preorder.push_back(third_leaf);

        _tree-&gt;_levelorder.push_back(first_internal);
        _tree-&gt;_levelorder.push_back(second_internal);
        _tree-&gt;_levelorder.push_back(third_leaf);
        _tree-&gt;_levelorder.push_back(first_leaf);
        _tree-&gt;_levelorder.push_back(second_leaf);
    }  

Before moving on…

Edit your Node class (file node.hpp) and uncomment the lines making TreeManip a friend class of Node. This will just involve removing the initial // from the two bold, blue lines shown below in node.hpp.

#pragma once	

#include &lt;string&gt;
#include &lt;vector&gt;
#include  &lt;iostream&gt;
//#include "split.hpp"

namespace strom {

    class Tree;
    <span style="color:#0000ff"><strong>class TreeManip;</strong></span>
    //class Likelihood;
    //class Updater;

    class Node {
            friend class Tree;
            <span style="color:#0000ff"><strong>friend class TreeManip;</strong></span>
            //friend class Likelihood;
            //friend class Updater;

        public:
                                        Node();
                                        ~Node();

                    Node *              getParent()     {return _parent;}
                    Node *              getLeftChild()  {return _left_child;}
                    Node *              getRightSib()   {return _right_sib;}
                    int                 getNumber()     {return _number;}
                    std::string         getName()       {return _name;}
                    //Split               getSplit()      {return _split;}

                    double              getEdgeLength() {return _edge_length;}
                    void                setEdgeLength(double v);

            static const double _smallest_edge_length;

            typedef std::vector&lt;Node&gt;    Vector;
            typedef std::vector&lt;Node *&gt;  PtrVector;

        private:

            void                clear();

            Node *              _left_child;
            Node *              _right_sib;
            Node *              _parent;
            int                 _number;
            std::string         _name;
            double              _edge_length;
            //Split               _split;
    };

    inline Node::Node() {
        std::cout &lt;&lt; "Creating Node object" &lt;&lt; std::endl;
        clear();
    }

    inline Node::~Node() {
        std::cout &lt;&lt; "Destroying Node object" &lt;&lt; std::endl;
    }

    inline void Node::clear() {
        _left_child = 0;
        _right_sib = 0;
        _parent = 0;
        _number = -1;
        _name = "";
        _edge_length = _smallest_edge_length;
    }

    inline void Node::setEdgeLength(double v) {
        _edge_length = (v &lt; _smallest_edge_length ? _smallest_edge_length : v);
    }

} 

Edit your Tree class (file tree.hpp) and delete all traces of createTestTree(). We no longer need Tree to have this capability because we can now ask TreeManip to create a test tree. The Tree class will also need to be modified so that TreeManip is a friend of Tree. I’ve indicated all lines in tree.hpp that need to be modified below in bold, blue text. I have commented out lines relating to createTestTree function so that I could show them to you, but you should feel free to just delete these lines entirely (they will be gone when I show you the contents of this file in future steps).

#pragma once	

#include &lt;memory&gt;
#include &lt;iostream&gt;
#include "node.hpp"

namespace strom {

    <span style="color:#0000ff"><strong>class TreeManip;</strong></span>
    //class Likelihood;
    //class Updater;

    class Tree {

            <span style="color:#0000ff"><strong>friend class TreeManip;</strong></span>
            //friend class Likelihood;
            //friend class Updater;

        public:

                                        Tree();
                                        ~Tree();

            bool                        isRooted() const;
            unsigned                    numLeaves() const;
            unsigned                    numInternals() const;
            unsigned                    numNodes() const;

            <span style="color:#0000ff"><strong>//void                        createTestTree();</strong></span>

        private:

            void                        clear();

            bool                        _is_rooted;
            Node *                      _root;
            unsigned                    _nleaves;
            unsigned                    _ninternals;
            Node::PtrVector             _preorder;
            Node::PtrVector             _levelorder;
            Node::Vector                _nodes;

        public:

            typedef std::shared_ptr&lt;Tree&gt; SharedPtr;
    };

    inline Tree::Tree() {
        std::cout &lt;&lt; "Constructing a Tree" &lt;&lt; std::endl;
        <span style="color:#0000ff"><strong>clear();</strong></span>
        <span style="color:#0000ff"><strong>//createTestTree();</strong></span>
    }

    inline Tree::~Tree() {
        std::cout &lt;&lt; "Destroying a Tree" &lt;&lt; std::endl;
    }

    inline void Tree::clear() {
        _is_rooted = false;
        _root = 0;
        _nodes.clear();
        _preorder.clear();
        _levelorder.clear();
    }

    inline bool Tree::isRooted() const {
        return _is_rooted;
    }

    inline unsigned Tree::numLeaves() const {
        return _nleaves;
    }

    inline unsigned Tree::numInternals() const {
        return _ninternals;
    }

    inline unsigned Tree::numNodes() const {
        return (unsigned)_nodes.size();
    }

    <span style="color:#0000ff"><strong>// inline void Tree::createTestTree() {</strong></span>
    <span style="color:#0000ff"><strong>// 	clear();</strong></span>
    <span style="color:#0000ff"><strong>// 	_nodes.resize(6);</strong></span>
    <span style="color:#0000ff"><strong>//</strong></span>
    <span style="color:#0000ff"><strong>// 	Node * root_node       = &_nodes[0];</strong></span>
    <span style="color:#0000ff"><strong>// 	Node * first_internal  = &_nodes[1];</strong></span>
    <span style="color:#0000ff"><strong>// 	Node * second_internal = &_nodes[2];</strong></span>
    <span style="color:#0000ff"><strong>// 	Node * first_leaf      = &_nodes[3];</strong></span>
    <span style="color:#0000ff"><strong>// 	Node * second_leaf     = &_nodes[4];</strong></span>
    <span style="color:#0000ff"><strong>// 	Node * third_leaf      = &_nodes[5];</strong></span>
    <span style="color:#0000ff"><strong>//</strong></span>
    <span style="color:#0000ff"><strong>// 	// Here is the structure of the tree (numbers in</strong></span>
    <span style="color:#0000ff"><strong>// 	// parentheses are node numbers, other numbers</strong></span>
    <span style="color:#0000ff"><strong>// 	// are edge lengths):</strong></span>
    <span style="color:#0000ff"><strong>// 	//</strong></span>
    <span style="color:#0000ff"><strong>// 	// first_leaf (0)   second_leaf (1)   third_leaf (2)</strong></span>
    <span style="color:#0000ff"><strong>// 	//      \              /                  /</strong></span>
    <span style="color:#0000ff"><strong>// 	//       \ 0.1        / 0.1              /</strong></span>
    <span style="color:#0000ff"><strong>// 	//        \          /                  /</strong></span>
    <span style="color:#0000ff"><strong>// 	//     second_internal (3)             / 0.2</strong></span>
    <span style="color:#0000ff"><strong>// 	//             \                      /</strong></span>
    <span style="color:#0000ff"><strong>// 	//              \ 0.1                /</strong></span>
    <span style="color:#0000ff"><strong>// 	//               \                  /</strong></span>
    <span style="color:#0000ff"><strong>// 	//                first_internal (4)</strong></span>
    <span style="color:#0000ff"><strong>// 	//                        |</strong></span>
    <span style="color:#0000ff"><strong>// 	//                        | 0.1</strong></span>
    <span style="color:#0000ff"><strong>// 	//                        |</strong></span>
    <span style="color:#0000ff"><strong>// 	//                    root_node (5)</strong></span>
    <span style="color:#0000ff"><strong>// 	//</strong></span>
    <span style="color:#0000ff"><strong>// 	root_node-&gt;_parent            = 0;</strong></span>
    <span style="color:#0000ff"><strong>// 	root_node-&gt;_left_child        = first_internal;</strong></span>
    <span style="color:#0000ff"><strong>// 	root_node-&gt;_right_sib         = 0;</strong></span>
    <span style="color:#0000ff"><strong>// 	root_node-&gt;_number            = 5;</strong></span>
    <span style="color:#0000ff"><strong>// 	root_node-&gt;_name              = "root node";</strong></span>
    <span style="color:#0000ff"><strong>// 	root_node-&gt;_edge_length       = 0.0;</strong></span>
    <span style="color:#0000ff"><strong>//</strong></span>
    <span style="color:#0000ff"><strong>// 	first_internal-&gt;_parent       = root_node;</strong></span>
    <span style="color:#0000ff"><strong>// 	first_internal-&gt;_left_child   = second_internal;</strong></span>
    <span style="color:#0000ff"><strong>// 	first_internal-&gt;_right_sib    = 0;</strong></span>
    <span style="color:#0000ff"><strong>// 	first_internal-&gt;_number       = 4;</strong></span>
    <span style="color:#0000ff"><strong>// 	first_internal-&gt;_name         = "first internal node";</strong></span>
    <span style="color:#0000ff"><strong>// 	first_internal-&gt;_edge_length  = 0.1;</strong></span>
    <span style="color:#0000ff"><strong>//</strong></span>
    <span style="color:#0000ff"><strong>// 	second_internal-&gt;_parent      = first_internal;</strong></span>
    <span style="color:#0000ff"><strong>// 	second_internal-&gt;_left_child  = first_leaf;</strong></span>
    <span style="color:#0000ff"><strong>// 	second_internal-&gt;_right_sib   = third_leaf;</strong></span>
    <span style="color:#0000ff"><strong>// 	second_internal-&gt;_number      = 3;</strong></span>
    <span style="color:#0000ff"><strong>// 	second_internal-&gt;_name        = "second internal node";</strong></span>
    <span style="color:#0000ff"><strong>// 	second_internal-&gt;_edge_length = 0.1;</strong></span>
    <span style="color:#0000ff"><strong>//</strong></span>
    <span style="color:#0000ff"><strong>// 	first_leaf-&gt;_parent           = second_internal;</strong></span>
    <span style="color:#0000ff"><strong>// 	first_leaf-&gt;_left_child       = 0;</strong></span>
    <span style="color:#0000ff"><strong>// 	first_leaf-&gt;_right_sib        = second_leaf;</strong></span>
    <span style="color:#0000ff"><strong>// 	first_leaf-&gt;_number           = 0;</strong></span>
    <span style="color:#0000ff"><strong>// 	first_leaf-&gt;_name             = "first leaf";</strong></span>
    <span style="color:#0000ff"><strong>// 	first_leaf-&gt;_edge_length      = 0.1;</strong></span>
    <span style="color:#0000ff"><strong>//</strong></span>
    <span style="color:#0000ff"><strong>// 	second_leaf-&gt;_parent          = second_internal;</strong></span>
    <span style="color:#0000ff"><strong>// 	second_leaf-&gt;_left_child      = 0;</strong></span>
    <span style="color:#0000ff"><strong>// 	second_leaf-&gt;_right_sib       = 0;</strong></span>
    <span style="color:#0000ff"><strong>// 	second_leaf-&gt;_number          = 1;</strong></span>
    <span style="color:#0000ff"><strong>// 	second_leaf-&gt;_name            = "second leaf";</strong></span>
    <span style="color:#0000ff"><strong>// 	second_leaf-&gt;_edge_length     = 0.1;</strong></span>
    <span style="color:#0000ff"><strong>//</strong></span>
    <span style="color:#0000ff"><strong>// 	third_leaf-&gt;_parent           = first_internal;</strong></span>
    <span style="color:#0000ff"><strong>// 	third_leaf-&gt;_left_child       = 0;</strong></span>
    <span style="color:#0000ff"><strong>// 	third_leaf-&gt;_right_sib        = 0;</strong></span>
    <span style="color:#0000ff"><strong>// 	third_leaf-&gt;_number           = 2;</strong></span>
    <span style="color:#0000ff"><strong>// 	third_leaf-&gt;_name             = "third leaf";</strong></span>
    <span style="color:#0000ff"><strong>// 	third_leaf-&gt;_edge_length      = 0.2;</strong></span>
    <span style="color:#0000ff"><strong>//</strong></span>
    <span style="color:#0000ff"><strong>// 	_is_rooted             = true;</strong></span>
    <span style="color:#0000ff"><strong>// 	_root                  = root_node;</strong></span>
    <span style="color:#0000ff"><strong>// 	_nleaves               = 3;</strong></span>
    <span style="color:#0000ff"><strong>//</strong></span>
    <span style="color:#0000ff"><strong>// 	// Note that root node is not included in _preorder</strong></span>
    <span style="color:#0000ff"><strong>// 	_preorder.push_back(first_internal);</strong></span>
    <span style="color:#0000ff"><strong>// 	_preorder.push_back(second_internal);</strong></span>
    <span style="color:#0000ff"><strong>// 	_preorder.push_back(first_leaf);</strong></span>
    <span style="color:#0000ff"><strong>// 	_preorder.push_back(second_leaf);</strong></span>
    <span style="color:#0000ff"><strong>// 	_preorder.push_back(third_leaf);</strong></span>
    <span style="color:#0000ff"><strong>//</strong></span>
    <span style="color:#0000ff"><strong>// 	_levelorder.push_back(first_internal);</strong></span>
    <span style="color:#0000ff"><strong>// 	_levelorder.push_back(second_internal);</strong></span>
    <span style="color:#0000ff"><strong>// 	_levelorder.push_back(third_leaf);</strong></span>
    <span style="color:#0000ff"><strong>// 	_levelorder.push_back(first_leaf);</strong></span>
    <span style="color:#0000ff"><strong>// 	_levelorder.push_back(second_leaf);</strong></span>
    <span style="color:#0000ff"><strong>// }</strong></span>

} 

< 4.0 | 4.1 | 4.2 >