Tree.hpp

// Copyright 2021 Arnaud Becheler    <abechele@umich.edu>
 
 
#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED
 
#include <vector>
 
namespace quetzal
{
namespace coalescence
{
namespace container
{
template <class CellT> class Tree
{
  private:
    Tree<CellT> *m_parent;
    CellT m_cell;
    std::vector<Tree<CellT>> m_children;
 
  public:
    Tree();
    Tree(const CellT &cell);
    Tree(CellT &&cell) noexcept;
    Tree(const Tree<CellT> &other);
    Tree(Tree<CellT> &&other) noexcept;
    Tree(CellT &&cell, std::vector<Tree<CellT>> &&children) noexcept;
    Tree<CellT> &operator=(const Tree<CellT> &other);
    Tree<CellT> &operator=(Tree<CellT> &&other) noexcept;
    const CellT &cell() const;
    CellT &cell();
    Tree<CellT> &add_child(const Tree<CellT> &subtree);
    Tree<CellT> &add_child(Tree<CellT> &&subtree) noexcept;
    Tree<CellT> &add_child(CellT &&cell) noexcept;
    bool has_parent() const
    {
        return m_parent != nullptr;
    }
    bool has_children() const;
    template <typename UnaryOperation> void visit_cells_by_pre_order_DFS(UnaryOperation op) const
    {
        op(this->cell());
        for (auto const &child : this->m_children)
        {
            child.visit_cells_by_pre_order_DFS(op);
        }
    }
    template <class UnaryOperation> void visit_subtrees_by_pre_order_DFS(UnaryOperation op)
    {
        op(*this);
        for (auto &child : this->m_children)
        {
            child.visit_subtrees_by_pre_order_DFS(op);
        }
    }
 
    template <typename Op1, typename Op2, typename Op3>
    void visit_subtrees_by_generic_DFS(Op1 preorder, Op2 inorder, Op3 postorder)
    {
        preorder(*this);
        for (auto &child : this->m_children)
        {
            child.visit_subtrees_by_generic_DFS(preorder, inorder, postorder);
            inorder(*this);
        }
        postorder(*this);
    }
 
    auto &parent()
    {
        assert(has_parent());
        return *m_parent;
    }
 
    auto const &parent() const
    {
        assert(has_parent());
        return *m_parent;
    }
 
    unsigned int nb_children() const
    {
        return m_children.size();
    }
    template <typename UnaryOperation> void visit_leaves_cells_by_DFS(UnaryOperation op) const
    {
        if (has_children())
        {
            for (auto const &child : this->m_children)
            {
                child.visit_leaves_cells_by_DFS(op);
            }
        }
        else
        {
            op(this->cell());
        }
    }
}; // end class Tree
 
template <typename CellT> Tree<CellT>::Tree() : m_parent(nullptr), m_cell(), m_children()
{
}
 
template <typename CellT> Tree<CellT>::Tree(const CellT &cell) : m_parent(nullptr), m_cell(cell), m_children()
{
}
 
template <typename CellT>
Tree<CellT>::Tree(CellT &&cell) noexcept : m_parent(nullptr), m_cell(std::move(cell)), m_children()
{
}
 
template <class CellT>
Tree<CellT>::Tree(const Tree<CellT> &other) : m_parent(nullptr), m_cell(other.m_cell), m_children(other.m_children)
{
    for (Tree<CellT> &child : m_children)
        child.m_parent = this;
}
 
template <class CellT>
Tree<CellT>::Tree(Tree<CellT> &&other) noexcept
    : m_parent(nullptr), m_cell(std::move(other.m_cell)), m_children(std::move(other.m_children))
{
    for (Tree<CellT> &child : m_children)
        child.m_parent = this;
}
 
template <class CellT>
Tree<CellT>::Tree(CellT &&cell, std::vector<Tree<CellT>> &&children) noexcept
    : m_parent(nullptr), m_cell(std::move(cell)), m_children(std::move(children))
{
    for (Tree<CellT> &child : m_children)
        child.m_parent = this;
}
 
template <class CellT> Tree<CellT> &Tree<CellT>::operator=(const Tree<CellT> &other)
{
    Tree<CellT> otherCopy(other);
    *this = std::move(otherCopy);
    return *this;
}
 
template <class CellT> Tree<CellT> &Tree<CellT>::operator=(Tree<CellT> &&other) noexcept
{
    m_cell = std::move(other.m_cell);
    m_children = std::move(other.m_children);
    for (Tree<CellT> &child : m_children)
        child.m_parent = this;
    return *this;
}
 
template <class CellT> const CellT &Tree<CellT>::cell() const
{
    return m_cell;
}
 
template <class CellT> CellT &Tree<CellT>::cell()
{
    return m_cell;
}
 
template <class CellT> Tree<CellT> &Tree<CellT>::add_child(const Tree<CellT> &subtree)
{
    Tree<CellT> otherCopy(subtree);
    otherCopy.m_parent = this;
    m_children.push_back(std::move(otherCopy));
    return *this;
}
 
template <class CellT> Tree<CellT> &Tree<CellT>::add_child(Tree<CellT> &&subtree) noexcept
{
    subtree.m_parent = this;
    m_children.push_back(std::move(subtree));
    return *this;
}
 
template <class CellT> Tree<CellT> &Tree<CellT>::add_child(CellT &&cell) noexcept
{
    Tree<CellT> subtree(std::move(cell));
    subtree.m_parent = this;
    m_children.push_back(std::move(subtree));
    return m_children.back();
}
 
template <class CellT> bool Tree<CellT>::has_children() const
{
    return !m_children.empty();
}
} // end namespace container
} // end namespace coalescence
} // end namespace quetzal
 
#endif