520 } |
520 } |
521 virtual void erase(const Node& node) { |
521 virtual void erase(const Node& node) { |
522 snapshot.eraseNode(node); |
522 snapshot.eraseNode(node); |
523 } |
523 } |
524 virtual void erase(const std::vector<Node>& nodes) { |
524 virtual void erase(const std::vector<Node>& nodes) { |
525 for (int i = 0; i < (int)nodes.size(); ++i) { |
525 for (int i = 0; i < int(nodes.size()); ++i) { |
526 snapshot.eraseNode(nodes[i]); |
526 snapshot.eraseNode(nodes[i]); |
527 } |
527 } |
528 } |
528 } |
529 virtual void build() { |
529 virtual void build() { |
530 NodeNotifier* _notifier = notifier(); |
|
531 Node node; |
530 Node node; |
532 std::vector<Node> nodes; |
531 std::vector<Node> nodes; |
533 for (_notifier->first(node); node != INVALID; |
532 for (notifier()->first(node); node != INVALID; |
534 _notifier->next(node)) { |
533 notifier()->next(node)) { |
535 nodes.push_back(node); |
534 nodes.push_back(node); |
536 } |
535 } |
537 for (int i = nodes.size() - 1; i >= 0; --i) { |
536 for (int i = nodes.size() - 1; i >= 0; --i) { |
538 snapshot.addNode(nodes[i]); |
537 snapshot.addNode(nodes[i]); |
539 } |
538 } |
540 } |
539 } |
541 virtual void clear() { |
540 virtual void clear() { |
542 NodeNotifier* _notifier = notifier(); |
|
543 Node node; |
541 Node node; |
544 for (_notifier->first(node); node != INVALID; |
542 for (notifier()->first(node); node != INVALID; |
545 _notifier->next(node)) { |
543 notifier()->next(node)) { |
546 snapshot.eraseNode(node); |
544 snapshot.eraseNode(node); |
547 } |
545 } |
548 } |
546 } |
549 |
547 |
550 Snapshot& snapshot; |
548 Snapshot& snapshot; |
572 } |
570 } |
573 virtual void erase(const Edge& edge) { |
571 virtual void erase(const Edge& edge) { |
574 snapshot.eraseEdge(edge); |
572 snapshot.eraseEdge(edge); |
575 } |
573 } |
576 virtual void erase(const std::vector<Edge>& edges) { |
574 virtual void erase(const std::vector<Edge>& edges) { |
577 for (int i = 0; i < (int)edges.size(); ++i) { |
575 for (int i = 0; i < int(edges.size()); ++i) { |
578 snapshot.eraseEdge(edges[i]); |
576 snapshot.eraseEdge(edges[i]); |
579 } |
577 } |
580 } |
578 } |
581 virtual void build() { |
579 virtual void build() { |
582 EdgeNotifier* _notifier = notifier(); |
|
583 Edge edge; |
580 Edge edge; |
584 std::vector<Edge> edges; |
581 std::vector<Edge> edges; |
585 for (_notifier->first(edge); edge != INVALID; |
582 for (notifier()->first(edge); edge != INVALID; |
586 _notifier->next(edge)) { |
583 notifier()->next(edge)) { |
587 edges.push_back(edge); |
584 edges.push_back(edge); |
588 } |
585 } |
589 for (int i = edges.size() - 1; i >= 0; --i) { |
586 for (int i = edges.size() - 1; i >= 0; --i) { |
590 snapshot.addEdge(edges[i]); |
587 snapshot.addEdge(edges[i]); |
591 } |
588 } |
592 } |
589 } |
593 virtual void clear() { |
590 virtual void clear() { |
594 EdgeNotifier* _notifier = notifier(); |
|
595 Edge edge; |
591 Edge edge; |
596 for (_notifier->first(edge); edge != INVALID; _notifier->next(edge)) { |
592 for (notifier()->first(edge); edge != INVALID; |
|
593 notifier()->next(edge)) { |
597 snapshot.eraseEdge(edge); |
594 snapshot.eraseEdge(edge); |
598 } |
595 } |
599 } |
596 } |
600 |
597 |
601 Snapshot& snapshot; |
598 Snapshot& snapshot; |
1267 } |
1264 } |
1268 virtual void erase(const Node& node) { |
1265 virtual void erase(const Node& node) { |
1269 snapshot.eraseNode(node); |
1266 snapshot.eraseNode(node); |
1270 } |
1267 } |
1271 virtual void erase(const std::vector<Node>& nodes) { |
1268 virtual void erase(const std::vector<Node>& nodes) { |
1272 for (int i = 0; i < (int)nodes.size(); ++i) { |
1269 for (int i = 0; i < int(nodes.size()); ++i) { |
1273 snapshot.eraseNode(nodes[i]); |
1270 snapshot.eraseNode(nodes[i]); |
1274 } |
1271 } |
1275 } |
1272 } |
1276 virtual void build() { |
1273 virtual void build() { |
1277 NodeNotifier* _notifier = notifier(); |
|
1278 Node node; |
1274 Node node; |
1279 std::vector<Node> nodes; |
1275 std::vector<Node> nodes; |
1280 for (_notifier->first(node); node != INVALID; |
1276 for (notifier()->first(node); node != INVALID; |
1281 _notifier->next(node)) { |
1277 notifier()->next(node)) { |
1282 nodes.push_back(node); |
1278 nodes.push_back(node); |
1283 } |
1279 } |
1284 for (int i = nodes.size() - 1; i >= 0; --i) { |
1280 for (int i = nodes.size() - 1; i >= 0; --i) { |
1285 snapshot.addNode(nodes[i]); |
1281 snapshot.addNode(nodes[i]); |
1286 } |
1282 } |
1287 } |
1283 } |
1288 virtual void clear() { |
1284 virtual void clear() { |
1289 NodeNotifier* _notifier = notifier(); |
|
1290 Node node; |
1285 Node node; |
1291 for (_notifier->first(node); node != INVALID; |
1286 for (notifier()->first(node); node != INVALID; |
1292 _notifier->next(node)) { |
1287 notifier()->next(node)) { |
1293 snapshot.eraseNode(node); |
1288 snapshot.eraseNode(node); |
1294 } |
1289 } |
1295 } |
1290 } |
1296 |
1291 |
1297 Snapshot& snapshot; |
1292 Snapshot& snapshot; |
1319 } |
1314 } |
1320 virtual void erase(const UEdge& edge) { |
1315 virtual void erase(const UEdge& edge) { |
1321 snapshot.eraseUEdge(edge); |
1316 snapshot.eraseUEdge(edge); |
1322 } |
1317 } |
1323 virtual void erase(const std::vector<UEdge>& edges) { |
1318 virtual void erase(const std::vector<UEdge>& edges) { |
1324 for (int i = 0; i < (int)edges.size(); ++i) { |
1319 for (int i = 0; i < int(edges.size()); ++i) { |
1325 snapshot.eraseUEdge(edges[i]); |
1320 snapshot.eraseUEdge(edges[i]); |
1326 } |
1321 } |
1327 } |
1322 } |
1328 virtual void build() { |
1323 virtual void build() { |
1329 UEdgeNotifier* _notifier = notifier(); |
|
1330 UEdge edge; |
1324 UEdge edge; |
1331 std::vector<UEdge> edges; |
1325 std::vector<UEdge> edges; |
1332 for (_notifier->first(edge); edge != INVALID; |
1326 for (notifier()->first(edge); edge != INVALID; |
1333 _notifier->next(edge)) { |
1327 notifier()->next(edge)) { |
1334 edges.push_back(edge); |
1328 edges.push_back(edge); |
1335 } |
1329 } |
1336 for (int i = edges.size() - 1; i >= 0; --i) { |
1330 for (int i = edges.size() - 1; i >= 0; --i) { |
1337 snapshot.addUEdge(edges[i]); |
1331 snapshot.addUEdge(edges[i]); |
1338 } |
1332 } |
1339 } |
1333 } |
1340 virtual void clear() { |
1334 virtual void clear() { |
1341 UEdgeNotifier* _notifier = notifier(); |
|
1342 UEdge edge; |
1335 UEdge edge; |
1343 for (_notifier->first(edge); edge != INVALID; |
1336 for (notifier()->first(edge); edge != INVALID; |
1344 _notifier->next(edge)) { |
1337 notifier()->next(edge)) { |
1345 snapshot.eraseUEdge(edge); |
1338 snapshot.eraseUEdge(edge); |
1346 } |
1339 } |
1347 } |
1340 } |
1348 |
1341 |
1349 Snapshot& snapshot; |
1342 Snapshot& snapshot; |
1573 node.id = bNodes[node.id >> 1].next; |
1566 node.id = bNodes[node.id >> 1].next; |
1574 } |
1567 } |
1575 } |
1568 } |
1576 |
1569 |
1577 void first(UEdge& edge) const { |
1570 void first(UEdge& edge) const { |
1578 int aNodeId = first_anode; |
1571 int aid = first_anode; |
1579 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
1572 while (aid != -1 && aNodes[aid].first_edge == -1) { |
1580 aNodeId = aNodes[aNodeId].next != -1 ? |
1573 aid = aNodes[aid].next != -1 ? |
1581 aNodes[aNodeId].next >> 1 : -1; |
1574 aNodes[aid].next >> 1 : -1; |
1582 } |
1575 } |
1583 if (aNodeId != -1) { |
1576 if (aid != -1) { |
1584 edge.id = aNodes[aNodeId].first_edge; |
1577 edge.id = aNodes[aid].first_edge; |
1585 } else { |
1578 } else { |
1586 edge.id = -1; |
1579 edge.id = -1; |
1587 } |
1580 } |
1588 } |
1581 } |
1589 void next(UEdge& edge) const { |
1582 void next(UEdge& edge) const { |
1590 int aNodeId = edges[edge.id].aNode >> 1; |
1583 int aid = edges[edge.id].aNode >> 1; |
1591 edge.id = edges[edge.id].next_out; |
1584 edge.id = edges[edge.id].next_out; |
1592 if (edge.id == -1) { |
1585 if (edge.id == -1) { |
1593 aNodeId = aNodes[aNodeId].next != -1 ? |
1586 aid = aNodes[aid].next != -1 ? |
1594 aNodes[aNodeId].next >> 1 : -1; |
1587 aNodes[aid].next >> 1 : -1; |
1595 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
1588 while (aid != -1 && aNodes[aid].first_edge == -1) { |
1596 aNodeId = aNodes[aNodeId].next != -1 ? |
1589 aid = aNodes[aid].next != -1 ? |
1597 aNodes[aNodeId].next >> 1 : -1; |
1590 aNodes[aid].next >> 1 : -1; |
1598 } |
1591 } |
1599 if (aNodeId != -1) { |
1592 if (aid != -1) { |
1600 edge.id = aNodes[aNodeId].first_edge; |
1593 edge.id = aNodes[aid].first_edge; |
1601 } else { |
1594 } else { |
1602 edge.id = -1; |
1595 edge.id = -1; |
1603 } |
1596 } |
1604 } |
1597 } |
1605 } |
1598 } |
1675 static bool bNode(const Node& node) { |
1668 static bool bNode(const Node& node) { |
1676 return (node.id & 1) == 1; |
1669 return (node.id & 1) == 1; |
1677 } |
1670 } |
1678 |
1671 |
1679 Node addANode() { |
1672 Node addANode() { |
1680 int aNodeId; |
1673 int aid; |
1681 if (first_free_anode == -1) { |
1674 if (first_free_anode == -1) { |
1682 aNodeId = aNodes.size(); |
1675 aid = aNodes.size(); |
1683 aNodes.push_back(NodeT()); |
1676 aNodes.push_back(NodeT()); |
1684 } else { |
1677 } else { |
1685 aNodeId = first_free_anode; |
1678 aid = first_free_anode; |
1686 first_free_anode = aNodes[first_free_anode].next; |
1679 first_free_anode = aNodes[first_free_anode].next; |
1687 } |
1680 } |
1688 if (first_anode != -1) { |
1681 if (first_anode != -1) { |
1689 aNodes[aNodeId].next = first_anode << 1; |
1682 aNodes[aid].next = first_anode << 1; |
1690 aNodes[first_anode].prev = aNodeId << 1; |
1683 aNodes[first_anode].prev = aid << 1; |
1691 } else { |
1684 } else { |
1692 aNodes[aNodeId].next = -1; |
1685 aNodes[aid].next = -1; |
1693 } |
1686 } |
1694 aNodes[aNodeId].prev = -1; |
1687 aNodes[aid].prev = -1; |
1695 first_anode = aNodeId; |
1688 first_anode = aid; |
1696 aNodes[aNodeId].first_edge = -1; |
1689 aNodes[aid].first_edge = -1; |
1697 return Node(aNodeId << 1); |
1690 return Node(aid << 1); |
1698 } |
1691 } |
1699 |
1692 |
1700 Node addBNode() { |
1693 Node addBNode() { |
1701 int bNodeId; |
1694 int bid; |
1702 if (first_free_bnode == -1) { |
1695 if (first_free_bnode == -1) { |
1703 bNodeId = bNodes.size(); |
1696 bid = bNodes.size(); |
1704 bNodes.push_back(NodeT()); |
1697 bNodes.push_back(NodeT()); |
1705 } else { |
1698 } else { |
1706 bNodeId = first_free_bnode; |
1699 bid = first_free_bnode; |
1707 first_free_bnode = bNodes[first_free_bnode].next; |
1700 first_free_bnode = bNodes[first_free_bnode].next; |
1708 } |
1701 } |
1709 if (first_bnode != -1) { |
1702 if (first_bnode != -1) { |
1710 bNodes[bNodeId].next = (first_bnode << 1) + 1; |
1703 bNodes[bid].next = (first_bnode << 1) + 1; |
1711 bNodes[first_bnode].prev = (bNodeId << 1) + 1; |
1704 bNodes[first_bnode].prev = (bid << 1) + 1; |
1712 } else { |
1705 } else { |
1713 bNodes[bNodeId].next = -1; |
1706 bNodes[bid].next = -1; |
1714 } |
1707 } |
1715 bNodes[bNodeId].prev = -1; |
1708 bNodes[bid].prev = -1; |
1716 first_bnode = bNodeId; |
1709 first_bnode = bid; |
1717 bNodes[bNodeId].first_edge = -1; |
1710 bNodes[bid].first_edge = -1; |
1718 return Node((bNodeId << 1) + 1); |
1711 return Node((bid << 1) + 1); |
1719 } |
1712 } |
1720 |
1713 |
1721 UEdge addEdge(const Node& source, const Node& target) { |
1714 UEdge addEdge(const Node& source, const Node& target) { |
1722 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); |
1715 LEMON_ASSERT(((source.id ^ target.id) & 1) == 1, NodeSetError()); |
1723 int edgeId; |
1716 int edgeId; |
1750 return UEdge(edgeId); |
1743 return UEdge(edgeId); |
1751 } |
1744 } |
1752 |
1745 |
1753 void erase(const Node& node) { |
1746 void erase(const Node& node) { |
1754 if (aNode(node)) { |
1747 if (aNode(node)) { |
1755 int aNodeId = node.id >> 1; |
1748 int aid = node.id >> 1; |
1756 if (aNodes[aNodeId].prev != -1) { |
1749 if (aNodes[aid].prev != -1) { |
1757 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next; |
1750 aNodes[aNodes[aid].prev >> 1].next = aNodes[aid].next; |
1758 } else { |
1751 } else { |
1759 first_anode = |
1752 first_anode = |
1760 aNodes[aNodeId].next != -1 ? aNodes[aNodeId].next >> 1 : -1; |
1753 aNodes[aid].next != -1 ? aNodes[aid].next >> 1 : -1; |
1761 } |
1754 } |
1762 if (aNodes[aNodeId].next != -1) { |
1755 if (aNodes[aid].next != -1) { |
1763 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev; |
1756 aNodes[aNodes[aid].next >> 1].prev = aNodes[aid].prev; |
1764 } |
1757 } |
1765 aNodes[aNodeId].next = first_free_anode; |
1758 aNodes[aid].next = first_free_anode; |
1766 first_free_anode = aNodeId; |
1759 first_free_anode = aid; |
1767 } else { |
1760 } else { |
1768 int bNodeId = node.id >> 1; |
1761 int bid = node.id >> 1; |
1769 if (bNodes[bNodeId].prev != -1) { |
1762 if (bNodes[bid].prev != -1) { |
1770 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next; |
1763 bNodes[bNodes[bid].prev >> 1].next = bNodes[bid].next; |
1771 } else { |
1764 } else { |
1772 first_bnode = |
1765 first_bnode = |
1773 bNodes[bNodeId].next != -1 ? bNodes[bNodeId].next >> 1 : -1; |
1766 bNodes[bid].next != -1 ? bNodes[bid].next >> 1 : -1; |
1774 } |
1767 } |
1775 if (bNodes[bNodeId].next != -1) { |
1768 if (bNodes[bid].next != -1) { |
1776 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev; |
1769 bNodes[bNodes[bid].next >> 1].prev = bNodes[bid].prev; |
1777 } |
1770 } |
1778 bNodes[bNodeId].next = first_free_bnode; |
1771 bNodes[bid].next = first_free_bnode; |
1779 first_free_bnode = bNodeId; |
1772 first_free_bnode = bid; |
1780 } |
1773 } |
1781 } |
1774 } |
1782 |
1775 |
1783 void erase(const UEdge& edge) { |
1776 void erase(const UEdge& edge) { |
1784 |
1777 |
2049 } |
2042 } |
2050 virtual void erase(const Node& node) { |
2043 virtual void erase(const Node& node) { |
2051 snapshot.eraseNode(node); |
2044 snapshot.eraseNode(node); |
2052 } |
2045 } |
2053 virtual void erase(const std::vector<Node>& nodes) { |
2046 virtual void erase(const std::vector<Node>& nodes) { |
2054 for (int i = 0; i < (int)nodes.size(); ++i) { |
2047 for (int i = 0; i < int(nodes.size()); ++i) { |
2055 snapshot.eraseNode(nodes[i]); |
2048 snapshot.eraseNode(nodes[i]); |
2056 } |
2049 } |
2057 } |
2050 } |
2058 virtual void build() { |
2051 virtual void build() { |
2059 NodeNotifier* _notifier = notifier(); |
|
2060 Node node; |
2052 Node node; |
2061 std::vector<Node> nodes; |
2053 std::vector<Node> nodes; |
2062 for (_notifier->first(node); node != INVALID; |
2054 for (notifier()->first(node); node != INVALID; |
2063 _notifier->next(node)) { |
2055 notifier()->next(node)) { |
2064 nodes.push_back(node); |
2056 nodes.push_back(node); |
2065 } |
2057 } |
2066 for (int i = nodes.size() - 1; i >= 0; --i) { |
2058 for (int i = nodes.size() - 1; i >= 0; --i) { |
2067 snapshot.addNode(nodes[i]); |
2059 snapshot.addNode(nodes[i]); |
2068 } |
2060 } |
2069 } |
2061 } |
2070 virtual void clear() { |
2062 virtual void clear() { |
2071 NodeNotifier* _notifier = notifier(); |
|
2072 Node node; |
2063 Node node; |
2073 for (_notifier->first(node); node != INVALID; |
2064 for (notifier()->first(node); node != INVALID; |
2074 _notifier->next(node)) { |
2065 notifier()->next(node)) { |
2075 snapshot.eraseNode(node); |
2066 snapshot.eraseNode(node); |
2076 } |
2067 } |
2077 } |
2068 } |
2078 |
2069 |
2079 Snapshot& snapshot; |
2070 Snapshot& snapshot; |
2101 } |
2092 } |
2102 virtual void erase(const UEdge& edge) { |
2093 virtual void erase(const UEdge& edge) { |
2103 snapshot.eraseUEdge(edge); |
2094 snapshot.eraseUEdge(edge); |
2104 } |
2095 } |
2105 virtual void erase(const std::vector<UEdge>& edges) { |
2096 virtual void erase(const std::vector<UEdge>& edges) { |
2106 for (int i = 0; i < (int)edges.size(); ++i) { |
2097 for (int i = 0; i < int(edges.size()); ++i) { |
2107 snapshot.eraseUEdge(edges[i]); |
2098 snapshot.eraseUEdge(edges[i]); |
2108 } |
2099 } |
2109 } |
2100 } |
2110 virtual void build() { |
2101 virtual void build() { |
2111 UEdgeNotifier* _notifier = notifier(); |
|
2112 UEdge edge; |
2102 UEdge edge; |
2113 std::vector<UEdge> edges; |
2103 std::vector<UEdge> edges; |
2114 for (_notifier->first(edge); edge != INVALID; |
2104 for (notifier()->first(edge); edge != INVALID; |
2115 _notifier->next(edge)) { |
2105 notifier()->next(edge)) { |
2116 edges.push_back(edge); |
2106 edges.push_back(edge); |
2117 } |
2107 } |
2118 for (int i = edges.size() - 1; i >= 0; --i) { |
2108 for (int i = edges.size() - 1; i >= 0; --i) { |
2119 snapshot.addUEdge(edges[i]); |
2109 snapshot.addUEdge(edges[i]); |
2120 } |
2110 } |
2121 } |
2111 } |
2122 virtual void clear() { |
2112 virtual void clear() { |
2123 UEdgeNotifier* _notifier = notifier(); |
|
2124 UEdge edge; |
2113 UEdge edge; |
2125 for (_notifier->first(edge); edge != INVALID; |
2114 for (notifier()->first(edge); edge != INVALID; |
2126 _notifier->next(edge)) { |
2115 notifier()->next(edge)) { |
2127 snapshot.eraseUEdge(edge); |
2116 snapshot.eraseUEdge(edge); |
2128 } |
2117 } |
2129 } |
2118 } |
2130 |
2119 |
2131 Snapshot& snapshot; |
2120 Snapshot& snapshot; |