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();
+ }
};
};