package metalexer.jflex.fsm;

import java.util.*;

public class ENFA {
    private final int numStates;
    private final int numSymbols;

    private final BitSet[/*state*/][/*symbol*/] transitions;
    private final BitSet[/*state*/] epsilons;
    private final Integer[/*state*/] actions;

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

    public NFA convertToNFA() {
        BitSet[/*state*/] epsilonClosures = new BitSet[numStates];
        for(int state = 0; state < numStates; state++) {
            epsilonClosures[state] = buildEpsilonClosure(state);
        }
        
        BitSet[/*state*/][/*symbol*/] nfaTransitions = new BitSet[numStates][numSymbols];
        for(int state = 0; state < numStates; state++) {
            for(int sym = 0; sym < numSymbols; sym++) {
                BitSet closure = epsilonClosures[state];
                BitSet destination = new BitSet(numStates);
                for(int st = closure.nextSetBit(0); st >= 0; st = closure.nextSetBit(st + 1)) {
                    destination.or(transitions[st][sym]);
                }
                destination = epsilonClosure(destination, epsilonClosures);
                nfaTransitions[state][sym] = destination;
            }
        }
        return new NFA(nfaTransitions, actions); //NB: contains unreachable states
    }

    private BitSet buildEpsilonClosure(int state) {
        BitSet closure = new BitSet();
        closure.set(state); //include original state
        //System.err.println("Building closure of " + toString(closure));
        while(true) {
            BitSet nextStep = buildEpsilonClosureStep(closure);
            if(nextStep.equals(closure)) {
                //System.err.println("Returning " + toString(closure));
                return closure;
            }
            closure = nextStep;
            //System.err.println("Step to " + toString(closure));
        }
    }

    private BitSet buildEpsilonClosureStep(BitSet stateGroup) {
        BitSet nextStep = new BitSet();
        nextStep.or(stateGroup); //include all actual states
        for(int state = stateGroup.nextSetBit(0); state >= 0; state = stateGroup.nextSetBit(state + 1)) {
            nextStep.or(epsilons[state]);
        }
        return nextStep;
    }
    
    private BitSet epsilonClosure(BitSet stateGroup, BitSet[] epsilonClosures) {
        BitSet closure = new BitSet();
        for(int state = stateGroup.nextSetBit(0); state >= 0; state = stateGroup.nextSetBit(state + 1)) {
            closure.or(epsilonClosures[state]);
        }
        //System.err.println("Closure of " + toString(stateGroup) + " is " + toString(closure));
        return closure;
    }
}
