package de.ugoe.cs.eventbench.coverage;

import java.security.InvalidParameterException;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;

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

/**
 * <p>
 * This class calculates various types of sequence coverage.
 * </p>
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class CoverageCalculator {

	/**
	 * <p>
	 * Stochastic process that is the foundation for probabilistic coverages and
	 * coverages with reference to all possible sequences.
	 * </p>
	 */
	private final IStochasticProcess process;

	/**
	 * <p>
	 * Sequences for which the coverage is calculated.
	 * </p>
	 */
	private final Collection<List<? extends Event<?>>> sequences;

	/**
	 * <p>
	 * Length of the subsequences in relation to which the covarage is
	 * calculated.
	 * </p>
	 */
	private final int length;

	/**
	 * <p>
	 * All subsequences of {@link #length} of {@link #sequences}.
	 * </p>
	 */
	private Collection<List<? extends Event<?>>> containedSubSeqs = null;

	/**
	 * <p>
	 * All subsequences of {@link #length} that can be generated by
	 * {@link #process}.
	 * </p>
	 */
	private Collection<List<? extends Event<?>>> allPossibleSubSeqs = null;

	/**
	 * <p>
	 * The probabilities of al subsequences of {@link #length} according to
	 * {@link #process}.
	 * </p>
	 */
	private Map<List<? extends Event<?>>, Double> subSeqWeights = null;

	/**
	 * <p>
	 * Constructor. Creates a new CoverageCalculator for a given stochastic
	 * process and generated sequences.
	 * </p>
	 * 
	 * @param process
	 *            stochastic process used for coverage calculations; must not be null
	 * @param sequences
	 *            sequences for which the coverage is calculated; must not be
	 *            null
	 * @param length
	 *            length of the subsequences for which the coverage is analyzed;
	 *            must be >0
	 */
	public CoverageCalculator(IStochasticProcess process,
			Collection<List<? extends Event<?>>> sequences, int length) {
		if( process==null ) {
			throw new InvalidParameterException("process must not be null");
		}
		if( sequences==null ) {
			throw new InvalidParameterException("sequences must not be null");
		}
		if( length<=0 ) {
			throw new InvalidParameterException("length must be >0; actual value: " + length);
		}
		this.process = process;
		this.sequences = sequences;
		this.length = length;
	}

	/**
	 * <p>
	 * Calculates the percentage of subsequences of length k that exist occur,
	 * including those that cannot be generated by {@link #process}.
	 * </p>
	 * 
	 * @return coverage percentage
	 */
	public double getCoverageAllNoWeight() {
		if (containedSubSeqs == null) {
			containedSubSeqs = containedSubSequences(sequences, length);
		}
		return ((double) containedSubSeqs.size())
				/ numSequences(process, length);
	}

	/**
	 * <p>
	 * Calculates the percentage of subsequences of length k that occur and can
	 * generated by {@link #process}.
	 * </p>
	 * 
	 * @return coverage percentage
	 */
	public double getCoveragePossibleNoWeight() {
		if (containedSubSeqs == null) {
			containedSubSeqs = containedSubSequences(sequences, length);
		}
		if (allPossibleSubSeqs == null) {
			allPossibleSubSeqs = process.generateSequences(length);
		}
		return ((double) containedSubSeqs.size()) / allPossibleSubSeqs.size();
	}

	/**
	 * <p>
	 * Calculates the weight of the subsequences that occur with relation to
	 * {@link #process}, i.e., the mass of the subsequence probability covered
	 * by the subsequences.
	 * </p>
	 * 
	 * @return coverage weight
	 */
	public double getCoveragePossibleWeight() {
		if (containedSubSeqs == null) {
			containedSubSeqs = containedSubSequences(sequences, length);
		}
		if (allPossibleSubSeqs == null) {
			allPossibleSubSeqs = process.generateSequences(length);
		}
		if (subSeqWeights == null) {
			subSeqWeights = generateWeights(process, allPossibleSubSeqs);
		}
		double weight = 0.0;
		for (List<? extends Event<?>> subSeq : containedSubSeqs) {
			weight += subSeqWeights.get(subSeq);
		}
		return weight;
	}

	/**
	 * <p>
	 * Calculates the weights for all sequences passed to this function as
	 * defined by the stochastic process and stores them in a {@link Map}.
	 * </p>
	 * 
	 * @param process
	 *            process used for weight calculation
	 * @param sequences
	 *            sequences for which the weights are calculated
	 * @return {@link Map} of weights
	 */
	private static Map<List<? extends Event<?>>, Double> generateWeights(
			IStochasticProcess process,
			Collection<List<? extends Event<?>>> sequences) {
		Map<List<? extends Event<?>>, Double> subSeqWeights = new LinkedHashMap<List<? extends Event<?>>, Double>();
		double sum = 0.0;
		for (List<? extends Event<?>> sequence : sequences) {
			double prob = 1.0;
			List<Event<?>> context = new LinkedList<Event<?>>();
			for (Event<?> event : sequence) {
				prob *= process.getProbability(context, event);
				context.add(event);
			}
			subSeqWeights.put(sequence, prob);
			sum += prob;
		}
		if (sum < 1.0) {
			for (Map.Entry<List<? extends Event<?>>, Double> entry : subSeqWeights
					.entrySet()) {
				entry.setValue(entry.getValue() / sum);
			}
		}
		return subSeqWeights;
	}

	/**
	 * <p>
	 * Calculates the number of all existing sequences of a given length,
	 * regardless whether they are possible or not.
	 * </p>
	 * 
	 * @param process
	 *            stochastic process whose symbols are the basis for this
	 *            calculation
	 * @param length
	 *            lenght of the sequences
	 * @return numStates^length
	 */
	private static long numSequences(IStochasticProcess process, int length) {
		return (long) Math.pow(process.getNumStates(), length);
	}

	/**
	 * <p>
	 * Creates a {@link Set} of all subsequences of a given length that are
	 * contained in a sequence collection.
	 * </p>
	 * 
	 * @param sequences
	 *            sequences from which the subsequences are extracted
	 * @param length
	 *            length of the subsequences
	 * @return {@link Set} of all subsequences
	 */
	private static Set<List<? extends Event<?>>> containedSubSequences(
			Collection<List<? extends Event<?>>> sequences, int length) {
		Set<List<? extends Event<?>>> containedSubSeqs = new LinkedHashSet<List<? extends Event<?>>>();
		for (List<? extends Event<?>> sequence : sequences) {
			List<Event<?>> subSeq = new LinkedList<Event<?>>();
			boolean minLengthReached = false;
			for (Event<?> event : sequence) {
				subSeq.add(event);
				if (!minLengthReached) {
					if (subSeq.size() == length) {
						minLengthReached = true;
					}
				} else {
					subSeq.remove(0);
				}
				if (minLengthReached) {
					if (!containedSubSeqs.contains(subSeq)) {
						containedSubSeqs.add(new LinkedList<Event<?>>(subSeq));
					}
				}
			}
		}
		return containedSubSeqs;
	}

}
