1 | package de.ugoe.cs.eventbench.coverage;
|
---|
2 |
|
---|
3 | import java.util.LinkedHashMap;
|
---|
4 | import java.util.LinkedHashSet;
|
---|
5 | import java.util.LinkedList;
|
---|
6 | import java.util.List;
|
---|
7 | import java.util.Map;
|
---|
8 | import java.util.Set;
|
---|
9 |
|
---|
10 | import de.ugoe.cs.eventbench.data.Event;
|
---|
11 | import de.ugoe.cs.eventbench.models.IStochasticProcess;
|
---|
12 |
|
---|
13 | public class CoverageCalculator {
|
---|
14 |
|
---|
15 | private final IStochasticProcess process;
|
---|
16 | private final List<List<? extends Event<?>>> sequences;
|
---|
17 | private final int length;
|
---|
18 |
|
---|
19 | private Set<List<? extends Event<?>>> containedSubSeqs = null;
|
---|
20 | private Set<List<? extends Event<?>>> allPossibleSubSeqs = null;
|
---|
21 | private Map<List<? extends Event<?>>, Double> subSeqWeights = null;
|
---|
22 |
|
---|
23 | |
---|
24 | public CoverageCalculator(IStochasticProcess process, List<List<? extends Event<?>>> sequences, int length) {
|
---|
25 | this.process = process;
|
---|
26 | this.sequences = sequences;
|
---|
27 | this.length = length;
|
---|
28 | }
|
---|
29 |
|
---|
30 |
|
---|
31 | public double getCoverageAllNoWeight() {
|
---|
32 | if( containedSubSeqs==null ) {
|
---|
33 | containedSubSeqs = containedSubSequences(sequences, length);
|
---|
34 | }
|
---|
35 | return((double) containedSubSeqs.size())/numSequences(process, length);
|
---|
36 | }
|
---|
37 |
|
---|
38 | public double getCoveragePossibleNoWeight() {
|
---|
39 | if( containedSubSeqs==null ) {
|
---|
40 | containedSubSeqs = containedSubSequences(sequences, length);
|
---|
41 | }
|
---|
42 | if( allPossibleSubSeqs==null ) {
|
---|
43 | allPossibleSubSeqs = process.generateSequences(length);
|
---|
44 | }
|
---|
45 | return((double) containedSubSeqs.size())/allPossibleSubSeqs.size();
|
---|
46 | }
|
---|
47 |
|
---|
48 | public double getCoveragePossibleWeight() {
|
---|
49 | if( containedSubSeqs==null ) {
|
---|
50 | containedSubSeqs = containedSubSequences(sequences, length);
|
---|
51 | }
|
---|
52 | if( allPossibleSubSeqs==null ) {
|
---|
53 | allPossibleSubSeqs = process.generateSequences(length);
|
---|
54 | }
|
---|
55 | if( subSeqWeights==null ) {
|
---|
56 | subSeqWeights = generateWeights(process, allPossibleSubSeqs);
|
---|
57 | }
|
---|
58 | double weight = 0.0;
|
---|
59 | for( List<? extends Event<?>> subSeq : containedSubSeqs ) {
|
---|
60 | weight += subSeqWeights.get(subSeq);
|
---|
61 | }
|
---|
62 | return weight;
|
---|
63 | }
|
---|
64 |
|
---|
65 | private Map<List<? extends Event<?>>, Double> generateWeights(IStochasticProcess process, Set<List<? extends Event<?>>> sequences) {
|
---|
66 | Map<List<? extends Event<?>>, Double> subSeqWeights = new LinkedHashMap<List<? extends Event<?>>, Double>();
|
---|
67 | double sum = 0.0;
|
---|
68 | for( List<? extends Event<?>> sequence : sequences ) {
|
---|
69 | double prob = 1.0;
|
---|
70 | List<Event<?>> context = new LinkedList<Event<?>>();
|
---|
71 | for( Event<?> event : sequence ) {
|
---|
72 | prob *= process.getProbability(context, event);
|
---|
73 | context.add(event);
|
---|
74 | }
|
---|
75 | subSeqWeights.put(sequence, prob);
|
---|
76 | sum += prob;
|
---|
77 | }
|
---|
78 | if( sum<1.0 ) {
|
---|
79 | for( Map.Entry<List<? extends Event<?>>, Double> entry : subSeqWeights.entrySet() ) {
|
---|
80 | entry.setValue(entry.getValue()/sum);
|
---|
81 | }
|
---|
82 | }
|
---|
83 | return subSeqWeights;
|
---|
84 | }
|
---|
85 |
|
---|
86 | private long numSequences(IStochasticProcess process, int length) {
|
---|
87 | return (long) Math.pow(process.getNumStates(), length);
|
---|
88 | }
|
---|
89 |
|
---|
90 | // O(numSeq*lenSeq)
|
---|
91 | private Set<List<? extends Event<?>>> containedSubSequences(List<List<? extends Event<?>>> sequences, int length) {
|
---|
92 | Set<List<? extends Event<?>>> containedSubSeqs = new LinkedHashSet<List<? extends Event<?>>>();
|
---|
93 | List<Event<?>> subSeq = new LinkedList<Event<?>>();
|
---|
94 | boolean minLengthReached = false;
|
---|
95 | for( List<? extends Event<?>> sequence : sequences ) {
|
---|
96 | for( Event<?> event : sequence ) {
|
---|
97 | subSeq.add(event);
|
---|
98 | if( !minLengthReached ) {
|
---|
99 | if( subSeq.size()==length ) {
|
---|
100 | minLengthReached=true;
|
---|
101 | }
|
---|
102 | } else {
|
---|
103 | subSeq.remove(0);
|
---|
104 | }
|
---|
105 | if( minLengthReached ) {
|
---|
106 | if( !containedSubSeqs.contains(subSeq) ) {
|
---|
107 | containedSubSeqs.add(new LinkedList<Event<?>>(subSeq));
|
---|
108 | }
|
---|
109 | }
|
---|
110 | }
|
---|
111 | }
|
---|
112 | return containedSubSeqs;
|
---|
113 | }
|
---|
114 |
|
---|
115 | }
|
---|