package de.ugoe.cs.eventbench.models;

import java.security.InvalidParameterException;
import java.util.ArrayList;
import java.util.Collection;
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;

/**
 * <p>
 * Implements a skeleton for stochastic processes that can calculate
 * probabilities based on a trie. The skeleton provides all functionalities of
 * {@link IStochasticProcess} except
 * {@link IStochasticProcess#getProbability(List, Event)}.
 * </p>
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public abstract class TrieBasedModel implements IStochasticProcess {

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

	/**
	 * <p>
	 * The order of the trie, i.e., the maximum length of subsequences stored in
	 * the trie.
	 * </p>
	 */
	protected int trieOrder;

	/**
	 * <p>
	 * Trie on which the probability calculations are based.
	 * </p>
	 */
	protected Trie<Event<?>> trie;

	/**
	 * <p>
	 * Random number generator used by probabilistic sequence generation
	 * methods.
	 * </p>
	 */
	protected final Random r;

	/**
	 * <p>
	 * Constructor. Creates a new TrieBasedModel that can be used for stochastic
	 * processes with a Markov order less than or equal to {@code markovOrder}.
	 * </p>
	 * 
	 * @param markovOrder
	 *            Markov order of the model
	 * @param r
	 *            random number generator used by probabilistic methods of the
	 *            class
	 */
	public TrieBasedModel(int markovOrder, Random r) {
		super();
		this.trieOrder = markovOrder + 1;
		this.r = r;
	}

	/**
	 * <p>
	 * Trains the model by generating a trie from which probabilities are
	 * calculated.
	 * </p>
	 * 
	 * @param sequences
	 *            training data
	 */
	public void train(Collection<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;
	}

	/**
	 * <p>
	 * Returns a Dot representation of the internal trie.
	 * </p>
	 * 
	 * @return dot representation of the internal trie
	 */
	public String getTrieDotRepresentation() {
		return trie.getDotRepresentation();
	}

	/**
	 * <p>
	 * Returns a {@link Tree} of the internal trie that can be used for
	 * visualization.
	 * </p>
	 * 
	 * @return {@link Tree} depicting the internal trie
	 */
	public Tree<TrieVertex, Edge> getTrieGraph() {
		return trie.getGraph();
	}

	/**
	 * <p>
	 * The string representation of the model is {@link Trie#toString()} of
	 * {@link #trie}.
	 * </p>
	 * 
	 * @see java.lang.Object#toString()
	 */
	@Override
	public String toString() {
		return trie.toString();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumStates()
	 */
	@Override
	public int getNumSymbols() {
		return trie.getNumSymbols();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getStateStrings()
	 */
	@Override
	public String[] getSymbolStrings() {
		String[] stateStrings = new String[getNumSymbols()];
		int i = 0;
		for (Event<?> symbol : trie.getKnownSymbols()) {
			stateStrings[i] = symbol.toString();
			i++;
		}
		return stateStrings;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getEvents()
	 */
	@Override
	public Collection<? extends Event<?>> getEvents() {
		return trie.getKnownSymbols();
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see
	 * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int)
	 */
	@Override
	public Collection<List<? extends Event<?>>> generateSequences(int length) {
		return generateSequences(length, false);
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see
	 * de.ugoe.cs.eventbench.models.IStochasticProcess#generateSequences(int,
	 * boolean)
	 */
	@Override
	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;
		}
		Collection<? extends Event<?>> events = getEvents();
		Collection<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;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see
	 * de.ugoe.cs.eventbench.models.IStochasticProcess#generateValidSequences
	 * (int)
	 */
	@Override
	public Collection<List<? extends Event<?>>> generateValidSequences(
			int length) {
		// check for min-length implicitly done by generateSequences
		Collection<List<? extends Event<?>>> allSequences = generateSequences(
				length, true);
		Collection<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;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see
	 * de.ugoe.cs.eventbench.models.IStochasticProcess#getProbability(java.util
	 * .List)
	 */
	@Override
	public double getProbability(List<? extends Event<?>> sequence) {
		double prob = 1.0;
		if (sequence != null) {
			List<Event<?>> context = new LinkedList<Event<?>>();
			for (Event<?> event : sequence) {
				prob *= getProbability(context, event);
				context.add(event);
			}
		}
		return prob;
	}

	/* (non-Javadoc)
	 * @see de.ugoe.cs.eventbench.models.IStochasticProcess#getNumFOMStates()
	 */
	@Override
	public int getNumFOMStates() {
		return trie.getNumLeafAncestors();
	}
}