package de.ugoe.cs.eventbench.models;

import java.security.InvalidParameterException;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Set;

import de.ugoe.cs.eventbench.data.Event;
import de.ugoe.cs.eventbench.models.Trie.Edge;
import de.ugoe.cs.eventbench.models.Trie.TrieVertex;
import edu.uci.ics.jung.graph.Tree;

public abstract class TrieBasedModel implements IStochasticProcess {

	/**
	 * Id for object serialization.
	 */
	private static final long serialVersionUID = 1L;

	protected int trieOrder;

	protected Trie<Event<?>> trie;
	protected final Random r;

	
	public TrieBasedModel(int markovOrder, Random r) {
		super();
		this.trieOrder = markovOrder+1;
		this.r = r;
	}

	public void train(List<List<Event<?>>> sequences) {
		trie = new Trie<Event<?>>();
		
		for(List<Event<?>> sequence : sequences) {
			List<Event<?>> currentSequence = new LinkedList<Event<?>>(sequence); // defensive copy
			currentSequence.add(0, Event.STARTEVENT);
			currentSequence.add(Event.ENDEVENT);
			
			trie.train(currentSequence, trieOrder);
		}
	}

	/* (non-Javadoc)
	 * @see de.ugoe.cs.eventbench.models.IStochasticProcess#randomSequence()
	 */
	@Override
	public List<? extends Event<?>> randomSequence() {
		List<Event<?>> sequence = new LinkedList<Event<?>>();
		
		IncompleteMemory<Event<?>> context = new IncompleteMemory<Event<?>>(trieOrder-1);
		context.add(Event.STARTEVENT);
		
		Event<?> currentState = Event.STARTEVENT;
		
		boolean endFound = false;
		
		while(!endFound) {
			double randVal = r.nextDouble();
			double probSum = 0.0;
			List<Event<?>> currentContext = context.getLast(trieOrder);
			for( Event<?> symbol : trie.getKnownSymbols() ) {
				probSum += getProbability(currentContext, symbol);
				if( probSum>=randVal ) {
					endFound = (symbol==Event.ENDEVENT);
					if( !(symbol==Event.STARTEVENT || symbol==Event.ENDEVENT) ) {
						// only add the symbol the sequence if it is not START or END
						context.add(symbol);
						currentState = symbol;
						sequence.add(currentState);
					}
					break;
				}
			}
		}
		return sequence;
	}
	
	public String getTrieDotRepresentation() {
		return trie.getDotRepresentation();
	}
	
	public Tree<TrieVertex, Edge> getTrieGraph() {
		return trie.getGraph();
	}

	@Override
	public String toString() {
		return trie.toString();
	}
	
	public int getNumStates() {
		return trie.getNumSymbols();
	}
	
	public String[] getStateStrings() {
		String[] stateStrings = new String[getNumStates()];
		int i=0;
		for( Event<?> symbol : trie.getKnownSymbols() ) {
			stateStrings[i] = symbol.toString();
			i++;
		}
		return stateStrings;
	}
	
	public Set<? extends Event<?>> getEvents() {
		return trie.getKnownSymbols();
	}
	
	public Set<List<? extends Event<?>>> generateSequences(int length) {
		return generateSequences(length, false);
		/*Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();;
		if( length<1 ) {
			throw new InvalidParameterException("Length of generated subsequences must be at least 1.");
		}
		if( length==1 ) {
			for( Event<?> event : getEvents() ) {
				List<Event<?>> subSeq = new LinkedList<Event<?>>();
				subSeq.add(event);
				sequenceSet.add(subSeq);
			}
			return sequenceSet;
		}
		Set<? extends Event<?>> events = getEvents();
		Set<List<? extends Event<?>>> seqsShorter = generateSequences(length-1);
		for( Event<?> event : events ) {
			for( List<? extends Event<?>> seqShorter : seqsShorter ) {
				Event<?> lastEvent = event;
				if( getProbability(seqShorter, lastEvent)>0.0 ) {
					List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter);
					subSeq.add(lastEvent);
					sequenceSet.add(subSeq);
				}
			}
		}
		return sequenceSet;
		*/
	}
	
	// if startValid, all sequences will start in Event.STARTEVENT
	public Set<List<? extends Event<?>>> generateSequences(int length, boolean fromStart) {
		Set<List<? extends Event<?>>> sequenceSet = new LinkedHashSet<List<? extends Event<?>>>();;
		if( length<1 ) {
			throw new InvalidParameterException("Length of generated subsequences must be at least 1.");
		}
		if( length==1 ) {
			if( fromStart ) {
				List<Event<?>> subSeq = new LinkedList<Event<?>>();
				subSeq.add(Event.STARTEVENT);
				sequenceSet.add(subSeq);
			} else {
				for( Event<?> event : getEvents() ) {
					List<Event<?>> subSeq = new LinkedList<Event<?>>();
					subSeq.add(event);
					sequenceSet.add(subSeq);
				}
			}
			return sequenceSet;
		}
		Set<? extends Event<?>> events = getEvents();
		Set<List<? extends Event<?>>> seqsShorter = generateSequences(length-1, fromStart);
		for( Event<?> event : events ) {
			for( List<? extends Event<?>> seqShorter : seqsShorter ) {
				Event<?> lastEvent = event;
				if( getProbability(seqShorter, lastEvent)>0.0 ) {
					List<Event<?>> subSeq = new ArrayList<Event<?>>(seqShorter);
					subSeq.add(lastEvent);
					sequenceSet.add(subSeq);
				}
			}
		}
		return sequenceSet;
	}
	
	// sequences from start to end
	public Set<List<? extends Event<?>>> generateValidSequences(int length) {
		// check for min-length implicitly done by generateSequences
		Set<List<? extends Event<?>>> allSequences = generateSequences(length, true);
		Set<List<? extends Event<?>>> validSequences = new LinkedHashSet<List<? extends Event<?>>>();
		for( List<? extends Event<?>> sequence : allSequences ) {
			if( sequence.size()==length && Event.ENDEVENT.equals(sequence.get(sequence.size()-1)) ) {
				validSequences.add(sequence);
			}
		}
		return validSequences;
	}

}