source: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/Trie.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.io.Serializable;
import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;

import de.ugoe.cs.util.StringTools;

import edu.uci.ics.jung.graph.DelegateTree;
import edu.uci.ics.jung.graph.Graph;
import edu.uci.ics.jung.graph.Tree;

/**
 * <p>
 * This class implements a <it>trie</it>, i.e., a tree of sequences that the occurence of
 * subsequences up to a predefined length. This length is the trie order.
 * </p>
 * 
 * @author Steffen Herbold
 * 
 * @param <T>
 *            Type of the symbols that are stored in the trie.
 * 
 * @see TrieNode
 */
public class Trie<T> implements IDotCompatible, Serializable {

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

    /**
     * <p>
     * Collection of all symbols occuring in the trie.
     * </p>
     */
    private Collection<T> knownSymbols;

    /**
     * <p>
     * Reference to the root of the trie.
     * </p>
     */
    private final TrieNode<T> rootNode;

    /**
     * <p>
     * Contructor. Creates a new Trie.
     * </p>
     */
    public Trie() {
        rootNode = new TrieNode<T>();
        knownSymbols = new LinkedHashSet<T>();
    }

    /**
     * <p>
     * Copy-Constructor. Creates a new Trie as the copy of other. The other trie must noch be null.
     * </p>
     * 
     * @param other
     *            Trie that is copied
     */
    public Trie(Trie<T> other) {
        if (other == null) {
            throw new IllegalArgumentException("other trie must not be null");
        }
        rootNode = new TrieNode<T>(other.rootNode);
        knownSymbols = new LinkedHashSet<T>(other.knownSymbols);
    }

    /**
     * <p>
     * Returns a collection of all symbols occuring in the trie.
     * </p>
     * 
     * @return symbols occuring in the trie
     */
    public Collection<T> getKnownSymbols() {
        return new LinkedHashSet<T>(knownSymbols);
    }

    /**
     * <p>
     * Trains the current trie using the given sequence and adds all subsequence of length
     * {@code maxOrder}.
     * </p>
     * 
     * @param sequence
     *            sequence whose subsequences are added to the trie
     * @param maxOrder
     *            maximum length of the subsequences added to the trie
     */
    public void train(List<T> sequence, int maxOrder) {
        if (maxOrder < 1) {
            return;
        }
        IncompleteMemory<T> latestActions = new IncompleteMemory<T>(maxOrder);
        int i = 0;
        for (T currentEvent : sequence) {
            latestActions.add(currentEvent);
            knownSymbols.add(currentEvent);
            i++;
            if (i >= maxOrder) {
                add(latestActions.getLast(maxOrder));
            }
        }
        int sequenceLength = sequence.size();
        for (int j = maxOrder - 1; j > 0; j--) {
            add(sequence.subList(sequenceLength - j, sequenceLength));
        }
    }

    /**
     * <p>
     * Adds a given subsequence to the trie and increases the counters accordingly.
     * </p>
     * 
     * @param subsequence
     *            subsequence whose counters are increased
     * @see TrieNode#add(List)
     */
    protected void add(List<T> subsequence) {
        if (subsequence != null && !subsequence.isEmpty()) {
            knownSymbols.addAll(subsequence);
            subsequence = new LinkedList<T>(subsequence); // defensive copy!
            T firstSymbol = subsequence.get(0);
            TrieNode<T> node = getChildCreate(firstSymbol);
            node.add(subsequence);
        }
    }

    /**
     * <p>
     * Returns the child of the root node associated with the given symbol or creates it if it does
     * not exist yet.
     * </p>
     * 
     * @param symbol
     *            symbol whose node is required
     * @return node associated with the symbol
     * @see TrieNode#getChildCreate(Object)
     */
    protected TrieNode<T> getChildCreate(T symbol) {
        return rootNode.getChildCreate(symbol);
    }

    /**
     * <p>
     * Returns the child of the root node associated with the given symbol or null if it does not
     * exist.
     * </p>
     * 
     * @param symbol
     *            symbol whose node is required
     * @return node associated with the symbol; null if no such node exists
     * @see TrieNode#getChild(Object)
     */
    protected TrieNode<T> getChild(T symbol) {
        return rootNode.getChild(symbol);
    }

    /**
     * <p>
     * Returns the number of occurences of the given sequence.
     * </p>
     * 
     * @param sequence
     *            sequence whose number of occurences is required
     * @return number of occurences of the sequence
     */
    public int getCount(List<T> sequence) {
        int count = 0;
        TrieNode<T> node = find(sequence);
        if (node != null) {
            count = node.getCount();
        }
        return count;
    }

    /**
     * <p>
     * Returns the number of occurences of the given prefix and a symbol that follows it.<br>
     * Convenience function to simplify usage of {@link #getCount(List)}.
     * </p>
     * 
     * @param sequence
     *            prefix of the sequence
     * @param follower
     *            suffix of the sequence
     * @return number of occurences of the sequence
     * @see #getCount(List)
     */
    public int getCount(List<T> sequence, T follower) {
        List<T> tmpSequence = new LinkedList<T>(sequence);
        tmpSequence.add(follower);
        return getCount(tmpSequence);

    }

    /**
     * <p>
     * Searches the trie for a given sequence and returns the node associated with the sequence or
     * null if no such node is found.
     * </p>
     * 
     * @param sequence
     *            sequence that is searched for
     * @return node associated with the sequence
     * @see TrieNode#find(List)
     */
    public TrieNode<T> find(List<T> sequence) {
        if (sequence == null || sequence.isEmpty()) {
            return rootNode;
        }
        List<T> sequenceCopy = new LinkedList<T>(sequence);
        TrieNode<T> result = null;
        TrieNode<T> node = getChild(sequenceCopy.get(0));
        if (node != null) {
            sequenceCopy.remove(0);
            result = node.find(sequenceCopy);
        }
        return result;
    }

    /**
     * <p>
     * Returns a collection of all symbols that follow a given sequence in the trie. In case the
     * sequence is not found or no symbols follow the sequence the result will be empty.
     * </p>
     * 
     * @param sequence
     *            sequence whose followers are returned
     * @return symbols following the given sequence
     * @see TrieNode#getFollowingSymbols()
     */
    public Collection<T> getFollowingSymbols(List<T> sequence) {
        Collection<T> result = new LinkedList<T>();
        TrieNode<T> node = find(sequence);
        if (node != null) {
            result = node.getFollowingSymbols();
        }
        return result;
    }

    /**
     * <p>
     * Returns the longest suffix of the given context that is contained in the tree and whose
     * children are leaves.
     * </p>
     * 
     * @param context
     *            context whose suffix is searched for
     * @return longest suffix of the context
     */
    public List<T> getContextSuffix(List<T> context) {
        List<T> contextSuffix;
        if (context != null) {
            contextSuffix = new LinkedList<T>(context); // defensive copy
        }
        else {
            contextSuffix = new LinkedList<T>();
        }
        boolean suffixFound = false;

        while (!suffixFound) {
            if (contextSuffix.isEmpty()) {
                suffixFound = true; // suffix is the empty word
            }
            else {
                TrieNode<T> node = find(contextSuffix);
                if (node != null) {
                    if (!node.getFollowingSymbols().isEmpty()) {
                        suffixFound = true;
                    }
                }
                if (!suffixFound) {
                    contextSuffix.remove(0);
                }
            }
        }

        return contextSuffix;
    }

    /**
     * <p>
     * Helper class for graph visualization of a trie.
     * </p>
     * 
     * @author Steffen Herbold
     * @version 1.0
     */
    static public class Edge {}

    /**
     * <p>
     * Helper class for graph visualization of a trie.
     * </p>
     * 
     * @author Steffen Herbold
     * @version 1.0
     */
    static public class TrieVertex {

        /**
         * <p>
         * Id of the vertex.
         * </p>
         */
        private String id;

        /**
         * <p>
         * Contructor. Creates a new TrieVertex.
         * </p>
         * 
         * @param id
         *            id of the vertex
         */
        protected TrieVertex(String id) {
            this.id = id;
        }

        /**
         * <p>
         * Returns the id of the vertex.
         * </p>
         * 
         * @see java.lang.Object#toString()
         */
        @Override
        public String toString() {
            return id;
        }
    }

    /**
     * <p>
     * Returns a {@link Graph} representation of the trie.
     * </p>
     * 
     * @return {@link Graph} representation of the trie
     */
    protected Tree<TrieVertex, Edge> getGraph() {
        DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>();
        rootNode.getGraph(null, graph);
        return graph;
    }

    /*
     * (non-Javadoc)
     * 
     * @see de.ugoe.cs.autoquest.usageprofiles.IDotCompatible#getDotRepresentation()
     */
    public String getDotRepresentation() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("digraph model {" + StringTools.ENDLINE);
        rootNode.appendDotRepresentation(stringBuilder);
        stringBuilder.append('}' + StringTools.ENDLINE);
        return stringBuilder.toString();
    }

    /**
     * <p>
     * Returns the string representation of the root node.
     * </p>
     * 
     * @see TrieNode#toString()
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        return rootNode.toString();
    }

    /**
     * <p>
     * Returns the number of symbols contained in the trie.
     * </p>
     * 
     * @return number of symbols contained in the trie
     */
    public int getNumSymbols() {
        return knownSymbols.size();
    }

    /**
     * <p>
     * Returns the number of trie nodes that are ancestors of a leaf. This is the equivalent to the
     * number of states a first-order markov model would have.
     * <p>
     * 
     * @return number of trie nodes that are ancestors of leafs.
     */
    public int getNumLeafAncestors() {
        List<TrieNode<T>> ancestors = new LinkedList<TrieNode<T>>();
        rootNode.getLeafAncestors(ancestors);
        return ancestors.size();
    }

    /**
     * <p>
     * Returns the number of trie nodes that are leafs.
     * </p>
     * 
     * @return number of leafs in the trie
     */
    public int getNumLeafs() {
        return rootNode.getNumLeafs();
    }

    /**
     * <p>
     * Updates the list of known symbols by replacing it with all symbols that are found in the
     * child nodes of the root node. This should be the same as all symbols that are contained in
     * the trie.
     * </p>
     */
    public void updateKnownSymbols() {
        knownSymbols = new HashSet<T>();
        for (TrieNode<T> node : rootNode.getChildren()) {
            knownSymbols.add(node.getSymbol());
        }
    }

    /**
     * <p>
     * Two Tries are defined as equal, if their {@link #rootNode} are equal.
     * </p>
     * 
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @SuppressWarnings("rawtypes")
    @Override
    public boolean equals(Object other) {
        if (other == this) {
            return true;
        }
        if (other instanceof Trie) {
            return rootNode.equals(((Trie) other).rootNode);
        }
        return false;
    }

    /*
     * (non-Javadoc)
     * 
     * @see java.lang.Object#hashCode()
     */
    @Override
    public int hashCode() {
        int multiplier = 17;
        int hash = 42;
        if (rootNode != null) {
            hash = multiplier * hash + rootNode.hashCode();
        }
        return hash;
    }
}