Changeset 2189:de2b77e3868c in lemon-0.x
- Timestamp:
- 09/04/06 13:08:32 (18 years ago)
- Branch:
- default
- Phase:
- public
- Convert:
- svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2914
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
lemon/list_graph.h
r2160 r2189 503 503 /// restore() function. 504 504 /// 505 /// \warning Edge and node deletions cannot be restored. 505 /// \warning Edge and node deletions cannot be restored. This 506 /// events invalidate the snapshot. 506 507 class Snapshot { 507 public:508 509 class UnsupportedOperation : public LogicError {510 public:511 virtual const char* what() const throw() {512 return "lemon::ListGraph::Snapshot::UnsupportedOperation";513 }514 };515 516 517 508 protected: 518 509 … … 544 535 virtual void erase(const std::vector<Node>& nodes) { 545 536 for (int i = 0; i < (int)nodes.size(); ++i) { 546 if (!snapshot.eraseNode(nodes[i])) break;537 snapshot.eraseNode(nodes[i]); 547 538 } 548 539 } … … 562 553 Node node; 563 554 for (notifier->first(node); node != INVALID; notifier->next(node)) { 564 if (!snapshot.eraseNode(node)) break;555 snapshot.eraseNode(node); 565 556 } 566 557 } … … 594 585 virtual void erase(const std::vector<Edge>& edges) { 595 586 for (int i = 0; i < (int)edges.size(); ++i) { 596 if (!snapshot.eraseEdge(edges[i])) break;587 snapshot.eraseEdge(edges[i]); 597 588 } 598 589 } … … 612 603 Edge edge; 613 604 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { 614 if (!snapshot.eraseEdge(edge)) break;605 snapshot.eraseEdge(edge); 615 606 } 616 607 } … … 631 622 added_nodes.push_front(node); 632 623 } 633 booleraseNode(const Node& node) {624 void eraseNode(const Node& node) { 634 625 std::list<Node>::iterator it = 635 626 std::find(added_nodes.begin(), added_nodes.end(), node); 636 627 if (it == added_nodes.end()) { 637 628 clear(); 638 return false; 629 edge_observer_proxy.detach(); 630 throw NodeNotifier::ImmediateDetach(); 639 631 } else { 640 632 added_nodes.erase(it); 641 return true;642 633 } 643 634 } … … 646 637 added_edges.push_front(edge); 647 638 } 648 booleraseEdge(const Edge& edge) {639 void eraseEdge(const Edge& edge) { 649 640 std::list<Edge>::iterator it = 650 641 std::find(added_edges.begin(), added_edges.end(), edge); 651 642 if (it == added_edges.end()) { 652 643 clear(); 653 return false; 644 node_observer_proxy.detach(); 645 throw EdgeNotifier::ImmediateDetach(); 654 646 } else { 655 647 added_edges.erase(it); 656 return true;657 648 } 658 649 } … … 669 660 } 670 661 662 bool attached() const { 663 return node_observer_proxy.attached(); 664 } 665 671 666 void clear() { 672 detach();673 667 added_nodes.clear(); 674 668 added_edges.clear(); … … 703 697 /// \param _graph The graph we make the snapshot of. 704 698 void save(ListGraph &_graph) { 705 clear(); 699 if (attached()) { 700 detach(); 701 clear(); 702 } 706 703 attach(_graph); 707 704 } … … 712 709 void restore() { 713 710 detach(); 714 while(!added_edges.empty()) {715 graph->erase(added_edges.front()); 716 added_edges.pop_front();711 for(std::list<Edge>::iterator it = added_edges.begin(); 712 it != added_edges.end(); ++it) { 713 graph->erase(*it); 717 714 } 718 while(!added_nodes.empty()) { 719 graph->erase(added_nodes.front()); 720 added_nodes.pop_front();715 for(std::list<Node>::iterator it = added_nodes.begin(); 716 it != added_nodes.end(); ++it) { 717 graph->erase(*it); 721 718 } 719 clear(); 722 720 } 723 721 … … 726 724 /// Gives back true when the snapshot is valid. 727 725 bool valid() const { 728 return node_observer_proxy.attached();726 return attached(); 729 727 } 730 728 }; … … 860 858 erase(b); 861 859 } 860 861 862 /// \brief Class to make a snapshot of the graph and restore 863 /// to it later. 864 /// 865 /// Class to make a snapshot of the graph and to restore it 866 /// later. 867 /// 868 /// The newly added nodes and undirected edges can be removed 869 /// using the restore() function. 870 /// 871 /// \warning Edge and node deletions cannot be restored. This 872 /// events invalidate the snapshot. 873 class Snapshot { 874 protected: 875 876 typedef Parent::NodeNotifier NodeNotifier; 877 878 class NodeObserverProxy : public NodeNotifier::ObserverBase { 879 public: 880 881 NodeObserverProxy(Snapshot& _snapshot) 882 : snapshot(_snapshot) {} 883 884 using NodeNotifier::ObserverBase::attach; 885 using NodeNotifier::ObserverBase::detach; 886 using NodeNotifier::ObserverBase::attached; 887 888 protected: 889 890 virtual void add(const Node& node) { 891 snapshot.addNode(node); 892 } 893 virtual void add(const std::vector<Node>& nodes) { 894 for (int i = nodes.size() - 1; i >= 0; ++i) { 895 snapshot.addNode(nodes[i]); 896 } 897 } 898 virtual void erase(const Node& node) { 899 snapshot.eraseNode(node); 900 } 901 virtual void erase(const std::vector<Node>& nodes) { 902 for (int i = 0; i < (int)nodes.size(); ++i) { 903 snapshot.eraseNode(nodes[i]); 904 } 905 } 906 virtual void build() { 907 NodeNotifier* notifier = getNotifier(); 908 Node node; 909 std::vector<Node> nodes; 910 for (notifier->first(node); node != INVALID; notifier->next(node)) { 911 nodes.push_back(node); 912 } 913 for (int i = nodes.size() - 1; i >= 0; --i) { 914 snapshot.addNode(nodes[i]); 915 } 916 } 917 virtual void clear() { 918 NodeNotifier* notifier = getNotifier(); 919 Node node; 920 for (notifier->first(node); node != INVALID; notifier->next(node)) { 921 snapshot.eraseNode(node); 922 } 923 } 924 925 Snapshot& snapshot; 926 }; 927 928 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase { 929 public: 930 931 UEdgeObserverProxy(Snapshot& _snapshot) 932 : snapshot(_snapshot) {} 933 934 using UEdgeNotifier::ObserverBase::attach; 935 using UEdgeNotifier::ObserverBase::detach; 936 using UEdgeNotifier::ObserverBase::attached; 937 938 protected: 939 940 virtual void add(const UEdge& edge) { 941 snapshot.addUEdge(edge); 942 } 943 virtual void add(const std::vector<UEdge>& edges) { 944 for (int i = edges.size() - 1; i >= 0; ++i) { 945 snapshot.addUEdge(edges[i]); 946 } 947 } 948 virtual void erase(const UEdge& edge) { 949 snapshot.eraseUEdge(edge); 950 } 951 virtual void erase(const std::vector<UEdge>& edges) { 952 for (int i = 0; i < (int)edges.size(); ++i) { 953 snapshot.eraseUEdge(edges[i]); 954 } 955 } 956 virtual void build() { 957 UEdgeNotifier* notifier = getNotifier(); 958 UEdge edge; 959 std::vector<UEdge> edges; 960 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { 961 edges.push_back(edge); 962 } 963 for (int i = edges.size() - 1; i >= 0; --i) { 964 snapshot.addUEdge(edges[i]); 965 } 966 } 967 virtual void clear() { 968 UEdgeNotifier* notifier = getNotifier(); 969 UEdge edge; 970 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { 971 snapshot.eraseUEdge(edge); 972 } 973 } 974 975 Snapshot& snapshot; 976 }; 977 978 ListUGraph *graph; 979 980 NodeObserverProxy node_observer_proxy; 981 UEdgeObserverProxy edge_observer_proxy; 982 983 std::list<Node> added_nodes; 984 std::list<UEdge> added_edges; 985 986 987 void addNode(const Node& node) { 988 added_nodes.push_front(node); 989 } 990 void eraseNode(const Node& node) { 991 std::list<Node>::iterator it = 992 std::find(added_nodes.begin(), added_nodes.end(), node); 993 if (it == added_nodes.end()) { 994 clear(); 995 edge_observer_proxy.detach(); 996 throw NodeNotifier::ImmediateDetach(); 997 } else { 998 added_nodes.erase(it); 999 } 1000 } 1001 1002 void addUEdge(const UEdge& edge) { 1003 added_edges.push_front(edge); 1004 } 1005 void eraseUEdge(const UEdge& edge) { 1006 std::list<UEdge>::iterator it = 1007 std::find(added_edges.begin(), added_edges.end(), edge); 1008 if (it == added_edges.end()) { 1009 clear(); 1010 node_observer_proxy.detach(); 1011 throw UEdgeNotifier::ImmediateDetach(); 1012 } else { 1013 added_edges.erase(it); 1014 } 1015 } 1016 1017 void attach(ListUGraph &_graph) { 1018 graph = &_graph; 1019 node_observer_proxy.attach(graph->getNotifier(Node())); 1020 edge_observer_proxy.attach(graph->getNotifier(UEdge())); 1021 } 1022 1023 void detach() { 1024 node_observer_proxy.detach(); 1025 edge_observer_proxy.detach(); 1026 } 1027 1028 bool attached() const { 1029 return node_observer_proxy.attached(); 1030 } 1031 1032 void clear() { 1033 added_nodes.clear(); 1034 added_edges.clear(); 1035 } 1036 1037 public: 1038 1039 /// \brief Default constructor. 1040 /// 1041 /// Default constructor. 1042 /// To actually make a snapshot you must call save(). 1043 Snapshot() 1044 : graph(0), node_observer_proxy(*this), 1045 edge_observer_proxy(*this) {} 1046 1047 /// \brief Constructor that immediately makes a snapshot. 1048 /// 1049 /// This constructor immediately makes a snapshot of the graph. 1050 /// \param _graph The graph we make a snapshot of. 1051 Snapshot(ListUGraph &_graph) 1052 : node_observer_proxy(*this), 1053 edge_observer_proxy(*this) { 1054 attach(_graph); 1055 } 1056 1057 /// \brief Make a snapshot. 1058 /// 1059 /// Make a snapshot of the graph. 1060 /// 1061 /// This function can be called more than once. In case of a repeated 1062 /// call, the previous snapshot gets lost. 1063 /// \param _graph The graph we make the snapshot of. 1064 void save(ListUGraph &_graph) { 1065 if (attached()) { 1066 detach(); 1067 clear(); 1068 } 1069 attach(_graph); 1070 } 1071 1072 /// \brief Undo the changes until the last snapshot. 1073 // 1074 /// Undo the changes until the last snapshot created by save(). 1075 void restore() { 1076 detach(); 1077 for(std::list<UEdge>::iterator it = added_edges.begin(); 1078 it != added_edges.end(); ++it) { 1079 graph->erase(*it); 1080 } 1081 for(std::list<Node>::iterator it = added_nodes.begin(); 1082 it != added_nodes.end(); ++it) { 1083 graph->erase(*it); 1084 } 1085 clear(); 1086 } 1087 1088 /// \brief Gives back true when the snapshot is valid. 1089 /// 1090 /// Gives back true when the snapshot is valid. 1091 bool valid() const { 1092 return attached(); 1093 } 1094 }; 862 1095 }; 863 1096 … … 1106 1339 bNodes[bNodeId].next = -1; 1107 1340 } 1341 bNodes[bNodeId].prev = -1; 1108 1342 first_bnode = bNodeId; 1109 1343 bNodes[bNodeId].first_edge = -1; … … 1149 1383 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next; 1150 1384 } else { 1151 first_anode = aNodes[aNodeId].next >> 1; 1385 first_anode = 1386 aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1; 1152 1387 } 1153 1388 if (aNodes[aNodeId].next != -1) { … … 1161 1396 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next; 1162 1397 } else { 1163 first_bnode = bNodes[bNodeId].next >> 1; 1398 first_bnode = 1399 bNodes[bNodeId].next != -1 ? bNodes[bNodeId].next >> 1 : -1; 1164 1400 } 1165 1401 if (bNodes[bNodeId].next != -1) { … … 1397 1633 } 1398 1634 1635 /// \brief Class to make a snapshot of the graph and restore 1636 /// to it later. 1637 /// 1638 /// Class to make a snapshot of the graph and to restore it 1639 /// later. 1640 /// 1641 /// The newly added nodes and undirected edges can be removed 1642 /// using the restore() function. 1643 /// 1644 /// \warning Edge and node deletions cannot be restored. This 1645 /// events invalidate the snapshot. 1646 class Snapshot { 1647 protected: 1648 1649 typedef Parent::NodeNotifier NodeNotifier; 1650 1651 class NodeObserverProxy : public NodeNotifier::ObserverBase { 1652 public: 1653 1654 NodeObserverProxy(Snapshot& _snapshot) 1655 : snapshot(_snapshot) {} 1656 1657 using NodeNotifier::ObserverBase::attach; 1658 using NodeNotifier::ObserverBase::detach; 1659 using NodeNotifier::ObserverBase::attached; 1660 1661 protected: 1662 1663 virtual void add(const Node& node) { 1664 snapshot.addNode(node); 1665 } 1666 virtual void add(const std::vector<Node>& nodes) { 1667 for (int i = nodes.size() - 1; i >= 0; ++i) { 1668 snapshot.addNode(nodes[i]); 1669 } 1670 } 1671 virtual void erase(const Node& node) { 1672 snapshot.eraseNode(node); 1673 } 1674 virtual void erase(const std::vector<Node>& nodes) { 1675 for (int i = 0; i < (int)nodes.size(); ++i) { 1676 snapshot.eraseNode(nodes[i]); 1677 } 1678 } 1679 virtual void build() { 1680 NodeNotifier* notifier = getNotifier(); 1681 Node node; 1682 std::vector<Node> nodes; 1683 for (notifier->first(node); node != INVALID; notifier->next(node)) { 1684 nodes.push_back(node); 1685 } 1686 for (int i = nodes.size() - 1; i >= 0; --i) { 1687 snapshot.addNode(nodes[i]); 1688 } 1689 } 1690 virtual void clear() { 1691 NodeNotifier* notifier = getNotifier(); 1692 Node node; 1693 for (notifier->first(node); node != INVALID; notifier->next(node)) { 1694 snapshot.eraseNode(node); 1695 } 1696 } 1697 1698 Snapshot& snapshot; 1699 }; 1700 1701 class UEdgeObserverProxy : public UEdgeNotifier::ObserverBase { 1702 public: 1703 1704 UEdgeObserverProxy(Snapshot& _snapshot) 1705 : snapshot(_snapshot) {} 1706 1707 using UEdgeNotifier::ObserverBase::attach; 1708 using UEdgeNotifier::ObserverBase::detach; 1709 using UEdgeNotifier::ObserverBase::attached; 1710 1711 protected: 1712 1713 virtual void add(const UEdge& edge) { 1714 snapshot.addUEdge(edge); 1715 } 1716 virtual void add(const std::vector<UEdge>& edges) { 1717 for (int i = edges.size() - 1; i >= 0; ++i) { 1718 snapshot.addUEdge(edges[i]); 1719 } 1720 } 1721 virtual void erase(const UEdge& edge) { 1722 snapshot.eraseUEdge(edge); 1723 } 1724 virtual void erase(const std::vector<UEdge>& edges) { 1725 for (int i = 0; i < (int)edges.size(); ++i) { 1726 snapshot.eraseUEdge(edges[i]); 1727 } 1728 } 1729 virtual void build() { 1730 UEdgeNotifier* notifier = getNotifier(); 1731 UEdge edge; 1732 std::vector<UEdge> edges; 1733 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { 1734 edges.push_back(edge); 1735 } 1736 for (int i = edges.size() - 1; i >= 0; --i) { 1737 snapshot.addUEdge(edges[i]); 1738 } 1739 } 1740 virtual void clear() { 1741 UEdgeNotifier* notifier = getNotifier(); 1742 UEdge edge; 1743 for (notifier->first(edge); edge != INVALID; notifier->next(edge)) { 1744 snapshot.eraseUEdge(edge); 1745 } 1746 } 1747 1748 Snapshot& snapshot; 1749 }; 1750 1751 ListBpUGraph *graph; 1752 1753 NodeObserverProxy node_observer_proxy; 1754 UEdgeObserverProxy edge_observer_proxy; 1755 1756 std::list<Node> added_nodes; 1757 std::list<UEdge> added_edges; 1758 1759 1760 void addNode(const Node& node) { 1761 added_nodes.push_front(node); 1762 } 1763 void eraseNode(const Node& node) { 1764 std::list<Node>::iterator it = 1765 std::find(added_nodes.begin(), added_nodes.end(), node); 1766 if (it == added_nodes.end()) { 1767 clear(); 1768 edge_observer_proxy.detach(); 1769 throw NodeNotifier::ImmediateDetach(); 1770 } else { 1771 added_nodes.erase(it); 1772 } 1773 } 1774 1775 void addUEdge(const UEdge& edge) { 1776 added_edges.push_front(edge); 1777 } 1778 void eraseUEdge(const UEdge& edge) { 1779 std::list<UEdge>::iterator it = 1780 std::find(added_edges.begin(), added_edges.end(), edge); 1781 if (it == added_edges.end()) { 1782 clear(); 1783 node_observer_proxy.detach(); 1784 throw UEdgeNotifier::ImmediateDetach(); 1785 } else { 1786 added_edges.erase(it); 1787 } 1788 } 1789 1790 void attach(ListBpUGraph &_graph) { 1791 graph = &_graph; 1792 node_observer_proxy.attach(graph->getNotifier(Node())); 1793 edge_observer_proxy.attach(graph->getNotifier(UEdge())); 1794 } 1795 1796 void detach() { 1797 node_observer_proxy.detach(); 1798 edge_observer_proxy.detach(); 1799 } 1800 1801 bool attached() const { 1802 return node_observer_proxy.attached(); 1803 } 1804 1805 void clear() { 1806 added_nodes.clear(); 1807 added_edges.clear(); 1808 } 1809 1810 public: 1811 1812 /// \brief Default constructor. 1813 /// 1814 /// Default constructor. 1815 /// To actually make a snapshot you must call save(). 1816 Snapshot() 1817 : graph(0), node_observer_proxy(*this), 1818 edge_observer_proxy(*this) {} 1819 1820 /// \brief Constructor that immediately makes a snapshot. 1821 /// 1822 /// This constructor immediately makes a snapshot of the graph. 1823 /// \param _graph The graph we make a snapshot of. 1824 Snapshot(ListBpUGraph &_graph) 1825 : node_observer_proxy(*this), 1826 edge_observer_proxy(*this) { 1827 attach(_graph); 1828 } 1829 1830 /// \brief Make a snapshot. 1831 /// 1832 /// Make a snapshot of the graph. 1833 /// 1834 /// This function can be called more than once. In case of a repeated 1835 /// call, the previous snapshot gets lost. 1836 /// \param _graph The graph we make the snapshot of. 1837 void save(ListBpUGraph &_graph) { 1838 if (attached()) { 1839 detach(); 1840 clear(); 1841 } 1842 attach(_graph); 1843 } 1844 1845 /// \brief Undo the changes until the last snapshot. 1846 // 1847 /// Undo the changes until the last snapshot created by save(). 1848 void restore() { 1849 detach(); 1850 for(std::list<UEdge>::iterator it = added_edges.begin(); 1851 it != added_edges.end(); ++it) { 1852 graph->erase(*it); 1853 } 1854 for(std::list<Node>::iterator it = added_nodes.begin(); 1855 it != added_nodes.end(); ++it) { 1856 graph->erase(*it); 1857 } 1858 clear(); 1859 } 1860 1861 /// \brief Gives back true when the snapshot is valid. 1862 /// 1863 /// Gives back true when the snapshot is valid. 1864 bool valid() const { 1865 return attached(); 1866 } 1867 }; 1399 1868 }; 1400 1869
Note: See TracChangeset
for help on using the changeset viewer.