<gh_stars>0
import enum
from sortedcontainers import SortedList


class SymbolNode:
    __node_id = 0

    @staticmethod
    def __get_node_id():
        SymbolNode.__node_id += 1
        return SymbolNode.__node_id

    class NodeNature(enum.Enum):
        NON_TERMINAL = 0
        TERMINAL = 1

    def __init__(self, node_nature=None):

        self.__node_id = SymbolNode.__get_node_id()

        # These are always sorted
        # self.__sub_graph_word_left = []
        self.__subgraph_word = SortedList()

        self.__child_nodes = {}  # stores the associations {symbol -> node}
        self.__reverse_index_child_nodes = {}  # stores the associations {node -> set of symbols}

        self.__parent_nodes = set()  # stores the parent nodes

        if node_nature is None:
            self.__node_nature = SymbolNode.NodeNature.NON_TERMINAL
        else:
            self.__node_nature = node_nature

    def __str__(self):

        result = []
        result.append(self.__node_id)
        for node, symbol_set in self.__reverse_index_child_nodes.items():
            result.append(
                ((self.__node_id, node.get_node_id()), symbol_set)
            )
        result.append("Terminal" if self.__node_nature is SymbolNode.NodeNature.TERMINAL else "Non-Terminal")
        # return str({"node id:": self.__node_id,
        #             " child nodes:": [node.get_all_child_node_id() for node in self.__reverse_index_child_nodes]})

        return str(result)

    def get_edges_and_labels(self):
        edges = []
        edge_labels = {}
        for node, symbol_set in self.__reverse_index_child_nodes.items():
            cur_node_id = str(self.__node_id)
            conn_node_id = str(node.get_node_id())
            edges.append((cur_node_id, conn_node_id))
            edge_labels[(cur_node_id, conn_node_id)] = str(symbol_set)

        return edges, edge_labels, self.get_node_nature()

    def get_node_nature(self):
        return self.__node_nature

    def mark_node_terminal(self):
        self.__node_nature = SymbolNode.NodeNature.TERMINAL

    def mark_node_non_terminal(self):
        self.__node_nature = SymbolNode.NodeNature.NON_TERMINAL

    def __hash__(self):
        return hash(self.__node_id)

    def get_node_id(self):
        return self.__node_id

    def __add_child_node_low(self, symbol, node):
        self.__child_nodes[symbol] = node
        if node not in self.__reverse_index_child_nodes:
            self.__reverse_index_child_nodes[node] = set()
        self.__reverse_index_child_nodes[node].add(symbol)
        node.__parent_nodes.add(self)

    def add_child_node(self, symbol, node, subset_word_right):
        """
        Forcefully adds child node, even if a different node was already present,
        by replacing the previous node
        :param symbol:
        :param node:
        :param subset_word_right:
        :return:
        """
        if symbol not in self.__child_nodes:
            self.__add_child_node_low(symbol, node)

        # self.__sub_graph_word_left.append(tuple(sub_graph_word_left))
        # self.__sub_graph_word_left.sort()
        subset_word_right = tuple(subset_word_right)

        if subset_word_right not in self.__subgraph_word:
            self.__subgraph_word.add(tuple(subset_word_right))

        # sorting ensures that each subgraph with the same structure
        # will have the same value (when hashed)
        # self.__subgraph_word.sort()

    def __reset_parents_low(self):
        self.__parent_nodes = set()

    def __remove_parent_node_connection(self, parent_node):
        if parent_node in self.__parent_nodes:
            self.__parent_nodes.remove(parent_node)

    def __remove_child_node_connection(self, child_node):
        if child_node in self.__reverse_index_child_nodes:
            symbol_set = self.__reverse_index_child_nodes[child_node]
            for symbol in symbol_set:
                del self.__child_nodes[symbol]
            del self.__reverse_index_child_nodes[child_node]

    def __disconnect_from_parent_node(self, parent_node):
        self.__remove_parent_node_connection(parent_node)
        parent_node.__remove_child_node_connection(self)

    def __disconnect_from_child_node(self, child_node):
        child_node.__remove_parent_node_connection(self)
        self.__remove_child_node_connection(child_node)

    def __get_parent_node_key_tuple(self, parent_node):
        if parent_node in self.__parent_nodes:
            return tuple(parent_node.__reverse_index_child_nodes[self])

    def steal_parent_links(self, node):
        parent_nodes = tuple(node.__parent_nodes)
        for parent_node in parent_nodes:
            symbol_tuple = node.__get_parent_node_key_tuple(parent_node)
            node.__disconnect_from_parent_node(parent_node)
            for symbol in symbol_tuple:
                parent_node.__add_child_node_low(symbol, self)

    def get_subgraph_words_tuple(self):
        return tuple(self.__subgraph_word)

    def link_to_child_exists(self, symbol):
        return symbol in self.__child_nodes

    def get_child_node(self, symbol):
        if self.link_to_child_exists(symbol):
            return self.__child_nodes[symbol]

    def get_all_child_node_symbols(self):
        return list(self.__child_nodes.keys())

    def get_all_child_node_id(self):

        result = []

        for node in self.__child_nodes.values():
            result.append(node.get_node_id())

        return result

    def get_all_child_nodes(self):
        """
        unused- to be deleted
        :return:
        """
        return list(self.__child_nodes.values())

    def get_all_parent_node_id(self):
        result = []

        for node in self.__parent_nodes:
            result.append(node.get_node_id())

        return result

    def get_all_parent_nodes(self):
        """
        unused- to be deleted
        :return:
        """
        return tuple(self.__parent_nodes)

import enum
from sortedcontainers import SortedList


class SymbolNode:
    __node_id = 0

    @staticmethod
    def __get_node_id():
        SymbolNode.__node_id += 1
        return SymbolNode.__node_id

    class NodeNature(enum.Enum):
        NON_TERMINAL = 0
        TERMINAL = 1

    def __init__(self, node_nature=None):

        self.__node_id = SymbolNode.__get_node_id()

        # These are always sorted
        # self.__sub_graph_word_left = []
        self.__subgraph_word = SortedList()

        self.__child_nodes = {}  # stores the associations {symbol -> node}
        self.__reverse_index_child_nodes = {}  # stores the associations {node -> set of symbols}

        self.__parent_nodes = set()  # stores the parent nodes

        if node_nature is None:
            self.__node_nature = SymbolNode.NodeNature.NON_TERMINAL
        else:
            self.__node_nature = node_nature

    def __str__(self):

        result = []
        result.append(self.__node_id)
        for node, symbol_set in self.__reverse_index_child_nodes.items():
            result.append(
                ((self.__node_id, node.get_node_id()), symbol_set)
            )
        result.append("Terminal" if self.__node_nature is SymbolNode.NodeNature.TERMINAL else "Non-Terminal")
        # return str({"node id:": self.__node_id,
        #             " child nodes:": [node.get_all_child_node_id() for node in self.__reverse_index_child_nodes]})

        return str(result)

    def get_edges_and_labels(self):
        edges = []
        edge_labels = {}
        for node, symbol_set in self.__reverse_index_child_nodes.items():
            cur_node_id = str(self.__node_id)
            conn_node_id = str(node.get_node_id())
            edges.append((cur_node_id, conn_node_id))
            edge_labels[(cur_node_id, conn_node_id)] = str(symbol_set)

        return edges, edge_labels, self.get_node_nature()

    def get_node_nature(self):
        return self.__node_nature

    def mark_node_terminal(self):
        self.__node_nature = SymbolNode.NodeNature.TERMINAL

    def mark_node_non_terminal(self):
        self.__node_nature = SymbolNode.NodeNature.NON_TERMINAL

    def __hash__(self):
        return hash(self.__node_id)

    def get_node_id(self):
        return self.__node_id

    def __add_child_node_low(self, symbol, node):
        self.__child_nodes[symbol] = node
        if node not in self.__reverse_index_child_nodes:
            self.__reverse_index_child_nodes[node] = set()
        self.__reverse_index_child_nodes[node].add(symbol)
        node.__parent_nodes.add(self)

    def add_child_node(self, symbol, node, subset_word_right):
        """
        Forcefully adds child node, even if a different node was already present,
        by replacing the previous node
        :param symbol:
        :param node:
        :param subset_word_right:
        :return:
        """
        if symbol not in self.__child_nodes:
            self.__add_child_node_low(symbol, node)

        # self.__sub_graph_word_left.append(tuple(sub_graph_word_left))
        # self.__sub_graph_word_left.sort()
        subset_word_right = tuple(subset_word_right)

        if subset_word_right not in self.__subgraph_word:
            self.__subgraph_word.add(tuple(subset_word_right))

        # sorting ensures that each subgraph with the same structure
        # will have the same value (when hashed)
        # self.__subgraph_word.sort()

    def __reset_parents_low(self):
        self.__parent_nodes = set()

    def __remove_parent_node_connection(self, parent_node):
        if parent_node in self.__parent_nodes:
            self.__parent_nodes.remove(parent_node)

    def __remove_child_node_connection(self, child_node):
        if child_node in self.__reverse_index_child_nodes:
            symbol_set = self.__reverse_index_child_nodes[child_node]
            for symbol in symbol_set:
                del self.__child_nodes[symbol]
            del self.__reverse_index_child_nodes[child_node]

    def __disconnect_from_parent_node(self, parent_node):
        self.__remove_parent_node_connection(parent_node)
        parent_node.__remove_child_node_connection(self)

    def __disconnect_from_child_node(self, child_node):
        child_node.__remove_parent_node_connection(self)
        self.__remove_child_node_connection(child_node)

    def __get_parent_node_key_tuple(self, parent_node):
        if parent_node in self.__parent_nodes:
            return tuple(parent_node.__reverse_index_child_nodes[self])

    def steal_parent_links(self, node):
        parent_nodes = tuple(node.__parent_nodes)
        for parent_node in parent_nodes:
            symbol_tuple = node.__get_parent_node_key_tuple(parent_node)
            node.__disconnect_from_parent_node(parent_node)
            for symbol in symbol_tuple:
                parent_node.__add_child_node_low(symbol, self)

    def get_subgraph_words_tuple(self):
        return tuple(self.__subgraph_word)

    def link_to_child_exists(self, symbol):
        return symbol in self.__child_nodes

    def get_child_node(self, symbol):
        if self.link_to_child_exists(symbol):
            return self.__child_nodes[symbol]

    def get_all_child_node_symbols(self):
        return list(self.__child_nodes.keys())

    def get_all_child_node_id(self):

        result = []

        for node in self.__child_nodes.values():
            result.append(node.get_node_id())

        return result

    def get_all_child_nodes(self):
        """
        unused- to be deleted
        :return:
        """
        return list(self.__child_nodes.values())

    def get_all_parent_node_id(self):
        result = []

        for node in self.__parent_nodes:
            result.append(node.get_node_id())

        return result

    def get_all_parent_nodes(self):
        """
        unused- to be deleted
        :return:
        """
        return tuple(self.__parent_nodes)
# These are always sorted # self.__sub_graph_word_left = [] # stores the associations {symbol -> node} # stores the associations {node -> set of symbols} # stores the parent nodes # return str({"node id:": self.__node_id, #             " child nodes:": [node.get_all_child_node_id() for node in self.__reverse_index_child_nodes]}) Forcefully adds child node, even if a different node was already present,         by replacing the previous node         :param symbol:         :param node:         :param subset_word_right:         :return: # self.__sub_graph_word_left.append(tuple(sub_graph_word_left)) # self.__sub_graph_word_left.sort() # sorting ensures that each subgraph with the same structure # will have the same value (when hashed) # self.__subgraph_word.sort() unused- to be deleted         :return: unused- to be deleted         :return: