source: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/ModelFlattener.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.usageprofiles;

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

import de.ugoe.cs.autoquest.eventcore.Event;
import de.ugoe.cs.autoquest.eventcore.StringEventType;

/**
 * <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().getId();
            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(new StringEventType(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().getId());
                    TrieNode<Event> firstOrderTransitionChild =
                        firstOrderNode.getChildCreate(new Event(new StringEventType(transitionID
                            .toString())));
                    firstOrderTransitionChild.setCount(transitionChild.getCount());
                }
            }
        }
    }
}