University of Connecticut University of UC Title Fallback Connecticut

Create the Tree class

The next step is to create a C++ class encapsulating the notion of a phylogenetic tree.

Create the Tree class in a file named tree.hpp using the class wizard (Windows) or Project Navigator (Mac).

If using Windows, again specify Inline to keep the wizard from requiring a source file name.

If using Mac, command-click on the project folder in the Project Navigator and choose New File… from the popup menu (be sure to name the new file tree.hpp and check the strom project).

Your IDE (Visual Studio Community on Windows or Xcode on Mac) will produce some default code in any new file it creates, but we will always replace the default code with our own code. Replace everything in the tree.hpp file now with the text below.

Contents of tree.hpp

#pragma once

#include <boost/shared_ptr.hpp>
#include <iostream>
#include <vector>

namespace strom
    {

    //template<class T> class TreeManip;
    //template<class T> class Likelihood;

    template <class T>
    class Tree
	{

        //friend class TreeManip<T>;
        //friend class Likelihood<T>;

	public:
		Tree();
		~Tree();

	private:

		T *                 getRoot();
		void                clear();

		bool                _is_rooted;
		unsigned            _nleaves;
		std::vector<T *>    _preorder;
		std::vector<T>      _nodes; 
  
	public:
		typedef boost::shared_ptr< Tree<T> > SharedPtr;
	};

    template <class T>
    inline Tree<T>::Tree()
	{
	std::cout << "Constructing a Tree" << std::endl;
	clear();
	}

    template <class T>
    inline Tree<T>::~Tree()
	{
	std::cout << "Destroying a Tree" << std::endl;
	}

    template <class T>
    inline T * Tree<T>::getRoot()
	{
	if (_preorder.size() > 0)
	    return _preorder[0]->_parent;
	else
	    return 0;
	}

    template <class T>
    inline void Tree<T>::clear()
	{
	_is_rooted = false;
	_nodes.clear();
	_preorder.clear();
	}

    }

Explanation of tree.hpp

Templates

The Tree class is immediately preceded by template<class T>, which tells the compiler that this class will be a template class. Making Tree a template class allows us to create tree objects with different types of nodes. If the Tree object will be used to only display a tree, we need only have a node class that contains minimal information (e.g. the name of the node and x and y coordinates that store where the node will be drawn, for example). On the other hand, if the Tree object will be used to, for example, summarize a posterior sample of trees, the node class will need to store more information (e.g. information about the split, or bipartition, defined by the node). The C++ class that represents the node (or vertex) of the tree is passed in as T when a Tree object is constructed, so making Tree a template allows us to use a node class that is appropriate for the type of activities the Tree object will be involved in.

You may note that the member functions are all labeled with the inline keyword. Template classes must be entirely specified in a header file, so every member function must be included and specified as an inline function. A function body declared as inline will usually be simply copied into the place where it is called, which is often more efficient than a function call. The compiler gets to decide, however, whether the body of a particular function will actually be inlined at a particular place in the code.

Constructor and destructor

The class declares a public constructor and a public destructor. As we saw for the Node class, the constructor is responsible for reserving the memory needed to store a new Tree object, and the destructor is in charge of freeing that memory. Our Tree constructor calls the member function clear() to initialize the data members of the Tree class. I have (temporarily) placed code in both constructor and destructor to write output. This output will allow us to easily see when a Tree object is being constructed or destructed. We will remove these output lines after we test the class.

Member functions

The accessor function getRoot() is provided to return a pointer to the root node, and the member function clear() is provided to restore a Tree object to its just-constructed state.

Data members

A boolean data member _is_rooted indicates whether the Tree object should be considered rooted or unrooted. An unsigned integer _nleaves stores the number of tip nodes (leaves) in the tree. Finally, two standard vector data members store nodes. The vector _nodes stores the node objects themselves, while the vector _preorder stores pointers to the node objects in _nodes.

Shared pointer

SharedPtr type is defined that represents a shared pointer (also known as a smart pointer) to our Tree class. Smart pointers keep track of how many references there are to a particular object. Once no other object is holding on to a reference (i.e. is pointing to) an object, the smart pointer takes care of deleting the object automatically. This makes memory management much easier because you, as the programmer, do not have to remember to delete objects as long as you always manage them via smart pointers.

Note that the type name we’ve defined is just SharedPtr, which is not specific to Tree. The fact that this type is defined within the Tree class declaration, however, means that we will always know the object referred to by this SharedPtr because to use it we will have to qualify it by the class name: Tree::SharedPtr tree.

Friends

As for the Node class, the TreeManip and Likelihood classes will need to have access to the private member functions and data members of the Tree class. Because TreeManip and Likelihood have not yet been created, these friend declarations are currently commented out.