package de.ugoe.cs.eventbench.commands; import java.security.InvalidParameterException; import java.util.Collection; import java.util.Iterator; import java.util.LinkedHashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Set; import de.ugoe.cs.eventbench.CommandHelpers; import de.ugoe.cs.eventbench.coverage.SequenceTools; import de.ugoe.cs.eventbench.data.Event; import de.ugoe.cs.eventbench.data.GlobalDataContainer; import de.ugoe.cs.eventbench.models.IStochasticProcess; import de.ugoe.cs.util.ArrayTools; import de.ugoe.cs.util.console.Command; import de.ugoe.cs.util.console.Console; /** *

* Command to generate test suite with a greedy strategy to achieve a desired * coverage. *

* * @author Steffen Herbold * @version 1.0 */ public class CMDgenerateGreedy implements Command { /** *

* Tolerance for double comparisons *

*/ final static double eps = 0.000000000001; /* * (non-Javadoc) * * @see de.ugoe.cs.util.console.Command#run(java.util.List) */ @Override public void run(List parameters) { String modelname; String sequencesName; int minLength; int maxLength; int coverageDepth; float desiredCoverage; boolean validEnd = true; try { modelname = (String) parameters.get(0); sequencesName = (String) parameters.get(1); minLength = Integer.parseInt((String) parameters.get(2)); maxLength = Integer.parseInt((String) parameters.get(3)); coverageDepth = Integer.parseInt((String) parameters.get(4)); desiredCoverage = Float.parseFloat((String) parameters.get(5)); if (parameters.size() >= 7) { validEnd = Boolean.parseBoolean((String) parameters.get(6)); } } catch (Exception e) { throw new InvalidParameterException(); } IStochasticProcess model = null; Object dataObject = GlobalDataContainer.getInstance() .getData(modelname); if (dataObject == null) { CommandHelpers.objectNotFoundMessage(modelname); return; } else if (!(dataObject instanceof IStochasticProcess)) { CommandHelpers.objectNotType(modelname, "IStochasticProcess"); return; } model = (IStochasticProcess) dataObject; // set up everything List>> allSequences = new LinkedList>>(); for (int length = minLength; length <= maxLength; length++) { if (validEnd) { allSequences.addAll(model.generateValidSequences(length + 2)); } else { allSequences.addAll(model.generateSequences(length + 1, true)); } } Console.traceln("" + allSequences.size() + " possible"); Collection>> allSubSeqs = model .generateSequences(coverageDepth); Map>, Double> weightMap = SequenceTools .generateWeights(model, allSubSeqs); Set>> coveredSubSeqs = new LinkedHashSet>>(); List>>> containedSubSeqs = new LinkedList>>>(); for (List> sequence : allSequences) { List>> wrapper = new LinkedList>>(); wrapper.add(sequence); Set>> currentSubSeqs = SequenceTools .containedSubSequences(wrapper, coverageDepth); containedSubSeqs.add(currentSubSeqs); } List>> testSuite = new LinkedList>>(); double currentCoverage = 0.0d; // Build test suite double prevGain = 1.0d; boolean gainEqual = false; while (currentCoverage < desiredCoverage) { Double[] sequenceGain = new Double[allSequences.size()]; int i = 0; for (Set>> containedSubSeq : containedSubSeqs) { double gain = 0.0d; Iterator>> subSeqIter = containedSubSeq .iterator(); while (subSeqIter.hasNext()) { List> subSeq = subSeqIter.next(); if (!coveredSubSeqs.contains(subSeq)) { gain += weightMap.get(subSeq); } else { subSeqIter.remove(); } } sequenceGain[i] = gain; // optimization using that the gain is monotonically decreasing if (Math.abs(gain - prevGain) <= eps) { gainEqual = true; break; } i++; } int maxIndex; if (gainEqual) { maxIndex = i; } else { maxIndex = ArrayTools.findMax(sequenceGain); } if (maxIndex < 0 || sequenceGain[maxIndex] <= 0.0 + eps) { Console.traceln("No gain anymore! Desired coverage cannot be satisfied!"); break; } prevGain = sequenceGain[maxIndex]; testSuite.add(allSequences.get(maxIndex)); coveredSubSeqs.addAll(containedSubSeqs.get(maxIndex)); currentCoverage += sequenceGain[maxIndex]; if (gainEqual) { allSequences.remove(maxIndex); containedSubSeqs.remove(maxIndex); gainEqual = false; } else { for (int j = sequenceGain.length - 1; j >= 0; j--) { if (j == maxIndex || sequenceGain[j] <= 0.0 + eps) { allSequences.remove(j); containedSubSeqs.remove(j); } } } } if (GlobalDataContainer.getInstance().addData(sequencesName, testSuite)) { CommandHelpers.dataOverwritten(sequencesName); } Console.println("" + testSuite.size() + " sequences generated"); Console.println("" + currentCoverage + " coverage achieved"); } /* * (non-Javadoc) * * @see de.ugoe.cs.util.console.Command#help() */ @Override public void help() { Console.println("generateGreedy {}"); } }