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