package utp;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.HashMap;
import java.util.Set;

public class Automaton<T> {
	private List<HashMap<T, Set<Integer>>> m_transitions;
	private boolean[] m_endStates;

	public Automaton(int n) {
		m_transitions = new ArrayList<HashMap<T, Set<Integer>>>(n);
		m_endStates = new boolean[n];
		for(int i  = 0 ; i < n ; i++)
		{
			m_transitions.add(new HashMap<T, Set<Integer>>());
			m_endStates[i] = false;
		}
	}
	
	public void addEdge(int a, int b, T symbol)
	{
		HashMap<T, Set<Integer>> nexts = m_transitions.get(a);
		Set<Integer> trg = nexts.get(symbol);
		if(trg == null)
		{
			trg = new HashSet<Integer>();
			nexts.put(symbol, trg);
		}
		trg.add(b);
	}
	
	public void removeEdge(int a, int b, T symbol)
	{
		HashMap<T, Set<Integer>> nexts = m_transitions.get(a);
		Set<Integer> trg = nexts.get(symbol);
		if(trg != null) trg.remove(b);
	}
	
	public void addEndState(int a)
	{
		m_endStates[a] = true;
	}
	
	public void removeEndState(int a)
	{
		m_endStates[a] = false;
	}
	
	public boolean isEnd(int a)
	{
		return m_endStates[a];
	}
	
	
	public boolean recognize(List<T> word)
	{
		return recognize(word, 0, 0);
	}
	
	private boolean recognize(List<T> word, int i, int s)
	{
		if(word.size() == i) return isEnd(s);
		T letter = word.get(i);
		Set<Integer> nexts = m_transitions.get(s).get(letter);
		if(nexts == null) return false;
		for(Integer nextState : nexts)
		{
			if(recognize(word, i+1, nextState)) return true;
		}
		return false;
	}
	
	public static void main(String[] args)
	{
		Automaton<String> aut = new Automaton<String>(4);
		
		aut.addEdge(0, 1, "a");
		aut.addEdge(0, 1, "b");
		
		aut.addEdge(0, 2, "a");
		aut.addEdge(0, 3, "b");
		
		aut.addEdge(1, 1, "a");
		aut.addEdge(1, 2, "a");
		
		aut.addEdge(2, 3, "a");
		
		aut.addEdge(3, 3, "b");
		
		aut.addEndState(3);
		
		
		List<String> word = Arrays.asList("a", "b", "a");
		
		System.out.println(aut.recognize(word));
		
		
		
		
		
	}
	

	
}