# HG changeset patch # User deba # Date 1151512064 0 # Node ID 677ea6c8169a0112147b7b489553516bf8be6450 # Parent 48ec8161f9e1d5e3dcf0ce8ae49054090dea0c31 new snapshot diff -r 48ec8161f9e1 -r 677ea6c8169a lemon/list_graph.h --- a/lemon/list_graph.h Wed Jun 28 15:38:45 2006 +0000 +++ b/lemon/list_graph.h Wed Jun 28 16:27:44 2006 +0000 @@ -346,9 +346,9 @@ /// Changes the target of \c e to \c n /// - ///\note The Edges and OutEdges - ///referencing the changed edge remain - ///valid. However InEdges are invalidated. + ///\note The Edges and OutEdgeIts referencing + ///the changed edge remain valid. However InEdgeIts are + ///invalidated. void changeTarget(Edge e, Node n) { Parent::changeTarget(e,n); } @@ -356,18 +356,18 @@ /// Changes the source of \c e to \c n /// - ///\note The Edges and InEdges - ///referencing the changed edge remain - ///valid. However OutEdges are invalidated. + ///\note The Edges and InEdgeIts referencing + ///the changed edge remain valid. However OutEdgeIts are + ///invalidated. void changeSource(Edge e, Node n) { Parent::changeSource(e,n); } /// Invert the direction of an edge. - ///\note The Edges - ///referencing the changed edge remain - ///valid. However OutEdges and InEdges are invalidated. + ///\note The Edges referencing the changed edge remain + ///valid. However OutEdgeIts and InEdgeIts are + ///invalidated. void reverseEdge(Edge e) { Node t=target(e); changeTarget(e,source(e)); @@ -438,8 +438,7 @@ ///\warning This functionality cannot be used together with the Snapshot ///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;) { OutEdgeIt f=e; @@ -447,7 +446,7 @@ changeSource(e,b); e=f; } - if(connect) addEdge(n,b); + if (connect) addEdge(n,b); return b; } @@ -459,26 +458,24 @@ ///\return The newly created node. ///\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)); changeTarget(e,b); return b; } - ///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. + /// \brief Class to make a snapshot of the graph and restore + /// to it later. /// - ///The newly added nodes and edges can be removed using the - ///restore() function. + /// Class to make a snapshot of the graph and to restore it + /// later. /// - ///\warning Edge and node deletions cannot be restored. - ///\warning Snapshots cannot be nested. - class Snapshot : protected Parent::NodeNotifier::ObserverBase, - protected Parent::EdgeNotifier::ObserverBase - { + /// The newly added nodes and edges can be removed using the + /// restore() function. + /// + /// \warning Edge and node deletions cannot be restored. + class Snapshot { public: class UnsupportedOperation : public LogicError { @@ -490,101 +487,220 @@ protected: + + 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& 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& 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 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& 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& 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 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 *g; + ListGraph *graph; + + NodeObserverProxy node_observer_proxy; + EdgeObserverProxy edge_observer_proxy; + std::list added_nodes; std::list added_edges; - - bool active; - virtual void add(const Node& n) { - added_nodes.push_back(n); - }; - virtual void erase(const Node&) - { - throw UnsupportedOperation(); + + + void addNode(const Node& node) { + added_nodes.push_front(node); } - virtual void add(const Edge& n) { - added_edges.push_back(n); - }; - virtual void erase(const Edge&) - { - throw UnsupportedOperation(); + bool eraseNode(const Node& node) { + std::list::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; + } } - ///\bug What is this used for? - /// - virtual void build() {} - ///\bug What is this used for? - /// - virtual void clear() {} + void addEdge(const Edge& edge) { + added_edges.push_front(edge); + } + bool eraseEdge(const Edge& edge) { + std::list::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 regist(ListGraph &_g) { - g=&_g; - Parent::NodeNotifier::ObserverBase::attach(g->getNotifier(Node())); - Parent::EdgeNotifier::ObserverBase::attach(g->getNotifier(Edge())); + void attach(ListGraph &_graph) { + graph = &_graph; + node_observer_proxy.attach(graph->getNotifier(Node())); + edge_observer_proxy.attach(graph->getNotifier(Edge())); } - void deregist() { - Parent::NodeNotifier::ObserverBase::detach(); - Parent::EdgeNotifier::ObserverBase::detach(); - g=0; + void detach() { + node_observer_proxy.detach(); + edge_observer_proxy.detach(); + } + + void clear() { + detach(); + added_nodes.clear(); + added_edges.clear(); } public: - ///Default constructur. + + /// \brief Default constructur. + /// + /// Default constructor. + /// To actually make a snapshot you must call save(). + Snapshot() + : graph(0), node_observer_proxy(*this), + edge_observer_proxy(*this) {} - ///Default constructur. - ///To actually make a snapshot you must call save(). - /// - 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? - /// - ~Snapshot() - { - if(g) deregist(); + /// \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); } - ///Make a snapshot. - - ///Make a snapshot of the graph. + /// \brief Make a snapshot. /// - ///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(); + /// 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 _graph The graph we make the snapshot of. + void save(ListGraph &_graph) { + clear(); + attach(_graph); } - ///Undo the changes until the last snapshot. - - ///Undo the changes until last snapshot created by save(). - /// - ///\todo This function might be called undo(). + /// \brief Undo the changes until the last snapshot. + // + /// Undo the changes until last snapshot created by save(). + /// + /// \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(); + } }; };