Tree.h

#ifndef TREE_H
#define TREE_H
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cassert>
#include <iomanip>

template <typename Item>
struct TreeNode{
    typedef std::vector<TreeNode*> TNvector;

    Item _data;

    TNvector _child;

    TreeNode(const Item& data = Item(),
             const TNvector& children = TNvector()) {
        _data = data;
        _child = children;
    }

    ~TreeNode()                                     {
        for(std::size_t i = 0; i < _child.size(); ++i){
            delete _child[i];
        }
    }

    Item& data()                                    {return _data;}

    TNvector& children()                            {return _child;}

    void setData(const Item& data)                  {_data = data;}

    void setChildren(const TNvector& children)      {_child = children;}

    void addChild(const Item& data)                 {_child.insert(_child.end(),new TreeNode<Item>(data));}

    Item data()                     const           {return _data;}

    TNvector children()             const           {return _child;}

    bool isLeaf()                   const           {return _child.empty();}

    friend std::ostream& operator <<
    (std::ostream& out, const TreeNode<Item>& T)   {
        out << T.data() << ":{ ";
        for(std::size_t i = 0; i < T._child.size(); ++i){
            if(i == T._child.size() - 1)
                out << *T._child[i];
            else
                out << *T._child[i] << " , ";
        }
        out << " } ";
        return out;
    }
};

//Namespace exclusive for TreeNode Functions
namespace rt{
    template <typename Item>
    void clear(TreeNode<Item>*& root){
        if(!root) return;
        for(std::size_t i = 0; i < root->children().size(); ++i)
            clear(root->children()[i]);
        delete root;
        root = nullptr;
    }

    template <typename Item>
    TreeNode<Item>* copy(const TreeNode<Item>* root){
        typename TreeNode<Item>::TNvector tChild;
        for(std::size_t i = 0; i < root->children().size(); ++i)
            tChild.insert(tChild.end(),copy(root->children()[i]));
        return new TreeNode<Item>(root->data(),tChild);
    }

    template <typename Item>
    std::size_t size(const TreeNode<Item>* root){
        if(root == NULL) return 0;
        std::size_t sum = 0;
        typename TreeNode<Item>::TNvector::const_iterator it = root->children().begin();
        while(it != root->children().end()){
            sum += size(*it);
            ++it;
        }
        return 1 + sum;
    }

    template <typename Item>
    std::size_t leaves(const TreeNode<Item>* root){
//        using namespace std;
//        cout << "in leaves" << endl;
        if(!root) return 0;
//        cout << "root is not nULL" << endl;
        if(root->isLeaf()) return 1;
//        cout << "root is not leaf" << endl;


        std::size_t num = 0;
        for(std::size_t i = 0; i < root->children().size(); ++i){
            num += leaves(root->children()[i]);
        }
        return num;
    }

    template <typename Item>
    TreeNode<Item>* search(TreeNode<Item>* root, const Item& item){
        if(!root) return nullptr;
        if(root->data() == item) return root;
        TreeNode<Item>* result;
        for(std::size_t i = 0; i < root->children().size(); ++i){
            result = search(root->children()[i],item);
            if(result) return result;
        }
        return nullptr;
    }

    template <typename Item>
    TreeNode<Item>* parent(TreeNode<Item>* root, const TreeNode<Item>* branch){
        if(!root || !branch) return nullptr;
        if(root == branch) return nullptr;
        TreeNode<Item>* result;
        for(std::size_t i = 0; i < root->children().size(); ++i){
            if(branch == root->children()[i])
                return root;
        }
        for(std::size_t i = 0; i < root->children().size(); ++i){
            result = parent(root->children()[i],branch);
            if(result) return result;
        }
        return nullptr;
    }

    template <typename Item>
    std::vector<TreeNode<Item>*> allLeaves(TreeNode<Item>* root){
        std::vector<TreeNode<Item>*> s;
        if(!root) return s;
        if(root->isLeaf()){
            s.insert(s.begin(),root);
            return s;
        }
        typename TreeNode<Item>::TNvector::const_iterator it = root->children().begin();
        while(it != root->children().end()){
            std::vector<TreeNode<Item>*> t = allLeaves(*it);
            s.insert(s.end(),t.begin(),t.end());
            ++it;
        }
        return s;
    }
}


template <typename Item>
class Tree{
protected:
    TreeNode<Item>* _root;
    TreeNode<Item>* _current;
public:
    Tree(){
        _root = nullptr;
        _current = _root;
    }

    Tree(TreeNode<Item>* root){
        _root = root;
        _current = _root;
    }

    Tree(const Tree<Item>& T){
        _root = rt::copy(T._root);
        _current = _root;
    }

    ~Tree(){
        clear();
    }

    Tree<Item>& operator =(const Tree<Item>& T){
        clear();
        _root = rt::copy(T._root);
        _current = _root;
        return *this;
    }

    void addHere(const Item& item){
        if(!_root){
            _root = new TreeNode<Item>(item);
            _current = _root;
        }
        else _current->addChild(item);
    }

    void addNode(TreeNode<Item>* parent, const Item& item){
        if(!_root){
            _root = new TreeNode<Item>(item);
            _current = _root;
        }
        else{
            if(!inTree(parent)) return;
            parent->addChild(item);
        }
    }

    TreeNode<Item>* search(const Item& item){
        return rt::search(_root,item);
    }

    bool inTree(TreeNode<Item>* node){
        if(node == _root) return true;
        else{
            if(rt::parent(_root,node))
                return true;
            else return false;
        }
    }

    bool empty() const{
        return (!_root);
    }

    void clear(){
        if(!empty()) rt::clear(_root);
    }

    std::size_t leafNum(){
        return rt::leaves(_root);
    }

    TreeNode<Item>* getParent(TreeNode<Item>* branch){
        return rt::parent(_root,branch);
    }

    TreeNode<Item>* getCurrent(){
        return _current;
    }

    void set(const Item& item){
        _current->setData(item);
    }

    void shiftToRoot(){
        _current = _root;
    }

    void shiftUp(){
        if(!hasParent()) return;
        _current = getParent(_current);
    }

    void shiftDown(std::size_t child){
        if(child >= _current->children().size()) return;
        _current = _current->children()[child];
    }

    void shiftTo(TreeNode<Item>* target){
        if(inTree(target))
            _current = target;
    }

    bool hasParent(){
        return (_current != _root);
    }

    bool hasChild(){
        return (!_current->isLeaf());
    }

    std::size_t childNum(){
        return (_current->children().size());
    }

    Item& get(){
        return (_current->data());
    }

    std::size_t size() const{
        return rt::size(_root);
    }

    std::vector<TreeNode<Item>*> getLeaves(){
        return rt::allLeaves(_root);
    }

    friend std::ostream& operator <<(std::ostream& out, const Tree<Item> T){
        out << *T._root;
        return out;
    }
};


#endif // TREE_H