Changeset 2114:677ea6c8169a in lemon-0.x

Timestamp:

06/28/06 18:27:44 (19 years ago)

Author:

Balazs Dezso

Branch:

default

Phase:

public

Convert:

svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2820

Message:

new snapshot

File:

• lemon/list_graph.h (modified) (8 diffs)

lemon/list_graph.h

@@ -347 +347 @@
     /// Changes the target of \c e to \c n
     ///
-    ///\note The <tt>Edge</tt>s and <tt>OutEdge</tt>s
-    ///referencing the changed edge remain
-    ///valid. However <tt>InEdge</tt>s are invalidated.
+    ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
+    ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
+    ///invalidated.
     void changeTarget(Edge e, Node n) { 
       Parent::changeTarget(e,n); 
@@ -357 +357 @@
     /// Changes the source of \c e to \c n
     ///
-    ///\note The <tt>Edge</tt>s and <tt>InEdge</tt>s
-    ///referencing the changed edge remain
-    ///valid. However <tt>OutEdge</tt>s are invalidated.
+    ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
+    ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
+    ///invalidated.
     void changeSource(Edge e, Node n) { 
       Parent::changeSource(e,n);
@@ -366 +366 @@
     /// Invert the direction of an edge.
 
-    ///\note The <tt>Edge</tt>s
-    ///referencing the changed edge remain
-    ///valid. However <tt>OutEdge</tt>s  and <tt>InEdge</tt>s are invalidated.
+    ///\note The <tt>Edge</tt>s referencing the changed edge remain
+    ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
+    ///invalidated.
     void reverseEdge(Edge e) {
       Node t=target(e);
@@ -439 +439 @@
     ///feature.
     ///\todo It could be implemented in a bit faster way.
-    Node split(Node n, bool connect = true) 
-    {
+    Node split(Node n, bool connect = true) {
       Node b = addNode();
       for(OutEdgeIt e(*this,n);e!=INVALID;) {
@@ -448 +447 @@
         e=f;
       }
-      if(connect) addEdge(n,b);
+      if (connect) addEdge(n,b);
       return b;
     }
@@ -460 +459 @@
     ///\warning This functionality
     ///cannot be used together with the Snapshot feature.
-    Node split(Edge e) 
-    {
+    Node split(Edge e) {
       Node b = addNode();
       addEdge(b,target(e));
@@ -468 +466 @@
     }
       
-    ///Class to make a snapshot of the graph and to restore  it later.
-
-    ///Class to make a snapshot of the graph and to restore  it later.
-    ///
-    ///The newly added nodes and edges can be removed using the
-    ///restore() function.
-    ///
-    ///\warning Edge and node deletions cannot be restored.
-    ///\warning Snapshots cannot be nested.
-    class Snapshot : protected Parent::NodeNotifier::ObserverBase,
-                     protected Parent::EdgeNotifier::ObserverBase
-    {
+    /// \brief Class to make a snapshot of the graph and restore
+    /// to it later.
+    ///
+    /// Class to make a snapshot of the graph and to restore it
+    /// later.
+    ///
+    /// The newly added nodes and edges can be removed using the
+    /// restore() function.
+    ///
+    /// \warning Edge and node deletions cannot be restored.
+    class Snapshot {
     public:
       
@@ -491 +488 @@
 
     protected:
-      
-      ListGraph *g;
+
+      typedef Parent::NodeNotifier NodeNotifier;
+
+      class NodeObserverProxy : public NodeNotifier::ObserverBase {
+      public:
+
+        NodeObserverProxy(Snapshot& _snapshot)
+          : snapshot(_snapshot) {}
+
+        using NodeNotifier::ObserverBase::attach;
+        using NodeNotifier::ObserverBase::detach;
+        using NodeNotifier::ObserverBase::attached;
+        
+      protected:
+        
+        virtual void add(const Node& node) {
+          snapshot.addNode(node);
+        }
+        virtual void add(const std::vector<Node>& nodes) {
+          for (int i = nodes.size() - 1; i >= 0; ++i) {
+            snapshot.addNode(nodes[i]);
+          }
+        }
+        virtual void erase(const Node& node) {
+          snapshot.eraseNode(node);
+        }
+        virtual void erase(const std::vector<Node>& nodes) {
+          for (int i = 0; i < (int)nodes.size(); ++i) {
+            if (!snapshot.eraseNode(nodes[i])) break;
+          }
+        }
+        virtual void build() {
+          NodeNotifier* notifier = getNotifier();
+          Node node;
+          std::vector<Node> nodes;
+          for (notifier->first(node); node != INVALID; notifier->next(node)) {
+            nodes.push_back(node);
+          }
+          for (int i = nodes.size() - 1; i >= 0; --i) {
+            snapshot.addNode(nodes[i]);
+          }
+        }
+        virtual void clear() {
+          NodeNotifier* notifier = getNotifier();
+          Node node;
+          for (notifier->first(node); node != INVALID; notifier->next(node)) {
+            if (!snapshot.eraseNode(node)) break;
+          }
+        }
+
+        Snapshot& snapshot;
+      };
+
+      class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
+      public:
+
+        EdgeObserverProxy(Snapshot& _snapshot)
+          : snapshot(_snapshot) {}
+
+        using EdgeNotifier::ObserverBase::attach;
+        using EdgeNotifier::ObserverBase::detach;
+        using EdgeNotifier::ObserverBase::attached;
+        
+      protected:
+
+        virtual void add(const Edge& edge) {
+          snapshot.addEdge(edge);
+        }
+        virtual void add(const std::vector<Edge>& edges) {
+          for (int i = edges.size() - 1; i >= 0; ++i) {
+            snapshot.addEdge(edges[i]);
+          }
+        }
+        virtual void erase(const Edge& edge) {
+          snapshot.eraseEdge(edge);
+        }
+        virtual void erase(const std::vector<Edge>& edges) {
+          for (int i = 0; i < (int)edges.size(); ++i) {
+            if (!snapshot.eraseEdge(edges[i])) break;
+          }
+        }
+        virtual void build() {
+          EdgeNotifier* notifier = getNotifier();
+          Edge edge;
+          std::vector<Edge> edges;
+          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
+            edges.push_back(edge);
+          }
+          for (int i = edges.size() - 1; i >= 0; --i) {
+            snapshot.addEdge(edges[i]);
+          }
+        }
+        virtual void clear() {
+          EdgeNotifier* notifier = getNotifier();
+          Edge edge;
+          for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
+            if (!snapshot.eraseEdge(edge)) break;
+          }
+        }
+
+        Snapshot& snapshot;
+      };
+      
+      ListGraph *graph;
+
+      NodeObserverProxy node_observer_proxy;
+      EdgeObserverProxy edge_observer_proxy;
+
       std::list<Node> added_nodes;
       std::list<Edge> added_edges;
-      
-      bool active;
-      virtual void add(const Node& n) {
-        added_nodes.push_back(n);
-      };
-      virtual void erase(const Node&) 
-      {
-        throw UnsupportedOperation();
-      }
-      virtual void add(const Edge& n) {
-        added_edges.push_back(n);
-      };
-      virtual void erase(const Edge&) 
-      {
-        throw UnsupportedOperation();
-      }
-
-      ///\bug What is this used for?
+
+
+      void addNode(const Node& node) {
+        added_nodes.push_front(node);        
+      }
+      bool eraseNode(const Node& node) {
+        std::list<Node>::iterator it = 
+          std::find(added_nodes.begin(), added_nodes.end(), node);
+        if (it == added_nodes.end()) {
+          clear();
+          return false;
+        } else {
+          added_nodes.erase(it);
+          return true;
+        }
+      }
+
+      void addEdge(const Edge& edge) {
+        added_edges.push_front(edge);        
+      }
+      bool eraseEdge(const Edge& edge) {
+        std::list<Edge>::iterator it = 
+          std::find(added_edges.begin(), added_edges.end(), edge);
+        if (it == added_edges.end()) {
+          clear();
+          return false;
+        } else {
+          added_edges.erase(it);
+          return true;
+        }        
+      }
+
+      void attach(ListGraph &_graph) {
+        graph = &_graph;
+        node_observer_proxy.attach(graph->getNotifier(Node()));
+        edge_observer_proxy.attach(graph->getNotifier(Edge()));
+      }
+            
+      void detach() {
+        node_observer_proxy.detach();
+        edge_observer_proxy.detach();
+      }
+
+      void clear() {
+        detach();
+        added_nodes.clear();
+        added_edges.clear();        
+      }
+
+    public:
+
+      /// \brief Default constructur.
       ///
-      virtual void build() {}
-      ///\bug What is this used for?
+      /// Default constructor.
+      /// To actually make a snapshot you must call save().
+      Snapshot() 
+        : graph(0), node_observer_proxy(*this), 
+          edge_observer_proxy(*this) {}
+      
+      /// \brief Constructor that immediately makes a snapshot.
+      ///      
+      /// This constructor immediately makes a snapshot of the graph.
+      /// \param _graph The graph we make a snapshot of.
+      Snapshot(ListGraph &_graph) 
+        : node_observer_proxy(*this), 
+          edge_observer_proxy(*this) {
+        attach(_graph);
+      }
+      
+      /// \brief Make a snapshot.
       ///
-      virtual void clear() {}
-
-      void regist(ListGraph &_g) {
-        g=&_g;
-        Parent::NodeNotifier::ObserverBase::attach(g->getNotifier(Node()));
-        Parent::EdgeNotifier::ObserverBase::attach(g->getNotifier(Edge()));
-      }
-            
-      void deregist() {
-        Parent::NodeNotifier::ObserverBase::detach();
-        Parent::EdgeNotifier::ObserverBase::detach();
-        g=0;
-      }
-
-    public:
-      ///Default constructur.
-      
-      ///Default constructur.
-      ///To actually make a snapshot you must call save().
+      /// Make a snapshot of the graph.
       ///
-      Snapshot() : g(0) {}
-      ///Constructor that immediately makes a snapshot.
-      
-      ///This constructor immediately makes a snapshot of the graph.
-      ///\param _g The graph we make a snapshot of.
-      Snapshot(ListGraph &_g) {
-        regist(_g);
-      }
-      ///\bug Is it necessary?
+      /// This function can be called more than once. In case of a repeated
+      /// call, the previous snapshot gets lost.
+      /// \param _graph The graph we make the snapshot of.
+      void save(ListGraph &_graph) {
+        clear();
+        attach(_graph);
+      }
+      
+      /// \brief Undo the changes until the last snapshot.
+      // 
+      /// Undo the changes until last snapshot created by save().
       ///
-      ~Snapshot() 
-      {
-        if(g) deregist();
-      }
-      
-      ///Make a snapshot.
-
-      ///Make a snapshot of the graph.
-      ///
-      ///This function can be called more than once. In case of a repeated
-      ///call, the previous snapshot gets lost.
-      ///\param _g The graph we make the snapshot of.
-      void save(ListGraph &_g) 
-      {
-        if(g!=&_g) {
-          if(g) deregist();
-          regist(_g);
-        }
-        added_nodes.clear();
-        added_edges.clear();
-      }
-      
-    ///Undo the changes until the last snapshot.
-
-    ///Undo the changes until last snapshot created by save().
-    ///
-    ///\todo This function might be called undo().
+      /// \todo This function might be called undo().
       void restore() {
-        ListGraph &old_g=*g;
-        deregist();
+        detach();
         while(!added_edges.empty()) {
-          old_g.erase(added_edges.front());
+          graph->erase(added_edges.front());
           added_edges.pop_front();
         }
         while(!added_nodes.empty()) {
-          old_g.erase(added_nodes.front());
+          graph->erase(added_nodes.front());
           added_nodes.pop_front();
         }
+      }
+
+      /// \brief Gives back true when the snapshot is valid.
+      ///
+      /// Gives back true when the snapshot is valid.
+      bool valid() const {
+        return node_observer_proxy.attached();
       }
     };