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