source: trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/TrieNode.java @ 1282

//   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.LinkedList;
import java.util.List;

import de.ugoe.cs.autoquest.usageprofiles.Trie.Edge;
import de.ugoe.cs.autoquest.usageprofiles.Trie.TrieVertex;
import de.ugoe.cs.util.StringTools;
import edu.uci.ics.jung.graph.DelegateTree;
import edu.uci.ics.jung.graph.Tree;

/**
 * <p>
 * This class implements a node of a trie. Each node is associated with a symbol and has a counter.
 * The counter marks the number of occurrences of the sequence defined by the path from the root of
 * the trie to this node.
 * </p>
 * 
 * @author Steffen Herbold, Patrick Harms
 * 
 * @param <T>
 *            Type of the symbols that are stored in the trie.
 * @see Trie
 */
class TrieNode<T> implements Serializable {

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

    /**
     * <p>
     * Counter for the number of occurrences of the sequence.
     * </p>
     */
    private int count;

    /**
     * <p>
     * Symbol associated with the node.
     * </p>
     */
    private final T symbol;

    /**
     * <p>
     * Child nodes of this node. If the node is a leaf this collection is empty.
     * </p>
     */
    private SymbolMap<T, TrieNode<T>> children;
    
    /**
     * <p>
     * Strategy for handling symbols, i.e., for comparing and storing them
     * </p>
     */
    private SymbolStrategy<T> strategy;

    /**
     * <p>
     * Constructor. Creates a new TrieNode without a symbol associated.<br>
     * <b>This constructor should only be used to create the root node of the trie!</b>
     * The strategy used by the trie node will be a {@link DefaultSymbolStrategy}.
     * </p>
     */
    TrieNode() {
        this(new DefaultSymbolStrategy<T>());
    }

    /**
     * <p>
     * Constructor. Creates a new TrieNode. The symbol must not be null.
     * The strategy used by the trie node will be a {@link DefaultSymbolStrategy}.
     * </p>
     * 
     * @param symbol
     *            symbol associated with the trie node
     * 
     * @throws IllegalArgumentException
     *            if the provided symbol is null
     */
    TrieNode(T symbol) {
        this(symbol, new DefaultSymbolStrategy<T>());
    }

    /**
     * <p>
     * Constructor. Creates a new TrieNode without a symbol associated using the provided
     * strategy.<br>
     * <b>This constructor should only be used to create the root node of the trie!</b>
     * <br>The strategy must not be null.
     * </p>
     * 
     * @param strategy
     *            the strategy used for comparing and storing symbols
     * 
     * @throws IllegalArgumentException
     *            if the provided strategy is null
     */
    TrieNode(SymbolStrategy<T> strategy) {
        if (strategy == null) {
            throw new IllegalArgumentException("strategy must not be null!");
        }
        this.strategy = strategy;
        this.symbol = null;
        count = 0;
        children = strategy.createSymbolMap();
    }

    /**
     * <p>
     * Constructor. Creates a new TrieNode using the provided strategy. The symbol and the
     * strategy must not be null.
     * </p>
     * 
     * @param symbol
     *            symbol associated with the trie node
     * @param strategy
     *            the strategy used for comparing and storing symbols
     * 
     * @throws IllegalArgumentException
     *            if the provided symbol or strategy is null
     */
    TrieNode(T symbol, SymbolStrategy<T> strategy) {
        if (symbol == null) {
            throw new IllegalArgumentException
                ("symbol must not be null. null is reserved for root node!");
        }
        this.symbol = symbol;
        
        if (strategy == null) {
            throw new IllegalArgumentException("strategy must not be null!");
        }
        this.strategy = strategy;

        count = 0;
        children = strategy.createSymbolMap();
    }

    /**
     * <p>
     * Copy-Constructor. Creates a new TrieNode as copy of other. Other must not be null.
     * </p>
     * 
     * @param other the trie node to create the copy of
     * 
     * @throws IllegalArgumentException
     *            if the provided node is null
     */
    TrieNode(TrieNode<T> other) {
        if (other == null) {
            throw new IllegalArgumentException("other must not be null");
        }
        symbol = other.symbol;
        count = other.count;
        strategy = other.strategy;
        children = strategy.createSymbolMap();
        
        for (TrieNode<T> child : other.children.getValues()) {
            children.addSymbol(child.getSymbol(), new TrieNode<T>(child));
        }
    }

    /**
     * <p>
     * Adds a given subsequence to the trie and increases the counters accordingly.
     * </p>
     * 
     * @param subsequence
     *            subsequence whose counters are increased
     * @see Trie#add(List)
     */
    public void add(List<T> subsequence) {
        if (!subsequence.isEmpty()) {
            if (!strategy.getSymbolComparator().equals(symbol, subsequence.get(0))) {
                // should be guaranteed by the recursion/TrieRoot!
                throw new AssertionError("Invalid trie operation!");
            }
            count++;
            subsequence.remove(0);
            if (!subsequence.isEmpty()) {
                T nextSymbol = subsequence.get(0);
                getChildCreate(nextSymbol).add(subsequence);
            }
        }
    }

    /**
     * <p>
     * Returns the symbol associated with the node.
     * </p>
     * 
     * @return symbol associated with the node
     */
    public T getSymbol() {
        return symbol;
    }

    /**
     * <p>
     * Returns the number of occurrences of the sequence represented by the node.
     * </p>
     * 
     * @return number of occurrences of the sequence represented by the node
     */
    public int getCount() {
        return count;
    }

    /**
     * <p>
     * Returns the child of the 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 Trie#getChildCreate(Object)
     */
    protected TrieNode<T> getChildCreate(T symbol) {
        TrieNode<T> node = getChild(symbol);
        if (node == null) {
            node = new TrieNode<T>(symbol, strategy);
            children.addSymbol(symbol, node);
        }
        return node;
    }

    /**
     * <p>
     * Returns the child of the 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 Trie#getChild(Object)
     */
    protected TrieNode<T> getChild(T symbol) {
        return children.getValue(symbol);
    }

    /**
     * <p>
     * Returns all children of this node.
     * </p>
     * 
     * @return children of this node
     */
    protected Collection<TrieNode<T>> getChildren() {
        return children.getValues();
    }

    /**
     * <p>
     * Searches the sub-trie of this trie node 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 Trie#find(List)
     */
    public TrieNode<T> find(List<T> subsequence) {
        TrieNode<T> result = null;
        if (subsequence.isEmpty()) {
            result = this;
        }
        else {
            TrieNode<T> node = getChild(subsequence.get(0));
            if (node != null) {
                subsequence.remove(0);
                result = node.find(subsequence);
            }
        }
        return result;
    }

    /**
     * <p>
     * Returns a collection of all symbols that follow this node, i.e., the symbols associated
     * with the children of this node.
     * </p>
     * 
     * @return symbols follow this node
     * @see TrieNode#getFollowingSymbols()
     */
    public Collection<T> getFollowingSymbols() {
        Collection<T> followingSymbols = new LinkedList<T>();
        for (TrieNode<T> child : children.getValues()) {
            followingSymbols.add(child.getSymbol());
        }
        return followingSymbols;
    }

    /**
     * <p>
     * The string representation of a node is {@code symbol.toString()#count}
     * </p>
     * 
     * @see java.lang.Object#toString()
     */
    @Override
    public String toString() {
        String str;
        
        if (symbol == null) {
            str = "ROOT";
        }
        else {
            str = symbol.toString() + " #" + count;
        }
        
        if (!children.isEmpty()) {
            str += StringTools.ENDLINE + children.toString();
        }
        return str;
    }

    /**
     * <p>
     * Generates a {@link Tree} representation of the trie.
     * </p>
     * 
     * @param parent
     *            parent vertex in the generated tree
     * @param graph
     *            complete tree
     */
    void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) {
        TrieVertex currentVertex;
        if (isRoot()) {
            currentVertex = new TrieVertex("root");
            graph.addVertex(currentVertex);
        }
        else {
            currentVertex = new TrieVertex(getSymbol().toString() + "#" + getCount());
            graph.addChild(new Edge(), parent, currentVertex);
        }
        for (TrieNode<T> node : children.getValues()) {
            node.getGraph(currentVertex, graph);
        }
    }

    /**
     * <p>
     * Appends the current node to the dot representation of the trie.
     * </p>
     * 
     * @param stringBuilder
     *            {@link StringBuilder} to which the dot representation is appended
     */
    void appendDotRepresentation(StringBuilder stringBuilder) {
        String thisSaneId;
        if (isRoot()) {
            thisSaneId = "root";
        }
        else {
            thisSaneId =
                symbol.toString().replace("\"", "\\\"").replaceAll("[\r\n]", "") + "#" + count;
        }
        stringBuilder.append(" " + hashCode() + " [label=\"" + thisSaneId + "\"];" +
            StringTools.ENDLINE);
        for (TrieNode<T> childNode : children.getValues()) {
            stringBuilder.append(" " + hashCode() + " -> " + childNode.hashCode() + ";" +
                StringTools.ENDLINE);
        }
        for (TrieNode<T> childNode : children.getValues()) {
            childNode.appendDotRepresentation(stringBuilder);
        }
    }

    /**
     * <p>
     * Checks if the node is a leaf.
     * </p>
     * 
     * @return true if the node is a leaf, false otherwise.
     */
    protected boolean isLeaf() {
        return children.isEmpty();
    }

    /**
     * <p>
     * Checks if the node is the root.
     * </p>
     * 
     * @return true if the node is the root of the trie, false otherwise
     */
    protected boolean isRoot() {
        return symbol == null;
    }

    /**
     * <p>
     * Recursive method that collects all nodes that are ancestors of leafs and stores them in the
     * set.
     * </p>
     * 
     * @param ancestors
     *            set of all ancestors of leafs
     */
    protected void getLeafAncestors(List<TrieNode<T>> ancestors) {
        boolean isAncestor = false;
        for (TrieNode<T> child : children.getValues()) {
            child.getLeafAncestors(ancestors);
            isAncestor |= child.isLeaf();
        }
        if (isAncestor) {
            ancestors.add(this);
        }
    }

    /**
     * <p>
     * Returns the number of descendants of this node that are leafs. This does not only include
     * direct children of this node, but all leafs in the sub-trie with this node as root.
     * </p>
     * 
     * @return number of leafs in this sub-trie
     */
    protected int getNumLeafs() {
        int numLeafs = 0;
        for (TrieNode<T> child : children.getValues()) {
            if (child.isLeaf()) {
                numLeafs++;
            }
            else {
                numLeafs += child.getNumLeafs();
            }
        }
        return numLeafs;
    }

    /**
     * <p>
     * Sets the {@link #count} of this node.
     * </p>
     * <p>
     * This function should only be used sparingly and very carefully! The count is usually
     * maintained automatically by the training procedures.
     * </p>
     * 
     * @param count
     *            new count
     */
    protected void setCount(int count) {
        this.count = count;
    }

    /**
     * <p>
     * Two TrieNodes are defined as equal, if their {@link #count}, {@link #symbol}, and
     * {@link #children} are equal. For the comparison of their symbols the comparator provided
     * by the symbol management strategy is used.
     * </p>
     * 
     * @see java.lang.Object#equals(java.lang.Object)
     */
    @SuppressWarnings({ "rawtypes", "unchecked" })
    @Override
    public boolean equals(Object other) {
        if (other == this) {
            return true;
        }
        if (other instanceof TrieNode) {
            TrieNode otherNode = (TrieNode) other;
            if (symbol == null) {
                return count == otherNode.count && otherNode.symbol == null &&
                    children.equals(otherNode.children);
            }
            else {
                return count == otherNode.count &&
                    symbol.getClass().isInstance(((TrieNode) other).symbol) &&
                    strategy.getSymbolComparator().equals(symbol, ((TrieNode<T>) other).symbol) &&
                    children.equals(((TrieNode) other).children);
            }
        }
        return false;
    }

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