source: trunk/quest-core-usageprofiles/src/main/java/de/ugoe/cs/quest/usageprofiles/DeterministicFiniteAutomaton.java @ 766

package de.ugoe.cs.quest.usageprofiles;

import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;

import de.ugoe.cs.quest.eventcore.Event;

/**
 * <p>
 * Implements a Deterministic Finite Automata (DFA) capable of random session generation. It is a
 * special case of a first-order Markov model, where the transition probability is equally high for
 * all following states.
 * </p>
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class DeterministicFiniteAutomaton extends FirstOrderMarkovModel {

    /**
     * <p>
     * Id for object serialization.
     * </p>
     */
    private static final long serialVersionUID = 1L;

    /**
     * <p>
     * Constructor. Creates a new DeterministicFiniteAutomaton.
     * </p>
     * 
     * @param r
     *            random number generator used by probabilistic methods of the class
     */
    public DeterministicFiniteAutomaton(Random r) {
        super(r);
    }

    /**
     * <p>
     * Calculates the proability of the next state. Each of the following states in the automaton is
     * equally probable.
     * </p>
     * 
     * @see de.ugoe.cs.quest.usageprofiles.IStochasticProcess#getProbability(java.util.List,
     *      de.ugoe.cs.quest.eventcore.Event)
     */
    @Override
    public double getProbability(List<Event> context, Event symbol) {
        if (context == null) {
            throw new IllegalArgumentException("context must not be null");
        }
        if (symbol == null) {
            throw new IllegalArgumentException("symbol must not be null");
        }
        double result = 0.0d;

        List<Event> contextCopy;
        if (context.size() >= trieOrder) {
            contextCopy =
                new LinkedList<Event>(context.subList(context.size() - trieOrder + 1,
                                                      context.size()));
        }
        else {
            contextCopy = new LinkedList<Event>(context);
        }

        Collection<Event> followers = trie.getFollowingSymbols(contextCopy);

        if (followers.size() != 0 && followers.contains(symbol)) {
            result = 1.0d / followers.size();
        }

        return result;
    }

}