package de.ugoe.cs.eventbench.models;

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

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

/**
 * <p>
 * Implements Prediction by Partial Match (PPM) based on the following formula
 * (LaTeX-style notation):<br>
 * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i} P_{MM^i}(X_n
 * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},... ,X_{n-min})<br>
 * P_{MM^i} denotes the probability in an i-th order Markov model.
 * </p>
 * 
 * @author Steffen Herbold
 * 
 */
public class PredictionByPartialMatch extends TrieBasedModel {

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

	/**
	 * <p>
	 * Minimum order of the Markov model.
	 * </p>
	 */
	protected int minOrder;

	/**
	 * <p>
	 * Probability to use a lower-order Markov model
	 * </p>
	 */
	protected double probEscape;

	/**
	 * <p>
	 * Constructor. Creates a new PredictionByPartialMatch model with a given
	 * Markov order and a default escape probability of 0.1.
	 * </p>
	 * 
	 * @param markovOrder
	 *            Markov order of the model
	 * @param r
	 *            random number generator used by probabilistic methods of the
	 *            class
	 */
	public PredictionByPartialMatch(int markovOrder, Random r) {
		this(markovOrder, r, 0.1);
	}

	/**
	 * <p>
	 * Creates a new PredictionByPartialMatch model with a given Markov order
	 * and escape probability.
	 * </p>
	 * 
	 * @param markovOrder
	 *            Markov order of the model
	 * @param r
	 *            random number generator used by probabilistic methods of the
	 *            class
	 * @param probEscape
	 *            escape probability used by the model
	 */
	public PredictionByPartialMatch(int markovOrder, Random r, double probEscape) {
		this(markovOrder, 0, r, probEscape);
	}

	/**
	 * <p>
	 * Creates a new PredictionByPartialMatch model with a given Markov order
	 * and escape probability.
	 * </p>
	 * 
	 * @param markovOrder
	 *            Markov order of the model
	 * @param minOrder
	 *            minimum order of the model; if this order is reached, there is
	 *            no escape
	 * @param r
	 *            random number generator used by probabilistic methods of the
	 *            class
	 * @param probEscape
	 *            escape probability used by the model
	 */
	public PredictionByPartialMatch(int markovOrder, int minOrder, Random r,
			double probEscape) {
		super(markovOrder, r);
		this.probEscape = probEscape;
		this.minOrder = minOrder;
	}

	/**
	 * <p>
	 * Sets the escape probability of the model.
	 * </p>
	 * 
	 * @param probEscape
	 *            new escape probability
	 */
	public void setProbEscape(double probEscape) {
		this.probEscape = probEscape;
	}

	/**
	 * <p>
	 * Returns the escape probability of the model.
	 * </p>
	 * 
	 * @return escape probability of the model
	 */
	public double getProbEscape() {
		return probEscape;
	}

	/**
	 * <p>
	 * Calculates the probability of the next event based on the formula:<br>
	 * P_{PPM}(X_n|X_{n-1},...,X_{n-k}) = \sum_{i=k}^min escape^{k-i}
	 * P_{MM^i}(X_n
	 * |X_{n-1},...,X_{n-i})(1-escape)+escape^(k-min)P(X_n|X_{n-i},...
	 * ,X_{n-min})<br>
	 * P_{MM^i} denotes the probability in an i-th order Markov model.
	 * </p>
	 */
	@Override
	public double getProbability(List<? extends Event<?>> context,
			Event<?> symbol) {
		double result = 0.0d;
		double resultCurrentContex = 0.0d;
		double resultShorterContex = 0.0d;

		List<Event<?>> contextCopy;
		if (context.size() >= trieOrder) {
			contextCopy = new LinkedList<Event<?>>(context.subList(
					context.size() - trieOrder + 1, context.size()));
		} else {
			contextCopy = new LinkedList<Event<?>>(context);
		}

		Collection<Event<?>> followers = trie.getFollowingSymbols(contextCopy); // \Sigma'
		int sumCountFollowers = 0; // N(s\sigma')
		for (Event<?> follower : followers) {
			sumCountFollowers += trie.getCount(contextCopy, follower);
		}

		int countSymbol = trie.getCount(contextCopy, symbol); // N(s\sigma)
		if (sumCountFollowers == 0) {
			resultCurrentContex = 0.0;
		} else {
			resultCurrentContex = (double) countSymbol / sumCountFollowers;
		}
		if (contextCopy.size() >= minOrder) {
			resultCurrentContex *= (1 - probEscape);
			contextCopy.remove(0);
			if (contextCopy.size() >= minOrder) {
				double probSuffix = getProbability(contextCopy, symbol);

				if (followers.size() == 0) {
					resultShorterContex = probSuffix;
				} else {
					resultShorterContex = probEscape * probSuffix;
				}
			}
		}
		result = resultCurrentContex + resultShorterContex;

		return result;
	}
}
