source: trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/autoquest/testgeneration/HybridGenerator.java @ 2218

//   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.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;
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 with a hybrid approach that is a mixture of random walks and drawing from
 * all possible sequences.
 * </p>
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class HybridGenerator {

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

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

    /**
     * <p>
     * Maximal length where it is possible to generate all sequences and draw from them.
     * </p>
     */
    private final int maxLengthAll;

    /**
     * <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>
     * Constructor. Creates a new HybridGenerator and ensures the validity of the parameters:
     * </p>
     * <ul>
     * <li>numSequences must at least be 1
     * <li>length must be at least 1
     * </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 length
     *            length of a test sequence
     * @param maxLengthAll
     *            maximal length where it is possible to generate all sequences and draw from them
     * @param validEnd
     *            defines if test cases have to end with the global end event {@link Event#ENDEVENT}
     *            (see {@link #validEnd})
     */
    public HybridGenerator(int numSequences, int length, int maxLengthAll, boolean validEnd) {
        // check validity of the parameters
        if (numSequences < 1) {
            throw new IllegalArgumentException("number of sequences must be at least 1 but is " +
                numSequences);
        }
        if (length < 1) {
            throw new IllegalArgumentException("length of test cases must be at least 1 but is " +
                length);
        }
        this.numSequences = numSequences;
        this.length = length;
        this.maxLengthAll = maxLengthAll;
        this.validEnd = validEnd;
    }

    /**
     * <p>
     * Generates a test suite with a hybrid approach that is a mixture of random walks and drawing
     * from all possible sequences
     * </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>>();

        List<List<Event>> seqsTmp =
            new ArrayList<List<Event>>(model.generateSequences(maxLengthAll + 1, true));

        Console.traceln(Level.INFO, "" + seqsTmp.size() + " of length " + maxLengthAll + " possible");
        List<Double> probabilities = new ArrayList<Double>(seqsTmp.size());
        double probSum = 0.0;
        for (List<Event> sequence : seqsTmp) {
            double prob = model.getProbability(sequence);
            probabilities.add(prob);
            probSum += prob;
        }

        Random r = new Random();
        int j = 0;
        while (sequences.size() < numSequences && j <= numSequences * 100) {
            j++;
            double randVal = r.nextDouble() * probSum;
            double sum = 0.0d;
            int index = -1;
            while (sum < randVal) {
                index++;
                double currentProb = probabilities.get(index);
                sum += currentProb;
            }
            List<Event> seqTmp = seqsTmp.get(index);
            if (!Event.ENDEVENT.equals(seqTmp.get(seqTmp.size() - 1))) {
                List<Event> sequence;
                if (validEnd) {
                    sequence = finishSequence(seqTmp, model, length + 2, validEnd);
                    if (sequence != null && sequence.size() != length + 2) {
                        sequence = null;
                    }
                }
                else {
                    sequence = finishSequence(seqTmp, model, length + 1, validEnd);
                    if (sequence != null && sequence.size() != length + 1) {
                        sequence = null;
                    }
                }
                if (sequence != null) {
                    sequences.add(sequence);
                }
            }
        }

        return sequences;
    }

    /**
     * <p>
     * Finishes a sequence with a random walk.
     * </p>
     * 
     * @param sequence
     *            sequence to be finished
     * @param model
     *            model used for the random walk
     * @param length
     *            desired length of the sequence
     * @param validEnd
     *            if the sequence should end in {@link Event#ENDEVENT}.
     * @return finished sequence of the desired length
     */
    private List<Event> finishSequence(List<Event> sequence,
                                       IStochasticProcess model,
                                       int length,
                                       boolean validEnd)
    {
        Random r = new Random();
        boolean endFound = false;
        List<Event> sequenceCopy = new LinkedList<Event>(sequence);
        final int maxIter = 30000;
        int iter = 0;
        while (!endFound && iter < maxIter) {
            iter++;
            sequenceCopy = new LinkedList<Event>(sequence);
            while (!endFound && sequenceCopy.size() <= length) {
                double randVal = r.nextDouble();
                double probSum = 0.0;
                for (Event symbol : model.getEvents()) {
                    probSum += model.getProbability(sequenceCopy, symbol);
                    if (probSum >= randVal) {
                        if (!(Event.STARTEVENT.equals(symbol) || (!validEnd && Event.ENDEVENT
                            .equals(symbol))))
                        {
                            // only add the symbol the sequence if it is not
                            // START
                            // or END
                            sequenceCopy.add(symbol);
                        }
                        endFound =
                            Event.ENDEVENT.equals(symbol) ||
                                (!validEnd && sequenceCopy.size() == length);
                        break;
                    }
                }
            }
        }
        if (iter == maxIter) {
            return null;
        }
        return sequenceCopy;
    }

}