2 Copyright (C) 2001-2006, William Joseph.
5 This file is part of GtkRadiant.
7 GtkRadiant is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or
10 (at your option) any later version.
12 GtkRadiant is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GtkRadiant; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
22 #if !defined (INCLUDED_TRAVERSELIB_H)
23 #define INCLUDED_TRAVERSELIB_H
25 #include "debugging/debugging.h"
29 #include "container/container.h"
35 class TraversableObserverInsertOutputIterator
38 scene::Traversable::Observer* m_observer;
40 typedef std::output_iterator_tag iterator_category;
41 typedef void difference_type;
42 typedef void value_type;
44 typedef void reference;
46 TraversableObserverInsertOutputIterator(scene::Traversable::Observer* observer)
47 : m_observer(observer)
50 TraversableObserverInsertOutputIterator& operator=(const NodeReference& node)
52 m_observer->insert(node);
55 TraversableObserverInsertOutputIterator& operator=(const NodeSmartReference& node)
57 m_observer->insert(node);
60 TraversableObserverInsertOutputIterator& operator*() { return *this; }
61 TraversableObserverInsertOutputIterator& operator++() { return *this; }
62 TraversableObserverInsertOutputIterator& operator++(int) { return *this; }
65 class TraversableObserverEraseOutputIterator
68 scene::Traversable::Observer* m_observer;
70 typedef std::output_iterator_tag iterator_category;
71 typedef void difference_type;
72 typedef void value_type;
74 typedef void reference;
76 TraversableObserverEraseOutputIterator(scene::Traversable::Observer* observer)
77 : m_observer(observer)
80 TraversableObserverEraseOutputIterator& operator=(const NodeReference& node)
82 m_observer->erase(node);
85 TraversableObserverEraseOutputIterator& operator=(const NodeSmartReference& node)
87 m_observer->erase(node);
90 TraversableObserverEraseOutputIterator& operator*() { return *this; }
91 TraversableObserverEraseOutputIterator& operator++() { return *this; }
92 TraversableObserverEraseOutputIterator& operator++(int) { return *this; }
94 typedef UnsortedSet<NodeSmartReference> UnsortedNodeSet;
96 /// \brief Calls \p observer->\c insert for each node that exists only in \p other and \p observer->\c erase for each node that exists only in \p self
97 inline void nodeset_diff(const UnsortedNodeSet& self, const UnsortedNodeSet& other, scene::Traversable::Observer* observer)
99 std::vector<NodeSmartReference> sorted(self.begin(), self.end());
100 std::vector<NodeSmartReference> other_sorted(other.begin(), other.end());
102 std::sort(sorted.begin(), sorted.end());
103 std::sort(other_sorted.begin(), other_sorted.end());
105 std::set_difference(sorted.begin(), sorted.end(), other_sorted.begin(), other_sorted.end(), TraversableObserverEraseOutputIterator(observer));
106 std::set_difference(other_sorted.begin(), other_sorted.end(), sorted.begin(), sorted.end(), TraversableObserverInsertOutputIterator(observer));
109 /// \brief A sequence of node references which notifies an observer of inserts and deletions, and uses the global undo system to provide undo for modifications.
110 class TraversableNodeSet : public scene::Traversable
112 UnsortedNodeSet m_children;
113 UndoableObject<TraversableNodeSet> m_undo;
114 Observer* m_observer;
116 void copy(const TraversableNodeSet& other)
118 m_children = other.m_children;
120 void notifyInsertAll()
124 for(UnsortedNodeSet::iterator i = m_children.begin(); i != m_children.end(); ++i)
126 m_observer->insert(*i);
130 void notifyEraseAll()
134 for(UnsortedNodeSet::iterator i = m_children.begin(); i != m_children.end(); ++i)
136 m_observer->erase(*i);
142 : m_undo(*this), m_observer(0)
145 TraversableNodeSet(const TraversableNodeSet& other)
146 : scene::Traversable(other), m_undo(*this), m_observer(0)
151 ~TraversableNodeSet()
155 TraversableNodeSet& operator=(const TraversableNodeSet& other)
157 #if 1 // optimised change-tracking using diff algorithm
160 nodeset_diff(m_children, other.m_children, m_observer);
164 TraversableNodeSet tmp(other);
169 void swap(TraversableNodeSet& other)
171 std::swap(m_children, other.m_children);
172 std::swap(m_observer, other.m_observer);
175 void attach(Observer* observer)
177 ASSERT_MESSAGE(m_observer == 0, "TraversableNodeSet::attach: observer cannot be attached");
178 m_observer = observer;
181 void detach(Observer* observer)
183 ASSERT_MESSAGE(m_observer == observer, "TraversableNodeSet::detach: observer cannot be detached");
187 /// \brief \copydoc scene::Traversable::insert()
188 void insert(scene::Node& node)
190 ASSERT_MESSAGE(&node != 0, "TraversableNodeSet::insert: sanity check failed");
193 ASSERT_MESSAGE(m_children.find(NodeSmartReference(node)) == m_children.end(), "TraversableNodeSet::insert - element already exists");
195 m_children.insert(NodeSmartReference(node));
199 m_observer->insert(node);
202 /// \brief \copydoc scene::Traversable::erase()
203 void erase(scene::Node& node)
205 ASSERT_MESSAGE(&node != 0, "TraversableNodeSet::erase: sanity check failed");
208 ASSERT_MESSAGE(m_children.find(NodeSmartReference(node)) != m_children.end(), "TraversableNodeSet::erase - failed to find element");
212 m_observer->erase(node);
215 m_children.erase(NodeSmartReference(node));
217 /// \brief \copydoc scene::Traversable::traverse()
218 void traverse(const Walker& walker)
220 UnsortedNodeSet::iterator i = m_children.begin();
221 while(i != m_children.end())
223 // post-increment the iterator
224 Node_traverseSubgraph(*i++, walker);
225 // the Walker can safely remove the current node from
226 // this container without invalidating the iterator
229 /// \brief \copydoc scene::Traversable::empty()
232 return m_children.empty();
235 void instanceAttach(MapFile* map)
237 m_undo.instanceAttach(map);
239 void instanceDetach(MapFile* map)
241 m_undo.instanceDetach(map);
247 /// \brief Swaps the values of \p self and \p other.
248 /// Overloads std::swap.
249 inline void swap(TraversableNodeSet& self, TraversableNodeSet& other)
256 class TraversableNode : public scene::Traversable
259 TraversableNode() : m_node(0), m_observer(0)
264 void attach(Observer* observer)
266 ASSERT_MESSAGE(m_observer == 0, "TraversableNode::attach - cannot attach observer");
267 m_observer = observer;
270 m_observer->insert(*m_node);
273 void detach(Observer* observer)
275 ASSERT_MESSAGE(m_observer == observer, "TraversableNode::detach - cannot detach observer");
278 m_observer->erase(*m_node);
282 void insert(scene::Node& node)
284 ASSERT_MESSAGE(m_node == 0, "TraversableNode::insert - element already exists");
291 m_observer->insert(node);
294 void erase(scene::Node& node)
296 ASSERT_MESSAGE(m_node == &node, "TraversableNode::erase - failed to find element");
300 m_observer->erase(node);
306 void traverse(const scene::Traversable::Walker& walker)
310 Node_traverseSubgraph(*m_node, walker);
325 Observer* m_observer;
328 class TraversableObserverInsert
332 TraversableObserverInsert(scene::Node& node) : node(node)
335 void operator()(scene::Traversable::Observer& observer) const
337 observer.insert(node);
341 class TraversableObserverErase
345 TraversableObserverErase(scene::Node& node) : node(node)
348 void operator()(scene::Traversable::Observer& observer) const
350 observer.erase(node);
354 class TraversableObserverPairRelay : public ReferencePair<scene::Traversable::Observer>, public scene::Traversable::Observer
357 void insert(scene::Node& node)
359 forEach(TraversableObserverInsert(node));
361 void erase(scene::Node& node)
363 forEach(TraversableObserverErase(node));
367 template<typename Type>
370 typedef UniqueSet<Type*> Values;
381 template<typename Functor>
382 void forEach(const Functor& functor)
384 for(typename Values::iterator i = m_values.begin(); i != m_values.end(); ++i)
391 class TraversableObserverRelay : public ReferenceSet<scene::Traversable::Observer>, public scene::Traversable::Observer
394 void insert(scene::Node& node)
396 forEach(TraversableObserverInsert(node));
398 void erase(scene::Node& node)
400 forEach(TraversableObserverErase(node));