package metalexer.jflex.fsm;

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 = stateGroup.nextSetBit(0); state >= 0; state = stateGroup.nextSetBit(state + 1)) {
                    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 = stateGroup.nextSetBit(0); state >= 0; state = stateGroup.nextSetBit(state + 1)) {
                if(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);
    }
}
