[434] | 1 | package de.ugoe.cs.quest.ui.commands;
|
---|
[288] | 2 |
|
---|
| 3 | import java.security.InvalidParameterException;
|
---|
[395] | 4 | import java.util.Collection;
|
---|
| 5 | import java.util.Iterator;
|
---|
[288] | 6 | import java.util.LinkedHashSet;
|
---|
[293] | 7 | import java.util.LinkedList;
|
---|
[288] | 8 | import java.util.List;
|
---|
[293] | 9 | import java.util.Map;
|
---|
| 10 | import java.util.Set;
|
---|
[639] | 11 | import java.util.logging.Level;
|
---|
[288] | 12 |
|
---|
[432] | 13 | import de.ugoe.cs.quest.CommandHelpers;
|
---|
| 14 | import de.ugoe.cs.quest.coverage.SequenceTools;
|
---|
[433] | 15 | import de.ugoe.cs.quest.eventcore.Event;
|
---|
[434] | 16 | import de.ugoe.cs.quest.ui.GlobalDataContainer;
|
---|
[433] | 17 | import de.ugoe.cs.quest.usageprofiles.IStochasticProcess;
|
---|
[293] | 18 | import de.ugoe.cs.util.ArrayTools;
|
---|
[288] | 19 | import de.ugoe.cs.util.console.Command;
|
---|
| 20 | import de.ugoe.cs.util.console.Console;
|
---|
| 21 |
|
---|
| 22 | /**
|
---|
| 23 | * <p>
|
---|
[294] | 24 | * Command to generate test suite with a greedy strategy to achieve a desired
|
---|
| 25 | * coverage.
|
---|
[288] | 26 | * </p>
|
---|
[294] | 27 | *
|
---|
[288] | 28 | * @author Steffen Herbold
|
---|
| 29 | * @version 1.0
|
---|
| 30 | */
|
---|
| 31 | public class CMDgenerateGreedy implements Command {
|
---|
[294] | 32 |
|
---|
| 33 | /**
|
---|
| 34 | * <p>
|
---|
| 35 | * Tolerance for double comparisons
|
---|
| 36 | * </p>
|
---|
| 37 | */
|
---|
[311] | 38 | final static double eps = 0.000000000001;
|
---|
[288] | 39 |
|
---|
[294] | 40 | /*
|
---|
| 41 | * (non-Javadoc)
|
---|
| 42 | *
|
---|
| 43 | * @see de.ugoe.cs.util.console.Command#run(java.util.List)
|
---|
| 44 | */
|
---|
[288] | 45 | @Override
|
---|
| 46 | public void run(List<Object> parameters) {
|
---|
| 47 | String modelname;
|
---|
| 48 | String sequencesName;
|
---|
| 49 | int minLength;
|
---|
| 50 | int maxLength;
|
---|
[293] | 51 | int coverageDepth;
|
---|
[288] | 52 | float desiredCoverage;
|
---|
[395] | 53 | boolean validEnd = true;
|
---|
[288] | 54 | try {
|
---|
| 55 | modelname = (String) parameters.get(0);
|
---|
| 56 | sequencesName = (String) parameters.get(1);
|
---|
| 57 | minLength = Integer.parseInt((String) parameters.get(2));
|
---|
| 58 | maxLength = Integer.parseInt((String) parameters.get(3));
|
---|
[293] | 59 | coverageDepth = Integer.parseInt((String) parameters.get(4));
|
---|
| 60 | desiredCoverage = Float.parseFloat((String) parameters.get(5));
|
---|
[395] | 61 | if (parameters.size() >= 7) {
|
---|
| 62 | validEnd = Boolean.parseBoolean((String) parameters.get(6));
|
---|
| 63 | }
|
---|
[288] | 64 | } catch (Exception e) {
|
---|
| 65 | throw new InvalidParameterException();
|
---|
| 66 | }
|
---|
| 67 |
|
---|
| 68 | IStochasticProcess model = null;
|
---|
| 69 | Object dataObject = GlobalDataContainer.getInstance()
|
---|
| 70 | .getData(modelname);
|
---|
| 71 | if (dataObject == null) {
|
---|
| 72 | CommandHelpers.objectNotFoundMessage(modelname);
|
---|
| 73 | return;
|
---|
| 74 | } else if (!(dataObject instanceof IStochasticProcess)) {
|
---|
| 75 | CommandHelpers.objectNotType(modelname, "IStochasticProcess");
|
---|
| 76 | return;
|
---|
| 77 | }
|
---|
| 78 | model = (IStochasticProcess) dataObject;
|
---|
[294] | 79 |
|
---|
[293] | 80 | // set up everything
|
---|
[547] | 81 | List<List<Event>> allSequences = new LinkedList<List<Event>>();
|
---|
[288] | 82 | for (int length = minLength; length <= maxLength; length++) {
|
---|
[395] | 83 | if (validEnd) {
|
---|
| 84 | allSequences.addAll(model.generateValidSequences(length + 2));
|
---|
| 85 | } else {
|
---|
| 86 | allSequences.addAll(model.generateSequences(length + 1, true));
|
---|
| 87 | }
|
---|
[288] | 88 | }
|
---|
[639] | 89 | Console.traceln(Level.INFO, "" + allSequences.size() + " possible");
|
---|
[294] | 90 |
|
---|
[547] | 91 | Collection<List<Event>> allSubSeqs = model
|
---|
[395] | 92 | .generateSequences(coverageDepth);
|
---|
[547] | 93 | Map<List<Event>, Double> weightMap = SequenceTools
|
---|
[294] | 94 | .generateWeights(model, allSubSeqs);
|
---|
[547] | 95 | Set<List<Event>> coveredSubSeqs = new LinkedHashSet<List<Event>>();
|
---|
[294] | 96 |
|
---|
[547] | 97 | List<Set<List<Event>>> containedSubSeqs = new LinkedList<Set<List<Event>>>();
|
---|
| 98 | for (List<Event> sequence : allSequences) {
|
---|
| 99 | List<List<Event>> wrapper = new LinkedList<List<Event>>();
|
---|
[293] | 100 | wrapper.add(sequence);
|
---|
[547] | 101 | Set<List<Event>> currentSubSeqs = SequenceTools
|
---|
[294] | 102 | .containedSubSequences(wrapper, coverageDepth);
|
---|
[293] | 103 | containedSubSeqs.add(currentSubSeqs);
|
---|
| 104 | }
|
---|
[294] | 105 |
|
---|
[547] | 106 | List<List<Event>> testSuite = new LinkedList<List<Event>>();
|
---|
[293] | 107 | double currentCoverage = 0.0d;
|
---|
[294] | 108 |
|
---|
[293] | 109 | // Build test suite
|
---|
[395] | 110 | double prevGain = 1.0d;
|
---|
| 111 | boolean gainEqual = false;
|
---|
[294] | 112 | while (currentCoverage < desiredCoverage) {
|
---|
[395] | 113 | Double[] sequenceGain = new Double[allSequences.size()];
|
---|
| 114 | int i = 0;
|
---|
[547] | 115 | for (Set<List<Event>> containedSubSeq : containedSubSeqs) {
|
---|
[293] | 116 | double gain = 0.0d;
|
---|
[547] | 117 | Iterator<List<Event>> subSeqIter = containedSubSeq
|
---|
[395] | 118 | .iterator();
|
---|
| 119 | while (subSeqIter.hasNext()) {
|
---|
[547] | 120 | List<Event> subSeq = subSeqIter.next();
|
---|
[294] | 121 | if (!coveredSubSeqs.contains(subSeq)) {
|
---|
[293] | 122 | gain += weightMap.get(subSeq);
|
---|
[395] | 123 | } else {
|
---|
| 124 | subSeqIter.remove();
|
---|
[293] | 125 | }
|
---|
| 126 | }
|
---|
| 127 | sequenceGain[i] = gain;
|
---|
[395] | 128 | // optimization using that the gain is monotonically decreasing
|
---|
| 129 | if (Math.abs(gain - prevGain) <= eps) {
|
---|
| 130 | gainEqual = true;
|
---|
| 131 | break;
|
---|
| 132 | }
|
---|
| 133 | i++;
|
---|
[293] | 134 | }
|
---|
[395] | 135 | int maxIndex;
|
---|
| 136 | if (gainEqual) {
|
---|
| 137 | maxIndex = i;
|
---|
| 138 | } else {
|
---|
| 139 | maxIndex = ArrayTools.findMax(sequenceGain);
|
---|
| 140 | }
|
---|
| 141 | if (maxIndex < 0 || sequenceGain[maxIndex] <= 0.0 + eps) {
|
---|
[639] | 142 | Console.traceln(Level.WARNING, "No gain anymore! Desired coverage cannot be satisfied!");
|
---|
[293] | 143 | break;
|
---|
| 144 | }
|
---|
[395] | 145 | prevGain = sequenceGain[maxIndex];
|
---|
[293] | 146 | testSuite.add(allSequences.get(maxIndex));
|
---|
| 147 | coveredSubSeqs.addAll(containedSubSeqs.get(maxIndex));
|
---|
[395] | 148 | currentCoverage += sequenceGain[maxIndex];
|
---|
| 149 | if (gainEqual) {
|
---|
| 150 | allSequences.remove(maxIndex);
|
---|
| 151 | containedSubSeqs.remove(maxIndex);
|
---|
| 152 | gainEqual = false;
|
---|
| 153 | } else {
|
---|
| 154 | for (int j = sequenceGain.length - 1; j >= 0; j--) {
|
---|
| 155 | if (j == maxIndex || sequenceGain[j] <= 0.0 + eps) {
|
---|
| 156 | allSequences.remove(j);
|
---|
| 157 | containedSubSeqs.remove(j);
|
---|
| 158 | }
|
---|
| 159 | }
|
---|
| 160 | }
|
---|
[293] | 161 | }
|
---|
[294] | 162 |
|
---|
[293] | 163 | if (GlobalDataContainer.getInstance().addData(sequencesName, testSuite)) {
|
---|
[288] | 164 | CommandHelpers.dataOverwritten(sequencesName);
|
---|
| 165 | }
|
---|
[293] | 166 | Console.println("" + testSuite.size() + " sequences generated");
|
---|
| 167 | Console.println("" + currentCoverage + " coverage achieved");
|
---|
[288] | 168 | }
|
---|
| 169 |
|
---|
[294] | 170 | /*
|
---|
| 171 | * (non-Javadoc)
|
---|
| 172 | *
|
---|
| 173 | * @see de.ugoe.cs.util.console.Command#help()
|
---|
| 174 | */
|
---|
[288] | 175 | @Override
|
---|
| 176 | public void help() {
|
---|
[395] | 177 | Console.println("generateGreedy <modelname> <sequencesName> <minLength> <maxLength> <coverageDepth> <desiredCoverage> {<validEnd>}");
|
---|
[288] | 178 | }
|
---|
| 179 |
|
---|
| 180 | }
|
---|