package de.ugoe.cs.quest.usageprofiles;

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

import de.ugoe.cs.quest.eventcore.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
	 * @throws InvalidParameterException thrown if minOrder is less than 0 or greater than markovOrder or probEscape is not in the interval (0,1)
	 */
	public PredictionByPartialMatch(int markovOrder, int minOrder, Random r,
			double probEscape) {
		super(markovOrder, r);
		if( minOrder< 0 ) {
			throw new InvalidParameterException("minOrder must be greather than or equal to 0");
		}
		if( minOrder>markovOrder) {
			throw new InvalidParameterException("minOrder must be less than or equal to markovOrder");
		}
		if( probEscape<=0.0 || probEscape>=1.0) {
			throw new InvalidParameterException("probEscape must be in the interval (0,1)");
		}
		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>
	 * 
	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List,
	 *      de.ugoe.cs.quest.eventcore.Event)
	 */
	@Override
	public double getProbability(List<Event> context,
			Event symbol) {
		if (context == null) {
			throw new InvalidParameterException("context must not be null");
		}
		if (symbol == null) {
			throw new InvalidParameterException("symbol must not be null");
		}
		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;
	}
}
