source: trunk/quest-ui-core/src/de/ugoe/cs/quest/commands/CMDgenerateGreedy.java @ 432

package de.ugoe.cs.quest.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.quest.CommandHelpers;
import de.ugoe.cs.quest.coverage.SequenceTools;
import de.ugoe.cs.quest.data.Event;
import de.ugoe.cs.quest.data.GlobalDataContainer;
import de.ugoe.cs.quest.models.IStochasticProcess;
import de.ugoe.cs.util.ArrayTools;
import de.ugoe.cs.util.console.Command;
import de.ugoe.cs.util.console.Console;

/**
 * <p>
 * Command to generate test suite with a greedy strategy to achieve a desired
 * coverage.
 * </p>
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class CMDgenerateGreedy implements Command {

        /**
         * <p>
         * Tolerance for double comparisons
         * </p>
         */
        final static double eps = 0.000000000001;

        /*
         * (non-Javadoc)
         * 
         * @see de.ugoe.cs.util.console.Command#run(java.util.List)
         */
        @Override
        public void run(List<Object> 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<List<? extends Event<?>>> allSequences = new LinkedList<List<? extends Event<?>>>();
                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<List<? extends Event<?>>> allSubSeqs = model
                                .generateSequences(coverageDepth);
                Map<List<? extends Event<?>>, Double> weightMap = SequenceTools
                                .generateWeights(model, allSubSeqs);
                Set<List<? extends Event<?>>> coveredSubSeqs = new LinkedHashSet<List<? extends Event<?>>>();

                List<Set<List<? extends Event<?>>>> containedSubSeqs = new LinkedList<Set<List<? extends Event<?>>>>();
                for (List<? extends Event<?>> sequence : allSequences) {
                        List<List<? extends Event<?>>> wrapper = new LinkedList<List<? extends Event<?>>>();
                        wrapper.add(sequence);
                        Set<List<? extends Event<?>>> currentSubSeqs = SequenceTools
                                        .containedSubSequences(wrapper, coverageDepth);
                        containedSubSeqs.add(currentSubSeqs);
                }

                List<List<? extends Event<?>>> testSuite = new LinkedList<List<? extends Event<?>>>();
                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<List<? extends Event<?>>> containedSubSeq : containedSubSeqs) {
                                double gain = 0.0d;
                                Iterator<List<? extends Event<?>>> subSeqIter = containedSubSeq
                                                .iterator();
                                while (subSeqIter.hasNext()) {
                                        List<? extends Event<?>> 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 <modelname> <sequencesName> <minLength> <maxLength> <coverageDepth> <desiredCoverage> {<validEnd>}");
        }

}