traverselib.h

Go to the documentation of this file.

/*
 Copyright (C) 2001-2006, William Joseph.
 All Rights Reserved.

 This file is part of GtkRadiant.

 GtkRadiant is free software; you can redistribute it and/or modify
 it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or
 (at your option) any later version.

 GtkRadiant is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of
 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 GNU General Public License for more details.

 You should have received a copy of the GNU General Public License
 along with GtkRadiant; if not, write to the Free Software
 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */

#if !defined (INCLUDED_TRAVERSELIB_H)
#define INCLUDED_TRAVERSELIB_H

#include "debugging/debugging.h"

#include "scenelib.h"
#include "undolib.h"
#include "container/container.h"

#include <list>
#include <vector>
#include <algorithm>
#include <cassert>

class TraversableObserverInsertOutputIterator
{
    protected:
        scene::Traversable::Observer* m_observer;
    public:
        typedef std::output_iterator_tag iterator_category;
        typedef void difference_type;
        typedef void value_type;
        typedef void pointer;
        typedef void reference;

        TraversableObserverInsertOutputIterator (scene::Traversable::Observer* observer) :
            m_observer(observer)
        {
        }
        TraversableObserverInsertOutputIterator& operator= (const NodeReference& node)
        {
            m_observer->insert(node);
            return *this;
        }
        TraversableObserverInsertOutputIterator& operator= (const NodeSmartReference& node)
        {
            m_observer->insert(node);
            return *this;
        }
        TraversableObserverInsertOutputIterator& operator* ()
        {
            return *this;
        }
        TraversableObserverInsertOutputIterator& operator++ ()
        {
            return *this;
        }
        TraversableObserverInsertOutputIterator& operator++ (int)
        {
            return *this;
        }
};

class TraversableObserverEraseOutputIterator
{
    protected:
        scene::Traversable::Observer* m_observer;
    public:
        typedef std::output_iterator_tag iterator_category;
        typedef void difference_type;
        typedef void value_type;
        typedef void pointer;
        typedef void reference;

        TraversableObserverEraseOutputIterator (scene::Traversable::Observer* observer) :
            m_observer(observer)
        {
        }
        TraversableObserverEraseOutputIterator& operator= (const NodeReference& node)
        {
            m_observer->erase(node);
            return *this;
        }
        TraversableObserverEraseOutputIterator& operator= (const NodeSmartReference& node)
        {
            m_observer->erase(node);
            return *this;
        }
        TraversableObserverEraseOutputIterator& operator* ()
        {
            return *this;
        }
        TraversableObserverEraseOutputIterator& operator++ ()
        {
            return *this;
        }
        TraversableObserverEraseOutputIterator& operator++ (int)
        {
            return *this;
        }
};
typedef UnsortedSet<NodeSmartReference> UnsortedNodeSet;

inline void nodeset_diff (const UnsortedNodeSet& self, const UnsortedNodeSet& other,
        scene::Traversable::Observer* observer)
{
    std::vector<NodeSmartReference> sorted(self.begin(), self.end());
    std::vector<NodeSmartReference> other_sorted(other.begin(), other.end());

    std::sort(sorted.begin(), sorted.end());
    std::sort(other_sorted.begin(), other_sorted.end());

    std::set_difference(sorted.begin(), sorted.end(), other_sorted.begin(), other_sorted.end(),
            TraversableObserverEraseOutputIterator(observer));
    std::set_difference(other_sorted.begin(), other_sorted.end(), sorted.begin(), sorted.end(),
            TraversableObserverInsertOutputIterator(observer));
}

class TraversableNodeSet: public scene::Traversable
{
        UnsortedNodeSet m_children;
        UndoableObject<TraversableNodeSet> m_undo;
        Observer* m_observer;

        void copy (const TraversableNodeSet& other)
        {
            m_children = other.m_children;
        }
        void notifyInsertAll ()
        {
            if (m_observer) {
                for (UnsortedNodeSet::iterator i = m_children.begin(); i != m_children.end(); ++i) {
                    m_observer->insert(*i);
                }
            }
        }
        void notifyEraseAll ()
        {
            if (m_observer) {
                for (UnsortedNodeSet::iterator i = m_children.begin(); i != m_children.end(); ++i) {
                    m_observer->erase(*i);
                }
            }
        }
    public:
        TraversableNodeSet () :
            m_undo(*this), m_observer(0)
        {
        }
        TraversableNodeSet (const TraversableNodeSet& other) :
            scene::Traversable(other), m_undo(*this), m_observer(0)
        {
            copy(other);
            notifyInsertAll();
        }
        ~TraversableNodeSet ()
        {
            notifyEraseAll();
        }
        TraversableNodeSet& operator= (const TraversableNodeSet& other)
        {
            // optimised change-tracking using diff algorithm
            if (m_observer) {
                nodeset_diff(m_children, other.m_children, m_observer);
            }
            copy(other);
            return *this;
        }
        void swap (TraversableNodeSet& other)
        {
            std::swap(m_children, other.m_children);
            std::swap(m_observer, other.m_observer);
        }

        void attach (Observer* observer)
        {
            ASSERT_MESSAGE(m_observer == 0, "TraversableNodeSet::attach: observer cannot be attached");
            m_observer = observer;
            notifyInsertAll();
        }
        void detach (Observer* observer)
        {
            ASSERT_MESSAGE(m_observer == observer, "TraversableNodeSet::detach: observer cannot be detached");
            notifyEraseAll();
            m_observer = 0;
        }
        void insert (scene::Node& node)
        {
            ASSERT_MESSAGE(&node != 0, "TraversableNodeSet::insert: sanity check failed");
            m_undo.save();

            ASSERT_MESSAGE(m_children.find(NodeSmartReference(node)) == m_children.end(), "TraversableNodeSet::insert - element already exists");

            m_children.insert(NodeSmartReference(node));

            if (m_observer) {
                m_observer->insert(node);
            }
        }
        void erase (scene::Node& node)
        {
            ASSERT_MESSAGE(&node != 0, "TraversableNodeSet::erase: sanity check failed");
            m_undo.save();

            ASSERT_MESSAGE(m_children.find(NodeSmartReference(node)) != m_children.end(), "TraversableNodeSet::erase - failed to find element");

            if (m_observer) {
                m_observer->erase(node);
            }

            m_children.erase(NodeSmartReference(node));
        }
        void traverse (const Walker& walker)
        {
            UnsortedNodeSet::iterator i = m_children.begin();
            while (i != m_children.end()) {
                // post-increment the iterator
                Node_traverseSubgraph(*i++, walker);
                // the Walker can safely remove the current node from
                // this container without invalidating the iterator
            }
        }
        bool empty () const
        {
            return m_children.empty();
        }

        void instanceAttach (MapFile* map)
        {
            m_undo.instanceAttach(map);
        }
        void instanceDetach (MapFile* map)
        {
            m_undo.instanceDetach(map);
        }
};

namespace std
{
    inline void swap (TraversableNodeSet& self, TraversableNodeSet& other)
    {
        self.swap(other);
    }
}

class TraversableNode: public scene::Traversable
{
    public:
        TraversableNode () :
            m_node(0), m_observer(0)
        {
        }

        // traverse
        void attach (Observer* observer)
        {
            ASSERT_MESSAGE(m_observer == 0, "TraversableNode::attach - cannot attach observer");
            m_observer = observer;
            if (m_node != 0) {
                m_observer->insert(*m_node);
            }
        }
        void detach (Observer* observer)
        {
            ASSERT_MESSAGE(m_observer == observer, "TraversableNode::detach - cannot detach observer");
            if (m_node != 0) {
                m_observer->erase(*m_node);
            }
            m_observer = 0;
        }
        void insert (scene::Node& node)
        {
            // Throw an exception if there is already a contained node
            assert(m_node == 0);

            m_node = &node;
            node.IncRef();

            if (m_observer != 0) {
                m_observer->insert(node);
            }
        }
        void erase (scene::Node& node)
        {
            assert(m_node == &node);

            if (m_observer != 0) {
                m_observer->erase(node);
            }

            m_node = 0;
            node.DecRef();
        }
        void traverse (const scene::Traversable::Walker& walker)
        {
            if (m_node != 0) {
                Node_traverseSubgraph(*m_node, walker);
            }
        }
        bool empty () const
        {
            return m_node != 0;
        }

        scene::Node& get ()
        {
            return *m_node;
        }

    private:
        scene::Node* m_node;
        Observer* m_observer;
};

class TraversableObserverInsert
{
        scene::Node& node;
    public:
        TraversableObserverInsert (scene::Node& node) :
            node(node)
        {
        }
        void operator() (scene::Traversable::Observer& observer) const
        {
            observer.insert(node);
        }
};

class TraversableObserverErase
{
        scene::Node& node;
    public:
        TraversableObserverErase (scene::Node& node) :
            node(node)
        {
        }
        void operator() (scene::Traversable::Observer& observer) const
        {
            observer.erase(node);
        }
};

class TraversableObserverPairRelay: public ReferencePair<scene::Traversable::Observer> ,
        public scene::Traversable::Observer
{
    public:
        void insert (scene::Node& node)
        {
            forEach(TraversableObserverInsert(node));
        }
        void erase (scene::Node& node)
        {
            forEach(TraversableObserverErase(node));
        }
};

template<typename Type>
class ReferenceSet
{
        typedef UniqueSet<Type*> Values;
        Values m_values;
    public:
        void attach (Type& t)
        {
            m_values.insert(&t);
        }
        void detach (Type& t)
        {
            m_values.erase(&t);
        }
        template<typename Functor>
        void forEach (const Functor& functor)
        {
            for (typename Values::iterator i = m_values.begin(); i != m_values.end(); ++i) {
                functor(*(*i));
            }
        }
};

class TraversableObserverRelay: public ReferenceSet<scene::Traversable::Observer> , public scene::Traversable::Observer
{
    public:
        TraversableObserverRelay ()
        {
        }
        ~TraversableObserverRelay ()
        {
        }

        void insert (scene::Node& node)
        {
            forEach(TraversableObserverInsert(node));
        }
        void erase (scene::Node& node)
        {
            forEach(TraversableObserverErase(node));
        }
};

#endif