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