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;
	}
	
}
