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 high-order Markov models.
 * </p>
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class HighOrderMarkovModel extends TrieBasedModel {

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

	/**
	 * <p>
	 * Constructor. Creates a new HighOrderMarkovModel with a defined Markov
	 * order.
	 * </p>
	 * 
	 * @param maxOrder
	 *            Markov order of the model
	 * @param r
	 *            random number generator used by probabilistic methods of the
	 *            class
	 */
	public HighOrderMarkovModel(int maxOrder, Random r) {
		super(maxOrder, r);
	}

	/**
	 * <p>
	 * Calculates the probability of the next Event being symbol based on the
	 * order of the Markov model. The order is defined in the constructor
	 * {@link #HighOrderMarkovModel(int, Random)}.
	 * </p>
	 * 
	 * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List,
	 *      de.ugoe.cs.quest.eventcore.Event)
	 */
	@Override
	public double getProbability(List<? extends 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;

		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);
		int sumCountFollowers = 0; // N(s\sigma')
		for (Event<?> follower : followers) {
			sumCountFollowers += trie.getCount(contextCopy, follower);
		}

		int countSymbol = trie.getCount(contextCopy, symbol);
		if (sumCountFollowers != 0) {
			result = ((double) countSymbol / sumCountFollowers);
		}

		return result;
	}

}
