source: trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/autoquest/testgeneration/DrawFromAllSequencesGenerator.java

//   Copyright 2012 Georg-August-Universität Göttingen, Germany
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

package de.ugoe.cs.autoquest.testgeneration;

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 java.util.logging.Level;

import de.ugoe.cs.autoquest.eventcore.Event;
import de.ugoe.cs.autoquest.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:
     * </p>
     * <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>
     * <p>
     * If one of these conditions is violated an {@link IllegalArgumentException} 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 IllegalArgumentException("number of sequences must be at least 1 but is " +
                numSequences);
        }
        if (maxLength < 1) {
            throw new IllegalArgumentException(
                                                "maximal allowed length of test cases must be at least 1 but is " +
                                                    maxLength);
        }
        if (minLength > maxLength) {
            throw new IllegalArgumentException(
                                                "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<Event>> generateTestSuite(IStochasticProcess model) {
        if (model == null) {
            throw new IllegalArgumentException("model must not be null!");
        }

        Collection<List<Event>> sequences = new LinkedHashSet<List<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(Level.INFO, "" + sequences.size() + " possible");
        if (!generateAll && numSequences < sequences.size()) {
            List<Double> probabilities = new ArrayList<Double>(sequences.size());
            double probSum = 0.0;
            for (List<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<Event>> retainedSequences = new LinkedList<List<Event>>();
            int index = 0;
            for (List<Event> sequence : sequences) {
                if (drawnSequences.contains(index)) {
                    retainedSequences.add(sequence);
                }
                index++;
            }
            sequences = retainedSequences;
        }
        return sequences;
    }

}