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 |
|
---|
15 | package de.ugoe.cs.autoquest.commands.usage;
|
---|
16 |
|
---|
17 | import java.util.Collection;
|
---|
18 | import java.util.Iterator;
|
---|
19 | import java.util.LinkedHashSet;
|
---|
20 | import java.util.LinkedList;
|
---|
21 | import java.util.List;
|
---|
22 | import java.util.Map;
|
---|
23 | import java.util.Set;
|
---|
24 | import java.util.logging.Level;
|
---|
25 |
|
---|
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;
|
---|
30 | import de.ugoe.cs.util.ArrayTools;
|
---|
31 | import de.ugoe.cs.util.console.Command;
|
---|
32 | import de.ugoe.cs.util.console.Console;
|
---|
33 | import de.ugoe.cs.util.console.GlobalDataContainer;
|
---|
34 |
|
---|
35 | /**
|
---|
36 | * <p>
|
---|
37 | * Command to generate test suite with a greedy strategy to achieve a desired
|
---|
38 | * coverage.
|
---|
39 | * </p>
|
---|
40 | *
|
---|
41 | * @author Steffen Herbold
|
---|
42 | * @version 1.0
|
---|
43 | */
|
---|
44 | public class CMDgenerateGreedy implements Command {
|
---|
45 |
|
---|
46 | /**
|
---|
47 | * <p>
|
---|
48 | * Tolerance for double comparisons
|
---|
49 | * </p>
|
---|
50 | */
|
---|
51 | final static double eps = 0.000000000001;
|
---|
52 |
|
---|
53 | /*
|
---|
54 | * (non-Javadoc)
|
---|
55 | *
|
---|
56 | * @see de.ugoe.cs.util.console.Command#run(java.util.List)
|
---|
57 | */
|
---|
58 | @Override
|
---|
59 | public void run(List<Object> parameters) {
|
---|
60 | String modelname;
|
---|
61 | String sequencesName;
|
---|
62 | int minLength;
|
---|
63 | int maxLength;
|
---|
64 | int coverageDepth;
|
---|
65 | float desiredCoverage;
|
---|
66 | boolean validEnd = true;
|
---|
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));
|
---|
72 | coverageDepth = Integer.parseInt((String) parameters.get(4));
|
---|
73 | desiredCoverage = Float.parseFloat((String) parameters.get(5));
|
---|
74 | if (parameters.size() >= 7) {
|
---|
75 | validEnd = Boolean.parseBoolean((String) parameters.get(6));
|
---|
76 | }
|
---|
77 | } catch (Exception e) {
|
---|
78 | throw new IllegalArgumentException();
|
---|
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;
|
---|
92 |
|
---|
93 | // set up everything
|
---|
94 | List<List<Event>> allSequences = new LinkedList<List<Event>>();
|
---|
95 | for (int length = minLength; length <= maxLength; length++) {
|
---|
96 | if (validEnd) {
|
---|
97 | allSequences.addAll(model.generateValidSequences(length + 2));
|
---|
98 | } else {
|
---|
99 | allSequences.addAll(model.generateSequences(length + 1, true));
|
---|
100 | }
|
---|
101 | }
|
---|
102 | Console.traceln(Level.INFO, "" + allSequences.size() + " possible");
|
---|
103 |
|
---|
104 | Collection<List<Event>> allSubSeqs = model
|
---|
105 | .generateSequences(coverageDepth);
|
---|
106 | Map<List<Event>, Double> weightMap = SequenceTools
|
---|
107 | .generateWeights(model, allSubSeqs);
|
---|
108 | Set<List<Event>> coveredSubSeqs = new LinkedHashSet<List<Event>>();
|
---|
109 |
|
---|
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>>();
|
---|
113 | wrapper.add(sequence);
|
---|
114 | Set<List<Event>> currentSubSeqs = SequenceTools
|
---|
115 | .containedSubSequences(wrapper, coverageDepth);
|
---|
116 | containedSubSeqs.add(currentSubSeqs);
|
---|
117 | }
|
---|
118 |
|
---|
119 | List<List<Event>> testSuite = new LinkedList<List<Event>>();
|
---|
120 | double currentCoverage = 0.0d;
|
---|
121 |
|
---|
122 | // Build test suite
|
---|
123 | double prevGain = 1.0d;
|
---|
124 | boolean gainEqual = false;
|
---|
125 | while (currentCoverage < desiredCoverage) {
|
---|
126 | Double[] sequenceGain = new Double[allSequences.size()];
|
---|
127 | int i = 0;
|
---|
128 | for (Set<List<Event>> containedSubSeq : containedSubSeqs) {
|
---|
129 | double gain = 0.0d;
|
---|
130 | Iterator<List<Event>> subSeqIter = containedSubSeq
|
---|
131 | .iterator();
|
---|
132 | while (subSeqIter.hasNext()) {
|
---|
133 | List<Event> subSeq = subSeqIter.next();
|
---|
134 | if (!coveredSubSeqs.contains(subSeq)) {
|
---|
135 | gain += weightMap.get(subSeq);
|
---|
136 | } else {
|
---|
137 | subSeqIter.remove();
|
---|
138 | }
|
---|
139 | }
|
---|
140 | sequenceGain[i] = gain;
|
---|
141 | // optimization using that the gain is monotonically decreasing
|
---|
142 | if (Math.abs(gain - prevGain) <= eps) {
|
---|
143 | gainEqual = true;
|
---|
144 | break;
|
---|
145 | }
|
---|
146 | i++;
|
---|
147 | }
|
---|
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) {
|
---|
155 | Console.traceln(Level.WARNING, "No gain anymore! Desired coverage cannot be satisfied!");
|
---|
156 | break;
|
---|
157 | }
|
---|
158 | prevGain = sequenceGain[maxIndex];
|
---|
159 | testSuite.add(allSequences.get(maxIndex));
|
---|
160 | coveredSubSeqs.addAll(containedSubSeqs.get(maxIndex));
|
---|
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 | }
|
---|
174 | }
|
---|
175 |
|
---|
176 | if (GlobalDataContainer.getInstance().addData(sequencesName, testSuite)) {
|
---|
177 | CommandHelpers.dataOverwritten(sequencesName);
|
---|
178 | }
|
---|
179 | Console.println("" + testSuite.size() + " sequences generated");
|
---|
180 | Console.println("" + currentCoverage + " coverage achieved");
|
---|
181 | }
|
---|
182 |
|
---|
183 | /*
|
---|
184 | * (non-Javadoc)
|
---|
185 | *
|
---|
186 | * @see de.ugoe.cs.util.console.Command#help()
|
---|
187 | */
|
---|
188 | @Override
|
---|
189 | public String help() {
|
---|
190 | return "generateGreedy <modelname> <sequencesName> <minLength> <maxLength> <coverageDepth> <desiredCoverage> {<validEnd>}";
|
---|
191 | }
|
---|
192 |
|
---|
193 | }
|
---|