source: trunk/autoquest-core-coverage/src/main/java/de/ugoe/cs/autoquest/coverage/SequenceTools.java @ 927

//   Copyright 2012 Georg-August-Universität Göttingen, Germany
//
//   Licensed under the Apache License, Version 2.0 (the "License");
//   you may not use this file except in compliance with the License.
//   You may obtain a copy of the License at
//
//       http://www.apache.org/licenses/LICENSE-2.0
//
//   Unless required by applicable law or agreed to in writing, software
//   distributed under the License is distributed on an "AS IS" BASIS,
//   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
//   See the License for the specific language governing permissions and
//   limitations under the License.

package de.ugoe.cs.autoquest.coverage;

import java.util.Collection;
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.autoquest.eventcore.Event;
import de.ugoe.cs.autoquest.usageprofiles.IStochasticProcess;

/**
 * <p>
 * This class gathers some helper functions to work with sequences.
 * </p>
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class SequenceTools {

    /**
     * <p>
     * Private constructor to prevent initializing of the class.
     * </p>
     */
    private SequenceTools() {

    }

    /**
     * <p>
     * Calculates the weights for all sequences passed to this function as defined by the stochastic
     * process and stores them in a {@link Map}. The weights are normalized, i.e., the sum of all
     * weights contained in this map is 1.
     * </p>
     * 
     * @param process
     *            process used for weight calculation
     * @param sequences
     *            sequences for which the weights are calculated
     * @return {@link Map} of weights
     */
    public static Map<List<Event>, Double> generateWeights(IStochasticProcess process,
                                                           Collection<List<Event>> sequences)
    {
        Map<List<Event>, Double> subSeqWeights = new LinkedHashMap<List<Event>, Double>();
        if (sequences != null && !sequences.isEmpty()) {
            if (process != null) {
                double sum = 0.0;
                for (List<Event> sequence : sequences) {
                    double prob = process.getProbability(sequence);
                    subSeqWeights.put(sequence, prob);
                    sum += prob;
                }
                if (sum < 1.0) {
                    for (Map.Entry<List<Event>, Double> entry : subSeqWeights.entrySet()) {
                        entry.setValue(entry.getValue() / sum);
                    }
                }
            }
            else {
                for (List<Event> sequence : sequences) {
                    subSeqWeights.put(sequence, 0.0d);
                }
            }
        }
        return subSeqWeights;
    }

    /**
     * <p>
     * Calculates the number of all existing sequences of a given length, regardless whether they
     * are possible or not.
     * </p>
     * 
     * @param process
     *            stochastic process whose symbols are the basis for this calculation
     * @param length
     *            lenght of the sequences
     * @return numStates^length
     * @throws IllegalArgumentException
     *             thrown if length less or equal to 0
     */
    public static long numSequences(IStochasticProcess process, int length) {
        if (length <= 0) {
            throw new IllegalArgumentException("length must be a positive integer");
        }
        long result = 0;
        if (process != null) {
            result = (long) Math.pow(process.getNumSymbols(), length);
        }
        return result;
    }

    /**
     * <p>
     * Creates a {@link Set} of all subsequences of a given length that are contained in a sequence
     * collection.
     * </p>
     * 
     * @param sequences
     *            sequences from which the subsequences are extracted
     * @param length
     *            length of the subsequences
     * @return {@link Set} of all subsequences
     * @throws IllegalArgumentException
     *             thrown if length less or equal to 0
     */
    public static Set<List<Event>> containedSubSequences(Collection<List<Event>> sequences,
                                                         int length)
    {
        if (length <= 0) {
            throw new IllegalArgumentException("length must be a positive integer");
        }
        Set<List<Event>> containedSubSeqs = new LinkedHashSet<List<Event>>();
        if (sequences != null) {
            for (List<Event> sequence : sequences) {
                List<Event> subSeq = new LinkedList<Event>();
                boolean minLengthReached = false;
                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;
    }
}