#!/usr/bin/env python

import curses.ascii as ascii
import copy, collections
from fa import FA

class DFA(FA):
    def __init__(self, transition, start, accepts, states, assoc):
        FA.__init__(self, transition, start, accepts, states)
        self.assoc = assoc

    def copy_from(self, dfa):
        self.start = dfa.start
        self.transition = copy.deepcopy(dfa.transition)
        self.accepts = copy.deepcopy(dfa.accepts)
        self.states = copy.deepcopy(dfa.states)
        self.assoc = copy.deepcopy(dfa.assoc)

    @classmethod
    def copy(cls, dfa_):
        dfa = DFA(dfa_)
        dfa.copy_from(dfa)
        return dfa

    def get_runtime(self):
        return DFARuntime(self)

class SuffixDFA(DFA):
    def __init__(self, dfa, pdfa):
        self.copy_from(dfa)
        self.pdfa = pdfa
        self.acceptable = dict()
        self.make_acceptable()

    def setdict(self):
        return collections.defaultdict(set)

    def make_acceptable(self):
        self.acceptable = collections.defaultdict(self.setdict)

        def search_acceptable(pcur, scur, searched, history, pstart):
            for i, pnext in self.pdfa.transition[pcur].iteritems():
                if (pnext, i) in searched: continue
                searched_ = searched + [(pnext, i)]
                snext = self.transition[(scur, i)]
                if scur not in history:
                    history_ = history + (scur,)
                else:
                    history_ = history
                if pnext in self.pdfa.accepts:
                    self.acceptable[snext][history_].add(pstart)
                search_acceptable(pnext, snext, searched_, history_, pstart)

        for s in self.pdfa.states:
            search_acceptable(s, self.start, [], (), s)

class DFARuntime(object):
    def __init__(self, DFA):
        self.DFA = DFA
        self.curState = self.DFA.start

    def do_transition(self, char):
        self.curState = self.DFA.transition[self.curState, char]

    def is_accept_state(self):
        return self.curState in self.DFA.accepts

    def accept(self, string):
        try:
            for alphabet in string:
                self.do_transition(alphabet)
        except KeyError:
            return False
        return self.is_accept_state()