NOW I do it right: #woxblox#
[divverent/netradiant.git] / libs / traverselib.h
1 /*
2 Copyright (C) 2001-2006, William Joseph.
3 All Rights Reserved.
4
5 This file is part of GtkRadiant.
6
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.
11
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.
16
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
20 */
21
22 #if !defined (INCLUDED_TRAVERSELIB_H)
23 #define INCLUDED_TRAVERSELIB_H
24
25 #include "debugging/debugging.h"
26
27 #include "scenelib.h"
28 #include "undolib.h"
29 #include "container/container.h"
30
31 #include <list>
32 #include <vector>
33 #include <algorithm>
34
35 class TraversableObserverInsertOutputIterator 
36 {
37 protected:
38   scene::Traversable::Observer* m_observer;
39 public:
40   typedef std::output_iterator_tag iterator_category;
41   typedef void difference_type;
42   typedef void value_type;
43   typedef void pointer;
44   typedef void reference;
45
46   TraversableObserverInsertOutputIterator(scene::Traversable::Observer* observer) 
47     : m_observer(observer)
48   {
49   }
50   TraversableObserverInsertOutputIterator& operator=(const NodeReference& node)
51   { 
52     m_observer->insert(node);
53     return *this;
54   }
55   TraversableObserverInsertOutputIterator& operator=(const NodeSmartReference& node)
56   { 
57     m_observer->insert(node);
58     return *this;
59   }
60   TraversableObserverInsertOutputIterator& operator*() { return *this; }
61   TraversableObserverInsertOutputIterator& operator++() { return *this; }
62   TraversableObserverInsertOutputIterator& operator++(int) { return *this; }
63 };
64
65 class TraversableObserverEraseOutputIterator 
66 {
67 protected:
68   scene::Traversable::Observer* m_observer;
69 public:
70   typedef std::output_iterator_tag iterator_category;
71   typedef void difference_type;
72   typedef void value_type;
73   typedef void pointer;
74   typedef void reference;
75
76   TraversableObserverEraseOutputIterator(scene::Traversable::Observer* observer) 
77     : m_observer(observer)
78   {
79   }
80   TraversableObserverEraseOutputIterator& operator=(const NodeReference& node)
81   { 
82     m_observer->erase(node);
83     return *this;
84   }
85   TraversableObserverEraseOutputIterator& operator=(const NodeSmartReference& node)
86   { 
87     m_observer->erase(node);
88     return *this;
89   }
90   TraversableObserverEraseOutputIterator& operator*() { return *this; }
91   TraversableObserverEraseOutputIterator& operator++() { return *this; }
92   TraversableObserverEraseOutputIterator& operator++(int) { return *this; }
93 };
94 typedef UnsortedSet<NodeSmartReference> UnsortedNodeSet;
95
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)
98 {
99   std::vector<NodeSmartReference> sorted(self.begin(), self.end());
100   std::vector<NodeSmartReference> other_sorted(other.begin(), other.end());
101
102   std::sort(sorted.begin(), sorted.end());
103   std::sort(other_sorted.begin(), other_sorted.end());
104
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));
107 }
108
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
111 {
112   UnsortedNodeSet m_children;
113   UndoableObject<TraversableNodeSet> m_undo;
114   Observer* m_observer;
115
116   void copy(const TraversableNodeSet& other)
117   {
118     m_children = other.m_children;
119   }
120   void notifyInsertAll()
121   {
122     if(m_observer)
123     {
124       for(UnsortedNodeSet::iterator i = m_children.begin(); i != m_children.end(); ++i)
125       {
126         m_observer->insert(*i);
127       }
128     }
129   }
130   void notifyEraseAll()
131   {
132     if(m_observer)
133     {
134       for(UnsortedNodeSet::iterator i = m_children.begin(); i != m_children.end(); ++i)
135       {
136         m_observer->erase(*i);
137       }
138     }
139   }
140 public:
141   TraversableNodeSet()
142     : m_undo(*this), m_observer(0)
143   {
144   }
145   TraversableNodeSet(const TraversableNodeSet& other)
146     : scene::Traversable(other), m_undo(*this), m_observer(0)
147   {
148     copy(other);
149     notifyInsertAll();
150   }
151   ~TraversableNodeSet()
152   {
153     notifyEraseAll();
154   }
155   TraversableNodeSet& operator=(const TraversableNodeSet& other)
156   {
157 #if 1 // optimised change-tracking using diff algorithm
158     if(m_observer)
159     {
160       nodeset_diff(m_children, other.m_children, m_observer);
161     }
162     copy(other);
163 #else
164     TraversableNodeSet tmp(other);
165     tmp.swap(*this);
166 #endif
167     return *this;
168   }
169   void swap(TraversableNodeSet& other)
170   {
171     std::swap(m_children, other.m_children);
172     std::swap(m_observer, other.m_observer);
173   }
174
175   void attach(Observer* observer)
176   {
177     ASSERT_MESSAGE(m_observer == 0, "TraversableNodeSet::attach: observer cannot be attached");
178     m_observer = observer;
179     notifyInsertAll();
180   }
181   void detach(Observer* observer)
182   {
183     ASSERT_MESSAGE(m_observer == observer, "TraversableNodeSet::detach: observer cannot be detached");
184     notifyEraseAll();
185     m_observer = 0;
186   }
187   /// \brief \copydoc scene::Traversable::insert()
188   void insert(scene::Node& node)
189   {
190     ASSERT_MESSAGE(&node != 0, "TraversableNodeSet::insert: sanity check failed");
191     m_undo.save();
192
193     ASSERT_MESSAGE(m_children.find(NodeSmartReference(node)) == m_children.end(), "TraversableNodeSet::insert - element already exists");
194
195     m_children.insert(NodeSmartReference(node));
196
197     if(m_observer)
198     {
199       m_observer->insert(node);
200     }
201   }
202   /// \brief \copydoc scene::Traversable::erase()
203   void erase(scene::Node& node)
204   {
205     ASSERT_MESSAGE(&node != 0, "TraversableNodeSet::erase: sanity check failed");
206     m_undo.save();
207
208     ASSERT_MESSAGE(m_children.find(NodeSmartReference(node)) != m_children.end(), "TraversableNodeSet::erase - failed to find element");
209
210     if(m_observer)
211     {
212       m_observer->erase(node);
213     }
214
215     m_children.erase(NodeSmartReference(node));
216   }
217   /// \brief \copydoc scene::Traversable::traverse()
218   void traverse(const Walker& walker)
219   {
220     UnsortedNodeSet::iterator i = m_children.begin();
221     while(i != m_children.end())
222     {
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
227     }
228   }
229   /// \brief \copydoc scene::Traversable::empty()
230   bool empty() const
231   {
232     return m_children.empty();
233   }
234
235   void instanceAttach(MapFile* map)
236   {
237     m_undo.instanceAttach(map);
238   }
239   void instanceDetach(MapFile* map)
240   {
241     m_undo.instanceDetach(map);
242   }
243 };
244
245 namespace std
246 {
247   /// \brief Swaps the values of \p self and \p other.
248   /// Overloads std::swap.
249   inline void swap(TraversableNodeSet& self, TraversableNodeSet& other)
250   {
251     self.swap(other);
252   }
253 }
254
255
256 class TraversableNode : public scene::Traversable
257 {
258 public:
259   TraversableNode() : m_node(0), m_observer(0)
260   {
261   }
262
263   // traverse
264   void attach(Observer* observer)
265   {
266     ASSERT_MESSAGE(m_observer == 0, "TraversableNode::attach - cannot attach observer");
267     m_observer = observer;
268     if(m_node != 0)
269     {
270       m_observer->insert(*m_node);
271     }
272   }
273   void detach(Observer* observer)
274   {
275     ASSERT_MESSAGE(m_observer == observer, "TraversableNode::detach - cannot detach observer");
276     if(m_node != 0)
277     {
278       m_observer->erase(*m_node);
279     }
280     m_observer = 0;
281   }
282   void insert(scene::Node& node)
283   {
284     ASSERT_MESSAGE(m_node == 0, "TraversableNode::insert - element already exists");
285
286     m_node = &node;
287     node.IncRef();
288
289     if(m_observer != 0)
290     {
291       m_observer->insert(node);
292     }
293   }
294   void erase(scene::Node& node)
295   {
296     ASSERT_MESSAGE(m_node == &node, "TraversableNode::erase - failed to find element");
297
298     if(m_observer != 0)
299     {
300       m_observer->erase(node);
301     }
302
303     m_node = 0;
304     node.DecRef();
305   }
306   void traverse(const scene::Traversable::Walker& walker)
307   {
308     if(m_node != 0)
309     {
310       Node_traverseSubgraph(*m_node, walker);
311     }
312   }
313   bool empty() const
314   {
315     return m_node != 0;
316   }
317
318   scene::Node& get()
319   {
320     return *m_node;
321   }
322
323 private:
324   scene::Node* m_node;
325   Observer* m_observer;
326 };
327
328 class TraversableObserverInsert
329 {
330   scene::Node& node;
331 public:
332   TraversableObserverInsert(scene::Node& node) : node(node)
333   {
334   }
335   void operator()(scene::Traversable::Observer& observer) const
336   {
337     observer.insert(node);
338   }
339 };
340
341 class TraversableObserverErase
342 {
343   scene::Node& node;
344 public:
345   TraversableObserverErase(scene::Node& node) : node(node)
346   {
347   }
348   void operator()(scene::Traversable::Observer& observer) const
349   {
350     observer.erase(node);
351   }
352 };
353
354 class TraversableObserverPairRelay : public ReferencePair<scene::Traversable::Observer>, public scene::Traversable::Observer
355 {
356 public:
357   void insert(scene::Node& node)
358   {
359     forEach(TraversableObserverInsert(node));
360   }
361   void erase(scene::Node& node)
362   {
363     forEach(TraversableObserverErase(node));
364   }
365 };
366
367 template<typename Type>
368 class ReferenceSet
369 {
370   typedef UniqueSet<Type*> Values;
371   Values m_values;
372 public:
373   void attach(Type& t)
374   {
375     m_values.insert(&t);
376   }
377   void detach(Type& t)
378   {
379     m_values.erase(&t);
380   }
381   template<typename Functor>
382   void forEach(const Functor& functor)
383   {
384     for(typename Values::iterator i = m_values.begin(); i != m_values.end(); ++i)
385     {
386       functor(*(*i));
387     }
388   }
389 };
390
391 class TraversableObserverRelay : public ReferenceSet<scene::Traversable::Observer>, public scene::Traversable::Observer
392 {
393 public:
394   void insert(scene::Node& node)
395   {
396     forEach(TraversableObserverInsert(node));
397   }
398   void erase(scene::Node& node)
399   {
400     forEach(TraversableObserverErase(node));
401   }
402 };
403
404
405 #endif