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

package de.ugoe.cs.eventbench.coverage;

import java.security.InvalidParameterException;
import java.util.ArrayList;
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<Event<?>>> sequences;
        private final int length;
        
        private Set<List<Event<?>>> containedSubSeqs = null;
        private Set<List<Event<?>>> allPossibleSubSeqs = null;
        private Map<List<Event<?>>, Double> subSeqWeights = null;
        
        
        public CoverageCalculator(IStochasticProcess process, List<List<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 = generateSubSequences(process, length);
                }
                return((double) containedSubSeqs.size())/allPossibleSubSeqs.size();
        }
        
        public double getCoveragePossibleWeight() {
                if( containedSubSeqs==null ) {
                        containedSubSeqs = containedSubSequences(sequences, length);
                }
                if( allPossibleSubSeqs==null ) {
                        allPossibleSubSeqs = generateSubSequences(process, length);
                }
                if( subSeqWeights==null ) {
                        subSeqWeights = generateWeights(process, allPossibleSubSeqs);
                }
                double weight = 0.0;
                for( List<Event<?>> subSeq : containedSubSeqs ) {
                        weight += subSeqWeights.get(subSeq);
                }
                return weight;
        }
        
        private Map<List<Event<?>>, Double> generateWeights(IStochasticProcess process, Set<List<Event<?>>> sequences) {
                Map<List<Event<?>>, Double> subSeqWeights = new LinkedHashMap<List<Event<?>>, Double>();
                double sum = 0.0;
                for( List<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<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(symbols^length)    
        private Set<List<Event<?>>> generateSubSequences(IStochasticProcess process, int length) {
                Set<List<Event<?>>> subSequenceSet = new LinkedHashSet<List<Event<?>>>();;
                if( length<1 ) {
                        throw new InvalidParameterException("Length of generated subsequences must be at least 1.");
                }
                if( length==1 ) {
                        for( Event<?> event : process.getEvents() ) {
                                List<Event<?>> subSeq = new LinkedList<Event<?>>();
                                subSeq.add(event);
                                subSequenceSet.add(subSeq);
                        }
                        return subSequenceSet;
                }
                Set<Event<?>> events = process.getEvents();
                Set<List<Event<?>>> subSeqsShorter = generateSubSequences(process, length-1);
                for( Event<?> event : events ) {
                        for( List<Event<?>> subSequence : subSeqsShorter ) {
                                Event<?> lastEvent = event;
                                if( process.getProbability(subSequence, lastEvent)>0.0 ) {
                                        List<Event<?>> subSeq = new ArrayList<Event<?>>(subSequence);
                                        subSeq.add(lastEvent);
                                        subSequenceSet.add(subSeq);
                                }
                        }
                }
                return subSequenceSet;
        }

        // O(numSeq*lenSeq)     
        private Set<List<Event<?>>> containedSubSequences(List<List<Event<?>>> sequences, int length) {
                Set<List<Event<?>>> containedSubSeqs = new LinkedHashSet<List<Event<?>>>();
                List<Event<?>> subSeq = new LinkedList<Event<?>>();
                boolean minLengthReached = false;
                for( List<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;
        }
        
}