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 ){
49 TraversableObserverInsertOutputIterator& operator=( const NodeReference& node ){
50 m_observer->insert( node );
53 TraversableObserverInsertOutputIterator& operator=( const NodeSmartReference& node ){
54 m_observer->insert( node );
57 TraversableObserverInsertOutputIterator& operator*() { return *this; }
58 TraversableObserverInsertOutputIterator& operator++() { return *this; }
59 TraversableObserverInsertOutputIterator& operator++( int ) { return *this; }
62 class TraversableObserverEraseOutputIterator
65 scene::Traversable::Observer* m_observer;
67 typedef std::output_iterator_tag iterator_category;
68 typedef void difference_type;
69 typedef void value_type;
71 typedef void reference;
73 TraversableObserverEraseOutputIterator( scene::Traversable::Observer* observer )
74 : m_observer( observer ){
76 TraversableObserverEraseOutputIterator& operator=( const NodeReference& node ){
77 m_observer->erase( node );
80 TraversableObserverEraseOutputIterator& operator=( const NodeSmartReference& node ){
81 m_observer->erase( node );
84 TraversableObserverEraseOutputIterator& operator*() { return *this; }
85 TraversableObserverEraseOutputIterator& operator++() { return *this; }
86 TraversableObserverEraseOutputIterator& operator++( int ) { return *this; }
88 typedef UnsortedSet<NodeSmartReference> UnsortedNodeSet;
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() );
95 std::sort( sorted.begin(), sorted.end() );
96 std::sort( other_sorted.begin(), other_sorted.end() );
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 ) );
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
105 UnsortedNodeSet m_children;
106 UndoableObject<TraversableNodeSet> m_undo;
107 Observer* m_observer;
109 void copy( const TraversableNodeSet& other ){
110 m_children = other.m_children;
112 void notifyInsertAll(){
114 for ( UnsortedNodeSet::iterator i = m_children.begin(); i != m_children.end(); ++i )
116 m_observer->insert( *i );
120 void notifyEraseAll(){
122 for ( UnsortedNodeSet::iterator i = m_children.begin(); i != m_children.end(); ++i )
124 m_observer->erase( *i );
130 : m_undo( *this ), m_observer( 0 ){
132 TraversableNodeSet( const TraversableNodeSet& other )
133 : scene::Traversable( other ), m_undo( *this ), m_observer( 0 ){
137 ~TraversableNodeSet(){
140 TraversableNodeSet& operator=( const TraversableNodeSet& other ){
141 #if 1 // optimised change-tracking using diff algorithm
143 nodeset_diff( m_children, other.m_children, m_observer );
147 TraversableNodeSet tmp( other );
152 void swap( TraversableNodeSet& other ){
153 std::swap( m_children, other.m_children );
154 std::swap( m_observer, other.m_observer );
157 void attach( Observer* observer ){
158 ASSERT_MESSAGE( m_observer == 0, "TraversableNodeSet::attach: observer cannot be attached" );
159 m_observer = observer;
162 void detach( Observer* observer ){
163 ASSERT_MESSAGE( m_observer == observer, "TraversableNodeSet::detach: observer cannot be detached" );
167 /// \brief \copydoc scene::Traversable::insert()
168 void insert( scene::Node& node ){
171 ASSERT_MESSAGE( m_children.find( NodeSmartReference( node ) ) == m_children.end(), "TraversableNodeSet::insert - element already exists" );
173 m_children.insert( NodeSmartReference( node ) );
176 m_observer->insert( node );
179 /// \brief \copydoc scene::Traversable::erase()
180 void erase( scene::Node& node ){
183 ASSERT_MESSAGE( m_children.find( NodeSmartReference( node ) ) != m_children.end(), "TraversableNodeSet::erase - failed to find element" );
186 m_observer->erase( node );
189 m_children.erase( NodeSmartReference( node ) );
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() )
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
202 /// \brief \copydoc scene::Traversable::empty()
204 return m_children.empty();
207 void instanceAttach( MapFile* map ){
208 m_undo.instanceAttach( map );
210 void instanceDetach( MapFile* map ){
211 m_undo.instanceDetach( map );
217 /// \brief Swaps the values of \p self and \p other.
218 /// Overloads std::swap.
219 inline void swap( TraversableNodeSet& self, TraversableNodeSet& other ){
225 class TraversableNode : public scene::Traversable
228 TraversableNode() : m_node( 0 ), m_observer( 0 ){
232 void attach( Observer* observer ){
233 ASSERT_MESSAGE( m_observer == 0, "TraversableNode::attach - cannot attach observer" );
234 m_observer = observer;
236 m_observer->insert( *m_node );
239 void detach( Observer* observer ){
240 ASSERT_MESSAGE( m_observer == observer, "TraversableNode::detach - cannot detach observer" );
242 m_observer->erase( *m_node );
246 void insert( scene::Node& node ){
247 ASSERT_MESSAGE( m_node == 0, "TraversableNode::insert - element already exists" );
252 if ( m_observer != 0 ) {
253 m_observer->insert( node );
256 void erase( scene::Node& node ){
257 ASSERT_MESSAGE( m_node == &node, "TraversableNode::erase - failed to find element" );
259 if ( m_observer != 0 ) {
260 m_observer->erase( node );
266 void traverse( const scene::Traversable::Walker& walker ){
268 Node_traverseSubgraph( *m_node, walker );
281 Observer* m_observer;
284 class TraversableObserverInsert
288 TraversableObserverInsert( scene::Node& node ) : node( node ){
290 void operator()( scene::Traversable::Observer& observer ) const {
291 observer.insert( node );
295 class TraversableObserverErase
299 TraversableObserverErase( scene::Node& node ) : node( node ){
301 void operator()( scene::Traversable::Observer& observer ) const {
302 observer.erase( node );
306 class TraversableObserverPairRelay : public ReferencePair<scene::Traversable::Observer>, public scene::Traversable::Observer
309 void insert( scene::Node& node ){
310 forEach( TraversableObserverInsert( node ) );
312 void erase( scene::Node& node ){
313 forEach( TraversableObserverErase( node ) );
317 template<typename Type>
320 typedef UniqueSet<Type*> Values;
323 void attach( Type& t ){
324 m_values.insert( &t );
326 void detach( Type& t ){
327 m_values.erase( &t );
329 template<typename Functor>
330 void forEach( const Functor& functor ){
331 for ( typename Values::iterator i = m_values.begin(); i != m_values.end(); ++i )
338 class TraversableObserverRelay : public ReferenceSet<scene::Traversable::Observer>, public scene::Traversable::Observer
341 void insert( scene::Node& node ){
342 forEach( TraversableObserverInsert( node ) );
344 void erase( scene::Node& node ){
345 forEach( TraversableObserverErase( node ) );