public static void assertMatches(Automaton automaton, List<String> valid, List<String> invalid) {
	String[] validStrings = valid.toArray(new String[0]);
	String[] invalidStrings = invalid.toArray(new String[0]);
	assertThat(matchSamples(automaton, validStrings), containsInAnyOrder(validStrings));
	assertThat(matchSamples(automaton, invalidStrings), empty());
} public static CharProvider chars(String sample) {
	return new StringCharProvider(sample, 0);
} public static List<String> invalid1() {
	return Arrays.asList(
		"b",
		"abb",
		"aaaabb",
		"aaaabaabb"
		);
} public static List<String> invalid2() {
	return Arrays.asList(
		"",
		"b",
		"ab",
		"baaa"
		);
} public static List<String> invalid3() {
	return Arrays.asList(
		"0110",
		"abcd"
		);
} public static List<String> invalid4() {
	return Arrays.asList(
		"",
		"b",
		"bbb",
		"baaaaba"
		);
} public static List<String> invalid8() {
	return Arrays.asList(
		"",
		"a"
		);
} public static List<String> invalid9() {
	return Arrays.asList(
		"",
		"a"
		);
} public static Set<String> matchPrefixes(Automaton a, String... samples) {
	PrefixCollector collector = new PrefixCollector();
	AutomatonMatcher matcher = a.matcher().withListener(collector);
	for (String sample : samples) {
		matcher.applyTo(chars(sample));
	}
	return new LinkedHashSet<String>(collector.getMatchedTexts());
} public static Set<String> matchSamples(Automaton a, String... samples) {
	MatchCollector collector = new MatchCollector();
	AutomatonMatcher matcher = a.matcher().withListener(collector);
	for (String sample : samples) {
		matcher.applyTo(chars(sample));
	}
	return new LinkedHashSet<String>(collector.getMatchedTexts());
} public static GenericAutomaton nfa1() {
	State state0 = new State(DefaultTokenType.ACCEPT);
	State state1 = new State(DefaultTokenType.ACCEPT);
	State state2 = new State();
	State state3 = new State();

	state0.addTransition(new ExactTransition('a', state1));
	state0.addTransition(new ExactTransition('a', state2));

	state1.addTransition(new ExactTransition('a', state1));
	state1.addTransition(new ExactTransition('a', state2));

	state2.addTransition(new ExactTransition('b', state1));
	state2.addTransition(new ExactTransition('b', state3));

	state3.addTransition(new ExactTransition('a', state1));
	state3.addTransition(new ExactTransition('a', state2));

	return new GenericAutomaton(state0);
} public static GenericAutomaton nfa2() {
	State state0 = new State();
	State state1 = new State(DefaultTokenType.ACCEPT);
	State state2 = new State();
	State state3 = new State();
	State state4 = new State();

	state0.addTransition(new ExactTransition('a', state1));
	state0.addTransition(new RangeTransition('a', 'b', state2));
	state0.addTransition(new ExactTransition('b', state3));

	state1.addTransition(new ExactTransition('a', state1));
	state1.addTransition(new ExactTransition('a', state2));

	state2.addTransition(new ExactTransition('b', state2));
	state2.addTransition(new ExactTransition('b', state3));
	state2.addTransition(new ExactTransition('b', state4));

	state3.addTransition(new ExactTransition('b', state3));
	state3.addTransition(new ExactTransition('b', state3));
	state3.addTransition(new RangeTransition('a', 'b', state4));

	return new GenericAutomaton(state0);
} public static GenericAutomaton nfa3() {
	State state1 = new State();
	State state2 = new State();
	State state3 = new State();
	State state4 = new State();
	State state6 = new State();
	State state7 = new State();
	State state8 = new State();
	State state9 = new State();
	State state10 = new State(DefaultTokenType.ACCEPT);

	state1.addTransition(new ExactTransition('0', state2));
	state1.addTransition(new ExactTransition('1', state6));

	state2.addTransition(new ExactTransition('0', state7));
	state2.addTransition(new ExactTransition('1', state3));

	state3.addTransition(new ExactTransition('0', state8));
	state3.addTransition(new ExactTransition('1', state4));

	state4.addTransition(new ExactTransition('0', state9));
	state4.addTransition(new ExactTransition('1', state10));

	state6.addTransition(new RangeTransition('0', '1', state7));

	state7.addTransition(new RangeTransition('0', '1', state8));

	state8.addTransition(new RangeTransition('0', '1', state10));

	return new GenericAutomaton(state1);
} public static GenericAutomaton nfa4() {
	State state0 = new State();
	State state1 = new State();
	State state2 = new State();
	State state3 = new State(DefaultTokenType.ACCEPT);

	state0.addTransition(new ExactTransition('a', state1));
	state0.addTransition(new RangeTransition('a', 'b', state2));

	state1.addTransition(new ExactTransition('a', state2));
	state1.addTransition(new ExactTransition('b', state3));

	state2.addTransition(new ExactTransition('a', state1));
	state2.addTransition(new ExactTransition('a', state2));
	state2.addTransition(new ExactTransition('b', state3));

	return new GenericAutomaton(state0);
} public static GenericAutomaton nfa5() {
	State state0 = new State(A);
	State state1 = new State(B);
	State state2 = new State();
	State state3 = new State();

	state0.addTransition(new ExactTransition('a', state1));
	state0.addTransition(new ExactTransition('a', state2));

	state1.addTransition(new ExactTransition('a', state1));
	state1.addTransition(new ExactTransition('a', state2));

	state2.addTransition(new ExactTransition('b', state1));
	state2.addTransition(new ExactTransition('b', state3));

	state3.addTransition(new ExactTransition('a', state1));
	state3.addTransition(new ExactTransition('a', state2));

	return new GenericAutomaton(state0);
} public static GenericAutomaton nfa8() {
	State state0 = new State();
	State state1 = new State();
	State state2 = new State(DefaultTokenType.ACCEPT);
	State state3 = new State();
	State state4 = new State(DefaultTokenType.ACCEPT);

	state0.addTransition(new ExactTransition('a', state1));
	state0.addTransition(new ExactTransition('a', state3));

	state1.addTransition(new ExactTransition('a', state2));

	state3.addTransition(new ExactTransition('a', state3));
	state3.addTransition(new ExactTransition('b', state4));

	return new GenericAutomaton(state0);
} public static GenericAutomaton nfa9() {
	State state0 = new State();
	State state1 = new State();
	State state2 = new State(DefaultTokenType.ACCEPT);
	State state3 = new State();
	State state4 = new State(DefaultTokenType.ACCEPT);

	state0.addTransition(new ExactTransition('a', state1));
	state0.addTransition(new ExactTransition('a', state3));

	state1.addTransition(new ExactTransition('a', state2));

	state2.addTransition(new ExactTransition('c', state0));

	state3.addTransition(new ExactTransition('a', state3));
	state3.addTransition(new ExactTransition('b', state4));

	return new GenericAutomaton(state0);
} public static List<String> valid1() {
	return Arrays.asList(
		"",
		"a",
		"aa",
		"aaa",
		"aaab",
		"aaaab",
		"aaaba",
		"aaaaba",
		"aaabab",
		"aaaabab",
		"aaababab",
		"aaaababab",
		"aaaabaaabaaaaaab"
		);
} public static List<String> valid2() {
	return Arrays.asList(
		"a",
		"aa",
		"aaa",
		"aaaa",
		"aaaaa"
		);
} public static List<String> valid3() {
	List<String> input = new ArrayList<String>(16);
	for (int i = 0; i < 16; i++) {
		StringBuilder buffer = new StringBuilder();
		buffer.append((i & 0x08) / 0x08);
		buffer.append((i & 0x04) / 0x04);
		buffer.append((i & 0x02) / 0x02);
		buffer.append((i & 0x01) / 0x01);
		input.add(buffer.toString());
	}
	input.remove("0110");
	return input;
} public static List<String> valid4() {
	return Arrays.asList(
		"bb",
		"aab",
		"aaaaaaab",
		"bab",
		"baaaab"
		);
} public static List<String> valid8() {
	return Arrays.asList(
		"aa",
		"aab"
		);
} public static List<String> valid9() {
	return Arrays.asList(
		"aa",
		"aab",
		"aacaa",
		"aacaab",
		"aacaacaa",
		"aacaacaab"
		);
} public static DFADeterministicMatcher isDeterministic() {
	return new DFADeterministicMatcher();
} public static GenericAutomaton match(char value) {
	State s = new State();
	State e = new State(DefaultTokenType.ACCEPT);

	s.addTransition(new ExactTransition(value, e));
	return new GenericAutomaton(s);
} public static GenericAutomaton matchConcatenation(GenericAutomaton... as) {
	return matchConcatenation(Arrays.asList(as));
} public static GenericAutomaton matchStarLoop(GenericAutomaton a) {
	State s = new State(DefaultTokenType.ACCEPT);
	State next = a.getStart();
	s.addTransition(new EpsilonTransition(next));
	for (State p : next.findAcceptStates()) {
		p.addTransition(new EpsilonTransition(s));
	}
	return new GenericAutomaton(s);
} public static GenericAutomatonMatcher matchesAutomaton() {
	return new GenericAutomatonMatcher();
} public static DotGraphMatcher startsWith(String prefix) {
	return new DotGraphMatcher().startingWith(prefix);
} public interface TokenType {

	boolean error();
	boolean accept();

} public static class ToCompactGenericAutomaton implements ToAutomaton<GenericAutomaton, GenericAutomaton>{

	@Override
	public GenericAutomaton transform(GenericAutomaton automaton) {
		return automaton.clone().eliminateEpsilons().eliminateDuplicateFinalStates().eliminateDuplicateTransitions();
	}
		
} public static class ToDeterministicAutomaton implements ToAutomaton<GenericAutomaton, DeterministicAutomaton> {

	@Override
	public DeterministicAutomaton transform(GenericAutomaton automaton) {
		GenericAutomaton almostDeterministic = automaton.clone().eliminateEpsilons().determinize();
		Map<com.almondtools.rexlex.automaton.GenericAutomaton.State, State> mappedStates = mapStates(almostDeterministic.findAllStates());
		return new DeterministicAutomaton(mappedStates.get(almostDeterministic.getStart()), mappedStates.get(almostDeterministic.getError()));
	}
		
} public static class ToMinimalDeterministicAutomaton implements ToAutomaton<GenericAutomaton, DeterministicAutomaton>{

	private TokenType remainder;

	public ToMinimalDeterministicAutomaton() {
	}

	public ToMinimalDeterministicAutomaton(TokenType remainder) {
		this.remainder = remainder;
	}

	@Override
	public DeterministicAutomaton transform(GenericAutomaton automaton) {
		GenericAutomaton almostDeterministic = automaton.clone().eliminateEpsilons().determinize();
		if (remainder != null) {
			GenericAutomaton almostMinimalDeterministic = almostDeterministic.totalizeAndClean(remainder).minimize();
			Map<com.almondtools.rexlex.automaton.GenericAutomaton.State, State> mappedStates = mapStates(almostMinimalDeterministic.findAllStates());
			return new DeterministicAutomaton(mappedStates.get(almostMinimalDeterministic.getStart()), mappedStates.get(almostMinimalDeterministic.getError()));
		} else {
			GenericAutomaton almostMinimalDeterministic = almostDeterministic.totalizeAndClean().minimize();
			Map<com.almondtools.rexlex.automaton.GenericAutomaton.State, State> mappedStates = mapStates(almostMinimalDeterministic.findAllStates());
			return new DeterministicAutomaton(mappedStates.get(almostMinimalDeterministic.getStart()), mappedStates.get(almostMinimalDeterministic.getError()));
		}
	}
		
} static class EpsilonTransition extends BasicTransition implements EventlessTransition {

	public EpsilonTransition(State target) {
		super(target);
	}

	@Override
	public String toString() {
		return new StringBuilder().append(" -> ").append(getTarget().getId()).toString();
	}

	@Override
	public int hashCode() {
		return 31 * super.hashCode();
	}

	@Override
	public boolean equals(Object obj) {
		return super.equals(obj);
	}

} public static interface EventTransition extends Transition {

	char getFrom();

	char getTo();

	boolean matches(char ch);

} static class ExactTransition extends BasicTransition implements EventTransition {

	private char value;

	public ExactTransition(char value, State target) {
		super(target);
		this.value = value;
	}

	public char getValue() {
		return value;
	}

	@Override
	public char getFrom() {
		return value;
	}

	@Override
	public char getTo() {
		return value;
	}

	@Override
	public boolean matches(char ch) {
		return value == ch;
	}

	@Override
	public String toString() {
		return new StringBuilder().append(" -<").append(charToString(value)).append(">-> ").append(getTarget().getId()).toString();
	}

	@Override
	public int hashCode() {
		return super.hashCode() + 17 * Character.valueOf(value);
	}

	@Override
	public boolean equals(Object obj) {
		if (!super.equals(obj)) {
			return false;
		}
		ExactTransition other = (ExactTransition) obj;
		return this.value == other.value;
	}

	@Override
	public ExactTransition clone() {
		ExactTransition transition = (ExactTransition) super.clone();
		transition.value = value;
		return transition;
	}

} static class RangeTransition extends BasicTransition implements EventTransition {

	private char from;
	private char to;

	public RangeTransition(char from, char to, State target) {
		super(target);
		this.from = from;
		this.to = to;
	}

	@Override
	public char getFrom() {
		return from;
	}

	@Override
	public char getTo() {
		return to;
	}

	@Override
	public boolean matches(char ch) {
		return ch >= from && ch <= to;
	}

	@Override
	public String toString() {
		return new StringBuilder().append(" -<").append(charToString(from)).append("..").append(charToString(to)).append(">-> ").append(getTarget().getId()).toString();
	}

	@Override
	public int hashCode() {
		return super.hashCode() + 13 * Character.valueOf(from).hashCode() + 31 * Character.valueOf(to);
	}

	@Override
	public boolean equals(Object obj) {
		if (!super.equals(obj)) {
			return false;
		}
		RangeTransition other = (RangeTransition) obj;
		return this.from == other.from && this.to == other.to;
	}

	@Override
	public RangeTransition clone() {
		RangeTransition transition = (RangeTransition) super.clone();
		transition.from = from;
		transition.to = to;
		return transition;
	}

} public static class State implements Cloneable {

	private TokenType type;
	private List<Transition> transitions;
	private List<State> closure;
	private List<EventTransition> nextclosure;

	public State() {
		this.transitions = new ArrayList<Transition>();
	}

	public State(TokenType type) {
		this.type = type;
		this.transitions = new ArrayList<Transition>();
	}

	public boolean accept() {
		return type != null && type.accept();
	}

	public boolean error() {
		return type != null && type.error();
	}

	public boolean acceptClosure() {
		if (accept()) {
			return true;
		} else {
			for (State state : getClosure()) {
				if (state.accept()) {
					return true;
				}
			}
			return false;
		}
	}

	public String getId() {
		return String.valueOf(System.identityHashCode(this));
	}

	public void setType(TokenType type) {
		this.type = type;
	}

	public TokenType getType() {
		return type;
	}

	public void addTransition(Transition transition) {
		if (!transitions.contains(transition)) {
			this.transitions.add(transition);
			clearCaches();
		}
	}

	public int removeTransition(Transition transition) {
		int pos = transitions.indexOf(transition);
		transitions.remove(pos);
		while (pos > -1) {
			clearCaches();
			pos = transitions.indexOf(transition);
		}
		return pos;
	}

	public void addTransitions(List<Transition> transitions) {
		for (Transition transition : transitions) {
			addTransition(transition);
		}
	}

	public void replaceTransition(Transition transition, Transition replacetransition) {
		int pos = transitions.indexOf(transition);
		while (pos > -1) {
			transitions.remove(pos);
			transitions.add(pos, replacetransition);
			clearCaches();
			pos = transitions.indexOf(transition);
		}
	}

	public void replaceTransition(Transition transition, List<Transition> replacetransitions) {
		int pos = transitions.indexOf(transition);
		while (pos > -1) {
			transitions.remove(pos);
			transitions.addAll(pos, replacetransitions);
			clearCaches();
			pos = transitions.indexOf(transition);
		}
	}

	public List<Transition> getTransitions() {
		return transitions;
	}

	public void setTransitions(List<Transition> transitions) {
		this.transitions = transitions;
		clearCaches();
	}

	SortedSet<EventTransition> computeSortedEventTransitions() {
		SortedSet<EventTransition> sortedTransitions = new TreeSet<EventTransition>(new Comparator<EventTransition>() {

			@Override
			public int compare(EventTransition o1, EventTransition o2) {
				int result = o1.getFrom() - o2.getFrom();
				if (result == 0) {
					result = o1.getTo() - o2.getTo();
				}
				return result;
			}
		});
		sortedTransitions.addAll(getEventTransitions());
		return sortedTransitions;
	}

	List<EventTransition> getEventTransitions() {
		List<EventTransition> eventTransitions = new ArrayList<EventTransition>();
		for (Transition transition : transitions) {
			if (transition instanceof EventTransition) {
				eventTransitions.add((EventTransition) transition);
			}
		}
		return eventTransitions;
	}

	public boolean inlineEpsilons(TokenTypeFactory tokenTypes) {
		boolean changed = false;
		for (int i = 0; i < transitions.size(); i++) {
			Transition transition = transitions.get(i);
			if (transition instanceof EpsilonTransition) {
				State target = transition.getTarget();
				type = tokenTypes.union(target.getType(), type);
				transitions.remove(i);
				for (Transition t : target.getTransitions()) {
					if (!transitions.contains(t)) {
						transitions.add(i, t);
						i++;
					}
				}
				i--;
				changed = true;
			}
		}
		if (changed) {
			clearCaches();
		}
		return changed;
	}

	public void eliminateDuplicateTransitions() {
		int oldsize = transitions.size();
		Set<Transition> found = new HashSet<Transition>();
		Iterator<Transition> transitionIterator = transitions.iterator();
		while (transitionIterator.hasNext()) {
			Transition transition = transitionIterator.next();
			boolean success = found.add(transition);
			if (!success) {
				transitionIterator.remove();
			}
		}
		if (oldsize != transitions.size()) {
			clearCaches();
		}
	}

	public void eliminateErrorTransitions() {
		int oldsize = transitions.size();
		Iterator<Transition> transitionIterator = transitions.iterator();
		while (transitionIterator.hasNext()) {
			Transition transition = transitionIterator.next();
			if (transition.getTarget().error()) {
				transitionIterator.remove();
			}
		}
		if (oldsize != transitions.size()) {
			clearCaches();
		}
	}

	void mergeAdjacentTransitions() {
		SortedSet<EventTransition> sortedTransitions = computeSortedEventTransitions();
		LinkedList<EventTransition> mergedTransitions = new LinkedList<EventTransition>();

		for (EventTransition transition : sortedTransitions) {
			if (mergedTransitions.isEmpty()) {
				mergedTransitions.add(transition);
			} else {
				EventTransition last = mergedTransitions.getLast();
				char lastFrom = last.getFrom();
				char lastTo = last.getTo();
				char nextFrom = transition.getFrom();
				char nextTo = transition.getTo();
				if (lastTo + 1 >= nextFrom && last.getTarget() == transition.getTarget()) {
					mergedTransitions.removeLast();
					char from = lastFrom < nextFrom ? lastFrom : nextFrom;
					char to = lastTo < nextTo ? nextTo : lastTo;
					mergedTransitions.add(new RangeTransition(from, to, last.getTarget()));
				} else {
					mergedTransitions.add(transition);
				}
			}
		}
		this.transitions = new ArrayList<Transition>(mergedTransitions);
	}

	public SortedSet<Character> getRelevantCharacters() {
		SortedSet<Character> relevant = new TreeSet<Character>();
		relevant.add(Character.MIN_VALUE);
		for (EventTransition transition : getSortedNextClosure()) {
			char from = ((EventTransition) transition).getFrom();
			relevant.add(from);

			char to = ((EventTransition) transition).getTo();
			if (to < Character.MAX_VALUE) {
				relevant.add(after(to));
			}
		}
		return relevant;
	}

	private void clearCaches() {
		this.closure = null;
		this.nextclosure = null;
	}

	public List<State> getClosure() {
		if (closure == null) {
			closure = computeClosure();
		}
		return closure;
	}

	private List<State> computeClosure() {
		Set<State> closure = new LinkedHashSet<State>();
		List<State> todo = Lists.of(this);
		while (!todo.isEmpty()) {
			State state = todo.remove(0);
			if (!closure.contains(state)) {
				closure.add(state);
				for (Transition transition : state.getTransitions()) {
					if (transition instanceof EpsilonTransition) {
						todo.add(transition.getTarget());
					}
				}
			}
		}
		return new ArrayList<State>(closure);
	}

	public List<EventTransition> getNextClosure() {
		if (nextclosure == null) {
			nextclosure = computeNextClosure();
		}
		return nextclosure;
	}

	private List<EventTransition> computeNextClosure() {
		List<EventTransition> nexts = new ArrayList<EventTransition>();
		for (State state : getClosure()) {
			for (Transition transition : state.getTransitions()) {
				if (transition instanceof EventTransition) {
					nexts.add((EventTransition) transition);
				}
			}
		}
		return nexts;
	}

	public Set<TokenType> getTypeClosure() {
		Set<TokenType> types = new HashSet<TokenType>();
		for (State state : getClosure()) {
			TokenType stateType = state.getType();
			if (stateType != null) {
				types.add(stateType);
			}
		}
		return types;
	}

	public List<EventTransition> getSortedNextClosure() {
		List<EventTransition> closure = new ArrayList<EventTransition>(getNextClosure());
		Collections.sort(closure, new TransitionComparator());
		return closure;
	}

	public Set<State> getConnectedStates() {
		Set<State> reachable = new LinkedHashSet<State>();
		for (Transition transition : transitions) {
			reachable.add(transition.getTarget());
		}
		return reachable;
	}

	public List<EventTransition> nexts(char ch) {
		List<EventTransition> nexts = new LinkedList<EventTransition>();
		for (EventTransition transition : getNextClosure()) {
			if (transition.matches(ch)) {
				nexts.add(transition);
			}
		}
		return nexts;
	}

	@Override
	public State clone() {
		try {
			State clone = (State) super.clone();
			clone.type = type;
			clone.transitions = new ArrayList<Transition>(transitions.size());
			return clone;
		} catch (CloneNotSupportedException e) {
			return null;
		}
	}

	public <T> T apply(StateVisitor<T> visitor) {
		return visitor.visitState(this);
	}

	@Override
	public String toString() {
		StringBuilder buffer = new StringBuilder("state(").append(getId()).append(")\n");
		for (Transition transition : transitions) {
			buffer.append('\t').append(transition.toString()).append('\n');
		}
		return buffer.toString();
	}

	public void addErrorTransitions(State error) {
		char min = Character.MAX_VALUE;
		char max = Character.MIN_VALUE;

		char current = Character.MIN_VALUE;
		for (EventTransition transition : getSortedNextClosure()) {
			char from = transition.getFrom();
			if (from < min) {
				min = from;
			}
			char to = transition.getTo();
			if (to > max) {
				max = to;
			}

			if (from == current + 1) {
				transitions.add(new ExactTransition(current, error));
			} else if (from > current) {
				transitions.add(new RangeTransition(current, before(from), error));
			}
			current = after(to);
		}
		if (max == Character.MAX_VALUE) {
			// MAX_VALUE already handled
		} else if (current == Character.MAX_VALUE) {
			transitions.add(new ExactTransition(Character.MAX_VALUE, error));
		} else {// current < Character.MAX_VALUE
			transitions.add(new RangeTransition(current, Character.MAX_VALUE, error));
		}
		clearCaches();
	}

	public State cloneTree() {
		return new Clone(this).apply().start();
	}

	public Set<State> findAcceptStates() {
		return new FindStates(this, new Predicate<State>() {
			@Override
			public boolean evaluate(State object) {
				return object.accept();
			}
		}).apply().states();
	}

	public Set<State> findReachableStates() {
		return new FindStates(this).apply().states();
	}

	public Set<State> findLiveStates() {
		Set<State> states = findReachableStates();
		Map<State, Set<State>> map = new HashMap<State, Set<State>>();
		for (State s : states) {
			map.put(s, new HashSet<State>());
		}
		for (State s : states) {
			for (Transition transition : s.getTransitions()) {
				map.get(transition.getTarget()).add(s);
			}
		}
		Set<State> live = new HashSet<State>(findAcceptStates());
		LinkedList<State> worklist = new LinkedList<State>(live);
		while (!worklist.isEmpty()) {
			State current = worklist.removeFirst();
			for (State previous : map.get(current)) {
				if (!live.contains(previous)) {
					live.add(previous);
					worklist.add(previous);
				}
			}
		}
		return live;
	}

} public static interface Transition extends Cloneable {

	State getTarget();

	void setTarget(State state);

	Transition clone();

	Transition clone(State target);

} public enum DefaultTokenType implements TokenType {
	IGNORE(), // state is acceptable, but match should be ignored
	ACCEPT(), // state is acceptable, and match may be returned
	ERROR(true) // state is not acceptable and indicates an error
	;

	private boolean error;

	private DefaultTokenType() {
		this(false);
	}

	private DefaultTokenType(boolean error) {
		this.error = error;
	}

	@Override
	public boolean error() {
		return error;
	}

	@Override
	public boolean accept() {
		return !error;
	}

	public static DefaultTokenType merge(DefaultTokenType type1, DefaultTokenType type2) {
		if (type1 == null) {
			return type2;
		} else if (type2 == null) {
			return type1;
		} else if (type1.compareTo(type2) > 0) {
			return type1;
		} else {
			return type2;
		}
	}

} public class Pattern {

	private static final GenericAutomatonBuilder DEFAULT_AUTOMATON_BUILDER = new GenericAutomatonBuilder();

	private String pattern;
	private MatcherBuilder builder;

	private Pattern(String pattern, MatcherBuilder builder) {
		this.pattern = pattern;
		this.builder = builder;
	}

	private static DefaultMatcherBuilder defaultMatcherBuilder() {
		return new DefaultMatcherBuilder();
	}

	public String pattern() {
		return pattern;
	}

	public static GenericAutomaton compileGenericAutomaton(String pattern, List<PatternOption> options) {
		List<PatternFlag> patternFlags = splitOf(options, PatternFlag.class);
		RegexParserOption[] parserOptions = new RegexParserOption[patternFlags.size()];
		for (int i = 0; i < parserOptions.length; i++) {
			parserOptions[i] = patternFlags.get(i).getOption();
		}
		RegexNode node = new RegexParser(pattern, parserOptions).parse();
		RemainderTokenType tokenType = splitFirst(options, RemainderTokenType.class);
		if (tokenType == null) {
			return automatonBuilder(options).buildFrom(node);
		} else {
			return automatonBuilder(options).buildFrom(node, tokenType.getRemainder());
		}
	}

	public static GenericAutomaton compileGenericAutomaton(String pattern, PatternOption... options) {
		return compileGenericAutomaton(pattern, list(options));
	}

	public static <T extends Automaton> T compileAutomaton(String pattern, ToAutomaton<GenericAutomaton, T> transformer, List<PatternOption> list) {
		GenericAutomaton genericAutomaton = compileGenericAutomaton(pattern, list);
		return transformer.transform(genericAutomaton);
	}

	public static <T extends Automaton> T compileAutomaton(String pattern, ToAutomaton<GenericAutomaton, T> transformer, PatternOption... options) {
		return compileAutomaton(pattern, transformer, list(options));
	}

	public static Pattern compile(String pattern, List<PatternOption> options) {
		GenericAutomaton genericAutomaton = compileGenericAutomaton(pattern, options);
		return new Pattern(pattern, matcherBuilder(options).initWith(genericAutomaton));
	}

	public static Pattern compile(String pattern, PatternOption... options) {
		return compile(pattern, list(options));
	}

	private static AutomatonBuilder automatonBuilder(List<PatternOption> options) {
		AutomatonBuilder builder = splitFirst(options, AutomatonBuilder.class);
		if (builder == null) {
			return DEFAULT_AUTOMATON_BUILDER;
		}
		return builder;
	}

	private static MatcherBuilder matcherBuilder(List<PatternOption> options) {
		MatcherBuilder builder = splitFirst(options, MatcherBuilder.class);
		if (builder == null) {
			return defaultMatcherBuilder();
		}
		return builder;
	}
	
	public Finder finder(String input) {
		return builder.buildFinder(input);
	}

	public Matcher matcher(String input) {
		return builder.buildMatcher(input);
	}

} public class RemainderTokenTypeFactory extends DefaultTokenTypeFactory implements TokenTypeFactory {

	private TokenType remainder;
	
	public RemainderTokenTypeFactory(TokenType remainder) {
		this.remainder = remainder;
	}
	
	@Override
	public TokenType union(TokenType type1, TokenType type2) {
		if (remainder.equals(type1)|| remainder.equals(type2)) {
			return remainder;
		}
		return super.union(type1, type2);
	}

	@Override
	public TokenType errorType() {
		return remainder;
	}

} public enum Accept implements TokenType {
	A,B,C,D,E,F,G,H,I,J,K,L,REMAINDER;

	@Override
	public boolean error() {
		return false;
	}
	
	@Override
	public boolean accept() {
		return true;
	}
} public class TestToken implements Token {

	private String literal;
	private TokenType type;

	public TestToken(String literal, TokenType type) {
		this.literal = literal;
		this.type = type;
	}
	
	@Override
	public String getLiteral() {
		return literal;
	}
	
	@Override
	public TokenType getType() {
		return type;
	}
	
	@Override
	public int hashCode() {
		return literal.hashCode() * 31 + type.hashCode();
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		TestToken other = (TestToken) obj;
		return this.type == other.type && this.literal.equals(other.literal);
	}
	
	@Override
	public String toString() {
		return literal + '(' + type.toString() + ')';
	}
	
} public class TestTokenFactory implements TokenFactory<TestToken>{

	@Override
	public TestToken createToken(String literal, TokenType type) {
		return new TestToken(literal, type);
	}
}
import static com.almondtools.rexlex.automaton.Automatons.assertMatches;
import static com.almondtools.rexlex.automaton.Automatons.chars;
import static com.almondtools.rexlex.automaton.Automatons.invalid1;
import static com.almondtools.rexlex.automaton.Automatons.invalid2;
import static com.almondtools.rexlex.automaton.Automatons.invalid3;
import static com.almondtools.rexlex.automaton.Automatons.invalid4;
import static com.almondtools.rexlex.automaton.Automatons.invalid8;
import static com.almondtools.rexlex.automaton.Automatons.invalid9;
import static com.almondtools.rexlex.automaton.Automatons.matchPrefixes;
import static com.almondtools.rexlex.automaton.Automatons.matchSamples;
import static com.almondtools.rexlex.automaton.Automatons.nfa1;
import static com.almondtools.rexlex.automaton.Automatons.nfa2;
import static com.almondtools.rexlex.automaton.Automatons.nfa3;
import static com.almondtools.rexlex.automaton.Automatons.nfa4;
import static com.almondtools.rexlex.automaton.Automatons.nfa5;
import static com.almondtools.rexlex.automaton.Automatons.nfa8;
import static com.almondtools.rexlex.automaton.Automatons.nfa9;
import static com.almondtools.rexlex.automaton.Automatons.valid1;
import static com.almondtools.rexlex.automaton.Automatons.valid2;
import static com.almondtools.rexlex.automaton.Automatons.valid3;
import static com.almondtools.rexlex.automaton.Automatons.valid4;
import static com.almondtools.rexlex.automaton.Automatons.valid8;
import static com.almondtools.rexlex.automaton.Automatons.valid9;
import static com.almondtools.rexlex.automaton.DFADeterministicMatcher.isDeterministic;
import static com.almondtools.rexlex.automaton.GenericAutomatonBuilder.match;
import static com.almondtools.rexlex.automaton.GenericAutomatonBuilder.matchConcatenation;
import static com.almondtools.rexlex.automaton.GenericAutomatonBuilder.matchStarLoop;
import static com.almondtools.rexlex.automaton.GenericAutomatonMatcher.matchesAutomaton;
import static com.almondtools.rexlex.pattern.DefaultTokenType.ACCEPT;
import static com.almondtools.rexlex.pattern.DefaultTokenType.ERROR;
import static com.almondtools.rexlex.pattern.DotGraphMatcher.startsWith;
import static com.almondtools.rexlex.tokens.Accept.A;
import static com.almondtools.rexlex.tokens.Accept.REMAINDER;
import static net.amygdalum.util.text.CharUtils.after;
import static org.hamcrest.CoreMatchers.equalTo;
import static org.hamcrest.CoreMatchers.hasItem;
import static org.hamcrest.CoreMatchers.hasItems;
import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.CoreMatchers.not;
import static org.hamcrest.Matchers.contains;
import static org.hamcrest.Matchers.containsInAnyOrder;
import static org.hamcrest.Matchers.empty;
import static org.hamcrest.Matchers.hasSize;
import static org.hamcrest.Matchers.lessThanOrEqualTo;
import static org.junit.Assert.assertThat;
import static org.junit.Assert.assertTrue;
import java.io.ByteArrayOutputStream;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import org.junit.Before;
import org.junit.Test;
import com.almondtools.rexlex.TokenType;
import com.almondtools.rexlex.automaton.FromGenericAutomaton.ToCompactGenericAutomaton;
import com.almondtools.rexlex.automaton.FromGenericAutomaton.ToDeterministicAutomaton;
import com.almondtools.rexlex.automaton.FromGenericAutomaton.ToMinimalDeterministicAutomaton;
import com.almondtools.rexlex.automaton.GenericAutomaton.EpsilonTransition;
import com.almondtools.rexlex.automaton.GenericAutomaton.EventTransition;
import com.almondtools.rexlex.automaton.GenericAutomaton.ExactTransition;
import com.almondtools.rexlex.automaton.GenericAutomaton.RangeTransition;
import com.almondtools.rexlex.automaton.GenericAutomaton.State;
import com.almondtools.rexlex.automaton.GenericAutomaton.Transition;
import com.almondtools.rexlex.pattern.DefaultTokenType;
import com.almondtools.rexlex.pattern.Pattern;
import com.almondtools.rexlex.pattern.RemainderTokenTypeFactory;
import com.almondtools.rexlex.tokens.Accept;
import com.almondtools.rexlex.tokens.TestToken;
import com.almondtools.rexlex.tokens.TestTokenFactory;
import net.amygdalum.util.text.CharUtils;

	@Test
	public void testComplexMakeEpsilonFree() throws Exception {
		GenericAutomaton a = match('a');
		GenericAutomaton b = match('b');
		GenericAutomaton ab = matchConcatenation(a, b);
		assertThat(ab, matchesAutomaton().containsTransition(NFATransitionMatcher.forClass(EpsilonTransition.class)));
		GenericAutomaton efree = ab.toAutomaton(new ToCompactGenericAutomaton());
		assertThat(efree, not(matchesAutomaton().containsTransition(NFATransitionMatcher.forClass(EpsilonTransition.class))));
	}

	@Test
	public void testComplexWithDoubleEpsilonConcatenatedStarLoopMakeEpsilonFree() throws Exception {
		GenericAutomaton a = match('a');
		GenericAutomaton space = createEpsilonAutomaton();
		GenericAutomaton astar = matchStarLoop(match('a'));
		GenericAutomaton aastar = matchConcatenation(a, space, astar);
		assertThat(matchSamples(aastar,"a"), contains("a"));
		assertThat(matchSamples(aastar,"aa"), contains("aa"));
		assertThat(matchSamples(aastar,"aaa"), contains("aaa"));
		GenericAutomaton efree = aastar.toAutomaton(new ToCompactGenericAutomaton());
		assertThat(matchSamples(efree,"a"), contains("a"));
		assertThat(matchSamples(efree,"aa"), contains("aa"));
		assertThat(matchSamples(efree,"aaa"), contains("aaa"));
	}

	private GenericAutomaton createEpsilonAutomaton() {
		State startspace = new State();
		State endspace = new State(DefaultTokenType.IGNORE);
		startspace.addTransition(new EpsilonTransition(endspace));
		GenericAutomaton space = new GenericAutomaton(startspace);
		return space;
	}

	@Test
	public void testVeryComplexMakeEpsilonFree() throws Exception {
		State s7486844 = new State();
		State s605645 = new State();
		State s12097592 = new State();
		State s17933228 = new State();
		State s11025290 = new State();
		State s17870931 = new State();
		State s14491894 = new State();
		State s27196165 = new State();
		State s2279771 = new State(DefaultTokenType.ACCEPT);
		State s30518483 = new State();
		State s11108810 = new State(DefaultTokenType.ACCEPT);

		s7486844.addTransition(new EpsilonTransition(s605645));
		s605645.addTransition(new EpsilonTransition(s12097592));
		s605645.addTransition(new EpsilonTransition(s17933228));
		s12097592.addTransition(new EpsilonTransition(s17933228));
		s12097592.addTransition(new EpsilonTransition(s17870931));
		s17933228.addTransition(new ExactTransition('a', s11025290));
		s11025290.addTransition(new EpsilonTransition(s12097592));
		s17870931.addTransition(new ExactTransition('a', s14491894));
		s14491894.addTransition(new EpsilonTransition(s27196165));
		s27196165.addTransition(new EpsilonTransition(s2279771));
		s2279771.addTransition(new EpsilonTransition(s30518483));
		s30518483.addTransition(new RangeTransition(Character.MIN_VALUE, Character.MAX_VALUE, s11108810));
		s11108810.addTransition(new EpsilonTransition(s2279771));

		GenericAutomaton a = new GenericAutomaton(s7486844);
		assertThat(matchSamples(a,"a"), contains("a"));
		assertThat(matchSamples(a,"aa"), hasItem("aa"));
		GenericAutomaton efree = a.toAutomaton(new ToCompactGenericAutomaton());
		assertThat(matchSamples(efree,"a"), contains("a"));
		assertThat(matchSamples(efree,"aa"), hasItem("aa"));
	}

	@Test
	public void testNexts() throws Exception {
		State s1 = new State(Accept.A);
		State s2 = new State();
		State s3 = new State();
		s1.addTransition(new ExactTransition('a', s2));
		s1.addTransition(new ExactTransition('a', s3));
		s2.addTransition(new ExactTransition('a', s1));
		s3.addTransition(new ExactTransition('b', s1));
		assertThat(targets(s1.nexts('a')), hasItems(s2, s3));
		assertThat(targets(s2.nexts('a')), hasItems(s1));
		assertThat(targets(s3.nexts('a')).size(), equalTo(0));
	}

	@Test
	public void testNextsWithEpsilon() throws Exception {
		State s1 = new State(Accept.A);
		State s2 = new State();
		State s3 = new State();
		s1.addTransition(new ExactTransition('a', s2));
		s1.addTransition(new EpsilonTransition(s3));
		s2.addTransition(new ExactTransition('a', s1));
		s3.addTransition(new ExactTransition('b', s1));
		assertThat(targets(s1.nexts('a')), hasItems(s2));
		assertThat(targets(s1.nexts('b')), hasItems(s1));
		assertThat(targets(s2.nexts('a')), hasItems(s1));
		assertThat(targets(s3.nexts('b')), hasItems(s1));
	}

	@Test
	public void testNextsWithCollidingEpsilon() throws Exception {
		State s1 = new State(Accept.A);
		State s2 = new State();
		State s3 = new State();
		s1.addTransition(new ExactTransition('a', s2));
		s1.addTransition(new EpsilonTransition(s3));
		s2.addTransition(new ExactTransition('a', s1));
		s3.addTransition(new ExactTransition('a', s3));
		s3.addTransition(new ExactTransition('b', s1));
		assertThat(targets(s1.nexts('a')), hasItems(s2, s3));
		assertThat(targets(s1.nexts('b')), hasItems(s1));
		assertThat(targets(s2.nexts('a')), hasItems(s1));
		assertThat(targets(s3.nexts('b')), hasItems(s1));
	}

	@Test
	public void testToDeterministicAutomaton1() throws Exception {
		GenericAutomaton nondet1 = nfa1();
		DeterministicAutomaton det1 = nondet1.toAutomaton(new ToDeterministicAutomaton());
		assertThat(det1, isDeterministic());
		assertMatches(det1, valid1(), invalid1());