allow undo “make detail/structural”, <3 @SpiKe, thanks @Garux, fix #76
[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         m_undo.save();
170
171         ASSERT_MESSAGE( m_children.find( NodeSmartReference( node ) ) == m_children.end(), "TraversableNodeSet::insert - element already exists" );
172
173         m_children.insert( NodeSmartReference( node ) );
174
175         if ( m_observer ) {
176                 m_observer->insert( node );
177         }
178 }
179 /// \brief \copydoc scene::Traversable::erase()
180 void erase( scene::Node& node ){
181         m_undo.save();
182
183         ASSERT_MESSAGE( m_children.find( NodeSmartReference( node ) ) != m_children.end(), "TraversableNodeSet::erase - failed to find element" );
184
185         if ( m_observer ) {
186                 m_observer->erase( node );
187         }
188
189         m_children.erase( NodeSmartReference( node ) );
190 }
191 /// \brief \copydoc scene::Traversable::traverse()
192 void traverse( const Walker& walker ){
193         UnsortedNodeSet::iterator i = m_children.begin();
194         while ( i != m_children.end() )
195         {
196                 // post-increment the iterator
197                 Node_traverseSubgraph( *i++, walker );
198                 // the Walker can safely remove the current node from
199                 // this container without invalidating the iterator
200         }
201 }
202 /// \brief \copydoc scene::Traversable::empty()
203 bool empty() const {
204         return m_children.empty();
205 }
206
207 void instanceAttach( MapFile* map ){
208         m_undo.instanceAttach( map );
209 }
210 void instanceDetach( MapFile* map ){
211         m_undo.instanceDetach( map );
212 }
213 };
214
215 namespace std
216 {
217 /// \brief Swaps the values of \p self and \p other.
218 /// Overloads std::swap.
219 inline void swap( TraversableNodeSet& self, TraversableNodeSet& other ){
220         self.swap( other );
221 }
222 }
223
224
225 class TraversableNode : public scene::Traversable
226 {
227 public:
228 TraversableNode() : m_node( 0 ), m_observer( 0 ){
229 }
230
231 // traverse
232 void attach( Observer* observer ){
233         ASSERT_MESSAGE( m_observer == 0, "TraversableNode::attach - cannot attach observer" );
234         m_observer = observer;
235         if ( m_node != 0 ) {
236                 m_observer->insert( *m_node );
237         }
238 }
239 void detach( Observer* observer ){
240         ASSERT_MESSAGE( m_observer == observer, "TraversableNode::detach - cannot detach observer" );
241         if ( m_node != 0 ) {
242                 m_observer->erase( *m_node );
243         }
244         m_observer = 0;
245 }
246 void insert( scene::Node& node ){
247         ASSERT_MESSAGE( m_node == 0, "TraversableNode::insert - element already exists" );
248
249         m_node = &node;
250         node.IncRef();
251
252         if ( m_observer != 0 ) {
253                 m_observer->insert( node );
254         }
255 }
256 void erase( scene::Node& node ){
257         ASSERT_MESSAGE( m_node == &node, "TraversableNode::erase - failed to find element" );
258
259         if ( m_observer != 0 ) {
260                 m_observer->erase( node );
261         }
262
263         m_node = 0;
264         node.DecRef();
265 }
266 void traverse( const scene::Traversable::Walker& walker ){
267         if ( m_node != 0 ) {
268                 Node_traverseSubgraph( *m_node, walker );
269         }
270 }
271 bool empty() const {
272         return m_node != 0;
273 }
274
275 scene::Node& get(){
276         return *m_node;
277 }
278
279 private:
280 scene::Node* m_node;
281 Observer* m_observer;
282 };
283
284 class TraversableObserverInsert
285 {
286 scene::Node& node;
287 public:
288 TraversableObserverInsert( scene::Node& node ) : node( node ){
289 }
290 void operator()( scene::Traversable::Observer& observer ) const {
291         observer.insert( node );
292 }
293 };
294
295 class TraversableObserverErase
296 {
297 scene::Node& node;
298 public:
299 TraversableObserverErase( scene::Node& node ) : node( node ){
300 }
301 void operator()( scene::Traversable::Observer& observer ) const {
302         observer.erase( node );
303 }
304 };
305
306 class TraversableObserverPairRelay : public ReferencePair<scene::Traversable::Observer>, public scene::Traversable::Observer
307 {
308 public:
309 void insert( scene::Node& node ){
310         forEach( TraversableObserverInsert( node ) );
311 }
312 void erase( scene::Node& node ){
313         forEach( TraversableObserverErase( node ) );
314 }
315 };
316
317 template<typename Type>
318 class ReferenceSet
319 {
320 typedef UniqueSet<Type*> Values;
321 Values m_values;
322 public:
323 void attach( Type& t ){
324         m_values.insert( &t );
325 }
326 void detach( Type& t ){
327         m_values.erase( &t );
328 }
329 template<typename Functor>
330 void forEach( const Functor& functor ){
331         for ( typename Values::iterator i = m_values.begin(); i != m_values.end(); ++i )
332         {
333                 functor( *( *i ) );
334         }
335 }
336 };
337
338 class TraversableObserverRelay : public ReferenceSet<scene::Traversable::Observer>, public scene::Traversable::Observer
339 {
340 public:
341 void insert( scene::Node& node ){
342         forEach( TraversableObserverInsert( node ) );
343 }
344 void erase( scene::Node& node ){
345         forEach( TraversableObserverErase( node ) );
346 }
347 };
348
349
350 #endif