tree.hpp

Go to the documentation of this file.

#ifndef TREE_HPP
#define TREE_HPP

#include <string>
//#include <list> // less efficiant
#include <forward_list>

using std::string;
using std::forward_list;

class TreeException : std::exception {
    private:
        char* _cause; 
    public:
        TreeException(char* cause):
            _cause(cause)
            {}
        
        virtual ~TreeException() throw(){
            // do nothing
        }
        
        virtual const char* what()const throw(){
            return _cause;
        }
};

template <typename T = char>
class Node {
    
    private:
        int _childNbr;
        T _tag;
        forward_list<Node<T>> _children;
    
    public:
        Node(const Node<T> &other):
            _childNbr(other._childNbr),
            _tag(other._tag),
            _children(other._children)
            {}
            
        Node(T data):
        _childNbr(0),
        _tag(data)
        {
            // initialize the simply-linked list
            _children = forward_list<Node<T>>();
        }
        
        ~Node(){
            // usefull ?
            //delete &_children;
            //delete &_tag;
        }
        
        Node<T>& operator=(Node<T> &other){
            // prevent objet copying itself
            if(this != &other){
                this->_childNbr = other._childNbr;
                this->_tag = other._key;
                this->_children = other._children;
            }
            return (*this); // allow a = b = c
        }
        
        bool operator==(const Node<T>& rhs){
            // same adress ⇒ same item
            return &this == &rhs;
        }
        
        bool operator!=(const Node<T>& rhs){
            return &this != &rhs;
            // return not(lhs == rhs);
        }
        
        bool isLeaf(){
            return 0 == _childNbr;
        }
        
        int height(){
            if(isLeaf()){
                return 0;
            }
            else {
                // start heights at zero
                // heights[0] : greatest height, heights[1] : computed height in the loop
                int heights[2] = {0,0};
                // for each child - using C++11 syntax
                for(Node<T> child : _children){
                    // compute child height and store it
                    heights[1] = 1 + child.height();
                    // if computed height is greater then the old one
                    if(heights[0] < heights[1]){
                        // store it as the new greate one
                        heights[0] = heights[1];
                    } // else, nothing
                }
                return heights[0];
            }
        }
        
        void append(T n_data){
            if(isLeaf()){
                // add the value in children list as a new node
                _children.push_front(Node<T>(n_data));
                _childNbr++;
            }
            else {
                std::cout << _tag << std::endl;
                bool undone = true;
                auto it = _children.begin();
                while(it != _children.end() and undone){
                    if(it->_tag != n_data){
                        it->append(n_data);
                        undone = !undone;
                    }
                    else{
                        ++it;
                    }
                }
            }
        }  
        
        void remove(T data){
            // remove child with the right tag
            bool undone = true;
            auto it=_children.begin();
            while(it != it.end() and undone){
                if(it->_tag == data and it->isLeaf()){
                    undone = !undone;
                    delete it;
                }
                ++it;
            }
            if(undone){
                throw TreeException("Element was not removed");
            }
        }
        
        T getTag(){ return _tag; }
        
        bool contains(T element){
            if(isLeaf()){
                return element == _tag;
            }
            else {
                // browse children
                bool here = false;
                auto it = _children.begin();
                while(not here and not it.end()){
                    here = it.contains(element);
                    ++it;
                }
                return here;
            }
        }
        
        string toString(){
            if(isLeaf()){
                return string(_tag);
            }
            else {
                string desc = string(_tag);
                for(Node<T> child: _children){
                    desc += ", " + child.toString();
                }
                return desc;
            }
        }

};

template <typename T = string>
class Tree {
    
    private:
        Node<T> _root; 
    public:
        Tree():
            _root(nullptr)
            {}
            
        Tree(const Tree<T> &other):
            _root(other._root)
            {}
        
        Tree(T element): 
            _root(Node<T>(element))
            {}
            //_root = Node<T>(element);
        
        ~Tree(){
            //delete &_root;
        }
        
        bool contains(T element){
            return _root->contains(element);
        }
        
        int height(){
            return _root.height();
        }
        
        void put(T element){
            _root.append(element);
        }
        
        void remove(T element){
            try{
                _root.remove(element);
            } catch(TreeException ex){
                // ?
            }
        }
        
        string toString(){
            return _root.toString();
        }

};

#endif // TREE_HPP