+ * 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}.
+ *
+ */
+ 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.
+ *
+ * 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 InvalidParameterException} 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 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;
+ }
+
+ /**
+ *
+ * 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 InvalidParameterException("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("" + 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;
+ }
+
+}
Index: /trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/HybridGenerator.java
===================================================================
--- /trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/HybridGenerator.java (revision 523)
+++ /trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/HybridGenerator.java (revision 523)
@@ -0,0 +1,219 @@
+package de.ugoe.cs.quest.testgeneration;
+
+import java.security.InvalidParameterException;
+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 de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.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.
+ *
+ */
+ 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.
+ *
+ * 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 InvalidParameterException} 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 InvalidParameterException(
+ "number of sequences must be at least 1 but is "
+ + numSequences);
+ }
+ if (length < 1) {
+ throw new InvalidParameterException(
+ "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 InvalidParameterException("model must not be null!");
+ }
+
+ Collection>> sequences = new LinkedHashSet>>();
+
+ List>> seqsTmp = new ArrayList>>(
+ model.generateSequences(maxLengthAll + 1, true));
+
+ Console.traceln("" + 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;
+ }
+
+}
Index: /trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/RandomWalkGenerator.java
===================================================================
--- /trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/RandomWalkGenerator.java (revision 523)
+++ /trunk/quest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/RandomWalkGenerator.java (revision 523)
@@ -0,0 +1,181 @@
+package de.ugoe.cs.quest.testgeneration;
+
+import java.security.InvalidParameterException;
+import java.util.Collection;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Set;
+
+import de.ugoe.cs.quest.eventcore.Event;
+import de.ugoe.cs.quest.usageprofiles.IStochasticProcess;
+
+/**
+ *
+ * Generates a test suite by randomly walking an {@link IStochasticProcess}.
+ *
+ */
+ 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.
+ *
+ * Maximal number of random walks performed before aborting the test case
+ * generation and returning a test suite with less than
+ * {@link #numSequences} test cases. This can happen if too many generated
+ * random walks have to be discarded because their length is not between
+ * {@link #minLength} and {@link #maxLength}.
+ *
+ */
+ private final long maxIter;
+
+ /**
+ *
+ * Actual number of random walks performed to generate the test suite.
+ *
+ */
+ private long actualIter = -1;
+
+ /**
+ *
+ * Constructor. Creates a new RandomWalkGenerator 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
+ *
maxIter must be greater than or equal to numSequences
+ *
+ * If one of these conditions is violated an
+ * {@link InvalidParameterException} 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 maxIter
+ * maximal number of random walks before aborting the test case
+ * generation (see {@link #maxIter})
+ */
+ public RandomWalkGenerator(int numSequences, int minLength, int maxLength,
+ boolean validEnd, long maxIter) {
+ // 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 + ")");
+ }
+ if (maxIter < numSequences) {
+ throw new InvalidParameterException(
+ "maximal number of iterations must greater than or equal to the number of sequences (number of sequences: "
+ + numSequences
+ + " ; max iterations: "
+ + maxIter
+ + ")");
+ }
+ this.numSequences = numSequences;
+ this.minLength = minLength;
+ this.maxLength = maxLength;
+ this.validEnd = validEnd;
+ this.maxIter = maxIter;
+ }
+
+ /**
+ *
+ * Generates a test suite by repeatedly randomly walking a stochastic
+ * process.
+ *
+ *
+ * @param model
+ * stochastic process which performs the random walks
+ * @return the test suite
+ */
+ @SuppressWarnings("unchecked")
+ public Collection>> generateTestSuite(
+ IStochasticProcess model) {
+ if (model == null) {
+ throw new InvalidParameterException("model must not be null!");
+ }
+
+ Set>> sequences = new HashSet>>(
+ numSequences);
+ actualIter = 0;
+ while (sequences.size() < numSequences && actualIter < maxIter) {
+ List> generatedSequence = model.randomSequence(
+ maxLength, validEnd);
+ if (generatedSequence.size() >= minLength
+ && generatedSequence.size() <= maxLength) {
+ ((List>) generatedSequence).add(0, Event.STARTEVENT);
+ if (validEnd) {
+ ((List>) generatedSequence).add(Event.ENDEVENT);
+ }
+ sequences.add(generatedSequence);
+ }
+ actualIter++;
+ }
+
+ return sequences;
+ }
+
+ /**
+ *
+ * Returns the actual number of random walks performed during the last call
+ * of {@link #generateTestSuite(IStochasticProcess)} or -1 if
+ * {@link #generateTestSuite(IStochasticProcess)} has not been called yet.
+ *
+ *
+ * @return actual number of random walks or -1 if
+ * {@link #generateTestSuite(IStochasticProcess)} has not been
+ * called
+ */
+ public long getActualIter() {
+ return actualIter;
+ }
+}