source: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/ModelFlattener.java

package de.ugoe.cs.eventbench.models;

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

import de.ugoe.cs.eventbench.data.Event;
import de.ugoe.cs.eventbench.data.ReplayableEvent;

/**
 * <p>
 * This class provides functions to create flattened first-order Markov models
 * from {@link HighOrderMarkovModel}s and {@link PredictionByPartialMatch}
 * models through state splitting.
 * </p>
 * <p>
 * If possible, the normal high-order markov model should be used, as the Events
 * may be broken by the flattener, as, e.g., the information
 * {@link ReplayableEvent}s contain is not preserved.
 * </p>
 * 
 * @author Steffen Herbold
 * @version 1.0
 */
public class ModelFlattener {

        private static final String EVENT_SEPARATOR = "-=-";

        Trie<Event<?>> firstOrderTrie;

        /**
         * <p>
         * Takes a {@link HighOrderMarkovModel} and returns a
         * {@link FirstOrderMarkovModel} that conserves the high-order memory
         * through state splitting.
         * </p>
         * 
         * @param model
         *            model that is flattened
         * @return flattened first-order Markov model
         */
        public FirstOrderMarkovModel flattenHighOrderMarkovModel(
                        HighOrderMarkovModel model) {
                int markovOrder = model.trieOrder - 1;
                FirstOrderMarkovModel firstOrderModel = new FirstOrderMarkovModel(
                                new Random());
                firstOrderModel.trieOrder = 2;
                if (markovOrder == 1) {
                        firstOrderModel.trie = new Trie<Event<?>>(model.trie);
                        firstOrderModel.trieOrder = 2;
                } else {
                        firstOrderTrie = new Trie<Event<?>>();
                        TrieNode<Event<?>> rootNode = model.trie.find(null);
                        generateFirstOrderTrie(rootNode, new LinkedList<String>(), markovOrder);
                        firstOrderTrie.updateKnownSymbols();
                        firstOrderModel.trie = firstOrderTrie;
                }

                return firstOrderModel;
        }

        /**
         * <p>
         * <b>This method is not available yet and always return null!</b>
         * </p>
         * <p>
         * Takes a {@link PredictionByPartialMatch} model and returns a
         * {@link FirstOrderMarkovModel} that conserves the high-order memory
         * through state splitting.
         * </p>
         * 
         * @param model
         *            model that is flattened
         * @return flattened first-order Markov model
         */
        public FirstOrderMarkovModel flattenPredictionByPartialMatch(
                        PredictionByPartialMatch model) {
                // TODO implement method
                return null;
        }

        /**
         * <p>
         * Converts all nodes of the given depth into first-order node through
         * state-splitting. For each node at the given depth a new node is created
         * and appropriate transitions will be added.
         * </p>
         * <p>
         * This method traverses through the tree recursively. If the recursion
         * reaches the desired depth in the tree, node are added.
         * </p>
         * 
         * @param currentNode
         *            node whose sub-trie is currently traversed
         * @param parentIDs
         *            ID strings of the ancestors of the currentNode
         * @param depth
         *            depth to go - NOT the current depth.
         */
        private void generateFirstOrderTrie(TrieNode<Event<?>> currentNode,
                        List<String> parentIDs, int depth) {
                for (TrieNode<Event<?>> child : currentNode.getChildren()) {
                        String currentId = child.getSymbol().getStandardId();
                        if (depth > 1) {
                                List<String> childParentIDs = new LinkedList<String>(parentIDs);
                                childParentIDs.add(currentId);
                                generateFirstOrderTrie(child, childParentIDs, depth - 1);

                        } else {
                                StringBuilder firstOrderID = new StringBuilder();
                                for (String parentID : parentIDs) {
                                        firstOrderID.append(parentID + EVENT_SEPARATOR);
                                }
                                firstOrderID.append(currentId);
                                TrieNode<Event<?>> firstOrderNode = firstOrderTrie
                                                .getChildCreate(new Event<Object>(firstOrderID
                                                                .toString()));
                                firstOrderNode.setCount(child.getCount());
                                for (TrieNode<Event<?>> transitionChild : child.getChildren()) {
                                        StringBuilder transitionID = new StringBuilder();
                                        for (String parentID : parentIDs.subList(1,
                                                        parentIDs.size())) {
                                                transitionID.append(parentID + EVENT_SEPARATOR);
                                        }
                                        transitionID.append(currentId + EVENT_SEPARATOR);
                                        transitionID.append(transitionChild.getSymbol()
                                                        .getStandardId());
                                        TrieNode<Event<?>> firstOrderTransitionChild = firstOrderNode
                                                        .getChildCreate(new Event<Object>(transitionID
                                                                        .toString()));
                                        firstOrderTransitionChild.setCount(transitionChild
                                                        .getCount());
                                }
                        }
                }
        }
}