1.1 --- a/lemon/list_graph.h Wed Jun 28 15:38:45 2006 +0000
1.2 +++ b/lemon/list_graph.h Wed Jun 28 16:27:44 2006 +0000
1.3 @@ -346,9 +346,9 @@
1.4
1.5 /// Changes the target of \c e to \c n
1.6 ///
1.7 - ///\note The <tt>Edge</tt>s and <tt>OutEdge</tt>s
1.8 - ///referencing the changed edge remain
1.9 - ///valid. However <tt>InEdge</tt>s are invalidated.
1.10 + ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing
1.11 + ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are
1.12 + ///invalidated.
1.13 void changeTarget(Edge e, Node n) {
1.14 Parent::changeTarget(e,n);
1.15 }
1.16 @@ -356,18 +356,18 @@
1.17
1.18 /// Changes the source of \c e to \c n
1.19 ///
1.20 - ///\note The <tt>Edge</tt>s and <tt>InEdge</tt>s
1.21 - ///referencing the changed edge remain
1.22 - ///valid. However <tt>OutEdge</tt>s are invalidated.
1.23 + ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing
1.24 + ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are
1.25 + ///invalidated.
1.26 void changeSource(Edge e, Node n) {
1.27 Parent::changeSource(e,n);
1.28 }
1.29
1.30 /// Invert the direction of an edge.
1.31
1.32 - ///\note The <tt>Edge</tt>s
1.33 - ///referencing the changed edge remain
1.34 - ///valid. However <tt>OutEdge</tt>s and <tt>InEdge</tt>s are invalidated.
1.35 + ///\note The <tt>Edge</tt>s referencing the changed edge remain
1.36 + ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are
1.37 + ///invalidated.
1.38 void reverseEdge(Edge e) {
1.39 Node t=target(e);
1.40 changeTarget(e,source(e));
1.41 @@ -438,8 +438,7 @@
1.42 ///\warning This functionality cannot be used together with the Snapshot
1.43 ///feature.
1.44 ///\todo It could be implemented in a bit faster way.
1.45 - Node split(Node n, bool connect = true)
1.46 - {
1.47 + Node split(Node n, bool connect = true) {
1.48 Node b = addNode();
1.49 for(OutEdgeIt e(*this,n);e!=INVALID;) {
1.50 OutEdgeIt f=e;
1.51 @@ -447,7 +446,7 @@
1.52 changeSource(e,b);
1.53 e=f;
1.54 }
1.55 - if(connect) addEdge(n,b);
1.56 + if (connect) addEdge(n,b);
1.57 return b;
1.58 }
1.59
1.60 @@ -459,26 +458,24 @@
1.61 ///\return The newly created node.
1.62 ///\warning This functionality
1.63 ///cannot be used together with the Snapshot feature.
1.64 - Node split(Edge e)
1.65 - {
1.66 + Node split(Edge e) {
1.67 Node b = addNode();
1.68 addEdge(b,target(e));
1.69 changeTarget(e,b);
1.70 return b;
1.71 }
1.72
1.73 - ///Class to make a snapshot of the graph and to restore it later.
1.74 -
1.75 - ///Class to make a snapshot of the graph and to restore it later.
1.76 + /// \brief Class to make a snapshot of the graph and restore
1.77 + /// to it later.
1.78 ///
1.79 - ///The newly added nodes and edges can be removed using the
1.80 - ///restore() function.
1.81 + /// Class to make a snapshot of the graph and to restore it
1.82 + /// later.
1.83 ///
1.84 - ///\warning Edge and node deletions cannot be restored.
1.85 - ///\warning Snapshots cannot be nested.
1.86 - class Snapshot : protected Parent::NodeNotifier::ObserverBase,
1.87 - protected Parent::EdgeNotifier::ObserverBase
1.88 - {
1.89 + /// The newly added nodes and edges can be removed using the
1.90 + /// restore() function.
1.91 + ///
1.92 + /// \warning Edge and node deletions cannot be restored.
1.93 + class Snapshot {
1.94 public:
1.95
1.96 class UnsupportedOperation : public LogicError {
1.97 @@ -490,101 +487,220 @@
1.98
1.99
1.100 protected:
1.101 +
1.102 + typedef Parent::NodeNotifier NodeNotifier;
1.103 +
1.104 + class NodeObserverProxy : public NodeNotifier::ObserverBase {
1.105 + public:
1.106 +
1.107 + NodeObserverProxy(Snapshot& _snapshot)
1.108 + : snapshot(_snapshot) {}
1.109 +
1.110 + using NodeNotifier::ObserverBase::attach;
1.111 + using NodeNotifier::ObserverBase::detach;
1.112 + using NodeNotifier::ObserverBase::attached;
1.113 +
1.114 + protected:
1.115 +
1.116 + virtual void add(const Node& node) {
1.117 + snapshot.addNode(node);
1.118 + }
1.119 + virtual void add(const std::vector<Node>& nodes) {
1.120 + for (int i = nodes.size() - 1; i >= 0; ++i) {
1.121 + snapshot.addNode(nodes[i]);
1.122 + }
1.123 + }
1.124 + virtual void erase(const Node& node) {
1.125 + snapshot.eraseNode(node);
1.126 + }
1.127 + virtual void erase(const std::vector<Node>& nodes) {
1.128 + for (int i = 0; i < (int)nodes.size(); ++i) {
1.129 + if (!snapshot.eraseNode(nodes[i])) break;
1.130 + }
1.131 + }
1.132 + virtual void build() {
1.133 + NodeNotifier* notifier = getNotifier();
1.134 + Node node;
1.135 + std::vector<Node> nodes;
1.136 + for (notifier->first(node); node != INVALID; notifier->next(node)) {
1.137 + nodes.push_back(node);
1.138 + }
1.139 + for (int i = nodes.size() - 1; i >= 0; --i) {
1.140 + snapshot.addNode(nodes[i]);
1.141 + }
1.142 + }
1.143 + virtual void clear() {
1.144 + NodeNotifier* notifier = getNotifier();
1.145 + Node node;
1.146 + for (notifier->first(node); node != INVALID; notifier->next(node)) {
1.147 + if (!snapshot.eraseNode(node)) break;
1.148 + }
1.149 + }
1.150 +
1.151 + Snapshot& snapshot;
1.152 + };
1.153 +
1.154 + class EdgeObserverProxy : public EdgeNotifier::ObserverBase {
1.155 + public:
1.156 +
1.157 + EdgeObserverProxy(Snapshot& _snapshot)
1.158 + : snapshot(_snapshot) {}
1.159 +
1.160 + using EdgeNotifier::ObserverBase::attach;
1.161 + using EdgeNotifier::ObserverBase::detach;
1.162 + using EdgeNotifier::ObserverBase::attached;
1.163 +
1.164 + protected:
1.165 +
1.166 + virtual void add(const Edge& edge) {
1.167 + snapshot.addEdge(edge);
1.168 + }
1.169 + virtual void add(const std::vector<Edge>& edges) {
1.170 + for (int i = edges.size() - 1; i >= 0; ++i) {
1.171 + snapshot.addEdge(edges[i]);
1.172 + }
1.173 + }
1.174 + virtual void erase(const Edge& edge) {
1.175 + snapshot.eraseEdge(edge);
1.176 + }
1.177 + virtual void erase(const std::vector<Edge>& edges) {
1.178 + for (int i = 0; i < (int)edges.size(); ++i) {
1.179 + if (!snapshot.eraseEdge(edges[i])) break;
1.180 + }
1.181 + }
1.182 + virtual void build() {
1.183 + EdgeNotifier* notifier = getNotifier();
1.184 + Edge edge;
1.185 + std::vector<Edge> edges;
1.186 + for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
1.187 + edges.push_back(edge);
1.188 + }
1.189 + for (int i = edges.size() - 1; i >= 0; --i) {
1.190 + snapshot.addEdge(edges[i]);
1.191 + }
1.192 + }
1.193 + virtual void clear() {
1.194 + EdgeNotifier* notifier = getNotifier();
1.195 + Edge edge;
1.196 + for (notifier->first(edge); edge != INVALID; notifier->next(edge)) {
1.197 + if (!snapshot.eraseEdge(edge)) break;
1.198 + }
1.199 + }
1.200 +
1.201 + Snapshot& snapshot;
1.202 + };
1.203
1.204 - ListGraph *g;
1.205 + ListGraph *graph;
1.206 +
1.207 + NodeObserverProxy node_observer_proxy;
1.208 + EdgeObserverProxy edge_observer_proxy;
1.209 +
1.210 std::list<Node> added_nodes;
1.211 std::list<Edge> added_edges;
1.212 -
1.213 - bool active;
1.214 - virtual void add(const Node& n) {
1.215 - added_nodes.push_back(n);
1.216 - };
1.217 - virtual void erase(const Node&)
1.218 - {
1.219 - throw UnsupportedOperation();
1.220 +
1.221 +
1.222 + void addNode(const Node& node) {
1.223 + added_nodes.push_front(node);
1.224 }
1.225 - virtual void add(const Edge& n) {
1.226 - added_edges.push_back(n);
1.227 - };
1.228 - virtual void erase(const Edge&)
1.229 - {
1.230 - throw UnsupportedOperation();
1.231 + bool eraseNode(const Node& node) {
1.232 + std::list<Node>::iterator it =
1.233 + std::find(added_nodes.begin(), added_nodes.end(), node);
1.234 + if (it == added_nodes.end()) {
1.235 + clear();
1.236 + return false;
1.237 + } else {
1.238 + added_nodes.erase(it);
1.239 + return true;
1.240 + }
1.241 }
1.242
1.243 - ///\bug What is this used for?
1.244 - ///
1.245 - virtual void build() {}
1.246 - ///\bug What is this used for?
1.247 - ///
1.248 - virtual void clear() {}
1.249 + void addEdge(const Edge& edge) {
1.250 + added_edges.push_front(edge);
1.251 + }
1.252 + bool eraseEdge(const Edge& edge) {
1.253 + std::list<Edge>::iterator it =
1.254 + std::find(added_edges.begin(), added_edges.end(), edge);
1.255 + if (it == added_edges.end()) {
1.256 + clear();
1.257 + return false;
1.258 + } else {
1.259 + added_edges.erase(it);
1.260 + return true;
1.261 + }
1.262 + }
1.263
1.264 - void regist(ListGraph &_g) {
1.265 - g=&_g;
1.266 - Parent::NodeNotifier::ObserverBase::attach(g->getNotifier(Node()));
1.267 - Parent::EdgeNotifier::ObserverBase::attach(g->getNotifier(Edge()));
1.268 + void attach(ListGraph &_graph) {
1.269 + graph = &_graph;
1.270 + node_observer_proxy.attach(graph->getNotifier(Node()));
1.271 + edge_observer_proxy.attach(graph->getNotifier(Edge()));
1.272 }
1.273
1.274 - void deregist() {
1.275 - Parent::NodeNotifier::ObserverBase::detach();
1.276 - Parent::EdgeNotifier::ObserverBase::detach();
1.277 - g=0;
1.278 + void detach() {
1.279 + node_observer_proxy.detach();
1.280 + edge_observer_proxy.detach();
1.281 + }
1.282 +
1.283 + void clear() {
1.284 + detach();
1.285 + added_nodes.clear();
1.286 + added_edges.clear();
1.287 }
1.288
1.289 public:
1.290 - ///Default constructur.
1.291 +
1.292 + /// \brief Default constructur.
1.293 + ///
1.294 + /// Default constructor.
1.295 + /// To actually make a snapshot you must call save().
1.296 + Snapshot()
1.297 + : graph(0), node_observer_proxy(*this),
1.298 + edge_observer_proxy(*this) {}
1.299
1.300 - ///Default constructur.
1.301 - ///To actually make a snapshot you must call save().
1.302 - ///
1.303 - Snapshot() : g(0) {}
1.304 - ///Constructor that immediately makes a snapshot.
1.305 -
1.306 - ///This constructor immediately makes a snapshot of the graph.
1.307 - ///\param _g The graph we make a snapshot of.
1.308 - Snapshot(ListGraph &_g) {
1.309 - regist(_g);
1.310 - }
1.311 - ///\bug Is it necessary?
1.312 - ///
1.313 - ~Snapshot()
1.314 - {
1.315 - if(g) deregist();
1.316 + /// \brief Constructor that immediately makes a snapshot.
1.317 + ///
1.318 + /// This constructor immediately makes a snapshot of the graph.
1.319 + /// \param _graph The graph we make a snapshot of.
1.320 + Snapshot(ListGraph &_graph)
1.321 + : node_observer_proxy(*this),
1.322 + edge_observer_proxy(*this) {
1.323 + attach(_graph);
1.324 }
1.325
1.326 - ///Make a snapshot.
1.327 -
1.328 - ///Make a snapshot of the graph.
1.329 + /// \brief Make a snapshot.
1.330 ///
1.331 - ///This function can be called more than once. In case of a repeated
1.332 - ///call, the previous snapshot gets lost.
1.333 - ///\param _g The graph we make the snapshot of.
1.334 - void save(ListGraph &_g)
1.335 - {
1.336 - if(g!=&_g) {
1.337 - if(g) deregist();
1.338 - regist(_g);
1.339 - }
1.340 - added_nodes.clear();
1.341 - added_edges.clear();
1.342 + /// Make a snapshot of the graph.
1.343 + ///
1.344 + /// This function can be called more than once. In case of a repeated
1.345 + /// call, the previous snapshot gets lost.
1.346 + /// \param _graph The graph we make the snapshot of.
1.347 + void save(ListGraph &_graph) {
1.348 + clear();
1.349 + attach(_graph);
1.350 }
1.351
1.352 - ///Undo the changes until the last snapshot.
1.353 -
1.354 - ///Undo the changes until last snapshot created by save().
1.355 - ///
1.356 - ///\todo This function might be called undo().
1.357 + /// \brief Undo the changes until the last snapshot.
1.358 + //
1.359 + /// Undo the changes until last snapshot created by save().
1.360 + ///
1.361 + /// \todo This function might be called undo().
1.362 void restore() {
1.363 - ListGraph &old_g=*g;
1.364 - deregist();
1.365 + detach();
1.366 while(!added_edges.empty()) {
1.367 - old_g.erase(added_edges.front());
1.368 + graph->erase(added_edges.front());
1.369 added_edges.pop_front();
1.370 }
1.371 while(!added_nodes.empty()) {
1.372 - old_g.erase(added_nodes.front());
1.373 + graph->erase(added_nodes.front());
1.374 added_nodes.pop_front();
1.375 }
1.376 }
1.377 +
1.378 + /// \brief Gives back true when the snapshot is valid.
1.379 + ///
1.380 + /// Gives back true when the snapshot is valid.
1.381 + bool valid() const {
1.382 + return node_observer_proxy.attached();
1.383 + }
1.384 };
1.385
1.386 };