package de.ugoe.cs.eventbench.models;

import java.io.Serializable;
import java.util.Collection;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import de.ugoe.cs.util.StringTools;

import edu.uci.ics.jung.graph.DelegateTree;
import edu.uci.ics.jung.graph.Tree;

public class Trie<T> implements IDotCompatible, Serializable {
	
	/**
	 * Id for object serialization.
	 */
	private static final long serialVersionUID = 1L;

	private Set<T> knownSymbols;
	
	private final TrieNode<T> rootNode;
	
	public Trie() {
		rootNode = new TrieNode<T>();
		knownSymbols = new LinkedHashSet<T>();
	}
	
	public Set<T> getKnownSymbols() {
		return new LinkedHashSet<T>(knownSymbols);
	}
	
	// trains the current Trie using the given sequence and adds all subsequence of length trieOrder
	public void train(List<T> sequence, int maxOrder) {
		IncompleteMemory<T> latestActions = new IncompleteMemory<T>(maxOrder);
		int i=0;
		for(T currentEvent : sequence) {
			latestActions.add(currentEvent);
			knownSymbols.add(currentEvent);
			i++;
			if( i>=maxOrder ) {
				add(latestActions.getLast(maxOrder));
			}
		}
		int sequenceLength = sequence.size();
		for( int j=maxOrder-1 ; j>0 ; j-- ) {
			add(sequence.subList(sequenceLength-j, sequenceLength));
		}
	}
	

	// increases the counters for each symbol in the subsequence
	public void add(List<T> subsequence) {
		if( subsequence!=null && !subsequence.isEmpty() ) {
			knownSymbols.addAll(subsequence);
			subsequence = new LinkedList<T>(subsequence);  // defensive copy!
			T firstSymbol = subsequence.get(0);
			TrieNode<T> node = getChildCreate(firstSymbol);
			node.add(subsequence);
		}
	}

	protected TrieNode<T>  getChildCreate(T symbol) {
		return rootNode.getChildCreate(symbol);
	}
	
	protected TrieNode<T> getChild(T symbol) {
		return rootNode.getChild(symbol);
	}

	// get the count of "sequence"
	public int getCount(List<T> sequence) {
		int count = 0;
		TrieNode<T> node = find(sequence);
		if( node!=null ) {
			count = node.getCount();
		}
		return count;
	}
	
	// get the count of "sequence,follower"
	public int getCount(List<T> sequence, T follower) {
		List<T> tmpSequence = new LinkedList<T>(sequence);
		tmpSequence.add(follower);
		return getCount(tmpSequence);
		
	}
	
	public TrieNode<T> find(List<T> sequence) {
		if( sequence==null || sequence.isEmpty() ) {
			return rootNode;
		}
		List<T> sequenceCopy = new LinkedList<T>(sequence);
		TrieNode<T> result = null;
		TrieNode<T> node = getChild(sequenceCopy.get(0));
		if( node!=null ) {
			sequenceCopy.remove(0);
			result = node.find(sequenceCopy);
		}
		return result;
	}
	
	// returns all symbols that follow the defined sequence
	public Collection<T> getFollowingSymbols(List<T> sequence) {
		Collection<T> result = new LinkedList<T>();
		TrieNode<T> node = find(sequence);
		if( node!=null ) {
			result = node.getFollowingSymbols();
		}
		return result;
	}
	
	// longest suffix of context, that is contained in the tree and whose children are leaves
	// possibly already deprecated
	public List<T> getContextSuffix(List<T> context) {
		List<T> contextSuffix = new LinkedList<T>(context); // defensive copy
		boolean suffixFound = false;
		
		while(!suffixFound) {
			if( contextSuffix.isEmpty() ) {
				suffixFound = true; // suffix is the empty word
			} else {
				TrieNode<T> node = find(contextSuffix);
				if( node!=null ) {
					if( !node.getFollowingSymbols().isEmpty() ) {
						suffixFound = true;
					}
				}
				if( !suffixFound ) {
					contextSuffix.remove(0);
				}
			}
		}
		
		return contextSuffix;
	}
	
	
	static public class Edge{}
	
	static public class TrieVertex {
		private String id;
		protected TrieVertex(String id) {
			this.id = id;
		}
		public String toString() {
			return id;
		}
	}
	
	protected Tree<TrieVertex, Edge> getGraph() {
		DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>();
		rootNode.getGraph(null, graph);
		return graph;
	}
	
	public String getDotRepresentation() {
		StringBuilder stringBuilder = new StringBuilder();
		stringBuilder.append("digraph model {" + StringTools.ENDLINE);
		rootNode.appendDotRepresentation(stringBuilder);
		stringBuilder.append('}' + StringTools.ENDLINE);
		return stringBuilder.toString();
	}
	
	@Override
	public String toString() {
		return rootNode.toString();
	}
	
	public int getNumSymbols() {
		return knownSymbols.size();
	}
}