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