###############################################
# module: cyk.py
# Elizabeth Hunt
# A02364151
###############################################


def format_table(derives: list[list[set]], max_row: int) -> str:
    table = ""
    n = len(derives)
    for row in range(max_row):
        curr_row = f"{row+1}: "
        for col in range(n - row):
            set_of_nonterminals = " ".join(derives[row][col])
            curr_row += f"|{set_of_nonterminals}|"
        table += curr_row + "\n"
    return table


class CYK(object):
    @staticmethod
    def is_in_cfl(test_string, cnfg, table_display_flag=False):
        n = len(test_string)
        derives = [[set() for _ in range(n)] for _ in range(n)]

        for i, terminal in enumerate(test_string):
            derives[0][i] |= cnfg.fetch_lhs(terminal)
        if table_display_flag:
            print(format_table(derives, 1))

        for length in range(2, n + 1):
            for start in range(n - length + 1):
                for split_idx in range(1, length):
                    for first in derives[split_idx - 1][start]:
                        for second in derives[length - split_idx - 1][
                            start + split_idx
                        ]:
                            derives[length - 1][start] |= cnfg.fetch_lhs(first, second)

            if table_display_flag:
                print(format_table(derives, length))

        return "S" in derives[n - 1][0]