/*
 * Created on Sep 16, 2005
 *
 */

package de.renew.fa.util;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Properties;
import java.util.Set;
import java.util.Stack;
import java.util.Vector;

import org.apache.log4j.Logger;

import net.automatalib.automata.fsa.impl.FastNFA;
import net.automatalib.automata.fsa.impl.FastNFAState;
import net.automatalib.words.Alphabet;

import CH.ifa.draw.figures.ArrowTip;
import CH.ifa.draw.figures.AttributeFigure;
import CH.ifa.draw.figures.PolyLineFigure;
import CH.ifa.draw.figures.TextFigure;
import CH.ifa.draw.util.Geom;
import de.renew.draw.storables.ontology.Connector;
import de.renew.draw.storables.ontology.Drawing;
import de.renew.draw.storables.ontology.Figure;
import de.renew.draw.storables.ontology.FigureEnumeration;
import de.renew.fa.FADrawing;
import de.renew.fa.figures.EndDecoration;
import de.renew.fa.figures.FAArcConnection;
import de.renew.fa.figures.FAStateFigure;
import de.renew.fa.figures.FATextFigure;
import de.renew.fa.figures.FigureDecoration;
import de.renew.fa.figures.StartDecoration;
import de.renew.fa.figures.StartEndDecoration;
import de.renew.fa.model.Arc;
import de.renew.fa.model.FA;
import de.renew.fa.model.FAImpl;
import de.renew.fa.model.Letter;
import de.renew.fa.model.State;
import de.renew.fa.model.Word;
import de.renew.fa.model.WordImpl;
import de.renew.faformalism.util.FAAutomatonSimulationHelper;
import de.renew.faformalism.util.FASyntaxChecker;
import de.renew.gui.CPNTextFigure;


/**
 * Provides some static methods for Finite Automata (FA) to convert model
 * <code>FA</code> into Renew drawing representations <code>FADrawing</code>
 * and vice versa. Also: incidence matrix generation, uniform arc name and
 * converts an FA into the <code>Properties</code> format.
 *
 *
 * @author cabac
 *
 */
public class FAHelper {
    private static final Logger LOGGER = Logger.getLogger(FAHelper.class);

    /**
     * Converts a model of a Finite Automata as <code> FA</code> into a Renew
     * drawing.
     *
     * @param fa -
     *            The model of the FA.
     * @return The Renew <code>Drawing</code>
     */
    public static Drawing convertModelToDrawing(FA fa) {
        HashMap<State, FAStateFigure> figures = new HashMap<State, FAStateFigure>();

        FADrawing faDrawing = new FADrawing();
        Iterator<State> itStates = fa.getStates();

        // States
        int xOffset = 0;
        int yToggle = 0;
        while (itStates.hasNext()) {
            State state = itStates.next();
            FAStateFigure stateFigure = new FAStateFigure();
            FATextFigure text = new FATextFigure(CPNTextFigure.LABEL, state.getName());
            text.setParent(stateFigure);
            faDrawing.add(stateFigure);
            faDrawing.add(text);

            stateFigure.setFillColor(Color.white);

            // FigureDecoration
            if (fa.startStates().contains(state)) {
                if (fa.endStates().contains(state)) {
                    stateFigure.setDecoration(new StartEndDecoration());
                } else {
                    stateFigure.setDecoration(new StartDecoration());
                }
            } else if (fa.endStates().contains(state)) {
                stateFigure.setDecoration(new EndDecoration());
            }
            Point loc = stateFigure.displayBox().getLocation();
            Dimension d = FAStateFigure.defaultDimension();
            int w2 = d.width / 2;
            int h2 = d.height / 2;
            stateFigure.displayBox(
                new Point(loc.x - w2, loc.y - h2),
                new Point(loc.x - w2 + d.width, loc.y - h2 + d.height));
            xOffset = xOffset + 100;
            yToggle = 1 - yToggle;
            stateFigure.moveBy(xOffset, 50 + 100 * yToggle);

            figures.put(state, stateFigure);
        }


        // System.out.println(FAHelper.getStates(fa));
        // Arcs
        // Iterator iter = arcs.values().iterator();
        // HashMap tuple = new HashMap();
        // while (iter.hasNext()) {
        // Arc arc = (Arc) iter.next();
        // StateTuple st = new StateTuple(arc);
        // tuple.put(st.getName(),st);
        // }
        Iterator<Arc> itArcs = fa.getArcs();
        while (itArcs.hasNext()) {
            Arc arc = itArcs.next();
            FAArcConnection faArcConnection =
                new FAArcConnection(null, new ArrowTip(), AttributeFigure.LINE_STYLE_NORMAL);
            faArcConnection
                .setAttribute("LineShape", Integer.valueOf(PolyLineFigure.BSPLINE_SHAPE));
            Word inscription = arc.getInscription();
            State startState = arc.getFrom();
            State endState = arc.getTo();
            Figure fromFigure = figures.get(startState);
            Figure toFigure = figures.get(endState);

            Connector fromCon = fromFigure.connectorAt(fromFigure.center());
            Connector toCon = toFigure.connectorAt(toFigure.center());

            faArcConnection.startPoint(fromFigure.center());
            faArcConnection.connectStart(fromCon);
            faArcConnection.endPoint(toFigure.center());
            faArcConnection.connectEnd(toCon);

            if (fromFigure.equals(toFigure)) {
                Point p = fromFigure.center();
                faArcConnection.insertPointAt(new Point(p.x - 50, p.y + 50), 1);

                faArcConnection.insertPointAt(new Point(p.x + 50, p.y + 50), 2);
            } else if (fa.hasArc(endState.getName(), startState.getName())) {
                Point d = getOrthonormalPointOffset(fromFigure, toFigure);
                faArcConnection.insertPointAt(d, 1);
            }
            FATextFigure text = new FATextFigure(CPNTextFigure.INSCRIPTION, inscription.getName());
            if (!inscription.isEmpty()) {
                text.setParent(faArcConnection);
            }
            faArcConnection.updateConnection();

            faDrawing.add(faArcConnection);
            if (!inscription.isEmpty()) {
                faDrawing.add(text);
            }
        }

        faDrawing.setName(fa.getName());
        return faDrawing;
    }

    private static Point getOrthonormalPointOffset(Figure fromFigure, Figure toFigure) {
        Point a = fromFigure.center();
        Point b = toFigure.center();
        Point s = Geom.middle(a, b);
        Point d = null;
        double distance = a.distance(b);
        double alpha = 50;
        double deltaX = (a.x - b.x) / distance;
        double deltaY = (a.y - b.y) / distance;

        d = new Point(
            Double.valueOf(s.x - alpha * deltaY).intValue(),
            Double.valueOf(s.y + alpha * deltaX).intValue());

        return d;

    }

    /**
     * Generates a standardized name for an Arc.
     *
     * @param inscription -
     *            the arc inscription.
     * @param from -
     *            the state
     * @param to -
     *            the other state
     *
     * @return A String containing the standardized name for the given Arc
     */
    public static String getArcName(Word inscription, State from, State to) {
        String inscriptionText;
        if (inscription.isEmpty()) {
            inscriptionText = "";
        } else {
            inscriptionText = inscription.getName();
        }
        return "(" + from.getName() + ":" + inscriptionText + ":" + to.getName() + ")";
    }

    //    /**
    //     * Calculates the incidence matrix as a <code>BoolMatrix</code>.
    //     *
    //     * @see de.renew.netanalysis.BoolMatrix for a given fa.
    //     * @param fa -
    //     *            the finite automata model.
    //     * @return The incidence matrix.
    //     */
    //    public static BoolMatrix getIncidenceMatrix(FA fa) {
    //        Iterator<State> iter = fa.getStates();
    //        HashMap<State, Integer> inverseStates = new HashMap<State, Integer>();
    //        int i = 0;
    //        while (iter.hasNext()) {
    //            State state = iter.next();
    //            // System.out.println(state.getName());
    //            inverseStates.put(state, Integer.valueOf(i++));
    //        }

    //        int size = fa.numberOfStates();
    //        BoolMatrix result = new BoolMatrix(size);
    //        Iterator<Arc> it = fa.getArcs();
    //        while (it.hasNext()) {
    //            Arc arc = it.next();
    //            State from = arc.getFrom();
    //            State to = arc.getTo();
    //            int fromInt = inverseStates.get(from).intValue();
    //            int toInt = inverseStates.get(to).intValue();
    //            result.setElement(fromInt, toInt, true);
    //        }
    //        result.toString();
    //        return result;
    //    }

    /**
     * Converts a Finite Automata represented as Renew <code>FADrawing</code>
     * into the model.
     *
     * @param drawing -
     *            The drawing representing an fa.
     * @return The model of the Finite Automata as <code>FA</code>.
     */
    public static FA getModel(FADrawing drawing) {
        FA fa = new FAImpl();
        fa.setName(drawing.getName());

        int lowestAvailableIndex = 0;
        HashMap<FAStateFigure, String> stateMap = new HashMap<>();
        // first run: all figures getting the states
        // adding states to fa
        FigureEnumeration enumeration = drawing.figures();
        while (enumeration.hasMoreElements()) {
            if (enumeration.nextElement() instanceof FAStateFigure stateFig) {
                String name = null;
                FigureEnumeration childEnum = stateFig.children();
                if (childEnum.hasMoreElements()) {
                    if (childEnum.nextFigure() instanceof FATextFigure text) {
                        name = text.getText();
                    }
                }
                if (stateMap.get(stateFig) != null) {
                    name = null;
                }
                stateMap.put(stateFig, name);
            }
        }
        for (FAStateFigure faState : stateMap.keySet()) {
            if (stateMap.get(faState) == null) {
                String name = "(" + lowestAvailableIndex + ")";
                while (fa.getStateByName(name) != null) {
                    lowestAvailableIndex++;
                    name = "(" + lowestAvailableIndex + ")";
                }
                lowestAvailableIndex++;
                stateMap.put(faState, name);
            }
            State state = fa.newState(stateMap.get(faState));
            // Take care of decorations.
            FigureDecoration deco = faState.getDecoration();
            if (deco != null) {
                if (deco instanceof StartDecoration) {
                    state.setStartState(true);
                }
                if (deco instanceof StartEndDecoration) {
                    state.setEndState(true);
                    state.setStartState(true);
                }
                if (deco instanceof EndDecoration) {
                    state.setEndState(true);
                }
            }
        }
        // second run getting the connections.
        enumeration = drawing.figures();
        while (enumeration.hasMoreElements()) {
            Figure fig = enumeration.nextElement();
            if (fig instanceof FAArcConnection) {
                FAArcConnection arc1 = ((FAArcConnection) fig);
                FigureEnumeration childEnum = arc1.children();
                Word inscription = null;
                if (childEnum.hasMoreElements()) {
                    TextFigure child = (TextFigure) childEnum.nextFigure();
                    String inscriptionText = child.getText();
                    if (inscriptionText.length() > 0) {
                        // new Word as inscription for the arc
                        inscription = fa.newWord(inscriptionText);
                        // add each letter of the Word to the Alphabet,
                        // if not already added.
                        for (int i = 0; i < inscriptionText.length(); i++) {
                            char character = inscriptionText.charAt(i);
                            if (character != ',') {
                                fa.newLetter(Character.toString(character));
                            }
                        }
                    } else {
                        System.err.println("FAHelper: length of text of inscription is 0.");
                        // this should not happen
                    }
                } else {
                    // Arc has no inscription. Treat as lambda arc.
                    inscription = fa.newWord("");
                }
                FAArcConnection line = (FAArcConnection) fig;
                Figure startfig = line.startFigure();
                Figure endfig = line.endFigure();

                // get names of connected figures; add arc to fa
                // if figures are FAStateFigure AND have inscription
                if (startfig instanceof FAStateFigure start
                    && endfig instanceof FAStateFigure end) {
                    State from = fa.getStateByName(stateMap.get(start));
                    State to = fa.getStateByName(stateMap.get(end));
                    fa.newArc(from, inscription, to);
                } else {
                    LOGGER.warn("Ignoring Arc: not connected to state figure.");
                }
            }
        }

        //DrawPlugin.getGui().openDrawing(convertModelToDrawing(fa)); //debug statement
        return fa;
    }

    /**
     * Returns a given fa as Properties. Thus an fa can be stored in a unique
     * way that can be read again.
     *
     * @param fa -
     *            The finite automata model.
     * @return The fa as Properties.
     */
    public static Properties toProperties(FA fa) {
        Properties properties = new Properties();
        properties.setProperty("Z", getStates(fa).toString());
        properties.setProperty("Sigma", getAlphabet(fa).toString());
        properties.setProperty("K", getArcs(fa).toString());
        properties.setProperty("Z_Start", fa.startStates().toString());
        properties.setProperty("Z_End", fa.endStates().toString());
        return properties;
    }

    private static Vector<State> getStates(FA fa) {
        Vector<State> v = new Vector<State>();
        Iterator<State> it = fa.getStates();
        while (it.hasNext()) {
            State state = it.next();
            v.add(state);
        }
        return v;
    }

    private static Vector<Letter> getAlphabet(FA fa) {
        Vector<Letter> v = new Vector<Letter>();
        Iterator<Letter> it = fa.getAlphabet();
        while (it.hasNext()) {
            Letter letter = it.next();
            v.add(letter);
        }
        return v;
    }

    private static Vector<Arc> getArcs(FA fa) {
        Vector<Arc> v = new Vector<Arc>();
        Iterator<Arc> it = fa.getArcs();
        while (it.hasNext()) {
            Arc arc = it.next();
            v.add(arc);
        }
        return v;
    }

    /**
     * This method converts a {@link de.renew.fa.model.FA} into a FastNFA.
     * This method is used by the {@link de.renew.fa.gui.FACompareGui} and its result is checked against other automata
     * using the <code>automataLib</code>.
     * When comparing two FastNFAs, their input alphabet needs to be identical.
     * Therefore, we require it to be precomputed.
     * @param fa the FA to convert
     * @param alphabet the alphabet of this nfa and the nfa it will be compared to
     * @return a FastNFA based on the inputs.
     */
    public static FastNFA<String> convertFAModelToAutomaton(FA fa, Alphabet<String> alphabet) {
        HashMap<Arc, List<String>> arcInscriptions = new HashMap<>();
        HashMap<State, List<Arc>> outGoingArcs = new HashMap<>();

        /*remember all arcs*/
        Iterator<Arc> arcIterator = fa.getArcs();
        while (arcIterator.hasNext()) {
            Arc arc = arcIterator.next();
            List<String> inscr =
                FAAutomatonSimulationHelper.splitNFAArcInscription(arc.getInscription().getName());
            arcInscriptions.put(arc, inscr);
            State from = arc.getFrom();
            List<Arc> outArcs = outGoingArcs.get(from);
            if (outArcs == null) {
                outArcs = new ArrayList<>();
            }
            outArcs.add(arc);
            outGoingArcs.put(from, outArcs);
        }

        /*find all states connected via epsilon-arcs*/
        HashMap<State, Set<State>> epsilonStates = new HashMap<>();
        for (State s : fa.getStatesAsArray()) {
            epsilonStates.put(s, depthFirstEpsilonSearch(s, outGoingArcs, arcInscriptions));
        }

        alphabet.remove("");
        FastNFA<String> nfa = new FastNFA<>(alphabet);
        HashMap<State, FastNFAState> stateMap = new HashMap<>();
        for (State s : fa.getStatesAsArray()) {
            boolean isAccepting = s.isEndState();
            for (State eState : epsilonStates.get(s)) {
                isAccepting = isAccepting || eState.isEndState();
            }
            stateMap.put(s, nfa.addState(isAccepting));
        }
        for (State s : fa.getStatesAsArray()) {
            if (s.isStartState()) {
                for (State eState : epsilonStates.get(s)) {
                    nfa.setInitial(stateMap.get(eState), true);
                }
            }
        }

        for (Arc arc : arcInscriptions.keySet()) {
            for (String inscr : arcInscriptions.get(arc)) {
                if (!inscr.isEmpty()) {
                    inscr = inscr.replaceAll("\\s", "");
                    State from = arc.getFrom();
                    Set<State> toClosure = epsilonStates.get(arc.getTo());
                    for (State to : toClosure) {
                        nfa.addTransition(stateMap.get(from), inscr, stateMap.get(to));
                    }
                }
            }
        }

        return nfa;
    }

    /**
     * This method finds all states that a given state can reach by just using epsilon-arcs.
     * @param state The state for which all connected states are to be found
     * @param outArcs The arcs of the automaton
     * @param arcInscriptions The Inscriptions of the automaton arcs
     * @return The set of states that can be reached from the given state by reading epsilon. Contains the given state.
     */
    private static Set<State> depthFirstEpsilonSearch(
        State state, HashMap<State, List<Arc>> outArcs, HashMap<Arc, List<String>> arcInscriptions)
    {
        Set<State> discovered = new HashSet<>();
        Stack<State> stack = new Stack<>();
        stack.push(state);
        while (!stack.isEmpty()) {
            State currentState = stack.pop();
            discovered.add(currentState);
            List<Arc> arcs = outArcs.get(currentState);
            if (arcs != null) {
                for (Arc a : arcs) {
                    if (a != null && arcInscriptions.get(a).contains("")
                        && !discovered.contains(a.getTo())) {
                        stack.push(a.getTo());
                    }
                }
            }
        }

        return discovered;
    }

    /**
     * Transforms a given RegEx into an NFA.
     * @param regex The RegEx to convert.
     * @return An NFA accepting the given language, or null if the RegEx was malformed
     * @require {@link FASyntaxChecker#checkNFAWordSyntax} to not throw an Exception
     */
    public static FA regexToNfa(String regex) {
        try {
            FASyntaxChecker.checkNFAWordSyntax(regex);
        } catch (Exception e) {
            e.printStackTrace();
            return null;
        }
        regex = regex.replaceAll("[+]", "|");
        regex = regex.replaceAll("\\^[|]", "+");
        regex = regex.replaceAll("\\^[*]", "*");

        return buildNFARecursively(regex, 0);
    }

    private final static String ACCEPTINGNAME = "accepting";
    private final static String INITIALNAME = "init";

    private static FA buildNFARecursively(String regex, int lowestAvailableIndex) {
        FA result = new FAImpl();
        State initialState = result.newState(INITIALNAME);
        initialState.setStartState(true);
        State acceptingState = result.newState(ACCEPTINGNAME);
        acceptingState.setEndState(true);

        if (regex.length() == 0) {//epsilon
            result.newArc(initialState, new WordImpl(""), acceptingState);
            return result;
        } else if (regex.length() == 1) {//single letter
            result.newArc(initialState, new WordImpl(regex), acceptingState);
            return result;
        }

        //find all union operators outside of brackets. we "split" on those.
        List<Integer> unionIndexList = new ArrayList<>();
        int openBracket = 0;
        for (int i = 0; i < regex.length(); i++) {
            switch (regex.charAt(i)) {
                case '(' -> openBracket++;
                case ')' -> openBracket--;
                case '|' -> {
                    if (openBracket == 0) {
                        unionIndexList.add(i);
                    }
                }
            }
        }
        if (!unionIndexList.isEmpty()) {
            //recursively call this method for each substring separated by union operations
            //add the resulting FAs to our result.
            int currentWordIndex = 0;
            List<FA> subAutomataList = new ArrayList<>();
            for (int unionIndex : unionIndexList) {
                FA temp = buildNFARecursively(
                    regex.substring(currentWordIndex, unionIndex), lowestAvailableIndex);
                subAutomataList.add(temp);
                lowestAvailableIndex += temp.numberOfStates() - 2; //init and accepting states didn't use an index
                currentWordIndex = unionIndex + 1;
            }
            //the last part was not processed yet
            FA temp = buildNFARecursively(regex.substring(currentWordIndex), lowestAvailableIndex);
            subAutomataList.add(temp);
            lowestAvailableIndex += temp.numberOfStates() - 2; //init and accepting states didn't use an index
            //we now iterate through all sub-automata and add them to our result
            for (FA automaton : subAutomataList) {
                //every automaton has at least two distinct states: initial and accepting
                //we add them now, so we know their name for later.
                State tempInit = result.newState("" + lowestAvailableIndex);
                lowestAvailableIndex++;
                State tempEnd = result.newState("" + lowestAvailableIndex);
                lowestAvailableIndex++;
                //these states of the sub-automaton need to be connected to our result via epsilon:
                result.newArc(initialState, new WordImpl(""), tempInit);
                result.newArc(tempEnd, new WordImpl(""), acceptingState);
                //we iterate through all arcs, since they already contain the information about their connected states
                Iterator<Arc> arcIterator = automaton.getArcs();
                while (arcIterator.hasNext()) {
                    addArc(result, arcIterator.next(), tempInit, tempEnd);
                }
            }
            //DrawPlugin.getGui().openDrawing(convertModelToDrawing(result));
            return result; //we can return here. After aggregating all recursive calls we already parsed the whole String
        }
        //we check if the input was one big bracket
        if (regex.charAt(0) == '(') {
            boolean oneBigBracket = true;
            openBracket = 0;
            for (int i = 0; i < regex.length(); i++) {
                switch (regex.charAt(i)) {
                    case '(' -> openBracket++;
                    case ')' -> {
                        openBracket--;
                        if (openBracket == 0) {
                            //are we at the end of the regex?
                            if (i == regex.length() - 2) {
                                //we are one char removed from the end. the bracket might end on '*' or '+' though
                                oneBigBracket =
                                    regex.charAt(i + 1) == '+' || regex.charAt(i + 1) == '*';
                            } else if (i != regex.length() - 1) {
                                //we not are at the end, but outside the bracket
                                oneBigBracket = false;
                            }
                        }
                    }
                }
                if (!oneBigBracket) {
                    openBracket = i + 1; //we use this index later on, when splitting the automatas into groups. the starting bracket is one group.
                    break;
                }
            }
            if (oneBigBracket) { //regex is (X)* or (X)+ or (X)
                if (regex.endsWith("*")) { //regex is (X)*
                    result.newArc(initialState, new WordImpl(""), acceptingState);
                    FA tempFA = buildNFARecursively(
                        regex.substring(1, regex.length() - 2), lowestAvailableIndex); //(X)* -> X
                    lowestAvailableIndex += tempFA.numberOfStates() - 2; //init and accepting states didn't use an index
                    State tempEnd = result.newState("" + lowestAvailableIndex);
                    result.newArc(tempEnd, new WordImpl(""), initialState);
                    Iterator<Arc> arcIterator = tempFA.getArcs();
                    while (arcIterator.hasNext()) {
                        addArc(result, arcIterator.next(), initialState, tempEnd);
                    }
                } else if (regex.endsWith("+")) { //regex is (X)+
                    FA tempFA = buildNFARecursively(
                        regex.substring(1, regex.length() - 2), lowestAvailableIndex); //(X)+ -> X
                    result.newArc(acceptingState, new WordImpl(""), initialState);
                    Iterator<Arc> arcIterator = tempFA.getArcs();
                    while (arcIterator.hasNext()) {
                        addArc(result, arcIterator.next(), initialState, acceptingState);
                    }
                } else { //regex is (X)
                    FA tempFA = buildNFARecursively(
                        regex.substring(1, regex.length() - 1), lowestAvailableIndex); //(X) -> X
                    Iterator<Arc> arcIterator = tempFA.getArcs();
                    while (arcIterator.hasNext()) {
                        addArc(result, arcIterator.next(), initialState, acceptingState);
                    }
                }
            } else {//regex is (X)*Y or (X)+Y or (X)Y
                int offset = 0;
                if (regex.charAt(openBracket) == '+' || regex.charAt(openBracket) == '*') {
                    //regex is (X)*Y or (X)+Y
                    offset++; //we do not want to cut off the * or + characters
                }
                FA leftFA = buildNFARecursively(
                    regex.substring(0, openBracket + offset), lowestAvailableIndex);
                lowestAvailableIndex += leftFA.numberOfStates() - 2; //init and accepting states didn't use an index;
                FA rightFA = buildNFARecursively(
                    regex.substring(openBracket + offset), lowestAvailableIndex);
                lowestAvailableIndex += rightFA.numberOfStates() - 2; //init and accepting states didn't use an index;
                State intermediate = result.newState("" + lowestAvailableIndex);
                lowestAvailableIndex++;
                State tempLeftInit = result.newState("" + lowestAvailableIndex);
                result.newArc(initialState, new WordImpl(""), tempLeftInit);
                Iterator<Arc> arcIterator = leftFA.getArcs();
                while (arcIterator.hasNext()) {
                    addArc(result, arcIterator.next(), tempLeftInit, intermediate);
                }
                arcIterator = rightFA.getArcs();
                while (arcIterator.hasNext()) {
                    addArc(result, arcIterator.next(), intermediate, acceptingState);
                }
                if (regex.charAt(openBracket) == '*') { //regex is (X)*Y
                    result.newArc(initialState, new WordImpl(""), intermediate);
                } else if (regex.charAt(openBracket) == '+') { //regex is (X)+Y
                    result.newArc(intermediate, new WordImpl(""), tempLeftInit);
                    result.newArc(initialState, new WordImpl(""), tempLeftInit);
                }
            }
        } else {
            //regex doesn't start with '('
            if (regex.charAt(1) == '*' || regex.charAt(1) == '+') {
                //regex is a*X or a+X
                State loopState = result.newState("" + lowestAvailableIndex);
                lowestAvailableIndex++;
                State nextState = result.newState("" + lowestAvailableIndex);
                lowestAvailableIndex++;
                FA rest = buildNFARecursively(regex.substring(2), lowestAvailableIndex);
                Iterator<Arc> arcIterator = rest.getArcs();
                while (arcIterator.hasNext()) {
                    addArc(result, arcIterator.next(), nextState, acceptingState);
                }
                result.newArc(initialState, new WordImpl(""), loopState);
                result.newArc(loopState, new WordImpl("" + regex.charAt(0)), loopState);
                if (regex.charAt(1) == '*') {
                    //regex is a*X
                    result.newArc(loopState, new WordImpl(""), nextState);
                } else {
                    //regex is a+X
                    result.newArc(loopState, new WordImpl("" + regex.charAt(0)), nextState);
                }
            } else {
                //regex is ab or a(X) or ...
                State nextState = result.newState("" + lowestAvailableIndex);
                lowestAvailableIndex++;
                result.newArc(initialState, new WordImpl("" + regex.charAt(0)), nextState);
                FA rest = buildNFARecursively(regex.substring(1), lowestAvailableIndex);
                Iterator<Arc> arcIterator = rest.getArcs();
                while (arcIterator.hasNext()) {
                    addArc(result, arcIterator.next(), nextState, acceptingState);
                }
            }
        }
        //DrawPlugin.getGui().openDrawing(convertModelToDrawing(result)); //debug statement
        return result;
    }

    private static void addArc(FA result, Arc arc, State tempInit, State tempEnd) {
        String fromName = arc.getFrom().getName();
        String toName = arc.getTo().getName();
        if (fromName.equals(INITIALNAME) && toName.equals(INITIALNAME)) {
            //loop
            result.newArc(tempInit, arc.getInscription(), tempInit);
        } else if (fromName.equals(ACCEPTINGNAME) && toName.equals(ACCEPTINGNAME)) {
            //loop
            result.newArc(tempEnd, arc.getInscription(), tempEnd);
        } else if (fromName.equals(INITIALNAME) && toName.equals(ACCEPTINGNAME)) {
            //the sub-automaton had an arc between initial and accepting state
            result.newArc(tempInit, arc.getInscription(), tempEnd);
        } else if (fromName.equals(ACCEPTINGNAME) && toName.equals(INITIALNAME)) {
            //the sub-automaton had an arc between accepting and initial state
            result.newArc(tempEnd, arc.getInscription(), tempInit);
        } else if (fromName.equals(INITIALNAME)) {
            //the corresponding arc in our result is no longer named init, but initName
            State to = result.getStateByName(toName);
            if (to == null) {
                to = result.newState(toName);
            }
            result.newArc(tempInit, arc.getInscription(), to);
        } else if (toName.equals(ACCEPTINGNAME)) {
            //the corresponding arc in our result is no longer named end, but endName
            State from = result.getStateByName(fromName);
            if (from == null) {
                from = result.newState(fromName);
            }
            result.newArc(from, arc.getInscription(), tempEnd);
        } else if (toName.equals(INITIALNAME)) {
            State from = result.getStateByName(fromName);
            if (from == null) {
                from = result.newState(fromName);
            }
            result.newArc(from, arc.getInscription(), tempInit);
        } else if (fromName.equals(ACCEPTINGNAME)) {
            State to = result.getStateByName(toName);
            if (to == null) {
                to = result.newState(fromName);
            }
            result.newArc(tempEnd, arc.getInscription(), to);
        } else {
            State from = result.getStateByName(fromName);
            if (from == null) {
                from = result.newState(fromName);
            }
            State to = result.getStateByName(toName);
            if (to == null) {
                to = result.newState(toName);
            }
            result.newArc(from, arc.getInscription(), to);
        }

    }

    // /**
    // * Writes the FA in XFA format.
    // */
    // public String toString() {
    // return "Z = " + states.values().toString() + "\nSigma = "
    // + alphabet.values().toString() + "\nK = "
    // + arcs.values().toString() + "\nZ_Start = "
    // + startStates().toString() + "\nZ_End = "
    // + endStates().toString();
    // }
}