// 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;
/**
*
* Generates a test suite with a hybrid approach that is a mixture of random walks and drawing from
* all possible sequences.
*
*
* @author Steffen Herbold
* @version 1.0
*/
public class HybridGenerator {
/**
*
* Number of sequences in the test suite.
*
*/
private final int numSequences;
/**
*
* Length of a test sequence.
*
*/
private final int length;
/**
*
* Maximal length where it is possible to generate all sequences and draw from them.
*
*/
private final int maxLengthAll;
/**
*
* 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;
/**
*
* Constructor. Creates a new HybridGenerator and ensures the validity of the parameters:
*
* - numSequences must at least be 1
*
- length must be at least 1
*
* If one of these conditions is violated an {@link IllegalArgumentException} is thrown.
*
*
* @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;
}
/**
*
* Generates a test suite with a hybrid approach that is a mixture of random walks and drawing
* from all possible sequences
*
*
* @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>();
List> seqsTmp =
new ArrayList>(model.generateSequences(maxLengthAll + 1, true));
Console.traceln(Level.INFO, "" + seqsTmp.size() + " of length " + maxLengthAll + " possible");
List probabilities = new ArrayList(seqsTmp.size());
double probSum = 0.0;
for (List 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 seqTmp = seqsTmp.get(index);
if (!Event.ENDEVENT.equals(seqTmp.get(seqTmp.size() - 1))) {
List 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;
}
/**
*
* Finishes a sequence with a random walk.
*
*
* @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 finishSequence(List sequence,
IStochasticProcess model,
int length,
boolean validEnd)
{
Random r = new Random();
boolean endFound = false;
List sequenceCopy = new LinkedList(sequence);
final int maxIter = 30000;
int iter = 0;
while (!endFound && iter < maxIter) {
iter++;
sequenceCopy = new LinkedList(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;
}
}