source: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/coverage/CoverageCalculator.java @ 93

package de.ugoe.cs.eventbench.coverage;

import java.util.LinkedHashMap;
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.data.Event;
import de.ugoe.cs.eventbench.models.IStochasticProcess;

public class CoverageCalculator {
        
        private final IStochasticProcess process;
        private final List<List<? extends Event<?>>> sequences;
        private final int length;
        
        private Set<List<? extends Event<?>>> containedSubSeqs = null;
        private Set<List<? extends Event<?>>> allPossibleSubSeqs = null;
        private Map<List<? extends Event<?>>, Double> subSeqWeights = null;
        
        
        public CoverageCalculator(IStochasticProcess process, List<List<? extends Event<?>>> sequences, int length) {
                this.process = process;
                this.sequences = sequences;
                this.length = length;
        }
        

        public double getCoverageAllNoWeight() {
                if( containedSubSeqs==null ) {
                        containedSubSeqs = containedSubSequences(sequences, length);
                }
                return((double) containedSubSeqs.size())/numSequences(process, length);
        }
        
        public double getCoveragePossibleNoWeight() {
                if( containedSubSeqs==null ) {
                        containedSubSeqs = containedSubSequences(sequences, length);
                }
                if( allPossibleSubSeqs==null ) {
                        allPossibleSubSeqs = process.generateSequences(length);
                }
                return((double) containedSubSeqs.size())/allPossibleSubSeqs.size();
        }
        
        public double getCoveragePossibleWeight() {
                if( containedSubSeqs==null ) {
                        containedSubSeqs = containedSubSequences(sequences, length);
                }
                if( allPossibleSubSeqs==null ) {
                        allPossibleSubSeqs = process.generateSequences(length);
                }
                if( subSeqWeights==null ) {
                        subSeqWeights = generateWeights(process, allPossibleSubSeqs);
                }
                double weight = 0.0;
                for( List<? extends Event<?>> subSeq : containedSubSeqs ) {
                        weight += subSeqWeights.get(subSeq);
                }
                return weight;
        }
        
        private Map<List<? extends Event<?>>, Double> generateWeights(IStochasticProcess process, Set<List<? extends Event<?>>> sequences) {
                Map<List<? extends Event<?>>, Double> subSeqWeights = new LinkedHashMap<List<? extends Event<?>>, Double>();
                double sum = 0.0;
                for( List<? extends Event<?>> sequence : sequences ) {
                        double prob = 1.0;
                        List<Event<?>> context = new LinkedList<Event<?>>();
                        for( Event<?> event : sequence ) {
                                prob *= process.getProbability(context, event);
                                context.add(event);
                        }
                        subSeqWeights.put(sequence, prob);
                        sum += prob;
                }
                if( sum<1.0 ) {
                        for( Map.Entry<List<? extends Event<?>>, Double> entry : subSeqWeights.entrySet() ) {
                                entry.setValue(entry.getValue()/sum);
                        }
                }
                return subSeqWeights;
        }
        
        private long numSequences(IStochasticProcess process, int length) {
                return (long) Math.pow(process.getNumStates(), length);
        }
        
        // O(numSeq*lenSeq)     
        private Set<List<? extends Event<?>>> containedSubSequences(List<List<? extends Event<?>>> sequences, int length) {
                Set<List<? extends Event<?>>> containedSubSeqs = new LinkedHashSet<List<? extends Event<?>>>();
                List<Event<?>> subSeq = new LinkedList<Event<?>>();
                boolean minLengthReached = false;
                for( List<? extends Event<?>> sequence : sequences ) {
                        for( Event<?> event : sequence ) {
                                subSeq.add(event);
                                if( !minLengthReached ) {
                                        if( subSeq.size()==length ) {
                                                minLengthReached=true;
                                        }
                                } else {
                                        subSeq.remove(0);
                                }
                                if( minLengthReached ) {
                                        if( !containedSubSeqs.contains(subSeq) ) {
                                                containedSubSeqs.add(new LinkedList<Event<?>>(subSeq));
                                        }
                                }
                        }
                }
                return containedSubSeqs;
        }
        
}