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 = 0; st < numStates; st++) {
                    if(closure.get(st)) {
                        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 = 0; state < numStates; state++) {
            if(stateGroup.get(state)) {
                nextStep.or(epsilons[state]);
            }
        }
        return nextStep;
    }
    
    private BitSet epsilonClosure(BitSet stateGroup, BitSet[] epsilonClosures) {
        BitSet closure = new BitSet();
        for(int state = 0; state < numStates; state++) {
            if(stateGroup.get(state)) {
                closure.or(epsilonClosures[state]);
            }
        }
        //System.err.println("Closure of " + toString(stateGroup) + " is " + toString(closure));
        return closure;
    }
    
    //TODO-AC: delete this
    public void dump() {
        System.out.println("ENFA");
        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("Epsilons:");
        for(int state = 0; state < numStates; state++) {
            System.out.println(toString(epsilons[state]));
        }
        System.out.println();
        System.out.println("Actions:");
        for(int state = 0; state < numStates; state++) {
            System.out.println(actions[state]);
        }
    }
    
    //TODO-AC: delete this
    private 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();
    }
}
