#!/usr/bin/env python2.6

"""
easim.py 0.1

Usage: easim.py <easpec> [<word>]...

Read a Deteministic Finite Automaton specification and a list of
words, and process the words using the DFA.

Options:

-h 
--help  Print this help.

-d
--dot   Print a description of the automaton in the Graphviz language
        suitable for processing with dot to get a graphical
        representation of the automaton.

-p      
--print Print back the automaton in tabular form.

Copyright 2014 Stephan Schulz, schulz@eprover.org

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program ; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston,
MA  02111-1307 USA 

The original copyright holder can be contacted as

Stephan Schulz 
DHBW Stuttgart
Informatik
Postfach 10 05 63
D-70004 Stuttgart
Germany

or via email (address above).
"""

import sys
import getopt


class DFA(object):
    """
    Object representing a (deterministic) finite automaton.
    """

    def __init__(self, spec):        
        self.states = set()
        self.sigma  = []
        self.delta  = {}        
        self.start  = None
        self.accept = set()
        self.parse(spec)

    def delta_fun(self, state, letter):
        return self.delta[(state, letter)]

    def proc_string(self, string):
        print "Processing: ", string

        state = self.start
        for c in string:
            newstate = self.delta_fun(state, c)
            print state, "::", c, "->", newstate
            state=newstate

        if state in self.accept:
            print "Accepted\n"
        else:
            print "Rejected\n"

    def parse(self, spec):
        
        lines = spec.split("\n")
        # Find sigma
        while True:
            i = lines.pop(0)
            l=i.strip()
            if l:
                sigmastr = l.split("|")[1]
                self.sigma = sigmastr.split()
                break
            
        # Skip ---------
        while True:
            i = lines.pop(0)
            l=i.strip()
            if l:
                break
        # Process the rest - "(->)?(*)? state | state1 ... staten"
        while lines:
            i = lines.pop(0)
            l=i.strip()
            if l:
                state, values = l.split("|")
                state = state.strip()
               
                start  = False
                accept = False
                if state.startswith("->"):
                    start = True
                    state = state[2:].strip()
                if state.startswith("*"):
                    accept = True
                    state = state[1:].strip()
                    
                self.states.add(state)
                if start:
                    self.start = state
                if accept:
                    self.accept.add(state)

                
                dvals = values.split()

                for i in xrange(len(self.sigma)):
                    self.delta[(state, self.sigma[i])] = dvals[i]

    def __str__(self):
        res = list()
        sigma = sorted(self.sigma)
        l1 = "         | "+" ".join(["%4s"%(i,) for i in sigma])
        res.append(l1)
        l2 = "-"*(len(l1)+1)
        res.append(l2)

        for i in sorted(self.states):
            if i == self.start:
                start = "->"
            else:
                start = "  "
            if i in self.accept:
                accept = "*"
            else:
                accept = " "
        
            xstate = "%2s %1s %3s | " %(start, accept, i)
            l = xstate+" ".join(["%4s"% (self.delta[(i,s)],) for s in sigma])
            res.append(l)
        
        return "\n".join(res)


    dfa_dot_template = """
digraph finite_state_machine {
   rankdir=LR;
   size="8,5"
   node [shape = plaintext]; dummy_x23z [label = ""];
   node [shape = doublecircle]; %s
   node [shape = circle]; %s
%s
}
"""
           
    def dotify(self):        

        accepts_str = " ".join(self.accept)
        if accepts_str:
            accepts_str += ";"

        other_states = [state for state in self.states if not state in self.accept]
        other_str = " ".join(other_states)
        if other_str:
            other_str += ";"
        
        transitions = []    
        if self.start:
            transitions.append("   dummy_x23z -> %s\n"%(self.start,))

        for i in self.delta.keys():
            source, label = i
            to = self.delta_fun(source, label)
            transitions.append("   %s -> %s [label = \"%s\"];\n"%
                               (source, to, label))
        
        transitions_str = "".join(transitions)

        return self.dfa_dot_template%(accepts_str,other_str,transitions_str)


dot = False
prt = False

if __name__ == '__main__':
    opts, args = getopt.gnu_getopt(sys.argv[1:], "hdp", ["help", "dot", "print"])

    for option, optarg in opts:
        if option in ["-h", "--help"]:
            print __doc__
            sys.exit()
        elif option in ["-d", "--dot"]:
            dot = True
        elif option in ["-p", "--print"]:
            prt = True
        else:
            sys.exit("Unknown option "+ option)

    if len(args)<1:
        print __doc__
        sys.exit()

    file = open(args[0], "r")
    str  = file.read()
    file.close()

    ea = DFA(str)

    if prt:
        print ea
        print
    if dot:
        print ea.dotify()
        print
    
    for arg in args[1:]:
        ea.proc_string(arg)