package de.ugoe.cs.eventbench.ppm;

import java.util.LinkedList;
import java.util.List;

public class Trie<T> {
	
	private List<TrieNode<T>> children = new LinkedList<TrieNode<T>>();
	

	public void add(List<T> subsequence) {
		if( !subsequence.isEmpty() ) {
			subsequence = new LinkedList<T>(subsequence);  // copy list!
			T firstSymbol = subsequence.get(0);
			getChildCreate(firstSymbol).add(subsequence);
		}
	}

	// FIXME clones of TrieNode.getChildCreate
	protected TrieNode<T>  getChildCreate(T symbol) {
		TrieNode<T> node = getChild(symbol);
		if( node==null ) {
			node = new TrieNode<T>(symbol);
			children.add(node);
		}
		return node;
	}
	
	// FIXME clones of TrieNode.getChild
	protected TrieNode<T> getChild(T symbol) {
		for( TrieNode<T> child : children ) {
			if( child.getSymbol().equals(symbol) ) {
				return child;
			}
		}
		return null;
	}

	public int getCount(List<T> sequence) {
		int count = 0;
		TrieNode<T> node = find(sequence);
		if( node!=null ) {
			count = node.getCount();
		}
		return count;
	}
	
	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) {
		TrieNode<T> result = null;
		if( !sequence.isEmpty() ) {
			TrieNode<T> node = getChild(sequence.get(0));
			if( node!=null ) {
				result = node.find(sequence);
			}
		}
		return result;
	}
	
	public List<T> getFollowingSymbols(List<T> sequence) {
		List<T> result = null;
		TrieNode<T> node = find(sequence);
		if( node!=null ) {
			result = node.getFollowingSymbols();
		}
		return result;
	}
	
	public List<T> getContextSuffix(List<T> context) {
		List<T> contextSuffix = new LinkedList<T>(context);
		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;
					}
				}
				contextSuffix.remove(0);
			}
		}
		
		return contextSuffix;
	}
	
	@Override
	public String toString() {
		return children.toString();
	}
}