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