package de.ugoe.cs.eventbench.ppm;

import java.awt.Dimension;
import java.awt.Rectangle;
import java.awt.Shape;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import javax.swing.JFrame;

import org.apache.commons.collections15.Transformer;

import de.ugoe.cs.eventbench.markov.IncompleteMemory;

import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.algorithms.layout.TreeLayout;
import edu.uci.ics.jung.graph.DelegateTree;
import edu.uci.ics.jung.graph.Tree;
import edu.uci.ics.jung.visualization.BasicVisualizationServer;
import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position;

public class Trie<T> {
	
	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 maxOrder
	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 List<T> getFollowingSymbols(List<T> sequence) {
		List<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;
		}
	}
	
	private Tree<TrieVertex, Edge> getGraph() {
		DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>();
		rootNode.getGraph(null, graph);
		return graph;
	}
	
	public void display() {
		Tree<TrieVertex, Edge> graph = this.getGraph();
		Layout<TrieVertex, Edge> layout = new TreeLayout<TrieVertex, Edge>(graph, 60);
		// The BasicVisualizationServer<V,E> is parameterized by the edge types
		BasicVisualizationServer<TrieVertex,Edge> vv =
		new BasicVisualizationServer<TrieVertex,Edge>(layout);
		vv.setPreferredSize(new Dimension(1100,850)); //Sets the viewing area size
		
		
		final Rectangle rect = new Rectangle(40, 20);
			
		Transformer<TrieVertex, Shape> vertexShapeTransformer =
			new Transformer<TrieVertex, Shape>() {
				public Shape transform(TrieVertex s) {
					return rect;
				}
		};
		vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR);
		vv.getRenderContext().setVertexShapeTransformer(vertexShapeTransformer);
		vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<TrieVertex>());
		
		JFrame frame = new JFrame("Trie");
		frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
		frame.getContentPane().add(vv);
		frame.pack();
		frame.setVisible(true);
	}
	
	@Override
	public String toString() {
		return rootNode.toString();
	}
}
