344 |
344 |
345 /// Changes the target of \c e to \c n |
345 /// Changes the target of \c e to \c n |
346 |
346 |
347 /// Changes the target of \c e to \c n |
347 /// Changes the target of \c e to \c n |
348 /// |
348 /// |
349 ///\note The <tt>Edge</tt>s and <tt>OutEdge</tt>s |
349 ///\note The <tt>Edge</tt>s and <tt>OutEdgeIt</tt>s referencing |
350 ///referencing the changed edge remain |
350 ///the changed edge remain valid. However <tt>InEdgeIt</tt>s are |
351 ///valid. However <tt>InEdge</tt>s are invalidated. |
351 ///invalidated. |
352 void changeTarget(Edge e, Node n) { |
352 void changeTarget(Edge e, Node n) { |
353 Parent::changeTarget(e,n); |
353 Parent::changeTarget(e,n); |
354 } |
354 } |
355 /// Changes the source of \c e to \c n |
355 /// Changes the source of \c e to \c n |
356 |
356 |
357 /// Changes the source of \c e to \c n |
357 /// Changes the source of \c e to \c n |
358 /// |
358 /// |
359 ///\note The <tt>Edge</tt>s and <tt>InEdge</tt>s |
359 ///\note The <tt>Edge</tt>s and <tt>InEdgeIt</tt>s referencing |
360 ///referencing the changed edge remain |
360 ///the changed edge remain valid. However <tt>OutEdgeIt</tt>s are |
361 ///valid. However <tt>OutEdge</tt>s are invalidated. |
361 ///invalidated. |
362 void changeSource(Edge e, Node n) { |
362 void changeSource(Edge e, Node n) { |
363 Parent::changeSource(e,n); |
363 Parent::changeSource(e,n); |
364 } |
364 } |
365 |
365 |
366 /// Invert the direction of an edge. |
366 /// Invert the direction of an edge. |
367 |
367 |
368 ///\note The <tt>Edge</tt>s |
368 ///\note The <tt>Edge</tt>s referencing the changed edge remain |
369 ///referencing the changed edge remain |
369 ///valid. However <tt>OutEdgeIt</tt>s and <tt>InEdgeIt</tt>s are |
370 ///valid. However <tt>OutEdge</tt>s and <tt>InEdge</tt>s are invalidated. |
370 ///invalidated. |
371 void reverseEdge(Edge e) { |
371 void reverseEdge(Edge e) { |
372 Node t=target(e); |
372 Node t=target(e); |
373 changeTarget(e,source(e)); |
373 changeTarget(e,source(e)); |
374 changeSource(e,t); |
374 changeSource(e,t); |
375 } |
375 } |
457 ///the graph, then the original edge is re-targeted to \c |
456 ///the graph, then the original edge is re-targeted to \c |
458 ///b. Finally an edge from \c b to the original target is added. |
457 ///b. Finally an edge from \c b to the original target is added. |
459 ///\return The newly created node. |
458 ///\return The newly created node. |
460 ///\warning This functionality |
459 ///\warning This functionality |
461 ///cannot be used together with the Snapshot feature. |
460 ///cannot be used together with the Snapshot feature. |
462 Node split(Edge e) |
461 Node split(Edge e) { |
463 { |
|
464 Node b = addNode(); |
462 Node b = addNode(); |
465 addEdge(b,target(e)); |
463 addEdge(b,target(e)); |
466 changeTarget(e,b); |
464 changeTarget(e,b); |
467 return b; |
465 return b; |
468 } |
466 } |
469 |
467 |
470 ///Class to make a snapshot of the graph and to restore it later. |
468 /// \brief Class to make a snapshot of the graph and restore |
471 |
469 /// to it later. |
472 ///Class to make a snapshot of the graph and to restore it later. |
470 /// |
473 /// |
471 /// Class to make a snapshot of the graph and to restore it |
474 ///The newly added nodes and edges can be removed using the |
472 /// later. |
475 ///restore() function. |
473 /// |
476 /// |
474 /// The newly added nodes and edges can be removed using the |
477 ///\warning Edge and node deletions cannot be restored. |
475 /// restore() function. |
478 ///\warning Snapshots cannot be nested. |
476 /// |
479 class Snapshot : protected Parent::NodeNotifier::ObserverBase, |
477 /// \warning Edge and node deletions cannot be restored. |
480 protected Parent::EdgeNotifier::ObserverBase |
478 class Snapshot { |
481 { |
|
482 public: |
479 public: |
483 |
480 |
484 class UnsupportedOperation : public LogicError { |
481 class UnsupportedOperation : public LogicError { |
485 public: |
482 public: |
486 virtual const char* exceptionName() const { |
483 virtual const char* exceptionName() const { |
488 } |
485 } |
489 }; |
486 }; |
490 |
487 |
491 |
488 |
492 protected: |
489 protected: |
493 |
490 |
494 ListGraph *g; |
491 typedef Parent::NodeNotifier NodeNotifier; |
|
492 |
|
493 class NodeObserverProxy : public NodeNotifier::ObserverBase { |
|
494 public: |
|
495 |
|
496 NodeObserverProxy(Snapshot& _snapshot) |
|
497 : snapshot(_snapshot) {} |
|
498 |
|
499 using NodeNotifier::ObserverBase::attach; |
|
500 using NodeNotifier::ObserverBase::detach; |
|
501 using NodeNotifier::ObserverBase::attached; |
|
502 |
|
503 protected: |
|
504 |
|
505 virtual void add(const Node& node) { |
|
506 snapshot.addNode(node); |
|
507 } |
|
508 virtual void add(const std::vector<Node>& nodes) { |
|
509 for (int i = nodes.size() - 1; i >= 0; ++i) { |
|
510 snapshot.addNode(nodes[i]); |
|
511 } |
|
512 } |
|
513 virtual void erase(const Node& node) { |
|
514 snapshot.eraseNode(node); |
|
515 } |
|
516 virtual void erase(const std::vector<Node>& nodes) { |
|
517 for (int i = 0; i < (int)nodes.size(); ++i) { |
|
518 if (!snapshot.eraseNode(nodes[i])) break; |
|
519 } |
|
520 } |
|
521 virtual void build() { |
|
522 NodeNotifier* notifier = getNotifier(); |
|
523 Node node; |
|
524 std::vector<Node> nodes; |
|
525 for (notifier->first(node); node != INVALID; notifier->next(node)) { |
|
526 nodes.push_back(node); |
|
527 } |
|
528 for (int i = nodes.size() - 1; i >= 0; --i) { |
|
529 snapshot.addNode(nodes[i]); |
|
530 } |
|
531 } |
|
532 virtual void clear() { |
|
533 NodeNotifier* notifier = getNotifier(); |
|
534 Node node; |
|
535 for (notifier->first(node); node != INVALID; notifier->next(node)) { |
|
536 if (!snapshot.eraseNode(node)) break; |
|
537 } |
|
538 } |
|
539 |
|
540 Snapshot& snapshot; |
|
541 }; |
|
542 |
|
543 class EdgeObserverProxy : public EdgeNotifier::ObserverBase { |
|
544 public: |
|
545 |
|
546 EdgeObserverProxy(Snapshot& _snapshot) |
|
547 : snapshot(_snapshot) {} |
|
548 |
|
549 using EdgeNotifier::ObserverBase::attach; |
|
550 using EdgeNotifier::ObserverBase::detach; |
|
551 using EdgeNotifier::ObserverBase::attached; |
|
552 |
|
553 protected: |
|
554 |
|
555 virtual void add(const Edge& edge) { |
|
556 snapshot.addEdge(edge); |
|
557 } |
|
558 virtual void add(const std::vector<Edge>& edges) { |
|
559 for (int i = edges.size() - 1; i >= 0; ++i) { |
|
560 snapshot.addEdge(edges[i]); |
|
561 } |
|
562 } |
|
563 virtual void erase(const Edge& edge) { |
|
564 snapshot.eraseEdge(edge); |
|
565 } |
|
566 virtual void erase(const std::vector<Edge>& edges) { |
|
567 for (int i = 0; i < (int)edges.size(); ++i) { |
|
568 if (!snapshot.eraseEdge(edges[i])) break; |
|
569 } |
|
570 } |
|
571 virtual void build() { |
|
572 EdgeNotifier* notifier = getNotifier(); |
|
573 Edge edge; |
|
574 std::vector<Edge> edges; |
|
575 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { |
|
576 edges.push_back(edge); |
|
577 } |
|
578 for (int i = edges.size() - 1; i >= 0; --i) { |
|
579 snapshot.addEdge(edges[i]); |
|
580 } |
|
581 } |
|
582 virtual void clear() { |
|
583 EdgeNotifier* notifier = getNotifier(); |
|
584 Edge edge; |
|
585 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { |
|
586 if (!snapshot.eraseEdge(edge)) break; |
|
587 } |
|
588 } |
|
589 |
|
590 Snapshot& snapshot; |
|
591 }; |
|
592 |
|
593 ListGraph *graph; |
|
594 |
|
595 NodeObserverProxy node_observer_proxy; |
|
596 EdgeObserverProxy edge_observer_proxy; |
|
597 |
495 std::list<Node> added_nodes; |
598 std::list<Node> added_nodes; |
496 std::list<Edge> added_edges; |
599 std::list<Edge> added_edges; |
497 |
600 |
498 bool active; |
601 |
499 virtual void add(const Node& n) { |
602 void addNode(const Node& node) { |
500 added_nodes.push_back(n); |
603 added_nodes.push_front(node); |
501 }; |
604 } |
502 virtual void erase(const Node&) |
605 bool eraseNode(const Node& node) { |
503 { |
606 std::list<Node>::iterator it = |
504 throw UnsupportedOperation(); |
607 std::find(added_nodes.begin(), added_nodes.end(), node); |
505 } |
608 if (it == added_nodes.end()) { |
506 virtual void add(const Edge& n) { |
609 clear(); |
507 added_edges.push_back(n); |
610 return false; |
508 }; |
611 } else { |
509 virtual void erase(const Edge&) |
612 added_nodes.erase(it); |
510 { |
613 return true; |
511 throw UnsupportedOperation(); |
614 } |
512 } |
615 } |
513 |
616 |
514 ///\bug What is this used for? |
617 void addEdge(const Edge& edge) { |
|
618 added_edges.push_front(edge); |
|
619 } |
|
620 bool eraseEdge(const Edge& edge) { |
|
621 std::list<Edge>::iterator it = |
|
622 std::find(added_edges.begin(), added_edges.end(), edge); |
|
623 if (it == added_edges.end()) { |
|
624 clear(); |
|
625 return false; |
|
626 } else { |
|
627 added_edges.erase(it); |
|
628 return true; |
|
629 } |
|
630 } |
|
631 |
|
632 void attach(ListGraph &_graph) { |
|
633 graph = &_graph; |
|
634 node_observer_proxy.attach(graph->getNotifier(Node())); |
|
635 edge_observer_proxy.attach(graph->getNotifier(Edge())); |
|
636 } |
|
637 |
|
638 void detach() { |
|
639 node_observer_proxy.detach(); |
|
640 edge_observer_proxy.detach(); |
|
641 } |
|
642 |
|
643 void clear() { |
|
644 detach(); |
|
645 added_nodes.clear(); |
|
646 added_edges.clear(); |
|
647 } |
|
648 |
|
649 public: |
|
650 |
|
651 /// \brief Default constructur. |
515 /// |
652 /// |
516 virtual void build() {} |
653 /// Default constructor. |
517 ///\bug What is this used for? |
654 /// To actually make a snapshot you must call save(). |
|
655 Snapshot() |
|
656 : graph(0), node_observer_proxy(*this), |
|
657 edge_observer_proxy(*this) {} |
|
658 |
|
659 /// \brief Constructor that immediately makes a snapshot. |
|
660 /// |
|
661 /// This constructor immediately makes a snapshot of the graph. |
|
662 /// \param _graph The graph we make a snapshot of. |
|
663 Snapshot(ListGraph &_graph) |
|
664 : node_observer_proxy(*this), |
|
665 edge_observer_proxy(*this) { |
|
666 attach(_graph); |
|
667 } |
|
668 |
|
669 /// \brief Make a snapshot. |
518 /// |
670 /// |
519 virtual void clear() {} |
671 /// Make a snapshot of the graph. |
520 |
|
521 void regist(ListGraph &_g) { |
|
522 g=&_g; |
|
523 Parent::NodeNotifier::ObserverBase::attach(g->getNotifier(Node())); |
|
524 Parent::EdgeNotifier::ObserverBase::attach(g->getNotifier(Edge())); |
|
525 } |
|
526 |
|
527 void deregist() { |
|
528 Parent::NodeNotifier::ObserverBase::detach(); |
|
529 Parent::EdgeNotifier::ObserverBase::detach(); |
|
530 g=0; |
|
531 } |
|
532 |
|
533 public: |
|
534 ///Default constructur. |
|
535 |
|
536 ///Default constructur. |
|
537 ///To actually make a snapshot you must call save(). |
|
538 /// |
672 /// |
539 Snapshot() : g(0) {} |
673 /// This function can be called more than once. In case of a repeated |
540 ///Constructor that immediately makes a snapshot. |
674 /// call, the previous snapshot gets lost. |
541 |
675 /// \param _graph The graph we make the snapshot of. |
542 ///This constructor immediately makes a snapshot of the graph. |
676 void save(ListGraph &_graph) { |
543 ///\param _g The graph we make a snapshot of. |
677 clear(); |
544 Snapshot(ListGraph &_g) { |
678 attach(_graph); |
545 regist(_g); |
679 } |
546 } |
680 |
547 ///\bug Is it necessary? |
681 /// \brief Undo the changes until the last snapshot. |
|
682 // |
|
683 /// Undo the changes until last snapshot created by save(). |
548 /// |
684 /// |
549 ~Snapshot() |
685 /// \todo This function might be called undo(). |
550 { |
|
551 if(g) deregist(); |
|
552 } |
|
553 |
|
554 ///Make a snapshot. |
|
555 |
|
556 ///Make a snapshot of the graph. |
|
557 /// |
|
558 ///This function can be called more than once. In case of a repeated |
|
559 ///call, the previous snapshot gets lost. |
|
560 ///\param _g The graph we make the snapshot of. |
|
561 void save(ListGraph &_g) |
|
562 { |
|
563 if(g!=&_g) { |
|
564 if(g) deregist(); |
|
565 regist(_g); |
|
566 } |
|
567 added_nodes.clear(); |
|
568 added_edges.clear(); |
|
569 } |
|
570 |
|
571 ///Undo the changes until the last snapshot. |
|
572 |
|
573 ///Undo the changes until last snapshot created by save(). |
|
574 /// |
|
575 ///\todo This function might be called undo(). |
|
576 void restore() { |
686 void restore() { |
577 ListGraph &old_g=*g; |
687 detach(); |
578 deregist(); |
|
579 while(!added_edges.empty()) { |
688 while(!added_edges.empty()) { |
580 old_g.erase(added_edges.front()); |
689 graph->erase(added_edges.front()); |
581 added_edges.pop_front(); |
690 added_edges.pop_front(); |
582 } |
691 } |
583 while(!added_nodes.empty()) { |
692 while(!added_nodes.empty()) { |
584 old_g.erase(added_nodes.front()); |
693 graph->erase(added_nodes.front()); |
585 added_nodes.pop_front(); |
694 added_nodes.pop_front(); |
586 } |
695 } |
|
696 } |
|
697 |
|
698 /// \brief Gives back true when the snapshot is valid. |
|
699 /// |
|
700 /// Gives back true when the snapshot is valid. |
|
701 bool valid() const { |
|
702 return node_observer_proxy.attached(); |
587 } |
703 } |
588 }; |
704 }; |
589 |
705 |
590 }; |
706 }; |
591 |
707 |