package metalexer.jflex.fsm;

import java.util.*;

public class DFA {
    private final int numStates;
    private final int numSymbols;
    private final Integer[/*state*/][/*symbol*/] transitions;
    private final Integer[/*state*/] actions;

    public DFA(Integer[][] transitions, Integer[] actions) {
        this.numStates = transitions.length;
        this.numSymbols = transitions[0].length;
        this.transitions = transitions;
        this.actions = actions;
    }

    //TODO-AC: this is very similar to the code for subset construction
    public DFA minimize() {
        boolean[][] areDistinct = findDistinct();
        int[] stateMap = buildStateMap(areDistinct);

        Map<Integer, Integer[/*symbol*/]> transitionMap = new HashMap<Integer, Integer[]>();
        Map<Integer, Integer> actionMap = new HashMap<Integer, Integer>();

        Integer minimalStartState = stateMap[0]; //always 0, but for clarity...
        Queue<Integer> workList = new LinkedList<Integer>();
        workList.add(minimalStartState);
        List<Integer> minimalStateList = new ArrayList<Integer>();
        while(!workList.isEmpty()) {
            //new state to process - attempt to add entries to both maps
            Integer state = workList.poll();
            if(transitionMap.containsKey(state)) {
                continue; //skip previously encountered states
            }

            //construct a new row for the transition map
            Integer[] row = new Integer[numSymbols];
            for(int sym = 0; sym < numSymbols; sym++) {
                Integer dest = stateMap[transitions[state][sym]];
                row[sym] = dest;
                workList.add(dest);
            }
            transitionMap.put(state, row);

            //add an entry to the action map
            actionMap.put(state, actions[stateMap[state]]);

            minimalStateList.add(state);
        }

        int minimalNumStates = minimalStateList.size();
        Integer[/*stateGroup*/][/*symbol*/] minimalTransitions = new Integer[minimalNumStates][numSymbols];
        Integer[/*stateGroup*/] minimalActions = new Integer[minimalNumStates];

        Map<Integer, Integer> minimalStateNumMap = new HashMap<Integer, Integer>();
        for(int i = 0; i < minimalNumStates; i++) {
            minimalStateNumMap.put(minimalStateList.get(i), i);
        }

        for(int i = 0; i < minimalNumStates; i++) {
            Integer minimalState = minimalStateList.get(i);
            Integer[] row = transitionMap.get(minimalState);
            Integer[] destinations = new Integer[numSymbols];
            for(int j = 0; j < numSymbols; j++) {
                destinations[j] = minimalStateNumMap.get(row[j]);
            }
            minimalTransitions[i] = destinations;
            minimalActions[i] = actionMap.get(minimalState);
        }

        return new DFA(minimalTransitions, minimalActions);
    }

    //from Introduction to Languages and the Theory of Computation, 3ed - John Martin, 2003
    //Algorithm 5.1
    //NB: only use the chunk where row < column
    private boolean[][] findDistinct() {
        boolean[][] areDistinct = new boolean[numStates][];
        //initialize array
        for(int i = 0; i < numStates; i++) {
            areDistinct[i] = new boolean[i];
            for(int j = 0; j < i; j++) {
                areDistinct[i][j] = !equals(actions[i], actions[j]);
            }
        }
        //at this point, false can become true but not vice versa
        while(true) {
            boolean changed = false;

            for(int i = 0; i < numStates; i++) {
                for(int j = 0; j < i; j++) {
                    if(areDistinct[i][j]) {
                        continue;
                    }
                    for(int sym = 0; sym < numSymbols; sym++) {
                        int dest1 = transitions[i][sym];
                        int dest2 = transitions[j][sym];
                        if(dest1 == dest2) {
                            continue;
                        } else if(dest1 < dest2) { //swap to ensure that dest1 is smaller
                            int tmp = dest1;
                            dest1 = dest2;
                            dest2 = tmp;
                        }
                        if(areDistinct[dest1][dest2]) {
                            areDistinct[i][j] = true;
                            changed = true;
                        }
                    }
                }
            }

            if(!changed) {
                break;
            }
        }
        return areDistinct;
    }

    private int[] buildStateMap(boolean[][] areDistinct) {
        int[] stateMap = new int[numStates];
        for(int i = 0; i < numStates; i++) {
            stateMap[i] = i; //default to identity map
            for(int j = 0; j < i; j++) {
                if(!areDistinct[i][j]) {
                    stateMap[i] = j; //override with earlier but equiv state
                    break;
                }
            }
        }
        return stateMap;
    }
    
    public DFA moveAcceptingToEnd() {
        class IndexActionPair implements Comparable<IndexActionPair>{
            int index;
            Integer action;
            public int compareTo(IndexActionPair o) {
                //can't move the first state since it is the start state
                if(this.index == 0) {
                    return -1;
                }
                if(o.index == 0) {
                    return 1;
                }
                if(this.action == null) {
                    return (o.action == null) ? 0 : -1;
                } else {
                    return (o.action == null) ? 1 : 0;
                }
            }
            
        }
        
        IndexActionPair[] array = new IndexActionPair[numStates];
        for(int i = 0; i < numStates; i++) {
            array[i] = new IndexActionPair();
            array[i].index = i;
            array[i].action = actions[i];
        }
        Arrays.sort(array);
        //now the action that was in position i is in position array[i].index
        
        Integer[][] newTransitions = new Integer[numStates][numSymbols];
        Integer[] newActions = new Integer[numStates];
        
        for(int state = 0; state < numStates; state++) {
            newActions[state] = array[state].action;
            for(int sym = 0; sym < numSymbols; sym++) {
                newTransitions[state][sym] = array[transitions[state][sym]].index;
            }
        }
        
        return new DFA(newTransitions, newActions);
    }

    public int getNumStates() {
        return numStates;
    }

    public int getNumSymbols() {
        return numSymbols;
    }

    public Integer[][] getTransitions() {
        return transitions;
    }

    public Integer[] getActions() {
        return actions;
    }

    private static boolean equals(Integer i1, Integer i2) {
        if(i1 == null || i2 == null) {
            return i1 == i2;
        } else {
            return i1.equals(i2);
        }
    }

    //TODO-AC: delete this
    public void dump() {
        System.out.println("DFA");
        System.out.println("Transitions:");
        for(int state = 0; state < numStates; state++) {
            for(int symbol = 0; symbol < numSymbols; symbol++) {
                System.out.print(transitions[state][symbol] + "\t");
            }
            System.out.println();
        }
        System.out.println();
        System.out.println("Actions:");
        for(int state = 0; state < numStates; state++) {
            System.out.println(actions[state]);
        }
    }
}
