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*() { return *this; }
56 TraversableObserverInsertOutputIterator& operator++() { return *this; }
57 TraversableObserverInsertOutputIterator& operator++(int) { return *this; }
60 class TraversableObserverEraseOutputIterator
63 scene::Traversable::Observer* m_observer;
65 typedef std::output_iterator_tag iterator_category;
66 typedef void difference_type;
67 typedef void value_type;
69 typedef void reference;
71 TraversableObserverEraseOutputIterator(scene::Traversable::Observer* observer)
72 : m_observer(observer)
75 TraversableObserverEraseOutputIterator& operator=(const NodeReference& node)
77 m_observer->erase(node);
80 TraversableObserverEraseOutputIterator& operator*() { return *this; }
81 TraversableObserverEraseOutputIterator& operator++() { return *this; }
82 TraversableObserverEraseOutputIterator& operator++(int) { return *this; }
85 typedef UnsortedSet<NodeSmartReference> UnsortedNodeSet;
87 /// \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
88 inline void nodeset_diff(const UnsortedNodeSet& self, const UnsortedNodeSet& other, scene::Traversable::Observer* observer)
90 std::vector<NodeReference> sorted(self.begin(), self.end());
91 std::vector<NodeReference> other_sorted(other.begin(), other.end());
93 std::sort(sorted.begin(), sorted.end());
94 std::sort(other_sorted.begin(), other_sorted.end());
96 std::set_difference(sorted.begin(), sorted.end(), other_sorted.begin(), other_sorted.end(), TraversableObserverEraseOutputIterator(observer));
97 std::set_difference(other_sorted.begin(), other_sorted.end(), sorted.begin(), sorted.end(), TraversableObserverInsertOutputIterator(observer));
100 /// \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.
101 class TraversableNodeSet : public scene::Traversable
103 UnsortedNodeSet m_children;
104 UndoableObject<TraversableNodeSet> m_undo;
105 Observer* m_observer;
107 void copy(const TraversableNodeSet& other)
109 m_children = other.m_children;
111 void notifyInsertAll()
115 for(UnsortedNodeSet::iterator i = m_children.begin(); i != m_children.end(); ++i)
117 m_observer->insert(*i);
121 void notifyEraseAll()
125 for(UnsortedNodeSet::iterator i = m_children.begin(); i != m_children.end(); ++i)
127 m_observer->erase(*i);
133 : m_undo(*this), m_observer(0)
136 TraversableNodeSet(const TraversableNodeSet& other)
137 : scene::Traversable(other), m_undo(*this), m_observer(0)
142 ~TraversableNodeSet()
146 TraversableNodeSet& operator=(const TraversableNodeSet& other)
148 #if 1 // optimised change-tracking using diff algorithm
151 nodeset_diff(m_children, other.m_children, m_observer);
155 TraversableNodeSet tmp(other);
160 void swap(TraversableNodeSet& other)
162 std::swap(m_children, other.m_children);
163 std::swap(m_observer, other.m_observer);
166 void attach(Observer* observer)
168 ASSERT_MESSAGE(m_observer == 0, "TraversableNodeSet::attach: observer cannot be attached");
169 m_observer = observer;
172 void detach(Observer* observer)
174 ASSERT_MESSAGE(m_observer == observer, "TraversableNodeSet::detach: observer cannot be detached");
178 /// \brief \copydoc scene::Traversable::insert()
179 void insert(scene::Node& node)
181 ASSERT_MESSAGE(&node != 0, "TraversableNodeSet::insert: sanity check failed");
184 ASSERT_MESSAGE(m_children.find(NodeSmartReference(node)) == m_children.end(), "TraversableNodeSet::insert - element already exists");
186 m_children.insert(NodeSmartReference(node));
190 m_observer->insert(node);
193 /// \brief \copydoc scene::Traversable::erase()
194 void erase(scene::Node& node)
196 ASSERT_MESSAGE(&node != 0, "TraversableNodeSet::erase: sanity check failed");
199 ASSERT_MESSAGE(m_children.find(NodeSmartReference(node)) != m_children.end(), "TraversableNodeSet::erase - failed to find element");
203 m_observer->erase(node);
206 m_children.erase(NodeSmartReference(node));
208 /// \brief \copydoc scene::Traversable::traverse()
209 void traverse(const Walker& walker)
211 UnsortedNodeSet::iterator i = m_children.begin();
212 while(i != m_children.end())
214 // post-increment the iterator
215 Node_traverseSubgraph(*i++, walker);
216 // the Walker can safely remove the current node from
217 // this container without invalidating the iterator
220 /// \brief \copydoc scene::Traversable::empty()
223 return m_children.empty();
226 void instanceAttach(MapFile* map)
228 m_undo.instanceAttach(map);
230 void instanceDetach(MapFile* map)
232 m_undo.instanceDetach(map);
238 /// \brief Swaps the values of \p self and \p other.
239 /// Overloads std::swap.
240 inline void swap(TraversableNodeSet& self, TraversableNodeSet& other)
247 class TraversableNode : public scene::Traversable
250 TraversableNode() : m_node(0), m_observer(0)
255 void attach(Observer* observer)
257 ASSERT_MESSAGE(m_observer == 0, "TraversableNode::attach - cannot attach observer");
258 m_observer = observer;
261 m_observer->insert(*m_node);
264 void detach(Observer* observer)
266 ASSERT_MESSAGE(m_observer == observer, "TraversableNode::detach - cannot detach observer");
269 m_observer->erase(*m_node);
273 void insert(scene::Node& node)
275 ASSERT_MESSAGE(m_node == 0, "TraversableNode::insert - element already exists");
282 m_observer->insert(node);
285 void erase(scene::Node& node)
287 ASSERT_MESSAGE(m_node == &node, "TraversableNode::erase - failed to find element");
291 m_observer->erase(node);
297 void traverse(const scene::Traversable::Walker& walker)
301 Node_traverseSubgraph(*m_node, walker);
316 Observer* m_observer;
319 class TraversableObserverInsert
323 TraversableObserverInsert(scene::Node& node) : node(node)
326 void operator()(scene::Traversable::Observer& observer) const
328 observer.insert(node);
332 class TraversableObserverErase
336 TraversableObserverErase(scene::Node& node) : node(node)
339 void operator()(scene::Traversable::Observer& observer) const
341 observer.erase(node);
345 class TraversableObserverPairRelay : public ReferencePair<scene::Traversable::Observer>, public scene::Traversable::Observer
348 void insert(scene::Node& node)
350 forEach(TraversableObserverInsert(node));
352 void erase(scene::Node& node)
354 forEach(TraversableObserverErase(node));
358 template<typename Type>
361 typedef UniqueSet<Type*> Values;
372 template<typename Functor>
373 void forEach(const Functor& functor)
375 for(typename Values::iterator i = m_values.begin(); i != m_values.end(); ++i)
382 class TraversableObserverRelay : public ReferenceSet<scene::Traversable::Observer>, public scene::Traversable::Observer
385 void insert(scene::Node& node)
387 forEach(TraversableObserverInsert(node));
389 void erase(scene::Node& node)
391 forEach(TraversableObserverErase(node));