[927] | 1 | // Copyright 2012 Georg-August-Universität Göttingen, Germany
|
---|
| 2 | //
|
---|
| 3 | // Licensed under the Apache License, Version 2.0 (the "License");
|
---|
| 4 | // you may not use this file except in compliance with the License.
|
---|
| 5 | // You may obtain a copy of the License at
|
---|
| 6 | //
|
---|
| 7 | // http://www.apache.org/licenses/LICENSE-2.0
|
---|
| 8 | //
|
---|
| 9 | // Unless required by applicable law or agreed to in writing, software
|
---|
| 10 | // distributed under the License is distributed on an "AS IS" BASIS,
|
---|
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
---|
| 12 | // See the License for the specific language governing permissions and
|
---|
| 13 | // limitations under the License.
|
---|
| 14 |
|
---|
[922] | 15 | package de.ugoe.cs.autoquest.commands.usage;
|
---|
[288] | 16 |
|
---|
[395] | 17 | import java.util.Collection;
|
---|
| 18 | import java.util.Iterator;
|
---|
[288] | 19 | import java.util.LinkedHashSet;
|
---|
[293] | 20 | import java.util.LinkedList;
|
---|
[288] | 21 | import java.util.List;
|
---|
[293] | 22 | import java.util.Map;
|
---|
| 23 | import java.util.Set;
|
---|
[639] | 24 | import java.util.logging.Level;
|
---|
[288] | 25 |
|
---|
[922] | 26 | import de.ugoe.cs.autoquest.CommandHelpers;
|
---|
| 27 | import de.ugoe.cs.autoquest.coverage.SequenceTools;
|
---|
| 28 | import de.ugoe.cs.autoquest.eventcore.Event;
|
---|
| 29 | import de.ugoe.cs.autoquest.usageprofiles.IStochasticProcess;
|
---|
[293] | 30 | import de.ugoe.cs.util.ArrayTools;
|
---|
[288] | 31 | import de.ugoe.cs.util.console.Command;
|
---|
| 32 | import de.ugoe.cs.util.console.Console;
|
---|
[667] | 33 | import de.ugoe.cs.util.console.GlobalDataContainer;
|
---|
[288] | 34 |
|
---|
| 35 | /**
|
---|
| 36 | * <p>
|
---|
[294] | 37 | * Command to generate test suite with a greedy strategy to achieve a desired
|
---|
| 38 | * coverage.
|
---|
[288] | 39 | * </p>
|
---|
[294] | 40 | *
|
---|
[288] | 41 | * @author Steffen Herbold
|
---|
| 42 | * @version 1.0
|
---|
| 43 | */
|
---|
| 44 | public class CMDgenerateGreedy implements Command {
|
---|
[294] | 45 |
|
---|
| 46 | /**
|
---|
| 47 | * <p>
|
---|
| 48 | * Tolerance for double comparisons
|
---|
| 49 | * </p>
|
---|
| 50 | */
|
---|
[311] | 51 | final static double eps = 0.000000000001;
|
---|
[288] | 52 |
|
---|
[294] | 53 | /*
|
---|
| 54 | * (non-Javadoc)
|
---|
| 55 | *
|
---|
| 56 | * @see de.ugoe.cs.util.console.Command#run(java.util.List)
|
---|
| 57 | */
|
---|
[288] | 58 | @Override
|
---|
| 59 | public void run(List<Object> parameters) {
|
---|
| 60 | String modelname;
|
---|
| 61 | String sequencesName;
|
---|
| 62 | int minLength;
|
---|
| 63 | int maxLength;
|
---|
[293] | 64 | int coverageDepth;
|
---|
[288] | 65 | float desiredCoverage;
|
---|
[395] | 66 | boolean validEnd = true;
|
---|
[288] | 67 | try {
|
---|
| 68 | modelname = (String) parameters.get(0);
|
---|
| 69 | sequencesName = (String) parameters.get(1);
|
---|
| 70 | minLength = Integer.parseInt((String) parameters.get(2));
|
---|
| 71 | maxLength = Integer.parseInt((String) parameters.get(3));
|
---|
[293] | 72 | coverageDepth = Integer.parseInt((String) parameters.get(4));
|
---|
| 73 | desiredCoverage = Float.parseFloat((String) parameters.get(5));
|
---|
[395] | 74 | if (parameters.size() >= 7) {
|
---|
| 75 | validEnd = Boolean.parseBoolean((String) parameters.get(6));
|
---|
| 76 | }
|
---|
[288] | 77 | } catch (Exception e) {
|
---|
[766] | 78 | throw new IllegalArgumentException();
|
---|
[288] | 79 | }
|
---|
| 80 |
|
---|
| 81 | IStochasticProcess model = null;
|
---|
| 82 | Object dataObject = GlobalDataContainer.getInstance()
|
---|
| 83 | .getData(modelname);
|
---|
| 84 | if (dataObject == null) {
|
---|
| 85 | CommandHelpers.objectNotFoundMessage(modelname);
|
---|
| 86 | return;
|
---|
| 87 | } else if (!(dataObject instanceof IStochasticProcess)) {
|
---|
| 88 | CommandHelpers.objectNotType(modelname, "IStochasticProcess");
|
---|
| 89 | return;
|
---|
| 90 | }
|
---|
| 91 | model = (IStochasticProcess) dataObject;
|
---|
[294] | 92 |
|
---|
[293] | 93 | // set up everything
|
---|
[547] | 94 | List<List<Event>> allSequences = new LinkedList<List<Event>>();
|
---|
[288] | 95 | for (int length = minLength; length <= maxLength; length++) {
|
---|
[395] | 96 | if (validEnd) {
|
---|
| 97 | allSequences.addAll(model.generateValidSequences(length + 2));
|
---|
| 98 | } else {
|
---|
| 99 | allSequences.addAll(model.generateSequences(length + 1, true));
|
---|
| 100 | }
|
---|
[288] | 101 | }
|
---|
[639] | 102 | Console.traceln(Level.INFO, "" + allSequences.size() + " possible");
|
---|
[294] | 103 |
|
---|
[547] | 104 | Collection<List<Event>> allSubSeqs = model
|
---|
[395] | 105 | .generateSequences(coverageDepth);
|
---|
[547] | 106 | Map<List<Event>, Double> weightMap = SequenceTools
|
---|
[294] | 107 | .generateWeights(model, allSubSeqs);
|
---|
[547] | 108 | Set<List<Event>> coveredSubSeqs = new LinkedHashSet<List<Event>>();
|
---|
[294] | 109 |
|
---|
[547] | 110 | List<Set<List<Event>>> containedSubSeqs = new LinkedList<Set<List<Event>>>();
|
---|
| 111 | for (List<Event> sequence : allSequences) {
|
---|
| 112 | List<List<Event>> wrapper = new LinkedList<List<Event>>();
|
---|
[293] | 113 | wrapper.add(sequence);
|
---|
[547] | 114 | Set<List<Event>> currentSubSeqs = SequenceTools
|
---|
[294] | 115 | .containedSubSequences(wrapper, coverageDepth);
|
---|
[293] | 116 | containedSubSeqs.add(currentSubSeqs);
|
---|
| 117 | }
|
---|
[294] | 118 |
|
---|
[547] | 119 | List<List<Event>> testSuite = new LinkedList<List<Event>>();
|
---|
[293] | 120 | double currentCoverage = 0.0d;
|
---|
[294] | 121 |
|
---|
[293] | 122 | // Build test suite
|
---|
[395] | 123 | double prevGain = 1.0d;
|
---|
| 124 | boolean gainEqual = false;
|
---|
[294] | 125 | while (currentCoverage < desiredCoverage) {
|
---|
[395] | 126 | Double[] sequenceGain = new Double[allSequences.size()];
|
---|
| 127 | int i = 0;
|
---|
[547] | 128 | for (Set<List<Event>> containedSubSeq : containedSubSeqs) {
|
---|
[293] | 129 | double gain = 0.0d;
|
---|
[547] | 130 | Iterator<List<Event>> subSeqIter = containedSubSeq
|
---|
[395] | 131 | .iterator();
|
---|
| 132 | while (subSeqIter.hasNext()) {
|
---|
[547] | 133 | List<Event> subSeq = subSeqIter.next();
|
---|
[294] | 134 | if (!coveredSubSeqs.contains(subSeq)) {
|
---|
[293] | 135 | gain += weightMap.get(subSeq);
|
---|
[395] | 136 | } else {
|
---|
| 137 | subSeqIter.remove();
|
---|
[293] | 138 | }
|
---|
| 139 | }
|
---|
| 140 | sequenceGain[i] = gain;
|
---|
[395] | 141 | // optimization using that the gain is monotonically decreasing
|
---|
| 142 | if (Math.abs(gain - prevGain) <= eps) {
|
---|
| 143 | gainEqual = true;
|
---|
| 144 | break;
|
---|
| 145 | }
|
---|
| 146 | i++;
|
---|
[293] | 147 | }
|
---|
[395] | 148 | int maxIndex;
|
---|
| 149 | if (gainEqual) {
|
---|
| 150 | maxIndex = i;
|
---|
| 151 | } else {
|
---|
| 152 | maxIndex = ArrayTools.findMax(sequenceGain);
|
---|
| 153 | }
|
---|
| 154 | if (maxIndex < 0 || sequenceGain[maxIndex] <= 0.0 + eps) {
|
---|
[639] | 155 | Console.traceln(Level.WARNING, "No gain anymore! Desired coverage cannot be satisfied!");
|
---|
[293] | 156 | break;
|
---|
| 157 | }
|
---|
[395] | 158 | prevGain = sequenceGain[maxIndex];
|
---|
[293] | 159 | testSuite.add(allSequences.get(maxIndex));
|
---|
| 160 | coveredSubSeqs.addAll(containedSubSeqs.get(maxIndex));
|
---|
[395] | 161 | currentCoverage += sequenceGain[maxIndex];
|
---|
| 162 | if (gainEqual) {
|
---|
| 163 | allSequences.remove(maxIndex);
|
---|
| 164 | containedSubSeqs.remove(maxIndex);
|
---|
| 165 | gainEqual = false;
|
---|
| 166 | } else {
|
---|
| 167 | for (int j = sequenceGain.length - 1; j >= 0; j--) {
|
---|
| 168 | if (j == maxIndex || sequenceGain[j] <= 0.0 + eps) {
|
---|
| 169 | allSequences.remove(j);
|
---|
| 170 | containedSubSeqs.remove(j);
|
---|
| 171 | }
|
---|
| 172 | }
|
---|
| 173 | }
|
---|
[293] | 174 | }
|
---|
[294] | 175 |
|
---|
[293] | 176 | if (GlobalDataContainer.getInstance().addData(sequencesName, testSuite)) {
|
---|
[288] | 177 | CommandHelpers.dataOverwritten(sequencesName);
|
---|
| 178 | }
|
---|
[293] | 179 | Console.println("" + testSuite.size() + " sequences generated");
|
---|
| 180 | Console.println("" + currentCoverage + " coverage achieved");
|
---|
[288] | 181 | }
|
---|
| 182 |
|
---|
[294] | 183 | /*
|
---|
| 184 | * (non-Javadoc)
|
---|
| 185 | *
|
---|
| 186 | * @see de.ugoe.cs.util.console.Command#help()
|
---|
| 187 | */
|
---|
[288] | 188 | @Override
|
---|
[664] | 189 | public String help() {
|
---|
| 190 | return "generateGreedy <modelname> <sequencesName> <minLength> <maxLength> <coverageDepth> <desiredCoverage> {<validEnd>}";
|
---|
[288] | 191 | }
|
---|
| 192 |
|
---|
| 193 | }
|
---|