Tree.h

Go to the documentation of this file.

// Honeycomb, Copyright (C) 2015 NewGamePlus Inc.  Distributed under the Boost Software License v1.0.
#pragma once

#include "Honey/String/Id.h"
#include "Honey/Object/ListenerList.h"
#include "Honey/Memory/SmallAllocator.h"

namespace honey
{


template<class Data_, class Key_ = Id, template<class> class Alloc = SmallAllocator>
class TreeNode
{
    template<class, class, template<class> class> friend class TreeNode;
public:
    typedef Data_ Data;
    typedef Key_ Key;
    
    typedef list<deref_wrap<TreeNode>, Alloc<deref_wrap<TreeNode>>> ChildList;
    typedef typename ChildList::iterator                ChildIter;
    typedef typename ChildList::const_iterator          ChildConstIter;
    typedef typename ChildList::reverse_iterator        ChildIterR;
    typedef typename ChildList::const_reverse_iterator  ChildConstIterR;
    
    typedef stdutil::unordered_multimap<Key, deref_wrap<TreeNode>, Alloc> ChildMap;
    typedef typename ChildMap::iterator                 ChildMapIter;
    typedef typename ChildMap::const_iterator           ChildMapConstIter;

    SIGNAL_DECL(TreeNode)
    SIGNAL(sigDestroy, (TreeNode& src));
    SIGNAL(sigSetData, (TreeNode& src, Data data));
    SIGNAL(sigSetKey, (TreeNode& src, Key key));
    SIGNAL(sigInsertChild, (TreeNode& src, TreeNode* childPos, TreeNode& child));
    SIGNAL(sigRemoveChild, (TreeNode& src, TreeNode& child));
    SIGNAL(sigSetParent, (TreeNode& src, TreeNode* parent));

    TreeNode()                                                  { init(); }
    TreeNode(const Data& data)                                  : _data(data) { init(); }
    TreeNode(const Data& data, const Key& key)                  : _data(data), _key(key) { init(); }

    virtual ~TreeNode()
    {
        setParent(nullptr);
        clearChildren();
        if (hasListenerList()) _listenerList().template dispatch<sigDestroy>(*this);
    }

    void setData(const Data& data)
    {
        _data = data;
        if (hasListenerList()) _listenerList().template dispatch<sigSetData>(*this, _data);
    }

    const Data& getData() const                                 { return _data; }
    Data& getData()                                             { return _data; }
    operator const Data&() const                                { return getData(); }
    operator Data&()                                            { return getData(); }
    const Data& operator*() const                               { return getData(); }
    Data& operator*()                                           { return getData(); }
    const Data& operator->() const                              { return getData(); }
    Data& operator->()                                          { return getData(); }

    void setKey(const Key& key)
    {
        if (hasParent() && _key != _keyNull)
        {
            //Erase key in parent
            ChildMapIter itMap = _parent->childMapIter(*this);
            assert(itMap != _parent->_childMap.end(), sout() << "Child not found in parent's children map. Parent Id: " << _parent->_key << " ; Child Id: " << _key);
            _parent->_childMap.erase(itMap);
        }
        
        _key = key;

        //Insert the child at new key
        if (hasParent()) _parent->_childMap.insert(make_pair(_key, this));
        if (hasListenerList()) _listenerList().template dispatch<sigSetKey>(*this, _key);
    }

    Key& getKey()                                               { return _key; }
    const Key& getKey() const                                   { return _key; }

    ChildIter setParent(TreeNode* parent)
    {
        if (hasParent()) _parent->removeChild(*this);
        if (parent) return parent->addChild(*this);
        return _childList.end();
    }

    const TreeNode* getParent() const                           { return _parent; }
    TreeNode* getParent()                                       { return _parent; }
    bool hasParent() const                                      { return _parent; }

    ChildIter addChild(TreeNode& child)
    {
        assert(&child != this);
        if (child.hasParent()) child._parent->removeChild(child);
        return insertChild(_childList.end(), child);
    }

    ChildIter setChild(ChildIter pos, TreeNode& child)          { return insertChild(removeChild(pos), child); }

    ChildIter insertChild(ChildIter pos, TreeNode& child)
    {
        assert(&child != this);
        //Remove child from parent
        if (child.hasParent()) child._parent->removeChild(child);
        if (child.hasListenerList()) child._listenerList().template dispatch<sigSetParent>(child, this);
        child._parent = this;
        //Insert child into list
        child._itSib = _childList.insert(pos, &child);
        //Insert child key into map
        if (child._key != _keyNull) _childMap.insert(make_pair(child._key, &child));
        if (hasListenerList()) _listenerList().template dispatch<sigInsertChild>(*this, pos != _childList.end() ? pos->ptr() : nullptr, child);
        return child._itSib;
    }
    
    ChildIter removeChild(TreeNode& child)
    {
        ChildIter itChild = childPos(child);
        if (itChild != _childList.end()) return removeChild(itChild);
        return _childList.end(); //Child not in parent
    }

    ChildIter removeChild(ChildIter pos)
    {
        TreeNode& child = *pos;
        assert(child._parent == this);
        if (hasListenerList()) _listenerList().template dispatch<sigRemoveChild>(*this, child);
        if (child.hasListenerList()) child._listenerList().template dispatch<sigSetParent>(child, nullptr);
        child._parent = nullptr;
        child._itSib = child._childList.end();
        //Erase from child list
        auto itRet = _childList.erase(pos);
        //Erase from map
        if (child._key != _keyNull)
        {
            ChildMapIter itMap = childMapIter(child);
            assert(itMap != _childMap.end(), sout() << "Child not found in parent's children map. Parent Id: " << _key << " ; Child Id: " << child._key);
            _childMap.erase(itMap);
        }
        return itRet;
    }

    void clearChildren()                                        { while (hasChildren()) removeChild(--_childList.end()); }

    Range_<ChildConstIter, ChildConstIter> children() const     { return range(_childList.begin(), _childList.end()); }
    Range_<ChildIter, ChildIter> children()                     { return range(_childList.begin(), _childList.end()); }

    Range_<ChildConstIterR, ChildConstIterR> childrenR() const  { return range(_childList.rbegin(), _childList.rend()); }
    Range_<ChildIterR, ChildIterR> childrenR()                  { return range(_childList.rbegin(), _childList.rend()); }

    szt childCount() const                                      { return _childList.size(); }

    bool hasChildren() const                                    { return childCount() > 0; }

    ChildConstIter childPos(const Key& key) const
    {
        auto it = _childMap.find(key);
        return it != _childMap.end() ? ChildConstIter(it->second->_itSib) : _childList.end();
    }
    ChildIter childPos(const Key& key)                          { auto ret = const_cast<const TreeNode*>(this)->childPos(key); return reinterpret_cast<ChildIter&>(ret); }
    
    ChildConstIter childPos(const TreeNode& child) const        { return child._parent == this ? ChildConstIter(child._itSib) : _childList.end(); }
    ChildIter childPos(const TreeNode& child)                   { auto ret = const_cast<const TreeNode*>(this)->childPos(child); return reinterpret_cast<ChildIter&>(ret); }

    const TreeNode* child(const Key& key) const
    {
        auto it = _childMap.find(key);
        return it != _childMap.end() ? it->second.ptr() : nullptr;
    }
    TreeNode* child(const Key& key)                             { return const_cast<TreeNode*>(const_cast<const TreeNode*>(this)->child(key)); }
    
    bool hasChild(const TreeNode& child) const                  { return childPos(child) != _childList.end(); }

    Range_<ChildMapIter, ChildMapIter> children(const Key& key) { return range(_childMap.equal_range(key)); }
    Range_<ChildMapConstIter, ChildMapConstIter> children(const Key& key) const
                                                                { return range(_childMap.equal_range(key)); }

    Range_<ChildConstIter, ChildConstIter> sibNext() const      { return hasParent() ? range(ChildConstIter(next(_itSib)), ChildConstIter(_parent->_childList.end())) : range(_childList.end(), _childList.end()); }
    Range_<ChildIter, ChildIter> sibNext()                      { auto ret = const_cast<const TreeNode*>(this)->sibNext(); return reinterpret_cast<Range_<ChildIter, ChildIter>&>(ret); }

    Range_<ChildConstIterR, ChildConstIterR> sibPrev() const    { return hasParent() ? range(ChildConstIterR(_itSib), ChildConstIterR(_parent->_childList.rend())) : range(_childList.rend(), _childList.rend()); }
    Range_<ChildIterR, ChildIterR> sibPrev()                    { auto ret = const_cast<const TreeNode*>(this)->sibPrev(); return reinterpret_cast<Range_<ChildIterR, ChildIterR>&>(ret); }
    
    szt sibCount() const                                        { return hasParent() ? _parent->childCount() - 1 : 0; }

    bool sibHasNext() const                                     { return hasParent() ? next(_itSib) != _parent->_childList.end() : false; }
    bool sibHasPrev() const                                     { return hasParent() ? ChildIterR(_itSib) != _parent->_childList.rend() : false; }

    const TreeNode& root() const
    {
        TreeNode* parent = this;
        while (parent->hasParent()) parent = parent->_parent;
        return *parent;
    }
    TreeNode& root()                                            { return const_cast<TreeNode&>(const_cast<const TreeNode*>(this)->root()); }

    bool isRoot() const                                         { return !hasParent(); }
    bool isLeaf() const                                         { return !hasChildren(); }

    bool isAncestor(const TreeNode& ancestor) const
    {
        for (auto node = getParent(); node; node = node->getParent())
            if (node == &ancestor) return true;
        return false;
    }

    bool isAncestorOf(const TreeNode& node) const               { return node.isAncestor(*this); }

    const TreeNode* findNode(const Key& key) const
    {
        if (_key == key) return this;
        for (auto& e : preOrd())
        {
            auto child = e.child(key);
            if (child) return child;
        }
        return nullptr;
    }
    TreeNode* findNode(const Key& key)                          { return const_cast<TreeNode*>(const_cast<const TreeNode*>(this)->findNode(key)); }


    template<class TreeNode>
    class PreOrdIter_
    {
    public:
        typedef std::bidirectional_iterator_tag     iterator_category;
        typedef TreeNode                            value_type;
        typedef sdt                                 difference_type;
        typedef TreeNode*                           pointer;
        typedef TreeNode&                           reference;
        
        PreOrdIter_()                                           : _root(nullptr), _node(nullptr), _skipChildren(false), _count(0) {}

        PreOrdIter_(TreeNode* root, bool end) :
            _skipChildren(false),
            _count(0)
        {
            assert(root);
            _root = root;
            _node = (!end) ? _root : _root->_parent;
        }

        PreOrdIter_& operator++()
        {
            if (_node == _root->_parent) return *this;

            if (!_node->isLeaf() && !_skipChildren)
            {
                //Non-leaf, move into first child
                _node = _node->_childList.begin()->ptr();
            }
            else
            {
                //Leaf, select next sibling.  If there is none then backtrack through parents until sibling is found.
                _skipChildren = false;
                TreeNode* parent;
                for (parent = _node; parent != _root->_parent; parent = parent->_parent)
                {
                    //Don't select siblings of root
                    if (parent != _root && parent->sibHasNext())
                    {
                        parent = begin(parent->sibNext())->ptr();
                        break;
                    }
                }

                _node = parent;
            }

            ++_count;
            return *this;
        }

        PreOrdIter_& operator--()
        {
            if (_node == _root) return *this;

            //If we are at traversal end / have a prev sibling...
            if (_node == _root->_parent || _node->sibHasPrev())
            {
                //Select deepest last child of root / prev sibling
                _node = (_node == _root->_parent) ? _root : begin(_node->sibPrev())->ptr();
                while (_node->childCount() > 0) _node = (--_node->_childList.end())->ptr();
            }
            else
            {
                //No previous sibling, go to parent
                _node = _node->_parent;
            }

            --_count;
            return *this;
        }

        PreOrdIter_ operator++(int)                             { auto tmp = *this; ++*this; return tmp; }
        PreOrdIter_ operator--(int)                             { auto tmp = *this; --*this; return tmp; }

        bool operator==(const PreOrdIter_& rhs) const           { return _node == rhs._node; }
        bool operator!=(const PreOrdIter_& rhs) const           { return !operator==(rhs); }

        reference operator*() const                             { assert(_node); return *_node; }
        pointer operator->() const                              { return &operator*(); }

        void skipChildren()                                     { _skipChildren = true; }

        szt count() const                                       { return _count; }

    private:
        TreeNode*   _root;
        TreeNode*   _node;
        bool        _skipChildren;
        szt         _count;
    };

    typedef PreOrdIter_<TreeNode> PreOrdIter;
    typedef PreOrdIter_<const TreeNode> PreOrdConstIter;

    typedef std::reverse_iterator<PreOrdConstIter> PreOrdConstIterR;
    typedef std::reverse_iterator<PreOrdIter> PreOrdIterR;

    Range_<PreOrdConstIter, PreOrdConstIter>    preOrd() const  { return range(PreOrdConstIter(this, false), PreOrdConstIter(this, true)); }
    Range_<PreOrdIter, PreOrdIter>              preOrd()        { return range(PreOrdIter(this, false), PreOrdIter(this, true)); }

    Range_<PreOrdConstIterR, PreOrdConstIterR>  preOrdR() const { auto range_ = preOrd(); return range(PreOrdConstIterR(end(range_)), PreOrdConstIterR(begin(range_))); }
    Range_<PreOrdIterR, PreOrdIterR>            preOrdR()       { auto range_ = preOrd(); return range(PreOrdIterR(end(range_)), PreOrdIterR(begin(range_))); }
    
    ListenerList& listeners()                                   { return _listenerList(); }
    
private:
    void init()
    {
        _parent = nullptr;
        _itSib = _childList.end();
    }
    
    ChildMapIter childMapIter(TreeNode& child)                  { return stdutil::findVal(_childMap, child._key, &child); }
    
    ListenerList& _listenerList()                               { if (_listenerList_p) return *_listenerList_p; return *(_listenerList_p = make_unique<ListenerList>()); }
    bool hasListenerList() const                                { return _listenerList_p; }

    Data _data;
    TreeNode* _parent;
    ChildIter _itSib;
    ChildList _childList;
    Key _key;
    ChildMap _childMap;
    UniquePtr<ListenerList> _listenerList_p;

    static const Key _keyNull;  
};

template<class Data, class Key, template<class> class Alloc>
const Key TreeNode<Data,Key,Alloc>::_keyNull;

}