// 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;
/**
*
* 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}.
*
*
* @author Steffen Herbold
* @version 1.0
*/
public class DrawFromAllSequencesGenerator {
/**
*
* Number of sequences in the test suite.
*
*/
private final int numSequences;
/**
*
* Minimal length of a test sequence.
*
*/
private final int minLength;
/**
*
* Maximal length of a test sequence.
*
*/
private final int maxLength;
/**
*
* 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.
*
*/
private final boolean validEnd;
/**
*
* If this member is true, the generated test suite contains all possible sequences and
* {@link #numSequences} is ignored.
*
*/
private final boolean generateAll;
/**
*
* Constructor. Creates a new DrawFromAllSequencesGenerator and ensures the validity of the
* parameters:
*
* - numSequences must at least be 1
*
- maxLength must at least be 1
*
- minLength must be less than or equal to maxLength
*
* If one of these conditions is violated an {@link IllegalArgumentException} is thrown.
*
*
* @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;
}
/**
*
* Generates a test suite by drawing from all possible sequences with valid lengths.
*
*
* @param model
* model used to determine the probability of each possible sequence
* @return the test suite
*/
public Collection> generateTestSuite(IStochasticProcess model) {
if (model == null) {
throw new IllegalArgumentException("model must not be null!");
}
Collection> sequences = new LinkedHashSet>();
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 probabilities = new ArrayList(sequences.size());
double probSum = 0.0;
for (List sequence : sequences) {
double prob = model.getProbability(sequence);
probabilities.add(prob);
probSum += prob;
}
Set drawnSequences = new HashSet(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> retainedSequences = new LinkedList>();
int index = 0;
for (List sequence : sequences) {
if (drawnSequences.contains(index)) {
retainedSequences.add(sequence);
}
index++;
}
sequences = retainedSequences;
}
return sequences;
}
}