import os

# Static DFA
# Deterministic Finite Automaton
# One start state, multiple final states, and one error state
# Can only add transitions
class DFA:

    def __init__(self, states_count, start_state, final_states, err_state):
        self.sc = states_count
        # adjency matrix for transitions
        # each entry is a set of chars
        self.adj = [set() for _ in range(self.sc*self.sc)]
        self.start = start_state
        self.finals = final_states
        self.err = err_state

        # transition matrix
        # trans[i][c] = j means consume char c from state i lead to state j
        self.trans = [dict() for _ in range(self.sc)] 

    # transition from state s0 to s1 with char c
    # c can be None for spontaneaous transitions
    def add_transition(self, s0, s1, c):
        assert c not in self.trans[s0] #define every transition only once
        self.trans[s0][c] = s1

    # doesn't write error state to limit number of transitions
    def save_dot(self, out_path):

        ENTRY = '__entry'
        
        with open(out_path, 'w') as f:
            f.write('digraph G {\n')
            f.write("rankdir=LR;\n")
            f.write('size="8,5"\n')
            f.write('node [shape = point ]; {};\n'.format(ENTRY))

            # Define states
            for s in range(self.sc):
                if s == self.err: #ignore error state
                    continue
                if s in self.finals:
                    f.write('node [shape = doublecircle]; ')
                else:
                    f.write('node [shape = circle]; ')
                f.write('{};\n'.format(s))
                

            # Draw transition for entry state
            f.write('{} -> {};\n'.format(ENTRY, self.start))
                
            #draw other transitions
            for s0 in range(self.sc):
                if s0 == self.err:
                    continue
                for c, s1 in self.trans[s0].items():
                    if s1 == self.err: #ignore error state
                        continue
                    f.write('{} -> {} [ label="{}" ];\n'.format(s0, s1, c))

            
                
            f.write('}\n')


    def logia_doc_write(self, doc):
        fname = doc.gen_file_name()
        dot_path = os.path.join(doc.out_dir(), fname + ".dot")
        self.save_dot(dot_path)
        doc.img("NFA", doc.get_file_path(fname + ".png"))

    # Check if the DFA is valid
    def check(self, alpha):

        # check if there is a transition for all char in every states
        # and only for chars
        for tr in self.trans:
            if len(tr) > 0: #ignore removed states
                assert sorted(alpha.larr) == sorted(tr.keys())
                
        # check if err state only lead to err state
        err_tr = self.trans[self.err]
        for s in err_tr.values():
            assert s == self.err

        # check if final state is empty
        # it doesn't check if reachable
        assert len(self.finals) > 0
        

    # returns True if s matches the DFA
    def match(self, s):
        state = self.start
        for c in s:
            state = self.trans[state][c]
        return state in self.finals
        

import os

# Static DFA
# Deterministic Finite Automaton
# One start state, multiple final states, and one error state
# Can only add transitions
class DFA:

    def __init__(self, states_count, start_state, final_states, err_state):
        self.sc = states_count
        # adjency matrix for transitions
        # each entry is a set of chars
        self.adj = [set() for _ in range(self.sc*self.sc)]
        self.start = start_state
        self.finals = final_states
        self.err = err_state

        # transition matrix
        # trans[i][c] = j means consume char c from state i lead to state j
        self.trans = [dict() for _ in range(self.sc)] 

    # transition from state s0 to s1 with char c
    # c can be None for spontaneaous transitions
    def add_transition(self, s0, s1, c):
        assert c not in self.trans[s0] #define every transition only once
        self.trans[s0][c] = s1

    # doesn't write error state to limit number of transitions
    def save_dot(self, out_path):

        ENTRY = '__entry'
        
        with open(out_path, 'w') as f:
            f.write('digraph G {\n')
            f.write("rankdir=LR;\n")
            f.write('size="8,5"\n')
            f.write('node [shape = point ]; {};\n'.format(ENTRY))

            # Define states
            for s in range(self.sc):
                if s == self.err: #ignore error state
                    continue
                if s in self.finals:
                    f.write('node [shape = doublecircle]; ')
                else:
                    f.write('node [shape = circle]; ')
                f.write('{};\n'.format(s))
                

            # Draw transition for entry state
            f.write('{} -> {};\n'.format(ENTRY, self.start))
                
            #draw other transitions
            for s0 in range(self.sc):
                if s0 == self.err:
                    continue
                for c, s1 in self.trans[s0].items():
                    if s1 == self.err: #ignore error state
                        continue
                    f.write('{} -> {} [ label="{}" ];\n'.format(s0, s1, c))

            
                
            f.write('}\n')


    def logia_doc_write(self, doc):
        fname = doc.gen_file_name()
        dot_path = os.path.join(doc.out_dir(), fname + ".dot")
        self.save_dot(dot_path)
        doc.img("NFA", doc.get_file_path(fname + ".png"))

    # Check if the DFA is valid
    def check(self, alpha):

        # check if there is a transition for all char in every states
        # and only for chars
        for tr in self.trans:
            if len(tr) > 0: #ignore removed states
                assert sorted(alpha.larr) == sorted(tr.keys())
                
        # check if err state only lead to err state
        err_tr = self.trans[self.err]
        for s in err_tr.values():
            assert s == self.err

        # check if final state is empty
        # it doesn't check if reachable
        assert len(self.finals) > 0
        

    # returns True if s matches the DFA
    def match(self, s):
        state = self.start
        for c in s:
            state = self.trans[state][c]
        return state in self.finals
        

# Static DFA # Deterministic Finite Automaton # One start state, multiple final states, and one error state # Can only add transitions # adjency matrix for transitions # each entry is a set of chars # transition matrix # trans[i][c] = j means consume char c from state i lead to state j # transition from state s0 to s1 with char c # c can be None for spontaneaous transitions #define every transition only once # doesn't write error state to limit number of transitions # Define states #ignore error state # Draw transition for entry state #draw other transitions #ignore error state # Check if the DFA is valid # check if there is a transition for all char in every states # and only for chars #ignore removed states # check if err state only lead to err state # check if final state is empty # it doesn't check if reachable # returns True if s matches the DFA