n_ary_tree.hpp

Go to the documentation of this file.

#ifndef N_ARY_TREE_HPP
#define N_ARY_TREE_HPP
 
#include <functional>
 
template <typename TType>
class Node
{
public:
    TType                                     data;
    std::vector<std::unique_ptr<Node<TType>>> _children;
    std::function<TType(std::vector<TType>)>  parentFunct;
    Node(TType value) : data(value) {}
 
    void addChild(const TType& child)
    {
        _children.push_back(std::make_unique<Node<TType>>(child));
    }
 
    Node<TType>* setParentFunct(std::function<TType(std::vector<TType>)> func)
    {
        parentFunct = func;
        return this;
    }
};
 
template <typename TType>
class NAryTree
{
private:
    std::unique_ptr<Node<TType>> _root;
 
public:
    NAryTree() : _root(nullptr) {}
    Node<TType>* setRoot(TType value)
    {
        if (_root == nullptr)
            _root = std::make_unique<Node<TType>>(value);
        return _root.get();
    }
 
    Node<TType>* getRoot() const
    {
        return _root.get();
    }
 
    Node<TType>* addChild(Node<TType>* parent, const TType& value)
    {
        if (!parent)
            return nullptr;
        parent->_children.push_back(std::make_unique<Node<TType>>(value));
        return parent->_children.back().get();
    }
 
    Node<TType>* addChildToRoot(const TType& value)
    {
        return addChild(_root.get(), value);
    }
 
    void preorder(std::function<void(TType)>& funct)
    {
        if (_root != nullptr)
            preorder(_root.get(), funct);
    }
 
    void preorder(Node<TType>* node, std::function<void(TType)>& funct)
    {
        if (node != nullptr)
        {
            funct(node->data);
            for (const auto& child : node->_children)
            {
                preorder(child.get(), funct);
            }
        }
    }
 
    std::vector<TType> preorderValues()
    {
        std::vector<TType> result;
        preorder(_root.get(), result);
        return result;
    }
 
    void preorder(Node<TType>* node, std::vector<TType>& result)
    {
        if (!node)
            return;
        result.push_back(node->data);
        for (const auto& child : node->_children)
            preorder(child.get(), result);
    }
 
    void postorder(std::function<void(TType)>& funct)
    {
        if (_root != nullptr)
            postorder(_root, funct);
    }
 
    void postorder(Node<TType>* node, std::function<void(TType)>& funct)
    {
        if (node != nullptr)
        {
            for (const auto& child : node->_children)
            {
                postorder(child.get(), funct);
            }
            funct(node->data);
        }
    }
 
    std::vector<TType> postorderValues()
    {
        std::vector<TType> result;
        postorder(_root.get(), result);
        return result;
    }
 
    void postorder(Node<TType>* node, std::vector<TType>& result)
    {
        if (!node)
            return;
 
        for (const auto& child : node->_children)
            postorder(child.get(), result);
 
        result.push_back(node->data);
    }
 
    template <typename TResult>
    TResult postorderCompute(Node<TType>* node)
    {
        if (!node)
            return TResult();
 
        std::vector<TResult> childResults;
 
        if (node->parentFunct)
        {
            for (const auto& child : node->_children)
                childResults.push_back(postorderCompute<TResult>(child.get()));
        }
        return node->parentFunct ? node->parentFunct(childResults) : TResult(node->data);
    }
};
#endif