package machine;

import java.util.*;

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

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

    public DFA convertToDFA() {
        Map<BitSet, BitSet[/*symbol*/]> transitionMap = new HashMap<BitSet, BitSet[]>();
        Map<BitSet, Integer> actionMap = new HashMap<BitSet, Integer>();

        BitSet startStateGroup = new BitSet(numStates);
        startStateGroup.set(0); //start state is always first
        Queue<BitSet> workList = new LinkedList<BitSet>();
        workList.add(startStateGroup);
        List<BitSet> stateGroupList = new ArrayList<BitSet>();
        while(!workList.isEmpty()) {
            //new state group to process - attempt to add entries to both maps
            BitSet stateGroup = workList.poll();
            if(transitionMap.containsKey(stateGroup)) {
                continue; //skip previously encountered states
            }

            //construct a new row for the transition map
            BitSet[] row = new BitSet[numSymbols];
            for(int sym = 0; sym < numSymbols; sym++) {
                BitSet destinationStateSet = new BitSet(numStates);
                for(int state = 0; state < numStates; state++) {
                    if(stateGroup.get(state)) {
                        destinationStateSet.or(transitions[state][sym]);
                    }
                }
                row[sym] = destinationStateSet;
                workList.add(destinationStateSet);
            }
            transitionMap.put(stateGroup, row);

            //add an entry to the action map if any state in the group has an action
            for(int state = 0; state < numStates; state++) {
                if(stateGroup.get(state) && actions[state] != null) {
                    actionMap.put(stateGroup, actions[state]);
                    break;
                }
            }

            stateGroupList.add(stateGroup);
        }

        int numStateGroups = stateGroupList.size();
        Integer[/*stateGroup*/][/*symbol*/] dfaTransitions = new Integer[numStateGroups][numSymbols];
        Integer[/*stateGroup*/] dfaActions = new Integer[numStateGroups];

        Map<BitSet, Integer> groupToStateMap = new HashMap<BitSet, Integer>();
        groupToStateMap.put(new BitSet(numSymbols), null); //map empty to null
        for(int i = 0; i < numStateGroups; i++) {
            BitSet stateGroup = stateGroupList.get(i);
            groupToStateMap.put(stateGroup, i);
        }

        for(int i = 0; i < numStateGroups; i++) {
            BitSet stateGroup = stateGroupList.get(i);
            BitSet[] row = transitionMap.get(stateGroup);
            Integer[] destinations = new Integer[numSymbols];
            for(int j = 0; j < numSymbols; j++) {
                destinations[j] = groupToStateMap.get(row[j]);
            }
            dfaTransitions[i] = destinations;
            dfaActions[i] = actionMap.get(stateGroup);
        }

        return new DFA(dfaTransitions, dfaActions);
    }
    
    public void dump() {
        System.out.println("NFA");
        System.out.println("Transitions:");
        for(int state = 0; state < numStates; state++) {
            for(int symbol = 0; symbol < numSymbols; symbol++) {
                System.out.print(toString(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]);
        }
    }
    
    public static String toString(BitSet set) {
        StringBuffer buf = new StringBuffer();
        buf.append('{');
        boolean first = true;
        for(int i = 0; i < set.size(); i++) {
            if(set.get(i)) {
                if(!first) {
                    buf.append(',');
                }
                buf.append(i);
                first = false;
            }
        }
        buf.append('}');
        return buf.toString();
    }
}
