// Path: src/main/java/nfa/transitionlabel/TransitionLabel.java
// public interface TransitionLabel {
// 	
// 	public static final int MIN_16UNICODE = 0;
// 	public static final int MAX_16UNICODE = 65536;
// 	
// 	public static final int MIN_DIGIT = 48;
// 	public static final int MAX_DIGIT = 57;
// 	
// 	public static final int MIN_SPACE = 9;
// 	public static final int MAX_SPACE = 13;
// 	
// 	public static final int MIN_WORD1 = 65;
// 	public static final int MAX_WORD1 = 90;
// 	
// 	public static final int MIN_WORD2 = 95;
// 	public static final int MAX_WORD2 = 95;
// 	
// 	public static final int MIN_WORD3 = 97;
// 	public static final int MAX_WORD3 = 122;
// 	
// 	public static final int HORIZONTAL_TAB = 9;
// 	
// 	public static final int VERTICAL_TAB = 11;
// 	
// 	public enum TransitionType {
// 		EPSILON,
// 		SYMBOL,
// 		OTHER
// 	}
// 	
// 	public TransitionType getTransitionType();
// 	
// 	public abstract boolean matches(String word);
// 	
// 	public abstract boolean matches(TransitionLabel tl);
// 	
// 	public abstract TransitionLabel intersection(TransitionLabel tl);
// 	
// 	public abstract TransitionLabel union(TransitionLabel tl);
// 	
// 	public abstract TransitionLabel complement();
// 	
// 	public abstract boolean isEmpty();
// 	
// 	public abstract String getSymbol();
// 
// 	public abstract TransitionLabel copy();
// 	
// 	public static void main(String [] args) {
// 		@SuppressWarnings("unused")
// 		Pattern p = Pattern.compile("\\p{ALPHA}");
// 	}
// 	
// }
// 
// Path: src/main/java/nfa/transitionlabel/TransitionLabel.java
// public enum TransitionType {
// 	EPSILON,
// 	SYMBOL,
// 	OTHER
// }


import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.Iterator;
import org.jgrapht.graph.DirectedPseudograph;
import nfa.transitionlabel.TransitionLabel;
import nfa.transitionlabel.TransitionLabel.TransitionType;
package nfa;




/**
 * A graph representing an NFA.
 * 
 * @author N. H. Weideman
 *
 */
public class NFAGraph extends DirectedPseudograph<NFAVertexND, NFAEdge> {
	private static final long serialVersionUID = 1L;

	/* The vertex representing the initial state of the NFA */
	private NFAVertexND initialState;

	public NFAVertexND getInitialState() {
		return initialState;
	}

	public void setInitialState(NFAVertexND initialState) {
		if (!super.containsVertex(initialState)) {
			throw new IllegalArgumentException("Graph does not contain vertex: " + initialState);
		}
		this.initialState = initialState;
	}

	/* The accepting states of the NFA */
	private HashSet<NFAVertexND> acceptingStates;

	public void addAcceptingState(NFAVertexND acceptingState) {
		if (!super.containsVertex(acceptingState)) {
			throw new IllegalArgumentException("Graph does not contain vertex: " + acceptingState);
		}
		acceptingStates.add(acceptingState);
	}

	public boolean isAcceptingState(String stateNumber) {
		return acceptingStates.contains(new NFAVertexND(stateNumber));
	}

	public boolean isAcceptingState(NFAVertexND state) {
		return acceptingStates.contains(state);
	}

	public void removeAcceptingState(NFAVertexND acceptingState) {
		if (!super.containsVertex(acceptingState)) {
			throw new IllegalArgumentException("Graph does not contains accepting state: " + acceptingState);
		}
		acceptingStates.remove(acceptingState);
	}

	public Set<NFAVertexND> getAcceptingStates() {
		return acceptingStates;
	}

	public NFAGraph() {
		super(NFAEdge.class);
		acceptingStates = new HashSet<NFAVertexND>();
	}

	/**
	 * @return A new instance of a NFAGraph equal to this instance
	 */
	public NFAGraph copy() {
		NFAGraph c = new NFAGraph();
		for (NFAVertexND v : super.vertexSet()) {
			c.addVertex(v.copy());
		}
		for (NFAEdge e : super.edgeSet()) {
			c.addEdge(e.copy());
		}

		if (initialState != null) {
			c.initialState = initialState.copy();
		}
		
		for (NFAVertexND v : acceptingStates) {
			c.addAcceptingState(v.copy());
		}
		return c;
	}

	/**
	 * Adds a new edge to the NFA graph
	 * 
	 * @param newEdge
	 *            The new edge to add
	 * @return true if this graph did not already contain the specified edge
	 */
	public boolean addEdge(NFAEdge newEdge) {
		if (newEdge == null) {
			throw new NullPointerException("New edge cannot be null");
		}
		if (newEdge.getTransitionLabel().isEmpty()) {
			return false;
		}
		
		NFAVertexND s = newEdge.getSourceVertex();
		NFAVertexND t = newEdge.getTargetVertex();
		if (super.containsEdge(newEdge)) {
			/* if the edge exists increase the number of its parallel edges */
			NFAEdge e = getEdge(newEdge);
			e.incNumParallel();
		} else if (newEdge.getIsEpsilonTransition()) {
			/* check if the NFA already has an epsilon transition between these states */
			Set<NFAEdge> es = super.getAllEdges(s, t);
			for (NFAEdge currentEdge : es) {
				if (currentEdge.equals(newEdge)) {
					/* if it does, add the new edge as a parallel edge (priorities don't matter between the same states) */
					currentEdge.incNumParallel();
					return true;
				}
			}
		} else {
			/* check if the new edge overlaps the current edges */
			Set<NFAEdge> es = super.getAllEdges(s, t);
			// TODO lightly tested
			for (NFAEdge currentEdge : es) {
				/* epsilon edges cannot overlap */
// Path: src/main/java/nfa/transitionlabel/TransitionLabel.java
// public interface TransitionLabel {
// 	
// 	public static final int MIN_16UNICODE = 0;
// 	public static final int MAX_16UNICODE = 65536;
// 	
// 	public static final int MIN_DIGIT = 48;
// 	public static final int MAX_DIGIT = 57;
// 	
// 	public static final int MIN_SPACE = 9;
// 	public static final int MAX_SPACE = 13;
// 	
// 	public static final int MIN_WORD1 = 65;
// 	public static final int MAX_WORD1 = 90;
// 	
// 	public static final int MIN_WORD2 = 95;
// 	public static final int MAX_WORD2 = 95;
// 	
// 	public static final int MIN_WORD3 = 97;
// 	public static final int MAX_WORD3 = 122;
// 	
// 	public static final int HORIZONTAL_TAB = 9;
// 	
// 	public static final int VERTICAL_TAB = 11;
// 	
// 	public enum TransitionType {
// 		EPSILON,
// 		SYMBOL,
// 		OTHER
// 	}
// 	
// 	public TransitionType getTransitionType();
// 	
// 	public abstract boolean matches(String word);
// 	
// 	public abstract boolean matches(TransitionLabel tl);
// 	
// 	public abstract TransitionLabel intersection(TransitionLabel tl);
// 	
// 	public abstract TransitionLabel union(TransitionLabel tl);
// 	
// 	public abstract TransitionLabel complement();
// 	
// 	public abstract boolean isEmpty();
// 	
// 	public abstract String getSymbol();
// 
// 	public abstract TransitionLabel copy();
// 	
// 	public static void main(String [] args) {
// 		@SuppressWarnings("unused")
// 		Pattern p = Pattern.compile("\\p{ALPHA}");
// 	}
// 	
// }
// 
// Path: src/main/java/nfa/transitionlabel/TransitionLabel.java
// public enum TransitionType {
// 	EPSILON,
// 	SYMBOL,
// 	OTHER
// }


// Path: src/main/java/nfa/NFAGraph.java
import java.io.File;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Set;
import java.util.Iterator;
import org.jgrapht.graph.DirectedPseudograph;
import nfa.transitionlabel.TransitionLabel;
import nfa.transitionlabel.TransitionLabel.TransitionType;

package nfa;




/**
 * A graph representing an NFA.
 * 
 * @author N. H. Weideman
 *
 */
public class NFAGraph extends DirectedPseudograph<NFAVertexND, NFAEdge> {
	private static final long serialVersionUID = 1L;

	/* The vertex representing the initial state of the NFA */
	private NFAVertexND initialState;

	public NFAVertexND getInitialState() {
		return initialState;
	}

	public void setInitialState(NFAVertexND initialState) {
		if (!super.containsVertex(initialState)) {
			throw new IllegalArgumentException("Graph does not contain vertex: " + initialState);
		}
		this.initialState = initialState;
	}

	/* The accepting states of the NFA */
	private HashSet<NFAVertexND> acceptingStates;

	public void addAcceptingState(NFAVertexND acceptingState) {
		if (!super.containsVertex(acceptingState)) {
			throw new IllegalArgumentException("Graph does not contain vertex: " + acceptingState);
		}
		acceptingStates.add(acceptingState);
	}

	public boolean isAcceptingState(String stateNumber) {
		return acceptingStates.contains(new NFAVertexND(stateNumber));
	}

	public boolean isAcceptingState(NFAVertexND state) {
		return acceptingStates.contains(state);
	}

	public void removeAcceptingState(NFAVertexND acceptingState) {
		if (!super.containsVertex(acceptingState)) {
			throw new IllegalArgumentException("Graph does not contains accepting state: " + acceptingState);
		}
		acceptingStates.remove(acceptingState);
	}

	public Set<NFAVertexND> getAcceptingStates() {
		return acceptingStates;
	}

	public NFAGraph() {
		super(NFAEdge.class);
		acceptingStates = new HashSet<NFAVertexND>();
	}

	/**
	 * @return A new instance of a NFAGraph equal to this instance
	 */
	public NFAGraph copy() {
		NFAGraph c = new NFAGraph();
		for (NFAVertexND v : super.vertexSet()) {
			c.addVertex(v.copy());
		}
		for (NFAEdge e : super.edgeSet()) {
			c.addEdge(e.copy());
		}

		if (initialState != null) {
			c.initialState = initialState.copy();
		}
		
		for (NFAVertexND v : acceptingStates) {
			c.addAcceptingState(v.copy());
		}
		return c;
	}

	/**
	 * Adds a new edge to the NFA graph
	 * 
	 * @param newEdge
	 *            The new edge to add
	 * @return true if this graph did not already contain the specified edge
	 */
	public boolean addEdge(NFAEdge newEdge) {
		if (newEdge == null) {
			throw new NullPointerException("New edge cannot be null");
		}
		if (newEdge.getTransitionLabel().isEmpty()) {
			return false;
		}
		
		NFAVertexND s = newEdge.getSourceVertex();
		NFAVertexND t = newEdge.getTargetVertex();
		if (super.containsEdge(newEdge)) {
			/* if the edge exists increase the number of its parallel edges */
			NFAEdge e = getEdge(newEdge);
			e.incNumParallel();
		} else if (newEdge.getIsEpsilonTransition()) {
			/* check if the NFA already has an epsilon transition between these states */
			Set<NFAEdge> es = super.getAllEdges(s, t);
			for (NFAEdge currentEdge : es) {
				if (currentEdge.equals(newEdge)) {
					/* if it does, add the new edge as a parallel edge (priorities don't matter between the same states) */
					currentEdge.incNumParallel();
					return true;
				}
			}
		} else {
			/* check if the new edge overlaps the current edges */
			Set<NFAEdge> es = super.getAllEdges(s, t);
			// TODO lightly tested
			for (NFAEdge currentEdge : es) {
				/* epsilon edges cannot overlap */
				if (currentEdge.getTransitionType() == TransitionType.SYMBOL) {