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