package de.ugoe.cs.quest.testgeneration;

import java.security.InvalidParameterException;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
import java.util.Set;

import de.ugoe.cs.quest.eventcore.Event;
import de.ugoe.cs.quest.usageprofiles.IStochasticProcess;
import de.ugoe.cs.util.console.Console;

/**
 * <p>
 * Generates a test suite by drawing from all possible sequences of a fixed
 * length according to the probabilities of the sequences in a
 * {@link IStochasticProcess}.
 * </p>
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class DrawFromAllSequencesGenerator {

	/**
	 * <p>
	 * Number of sequences in the test suite.
	 * </p>
	 */
	private final int numSequences;

	/**
	 * <p>
	 * Minimal length of a test sequence.
	 * </p>
	 */
	private final int minLength;

	/**
	 * <p>
	 * Maximal length of a test sequence.
	 * </p>
	 */
	private final int maxLength;

	/**
	 * <p>
	 * In case this member is true, only test cases that end in the global end
	 * event {@link Event#ENDEVENT} are generated. If it is false, the end event
	 * can be any event.
	 * </p>
	 */
	private final boolean validEnd;

	/**
	 * <p>
	 * If this member is true, the generated test suite contains all possible
	 * sequences and {@link #numSequences} is ignored.
	 * </p>
	 */
	private final boolean generateAll;

	/**
	 * <p>
	 * Constructor. Creates a new DrawFromAllSequencesGenerator and ensures the
	 * validity of the parameters:
	 * <ul>
	 * <li>numSequences must at least be 1
	 * <li>maxLength must at least be 1
	 * <li>minLength must be less than or equal to maxLength
	 * </ul>
	 * If one of these conditions is violated an
	 * {@link InvalidParameterException} is thrown.
	 * </p>
	 * 
	 * @param numSequences
	 *            number of sequences desired for the test suite
	 * @param minLength
	 *            minimal length of a test sequence
	 * @param maxLength
	 *            maximal length of a test sequence
	 * @param validEnd
	 *            defines if test cases have to end with the global end event
	 *            {@link Event#ENDEVENT} (see {@link #validEnd})
	 * @param generateAll
	 *            if this parameter is true, the test suite contains all
	 *            possible sequences and numSequences is ignored
	 */
	public DrawFromAllSequencesGenerator(int numSequences, int minLength,
			int maxLength, boolean validEnd, boolean generateAll) {
		// check validity of the parameters
		if (numSequences < 1) {
			throw new InvalidParameterException(
					"number of sequences must be at least 1 but is "
							+ numSequences);
		}
		if (maxLength < 1) {
			throw new InvalidParameterException(
					"maximal allowed length of test cases must be at least 1 but is "
							+ maxLength);
		}
		if (minLength > maxLength) {
			throw new InvalidParameterException(
					"minimal allowed length of test cases must be less than or equal to the maximal allowed length (min length: "
							+ minLength + " ; max length: " + maxLength + ")");
		}
		this.numSequences = numSequences;
		this.minLength = minLength;
		this.maxLength = maxLength;
		this.validEnd = validEnd;
		this.generateAll = generateAll;
	}

	/**
	 * <p>
	 * Generates a test suite by drawing from all possible sequences with valid
	 * lengths.
	 * </p>
	 * 
	 * @param model
	 *            model used to determine the probability of each possible
	 *            sequence
	 * @return the test suite
	 */
	public Collection<List<? extends Event<?>>> generateTestSuite(
			IStochasticProcess model) {
		if (model == null) {
			throw new InvalidParameterException("model must not be null!");
		}

		Collection<List<? extends Event<?>>> sequences = new LinkedHashSet<List<? extends Event<?>>>();
		for (int length = minLength; length <= maxLength; length++) {
			if (validEnd) {
				sequences.addAll(model.generateValidSequences(length + 2));
			} else {
				sequences.addAll(model.generateSequences(length + 1, true));
			}
		}
		Console.traceln("" + sequences.size() + " possible");
		if (!generateAll && numSequences < sequences.size()) {
			List<Double> probabilities = new ArrayList<Double>(sequences.size());
			double probSum = 0.0;
			for (List<? extends Event<?>> sequence : sequences) {
				double prob = model.getProbability(sequence);
				probabilities.add(prob);
				probSum += prob;
			}
			Set<Integer> drawnSequences = new HashSet<Integer>(numSequences);
			Random r = new Random();
			while (drawnSequences.size() < numSequences) {
				double randVal = r.nextDouble() * probSum;
				double sum = 0.0d;
				int index = -1;
				while (sum < randVal) {
					index++;
					double currentProb = probabilities.get(index);
					sum += currentProb;
				}
				if (!drawnSequences.contains(index)) {
					drawnSequences.add(index);
					probSum -= probabilities.get(index);
					probabilities.set(index, 0.0d);
				}
			}
			Collection<List<? extends Event<?>>> retainedSequences = new LinkedList<List<? extends Event<?>>>();
			int index = 0;
			for (List<? extends Event<?>> sequence : sequences) {
				if (drawnSequences.contains(index)) {
					retainedSequences.add(sequence);
				}
				index++;
			}
			sequences = retainedSequences;
		}
		return sequences;
	}

}
