706 |
706 |
707 void firstANode(Node& node) const { |
707 void firstANode(Node& node) const { |
708 node.id = first_anode != -1 ? (first_anode << 1) : -1; |
708 node.id = first_anode != -1 ? (first_anode << 1) : -1; |
709 } |
709 } |
710 void nextANode(Node& node) const { |
710 void nextANode(Node& node) const { |
711 node.id = aNodes[node.id >> 1].next_node; |
711 node.id = aNodes[node.id >> 1].next; |
712 } |
712 } |
713 |
713 |
714 void firstBNode(Node& node) const { |
714 void firstBNode(Node& node) const { |
715 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1; |
715 node.id = first_bnode != -1 ? (first_bnode << 1) + 1 : -1; |
716 } |
716 } |
717 void nextBNode(Node& node) const { |
717 void nextBNode(Node& node) const { |
718 node.id = bNodes[node.id >> 1].next_node; |
718 node.id = bNodes[node.id >> 1].next; |
719 } |
719 } |
720 |
720 |
721 void first(Node& node) const { |
721 void first(Node& node) const { |
722 if (first_anode != -1) { |
722 if (first_anode != -1) { |
723 node.id = (first_anode << 1); |
723 node.id = (first_anode << 1); |
727 node.id = -1; |
727 node.id = -1; |
728 } |
728 } |
729 } |
729 } |
730 void next(Node& node) const { |
730 void next(Node& node) const { |
731 if (aNode(node)) { |
731 if (aNode(node)) { |
732 node.id = aNodes[node.id >> 1].next_node; |
732 node.id = aNodes[node.id >> 1].next; |
733 if (node.id == -1) { |
733 if (node.id == -1) { |
734 if (first_bnode != -1) { |
734 if (first_bnode != -1) { |
735 node.id = (first_bnode << 1) + 1; |
735 node.id = (first_bnode << 1) + 1; |
736 } |
736 } |
737 } |
737 } |
738 } else { |
738 } else { |
739 node.id = bNodes[node.id >> 1].next_node; |
739 node.id = bNodes[node.id >> 1].next; |
740 } |
740 } |
741 } |
741 } |
742 |
742 |
743 void first(UEdge& edge) const { |
743 void first(UEdge& edge) const { |
744 int aNodeId = first_anode; |
744 int aNodeId = first_anode; |
745 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
745 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
746 aNodeId = aNodes[aNodeId].next_node != -1 ? |
746 aNodeId = aNodes[aNodeId].next != -1 ? |
747 aNodes[aNodeId].next_node >> 1 : -1; |
747 aNodes[aNodeId].next >> 1 : -1; |
748 } |
748 } |
749 if (aNodeId != -1) { |
749 if (aNodeId != -1) { |
750 edge.id = aNodes[aNodeId].first_edge; |
750 edge.id = aNodes[aNodeId].first_edge; |
751 } else { |
751 } else { |
752 edge.id = -1; |
752 edge.id = -1; |
754 } |
754 } |
755 void next(UEdge& edge) const { |
755 void next(UEdge& edge) const { |
756 int aNodeId = edges[edge.id].aNode >> 1; |
756 int aNodeId = edges[edge.id].aNode >> 1; |
757 edge.id = edges[edge.id].next_out; |
757 edge.id = edges[edge.id].next_out; |
758 if (edge.id == -1) { |
758 if (edge.id == -1) { |
759 aNodeId = aNodes[aNodeId].next_node != -1 ? |
759 aNodeId = aNodes[aNodeId].next != -1 ? |
760 aNodes[aNodeId].next_node >> 1 : -1; |
760 aNodes[aNodeId].next >> 1 : -1; |
761 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
761 while (aNodeId != -1 && aNodes[aNodeId].first_edge == -1) { |
762 aNodeId = aNodes[aNodeId].next_node != -1 ? |
762 aNodeId = aNodes[aNodeId].next != -1 ? |
763 aNodes[aNodeId].next_node >> 1 : -1; |
763 aNodes[aNodeId].next >> 1 : -1; |
764 } |
764 } |
765 if (aNodeId != -1) { |
765 if (aNodeId != -1) { |
766 edge.id = aNodes[aNodeId].first_edge; |
766 edge.id = aNodes[aNodeId].first_edge; |
767 } else { |
767 } else { |
768 edge.id = -1; |
768 edge.id = -1; |
847 if (first_free_anode == -1) { |
847 if (first_free_anode == -1) { |
848 aNodeId = aNodes.size(); |
848 aNodeId = aNodes.size(); |
849 aNodes.push_back(NodeT()); |
849 aNodes.push_back(NodeT()); |
850 } else { |
850 } else { |
851 aNodeId = first_free_anode; |
851 aNodeId = first_free_anode; |
852 first_free_anode = aNodes[first_free_anode].next_node; |
852 first_free_anode = aNodes[first_free_anode].next; |
853 } |
853 } |
854 aNodes[aNodeId].next_node = |
854 if (first_anode != -1) { |
855 first_anode != -1 ? (first_anode << 1) : -1; |
855 aNodes[aNodeId].next = first_anode << 1; |
|
856 aNodes[first_anode].prev = aNodeId << 1; |
|
857 } else { |
|
858 aNodes[aNodeId].next = -1; |
|
859 } |
|
860 aNodes[aNodeId].prev = -1; |
856 first_anode = aNodeId; |
861 first_anode = aNodeId; |
857 aNodes[aNodeId].first_edge = -1; |
862 aNodes[aNodeId].first_edge = -1; |
858 return Node(aNodeId << 1); |
863 return Node(aNodeId << 1); |
859 } |
864 } |
860 |
865 |
863 if (first_free_bnode == -1) { |
868 if (first_free_bnode == -1) { |
864 bNodeId = bNodes.size(); |
869 bNodeId = bNodes.size(); |
865 bNodes.push_back(NodeT()); |
870 bNodes.push_back(NodeT()); |
866 } else { |
871 } else { |
867 bNodeId = first_free_bnode; |
872 bNodeId = first_free_bnode; |
868 first_free_bnode = bNodes[first_free_bnode].next_node; |
873 first_free_bnode = bNodes[first_free_bnode].next; |
869 } |
874 } |
870 bNodes[bNodeId].next_node = |
875 if (first_bnode != -1) { |
871 first_bnode != -1 ? (first_bnode << 1) + 1 : -1; |
876 bNodes[bNodeId].next = (first_bnode << 1) + 1; |
|
877 bNodes[first_bnode].prev = (bNodeId << 1) + 1; |
|
878 } else { |
|
879 bNodes[bNodeId].next = -1; |
|
880 } |
872 first_bnode = bNodeId; |
881 first_bnode = bNodeId; |
873 bNodes[bNodeId].first_edge = -1; |
882 bNodes[bNodeId].first_edge = -1; |
874 return Node((bNodeId << 1) + 1); |
883 return Node((bNodeId << 1) + 1); |
875 } |
884 } |
876 |
885 |
907 } |
916 } |
908 |
917 |
909 void erase(const Node& node) { |
918 void erase(const Node& node) { |
910 if (aNode(node)) { |
919 if (aNode(node)) { |
911 int aNodeId = node.id >> 1; |
920 int aNodeId = node.id >> 1; |
912 aNodes[aNodeId].next_node = first_free_anode; |
921 if (aNodes[aNodeId].prev != -1) { |
|
922 aNodes[aNodes[aNodeId].prev >> 1].next = aNodes[aNodeId].next; |
|
923 } else { |
|
924 first_anode = aNodes[aNodeId].next >> 1; |
|
925 } |
|
926 if (aNodes[aNodeId].next != -1) { |
|
927 aNodes[aNodes[aNodeId].next >> 1].prev = aNodes[aNodeId].prev; |
|
928 } |
|
929 aNodes[aNodeId].next = first_free_anode; |
913 first_free_anode = aNodeId; |
930 first_free_anode = aNodeId; |
914 } else { |
931 } else { |
915 int bNodeId = node.id >> 1; |
932 int bNodeId = node.id >> 1; |
916 bNodes[bNodeId].next_node = first_free_bnode; |
933 if (bNodes[bNodeId].prev != -1) { |
|
934 bNodes[bNodes[bNodeId].prev >> 1].next = bNodes[bNodeId].next; |
|
935 } else { |
|
936 first_bnode = bNodes[bNodeId].next >> 1; |
|
937 } |
|
938 if (bNodes[bNodeId].next != -1) { |
|
939 bNodes[bNodes[bNodeId].next >> 1].prev = bNodes[bNodeId].prev; |
|
940 } |
|
941 bNodes[bNodeId].next = first_free_bnode; |
917 first_free_bnode = bNodeId; |
942 first_free_bnode = bNodeId; |
918 } |
943 } |
919 } |
944 } |
920 |
945 |
921 void erase(const UEdge& edge) { |
946 void erase(const UEdge& edge) { |
|
947 |
922 if (edges[edge.id].prev_out != -1) { |
948 if (edges[edge.id].prev_out != -1) { |
923 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; |
949 edges[edges[edge.id].prev_out].next_out = edges[edge.id].next_out; |
924 } else { |
950 } else { |
925 aNodes[edges[edge.id].aNode].first_edge = edges[edge.id].next_out; |
951 aNodes[edges[edge.id].aNode >> 1].first_edge = edges[edge.id].next_out; |
926 } |
952 } |
927 if (edges[edge.id].next_out != -1) { |
953 if (edges[edge.id].next_out != -1) { |
928 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; |
954 edges[edges[edge.id].next_out].prev_out = edges[edge.id].prev_out; |
929 } |
955 } |
|
956 |
930 if (edges[edge.id].prev_in != -1) { |
957 if (edges[edge.id].prev_in != -1) { |
931 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; |
958 edges[edges[edge.id].prev_in].next_in = edges[edge.id].next_in; |
932 } else { |
959 } else { |
933 bNodes[edges[edge.id].bNode].first_edge = edges[edge.id].next_in; |
960 bNodes[edges[edge.id].bNode >> 1].first_edge = edges[edge.id].next_in; |
934 } |
961 } |
935 if (edges[edge.id].next_in != -1) { |
962 if (edges[edge.id].next_in != -1) { |
936 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; |
963 edges[edges[edge.id].next_in].prev_in = edges[edge.id].prev_in; |
937 } |
964 } |
|
965 |
938 edges[edge.id].next_out = first_free_edge; |
966 edges[edge.id].next_out = first_free_edge; |
939 first_free_edge = edge.id; |
967 first_free_edge = edge.id; |
940 } |
968 } |
941 |
969 |
942 void clear() { |
970 void clear() { |