// Abstract finite state machine implementation  (version 3, Spring 2017)

/*
A finite state machine is defined by:
1. a number of states, with a designated start state and some accept states
2. a number of possible inputs
3. a table that defines for each state s and input i:
   i. additional conditions to check at the current state, and
      possibly actions to take.
  ii. the next state to transition to.

A finite state machine executes on a stream of inputs, starting at the
start state and ending when either the end of input is reached or an
accept state is reached.

In this implementation, states are always numbers and the start state
is always 0, but the input can be any type <T>.  The entry of each
action[state][input] is a an instance of interface action (also called
a "delegate").  Using the latest features added since jdk 1.8, we can
create classes and instances that implement action using convenient
"lambda expressions".

We will also use our own hashmap from the previous lab (if you don't have
it working, use java.util.HashMap instead).  The hashmap maps the input into
an array index (the column index of the 2D action table).

The following methods must be defined in the subclass:

    protected abstract void setHash(); // initializes hash table
    protected abstract void setStateTable(); // initializes action table
    protected abstract T nextInput(); //gets next available input, null if none
    protected boolean acceptState(int s) { return s==0; }  // should override

    The acceptState function defines which states are accepting
    states, and should be overridden in the subclass.

The constructor of the subclass must set the states and maxinputs variables
and create the action array.

In addition, the following boolean flags can be set for each instance
of the machine:

    public boolean trace = false; // for debuggging messages
    public boolean keeprunning = false; // runs after accept state reached
    public boolean skipbadinput = true; // invalid inputs are ignored

Setting trace to true will print the current state and input for each action.

If keeprunning is set to false, then the machine terminates upon reaching
the first accept state; if set to true, then it will continue to run until
the end of input is reached (when nextInput() returns null).  

If skipbadinput is set to false, then upon encountering an empty hash table
or action table entry, the program terminates with an error message; if set
to true (default) then the bad input is simply ignored: the machine stays at
the same state.

The machine is executed by public boolean run(), which returns true
if machine terminated in an accept state.  See dfa3.java for example.
*/

interface action  // entry of state transition table
{
    int act();   // perform action, returns new state
}

// abstract hash table interface to allow any hash table implementation:
interface Ihashmap<KT, DT> // from lab 5
{
    int size(); // return number of values currently in the table
    int remainingCapacity();  // return remaining capacity of the table

    boolean set(KT key, DT data); // insert new key,data pair
    // this function should return true if it replaced some existing data and
    // false if no data was previously associated with key.

    DT get(KT key); //search for data associated with key, null if not found

    boolean remove(KT key); // delete data associated with key.  This function
    // should return true if something was actually deleted, and false
    // if no data was previously associated with key.
}

// The following is an example of an "object adapter", which adopts another
// implementation of hash tables to be compliant with the above interface,
// in this case, it adopts the built-in java.util.HashMap class

class JHMadaptor<KT,DT> implements Ihashmap<KT,DT>
{
    protected java.util.HashMap<KT,DT> H; // internal java hash table
    public JHMadaptor() { H = new java.util.HashMap<KT,DT>(); }
    public JHMadaptor(int max) { H = new java.util.HashMap<KT,DT>(max); }
    public int size() { return H.size(); }
    public int remainingCapacity()
    { throw new RuntimeException("feature not available"); }

    public boolean set(KT key, DT value)
    {
	DT previous = H.put(key,value);  
	return (previous!=null);
    }

    public DT get(KT key)
    {
	return H.get(key);
    }

    public boolean remove(KT key)
    {
       DT prev = H.remove(key);
       return prev!=null;
    }
}//JHMadaptor


// main class for Abstract Finite State Machine:

public abstract class FSM3<T> // T indicates type of input, likely String
{ 
    // the following variables need to be initialized in subclass constructor
    protected int states;  // number of states, assume 0 is start state.
    protected int maxinputs; // number of different inputs
    protected action[][] M; // the state action/transition table.

    // Methods to be implemented or overridden in subclass: ****************
    protected abstract void setHash();
    protected abstract void setStateTable();
    protected abstract T nextInput(); //gets next available input, null if none
    protected boolean acceptState(int s) { return s==0; }  // should override

    // the following variable can be intialized in subclass setHash function
    protected Ihashmap<T,Integer> Hash; // maps input to column indices 

    protected int cs; // current state.
    public int cs() { return cs; }  // read only attribute

    // optional parameters that can be changed:
    public boolean trace = false; // for debugging messages
    public boolean keeprunning = false; // runs after accept state reached
    public boolean skipbadinput = true; // invalid inputs are ignored

    // polymorphic transition method, called for each input x
    public void transition(T x)
    {
	if (trace)
	    System.out.println("state "+cs+", input "+x);

	Integer i = Hash.get(x);  // get index from hash table
	if (i==null || i<0 || i>=maxinputs || M[cs][i]==null) //check bad input
	    {
		if (skipbadinput) return;
		else throw new RuntimeException("unrecognized input "+x);
	    }
	cs = M[cs][i].act();  // perform action and transition to new state
    }//transition

    public boolean run() // run machine, return true on success
    {
	//	setHash();   // should call in subclass
	//	setStateTable(); 
	cs = 0; // set current state to start state 
	T x = nextInput();
	while (x!=null && (keeprunning || !acceptState(cs)))
	    {
		transition(x);
		x = nextInput();
	    }
	if (trace) System.out.println("final state "+cs);
	return acceptState(cs); // returns true if ends in an accept state.
    }
}//FSM3