Index: /trunk/autoquest-core-testgeneration/.classpath
===================================================================
--- /trunk/autoquest-core-testgeneration/.classpath (revision 895)
+++ /trunk/autoquest-core-testgeneration/.classpath (revision 895)
@@ -0,0 +1,26 @@
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
Index: /trunk/autoquest-core-testgeneration/.project
===================================================================
--- /trunk/autoquest-core-testgeneration/.project (revision 895)
+++ /trunk/autoquest-core-testgeneration/.project (revision 895)
@@ -0,0 +1,23 @@
+
+
+ quest-core-testgeneration
+
+
+
+
+
+ org.eclipse.jdt.core.javabuilder
+
+
+
+
+ org.eclipse.m2e.core.maven2Builder
+
+
+
+
+
+ org.eclipse.m2e.core.maven2Nature
+ org.eclipse.jdt.core.javanature
+
+
Index: /trunk/autoquest-core-testgeneration/.settings/org.eclipse.jdt.core.prefs
===================================================================
--- /trunk/autoquest-core-testgeneration/.settings/org.eclipse.jdt.core.prefs (revision 895)
+++ /trunk/autoquest-core-testgeneration/.settings/org.eclipse.jdt.core.prefs (revision 895)
@@ -0,0 +1,5 @@
+eclipse.preferences.version=1
+org.eclipse.jdt.core.compiler.codegen.targetPlatform=1.6
+org.eclipse.jdt.core.compiler.compliance=1.6
+org.eclipse.jdt.core.compiler.problem.forbiddenReference=warning
+org.eclipse.jdt.core.compiler.source=1.6
Index: /trunk/autoquest-core-testgeneration/.settings/org.eclipse.m2e.core.prefs
===================================================================
--- /trunk/autoquest-core-testgeneration/.settings/org.eclipse.m2e.core.prefs (revision 895)
+++ /trunk/autoquest-core-testgeneration/.settings/org.eclipse.m2e.core.prefs (revision 895)
@@ -0,0 +1,4 @@
+activeProfiles=
+eclipse.preferences.version=1
+resolveWorkspaceProjects=true
+version=1
Index: /trunk/autoquest-core-testgeneration/pom.xml
===================================================================
--- /trunk/autoquest-core-testgeneration/pom.xml (revision 895)
+++ /trunk/autoquest-core-testgeneration/pom.xml (revision 895)
@@ -0,0 +1,30 @@
+
+
+ de.ugoe.cs.quest
+ quest
+ 0.0.1-SNAPSHOT
+
+ 4.0.0
+ quest-core-testgeneration
+ quest-core-testgeneration
+
+ ${quest-scm-trunk-dir}/quest-core-testgeneration
+
+
+
+ de.ugoe.cs.quest
+ quest-core-events
+ ${project.parent.version}
+
+
+ de.ugoe.cs.quest
+ quest-core-usageprofiles
+ ${project.parent.version}
+
+
+ de.ugoe.cs.quest
+ quest-core-coverage
+ ${project.parent.version}
+
+
+
Index: /trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/DrawFromAllSequencesGenerator.java
===================================================================
--- /trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/DrawFromAllSequencesGenerator.java (revision 895)
+++ /trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/DrawFromAllSequencesGenerator.java (revision 895)
@@ -0,0 +1,180 @@
+package de.ugoe.cs.quest.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.quest.eventcore.Event;
+import de.ugoe.cs.quest.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;
+ }
+
+}
Index: /trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/HybridGenerator.java
===================================================================
--- /trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/HybridGenerator.java (revision 895)
+++ /trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/HybridGenerator.java (revision 895)
@@ -0,0 +1,212 @@
+package de.ugoe.cs.quest.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.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.
+ *
+ *
+ * @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;
+ }
+
+}
Index: /trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/RandomWalkGenerator.java
===================================================================
--- /trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/RandomWalkGenerator.java (revision 895)
+++ /trunk/autoquest-core-testgeneration/src/main/java/de/ugoe/cs/quest/testgeneration/RandomWalkGenerator.java (revision 895)
@@ -0,0 +1,172 @@
+package de.ugoe.cs.quest.testgeneration;
+
+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}.
+ *
+ *
+ * @author Steffen Herbold
+ * @version 1.0
+ */
+public class RandomWalkGenerator {
+
+ /**
+ *
+ * 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;
+
+ /**
+ *
+ * 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 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 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 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 + ")");
+ }
+ if (maxIter < numSequences) {
+ throw new IllegalArgumentException(
+ "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
+ */
+ public Collection> generateTestSuite(IStochasticProcess model) {
+ if (model == null) {
+ throw new IllegalArgumentException("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;
+ }
+}