TreeClone.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/Graph/Tree.h"
#include "Honey/Object/ListenerQueue.h"

namespace honey
{

template<class TreeNode>
class TreeClone
{
public:

    TreeClone()
    {
        _listeners.push_back(&ListenerQueue::create<typename TreeNode::sigDestroy>(bind_fill(&TreeClone::onDestroy, this)));
        _listeners.push_back(&ListenerQueue::create<typename TreeNode::sigSetData>(bind_fill(&TreeClone::onSetData, this)));
        _listeners.push_back(&ListenerQueue::create<typename TreeNode::sigSetKey>(bind_fill(&TreeClone::onSetKey, this)));
        _listeners.push_back(&ListenerQueue::create<typename TreeNode::sigInsertChild>(bind_fill(&TreeClone::onInsertChild, this)));
        _listeners.push_back(&ListenerQueue::create<typename TreeNode::sigRemoveChild>(bind_fill(&TreeClone::onRemoveChild, this)));
    }

    ~TreeClone()                                        { clear(); }


    TreeNode& regNode(const TreeNode& rootNode)
    {
        //Check if node is already registered
        auto clone = getRegClone(rootNode);
        if (clone) return *clone;
        //Create a phantom that will be made into a proper clone after update
        return createPhantom(rootNode);
    }


    TreeNode* unregNode(const TreeNode& rootNode)
    {
        TreeNode* ret = nullptr;

        //We must be completely up-to-date to safely unregister
        update();

        for (auto& e : rootNode.preOrd())
        {
            auto clone = unregNodeSingle(e);
            if (!ret) ret = clone;
        }

        return ret;
    }


    const TreeNode* unregClone(const TreeNode& rootClone)
    {
        const TreeNode* ret = nullptr;

        //We must be completely up-to-date to safely unregister
        update();

        for (auto& e : rootClone.preOrd())
        {
            auto node = getOrigNode(e);
            if (!node) continue;
            auto res = unregNodeSingle(*node);
            if (!ret && res) ret = node;
        }

        return ret;
    }

    void update()
    {
        //Process all signals to bring cloned nodes into the latest up-to-date state
        for (auto& e : _listeners) e->process();

        //Clone any phantoms that were registered or attached as unknown children
        while (!_phantomMap.empty())
            cloneTree(*_phantomMap.begin()->first);
    }

    void clear()
    {
        //Remove listeners from orig nodes
        for (auto& node : keys(_regMap)) for (auto& e : _listeners) const_cast<TreeNode*>(node)->listeners().remove(*e);
        for (auto& e : _listeners) e->clear();

        //Free clone resources
        deleteRange(values(_cloneMap));
        _cloneMap.clear();
        _cloneRMap.clear();
        _regMap.clear();
        _phantomMap.clear();
        _unregMap.clear();
    }

    TreeNode* getClone(const TreeNode& node) const
    {
        auto it = _cloneMap.find(&node);
        if (it == _cloneMap.end()) return nullptr;
        return it->second;
    }

    const TreeNode* getOrigNode(const TreeNode& clone) const
    {
        auto it = _cloneRMap.find(const_cast<TreeNode*>(&clone));
        if (it == _cloneRMap.end()) return nullptr;
        return it->second;
    }

    bool isRegNode(const TreeNode& node) const          { return getRegClone(node); }
    bool isRegClone(const TreeNode& clone) const        { auto node = getOrigNode(clone); return node ? isRegNode(*node) : false; }

    szt cloneCount() const                              { return _cloneMap.size(); }
    szt regNodeCount() const                            { return _regMap.size() + _phantomMap.size(); }

private:

    void onDestroy(TreeNode& src)
    {
        auto clone = getRegClone(src);
        assert(clone && !_phantomMap.count(&src) && !_unregMap.count(&src));
        deleteClone(*clone);
    }

    void onSetData(TreeNode& src, const typename TreeNode::Data& data)
    {
        auto clone = getRegClone(src);
        assert(clone && !_phantomMap.count(&src) && !_unregMap.count(&src));
        clone->setData(data);
    }

    void onSetKey(TreeNode& src, const typename TreeNode::Key& key)
    {
        auto clone = getRegClone(src);
        assert(clone && !_phantomMap.count(&src) && !_unregMap.count(&src));
        clone->setKey(key);
    }

    void onInsertChild(TreeNode& src, TreeNode* childPos, TreeNode& child)
    {
        auto clone = getRegClone(src);
        assert(clone && !_phantomMap.count(&src) && !_unregMap.count(&src));
        
        //A null original child means insert at end of list
        auto it = end(clone->children());
        if (childPos)
        {
            //Original child not null, get the original child's clone
            childPos = getRegClone(*childPos);
            assert(childPos && !_unregMap.count(childPos));
            it = clone->childPos(*childPos);
        }

        //Child could be an unknown node, create phantom if necessary
        auto& cloneChild = regNode(child);

        clone->insertChild(it, cloneChild);
    }

    void onRemoveChild(TreeNode& src, TreeNode& child)
    {
        auto clone = getRegClone(src);
        assert(clone && !_phantomMap.count(&src) && !_unregMap.count(&src));

        //Get the original child's clone
        auto cloneChild = getRegClone(child);
        assert(cloneChild && !_unregMap.count(cloneChild));

        auto it = clone->childPos(*cloneChild);
        assert(it != end(clone->children()));

        clone->removeChild(it);
    }

    void deleteClone(TreeNode& clone)
    {
        auto it = _cloneRMap.find(&clone);
        assert(it != _cloneRMap.end() && it->second && !_phantomMap.count(it->second) && !_unregMap.count(it->second));
        _cloneMap.erase(it->second);
        _regMap.erase(it->second);
        _cloneRMap.erase(it);
        delete_(&clone);
    }

    TreeNode& allocClone(const TreeNode& node)
    {
        assert(!_cloneMap.count(&node));
        auto clone = new TreeNode();
        _cloneMap[&node] = clone;
        _cloneRMap[clone] = &node;
        return *clone;
    }

    TreeNode* phantom(const TreeNode& node) const
    {
        auto it = _phantomMap.find(&node);
        if (it == _phantomMap.end()) return nullptr;
        return it->second;
    }

    TreeNode* getRegClone(const TreeNode& regNode) const
    {
        auto it = _regMap.find(&regNode);
        if (it == _regMap.end()) return nullptr;
        return it->second;
    }

    TreeNode* getUnregClone(const TreeNode& node) const
    {
        auto it = _unregMap.find(&node);
        if (it == _unregMap.end()) return nullptr;
        return it->second;
    }

    TreeNode& createPhantom(const TreeNode& node)
    {
        //Phantom must not already exist
        assert(!_phantomMap.count(&node));
        //Pull a new clone from the unregistered list if possible
        auto phantom = getUnregClone(node);
        if (phantom) _unregMap.erase(&node);
        else phantom = &allocClone(node);
        _phantomMap[&node] = phantom;
        _regMap[&node] = phantom;
        phantom->setParent(nullptr);
        phantom->clearChildren();
        phantom->setData(node.getData());
        phantom->setKey(node.getKey());
        return *phantom;
    }

    void cloneTree(const TreeNode& parent)
    {
        auto phantom = this->phantom(parent);
        assert(phantom);
        _phantomMap.erase(&parent);

        //Recurse through original node's children, clone each child link
        for (auto& child : parent.children())
        {
            auto phantomChild = getRegClone(child);
            if (!phantomChild || phantomChild == this->phantom(child))
            {
                //Unknown node, need to clone it using phantom
                if (!phantomChild) phantomChild = &createPhantom(child);
                cloneTree(child);
            }
            phantom->addChild(*phantomChild);
        }

        for (auto& e : _listeners) const_cast<TreeNode&>(parent).listeners().add(*e);
    }

    TreeNode* unregNodeSingle(const TreeNode& node)
    {
        auto clone = getRegClone(node);
        if (!clone) return nullptr;

        //Clone's parent must not be registered
        assert(!clone->getParent() || !isRegClone(*clone->getParent()),
                    sout()  << "Node can't be unregistered because its parent is registered. Parent Id: "
                            << clone->getParent()->getKey() << " ; Child Id: " << clone->getKey());

        for (auto& e : _listeners) const_cast<TreeNode&>(node).listeners().remove(*e);

        _regMap.erase(&node);
        _phantomMap.erase(&node);
        _unregMap[&node] = clone;

        return clone;
    }

    typedef unordered_map<const TreeNode*, TreeNode*> CloneMap;
    typedef unordered_map<TreeNode*, const TreeNode*> CloneRMap;

    vector<ListenerQueue::Ptr> _listeners;
    CloneMap _cloneMap;
    CloneRMap _cloneRMap;
    CloneMap _regMap;
    CloneMap _phantomMap;
    CloneMap _unregMap;
};

}