lemon-0.x: comparison lemon/list

equal deleted inserted replaced

-:2c4c326fae8a
+:f2b87333b73b
 /// later.
 ///
 /// The newly added nodes and edges can be removed using the
 /// restore() function.
 ///
-/// \warning Edge and node deletions cannot be restored.
+/// \warning Edge and node deletions cannot be restored. This
+/// events invalidate the snapshot.
 class Snapshot {
-public:
-class UnsupportedOperation : public LogicError {
-public:
-	virtual const char* what() const throw() {
-	  return "lemon::ListGraph::Snapshot::UnsupportedOperation";
-	}
-};
 protected:
 typedef Parent::NodeNotifier NodeNotifier;
 class NodeObserverProxy : public NodeNotifier::ObserverBase {
 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;
+snapshot.eraseNode(nodes[i]);
 }
 }
 virtual void build() {
 NodeNotifier* notifier = getNotifier();
 Node node;
 }
 virtual void clear() {
 NodeNotifier* notifier = getNotifier();
 Node node;
 for (notifier->first(node); node != INVALID; notifier->next(node)) {
-if (!snapshot.eraseNode(node)) break;
+snapshot.eraseNode(node);
 }
 }
 Snapshot& snapshot;
 };
 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;
+snapshot.eraseEdge(edges[i]);
 }
 }
 virtual void build() {
 EdgeNotifier* notifier = getNotifier();
 Edge edge;
 }
 virtual void clear() {
 EdgeNotifier* notifier = getNotifier();
 Edge edge;
 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
-if (!snapshot.eraseEdge(edge)) break;
+snapshot.eraseEdge(edge);
 }
 }
 Snapshot& snapshot;
 };
 void addNode(const Node& node) {
 added_nodes.push_front(node);
 }
-bool eraseNode(const Node& node) {
+void 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;
+edge_observer_proxy.detach();
+throw NodeNotifier::ImmediateDetach();
 } else {
 added_nodes.erase(it);
-return true;
 }
 }
 void addEdge(const Edge& edge) {
 added_edges.push_front(edge);
 }
-bool eraseEdge(const Edge& edge) {
+void 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;
+node_observer_proxy.detach();
+throw EdgeNotifier::ImmediateDetach();
 } else {
 added_edges.erase(it);
-return true;
 }
 }
 void attach(ListGraph &_graph) {
 	graph = &_graph;
 void detach() {
 	node_observer_proxy.detach();
 	edge_observer_proxy.detach();
 }
+bool attached() const {
+return node_observer_proxy.attached();
+}
 void clear() {
-detach();
 added_nodes.clear();
 added_edges.clear();
 }
 public:
 ///
 /// 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();
+if (attached()) {
+detach();
+clear();
+}
 attach(_graph);
 }
 /// \brief Undo the changes until the last snapshot.
 //
 /// Undo the changes until the last snapshot created by save().
 void restore() {
 	detach();
-	while(!added_edges.empty()) {
+	for(std::list<Edge>::iterator it = added_edges.begin();
-	  graph->erase(added_edges.front());
+it != added_edges.end(); ++it) {
-	  added_edges.pop_front();
+	  graph->erase(*it);
 	}
-	while(!added_nodes.empty()) {
+	for(std::list<Node>::iterator it = added_nodes.begin();
-	  graph->erase(added_nodes.front());
+it != added_nodes.end(); ++it) {
-	  added_nodes.pop_front();
+	  graph->erase(*it);
 	}
+clear();
 }
 /// \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();
+return attached();
 }
 };
 };
 	}
 	e = f;
 }
 erase(b);
 }
+/// \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 undirected edges can be removed
+/// using the restore() function.
+///
+/// \warning Edge and node deletions cannot be restored. This
+/// events invalidate the snapshot.
+class Snapshot {
+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<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) {
+snapshot.eraseNode(nodes[i]);
+}
+}
+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)) {
+snapshot.eraseNode(node);
+}
+}
+Snapshot& snapshot;
+};
+class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
+public:
+UEdgeObserverProxy(Snapshot& _snapshot)
+: snapshot(_snapshot) {}
+using UEdgeNotifier::ObserverBase::attach;
+using UEdgeNotifier::ObserverBase::detach;
+using UEdgeNotifier::ObserverBase::attached;
+protected:
+virtual void add(const UEdge& edge) {
+snapshot.addUEdge(edge);
+}
+virtual void add(const std::vector<UEdge>& edges) {
+for (int i = edges.size() - 1; i >= 0; ++i) {
+snapshot.addUEdge(edges[i]);
+}
+}
+virtual void erase(const UEdge& edge) {
+snapshot.eraseUEdge(edge);
+}
+virtual void erase(const std::vector<UEdge>& edges) {
+for (int i = 0; i < (int)edges.size(); ++i) {
+snapshot.eraseUEdge(edges[i]);
+}
+}
+virtual void build() {
+UEdgeNotifier* notifier = getNotifier();
+UEdge edge;
+std::vector<UEdge> edges;
+for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
+edges.push_back(edge);
+}
+for (int i = edges.size() - 1; i >= 0; --i) {
+snapshot.addUEdge(edges[i]);
+}
+}
+virtual void clear() {
+UEdgeNotifier* notifier = getNotifier();
+UEdge edge;
+for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
+snapshot.eraseUEdge(edge);
+}
+}
+Snapshot& snapshot;
+};
+ListUGraph *graph;
+NodeObserverProxy node_observer_proxy;
+UEdgeObserverProxy edge_observer_proxy;
+std::list<Node> added_nodes;
+std::list<UEdge> added_edges;
+void addNode(const Node& node) {
+added_nodes.push_front(node);
+}
+void eraseNode(const Node& node) {
+std::list<Node>::iterator it =
+std::find(added_nodes.begin(), added_nodes.end(), node);
+if (it == added_nodes.end()) {
+clear();
+edge_observer_proxy.detach();
+throw NodeNotifier::ImmediateDetach();
+} else {
+added_nodes.erase(it);
+}
+}
+void addUEdge(const UEdge& edge) {
+added_edges.push_front(edge);
+}
+void eraseUEdge(const UEdge& edge) {
+std::list<UEdge>::iterator it =
+std::find(added_edges.begin(), added_edges.end(), edge);
+if (it == added_edges.end()) {
+clear();
+node_observer_proxy.detach();
+throw UEdgeNotifier::ImmediateDetach();
+} else {
+added_edges.erase(it);
+}
+}
+void attach(ListUGraph &_graph) {
+	graph = &_graph;
+	node_observer_proxy.attach(graph->getNotifier(Node()));
+edge_observer_proxy.attach(graph->getNotifier(UEdge()));
+}
+void detach() {
+	node_observer_proxy.detach();
+	edge_observer_proxy.detach();
+}
+bool attached() const {
+return node_observer_proxy.attached();
+}
+void clear() {
+added_nodes.clear();
+added_edges.clear();
+}
+public:
+/// \brief Default constructor.
+///
+/// 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(ListUGraph &_graph)
+: node_observer_proxy(*this),
+edge_observer_proxy(*this) {
+	attach(_graph);
+}
+/// \brief 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 _graph The graph we make the snapshot of.
+void save(ListUGraph &_graph) {
+if (attached()) {
+detach();
+clear();
+}
+attach(_graph);
+}
+/// \brief Undo the changes until the last snapshot.
+//
+/// Undo the changes until the last snapshot created by save().
+void restore() {
+	detach();
+	for(std::list<UEdge>::iterator it = added_edges.begin();
+it != added_edges.end(); ++it) {
+	  graph->erase(*it);
+	}
+	for(std::list<Node>::iterator it = added_nodes.begin();
+it != added_nodes.end(); ++it) {
+	  graph->erase(*it);
+	}
+clear();
+}
+/// \brief Gives back true when the snapshot is valid.
+///
+/// Gives back true when the snapshot is valid.
+bool valid() const {
+return attached();
+}
+};
 };
 class ListBpUGraphBase {
 public:
 bNodes[bNodeId].next = (first_bnode << 1) + 1;
 bNodes[first_bnode].prev = (bNodeId << 1) + 1;
 } else {
 bNodes[bNodeId].next = -1;
 }
+bNodes[bNodeId].prev = -1;
 first_bnode = bNodeId;
 bNodes[bNodeId].first_edge = -1;
 return Node((bNodeId << 1) + 1);
 }
 if (aNode(node)) {
 int aNodeId = node.id >> 1;
 if (aNodes[aNodeId].prev != -1) {
 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next;
 } else {
-first_anode = aNodes[aNodeId].next >> 1;
+first_anode =
+aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1;
 }
 if (aNodes[aNodeId].next != -1) {
 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev;
 }
 aNodes[aNodeId].next = first_free_anode;
 } else {
 int bNodeId = node.id >> 1;
 if (bNodes[bNodeId].prev != -1) {
 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next;
 } else {
-first_bnode = bNodes[bNodeId].next >> 1;
+first_bnode =
+bNodes[bNodeId].next != -1 ? bNodes[bNodeId].next >> 1 : -1;
 }
 if (bNodes[bNodeId].next != -1) {
 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev;
 }
 bNodes[bNodeId].next = first_free_bnode;
 }
 }
 erase(b);
 }
+/// \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 undirected edges can be removed
+/// using the restore() function.
+///
+/// \warning Edge and node deletions cannot be restored. This
+/// events invalidate the snapshot.
+class Snapshot {
+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<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) {
+snapshot.eraseNode(nodes[i]);
+}
+}
+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)) {
+snapshot.eraseNode(node);
+}
+}
+Snapshot& snapshot;
+};
+class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase {
+public:
+UEdgeObserverProxy(Snapshot& _snapshot)
+: snapshot(_snapshot) {}
+using UEdgeNotifier::ObserverBase::attach;
+using UEdgeNotifier::ObserverBase::detach;
+using UEdgeNotifier::ObserverBase::attached;
+protected:
+virtual void add(const UEdge& edge) {
+snapshot.addUEdge(edge);
+}
+virtual void add(const std::vector<UEdge>& edges) {
+for (int i = edges.size() - 1; i >= 0; ++i) {
+snapshot.addUEdge(edges[i]);
+}
+}
+virtual void erase(const UEdge& edge) {
+snapshot.eraseUEdge(edge);
+}
+virtual void erase(const std::vector<UEdge>& edges) {
+for (int i = 0; i < (int)edges.size(); ++i) {
+snapshot.eraseUEdge(edges[i]);
+}
+}
+virtual void build() {
+UEdgeNotifier* notifier = getNotifier();
+UEdge edge;
+std::vector<UEdge> edges;
+for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
+edges.push_back(edge);
+}
+for (int i = edges.size() - 1; i >= 0; --i) {
+snapshot.addUEdge(edges[i]);
+}
+}
+virtual void clear() {
+UEdgeNotifier* notifier = getNotifier();
+UEdge edge;
+for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
+snapshot.eraseUEdge(edge);
+}
+}
+Snapshot& snapshot;
+};
+ListBpUGraph *graph;
+NodeObserverProxy node_observer_proxy;
+UEdgeObserverProxy edge_observer_proxy;
+std::list<Node> added_nodes;
+std::list<UEdge> added_edges;
+void addNode(const Node& node) {
+added_nodes.push_front(node);
+}
+void eraseNode(const Node& node) {
+std::list<Node>::iterator it =
+std::find(added_nodes.begin(), added_nodes.end(), node);
+if (it == added_nodes.end()) {
+clear();
+edge_observer_proxy.detach();
+throw NodeNotifier::ImmediateDetach();
+} else {
+added_nodes.erase(it);
+}
+}
+void addUEdge(const UEdge& edge) {
+added_edges.push_front(edge);
+}
+void eraseUEdge(const UEdge& edge) {
+std::list<UEdge>::iterator it =
+std::find(added_edges.begin(), added_edges.end(), edge);
+if (it == added_edges.end()) {
+clear();
+node_observer_proxy.detach();
+throw UEdgeNotifier::ImmediateDetach();
+} else {
+added_edges.erase(it);
+}
+}
+void attach(ListBpUGraph &_graph) {
+	graph = &_graph;
+	node_observer_proxy.attach(graph->getNotifier(Node()));
+edge_observer_proxy.attach(graph->getNotifier(UEdge()));
+}
+void detach() {
+	node_observer_proxy.detach();
+	edge_observer_proxy.detach();
+}
+bool attached() const {
+return node_observer_proxy.attached();
+}
+void clear() {
+added_nodes.clear();
+added_edges.clear();
+}
+public:
+/// \brief Default constructor.
+///
+/// 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(ListBpUGraph &_graph)
+: node_observer_proxy(*this),
+edge_observer_proxy(*this) {
+	attach(_graph);
+}
+/// \brief 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 _graph The graph we make the snapshot of.
+void save(ListBpUGraph &_graph) {
+if (attached()) {
+detach();
+clear();
+}
+attach(_graph);
+}
+/// \brief Undo the changes until the last snapshot.
+//
+/// Undo the changes until the last snapshot created by save().
+void restore() {
+	detach();
+	for(std::list<UEdge>::iterator it = added_edges.begin();
+it != added_edges.end(); ++it) {
+	  graph->erase(*it);
+	}
+	for(std::list<Node>::iterator it = added_nodes.begin();
+it != added_nodes.end(); ++it) {
+	  graph->erase(*it);
+	}
+clear();
+}
+/// \brief Gives back true when the snapshot is valid.
+///
+/// Gives back true when the snapshot is valid.
+bool valid() const {
+return attached();
+}
+};
 };
 /// @}
 } //namespace lemon

changeset 2208	37b5c870a953
parent 2160	abd867cf8a9c
child 2231	06faf3f06d67