package de.ugoe.cs.eventbench.models;

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

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

public abstract class TrieBasedModel implements IStochasticProcess {

	protected int trieOrder;

	protected abstract double getProbability(List<Event<?>> context, Event<?> symbol);

	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;
	}

	@Override
	public String toString() {
		return trie.toString();
	}

}