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;

/**
 * <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}^1 escape^{i-1}
 * P_{MM^i}(X_n|X_{n-1},...,X_{n-i})(1-escape)<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>
	 * Probability to use a lower-order Markov model
	 * </p>
	 */
	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) {
		super(markovOrder, r);
		this.probEscape = probEscape;
	}

	/**
	 * <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}^1 escape^{i-1}
	 * P_{MM^i}(X_n|X_{n-1},...,X_{n-i})(1-escape)<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);
		}

		List<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 (contextCopy.size() == 0) {
			resultCurrentContex = ((double) countSymbol) / sumCountFollowers;
		} else {
			if (sumCountFollowers == 0) {
				resultCurrentContex = 0.0;
			} else {
				resultCurrentContex = ((double) countSymbol / sumCountFollowers)
						* (1 - probEscape);
			}
			contextCopy.remove(0);
			double probSuffix = getProbability(contextCopy, symbol);
			if (followers.size() == 0) {
				resultShorterContex = probSuffix;
			} else {
				resultShorterContex = probEscape * probSuffix;
			}
		}
		result = resultCurrentContex + resultShorterContex;

		return result;
	}
}