source: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java @ 399

package de.ugoe.cs.eventbench.models;

import java.io.Serializable;
import java.security.InvalidParameterException;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;

import de.ugoe.cs.eventbench.models.Trie.Edge;
import de.ugoe.cs.eventbench.models.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 occurences of the sequence
 * defined by the path from the root of the trie to this node.
 * </p>
 * 
 * @author Steffen Herbold
 * 
 * @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 occurences 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 Collection<TrieNode<T>> children;

        /**
         * <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>
         * </p>
         */
        TrieNode() {
                this.symbol = null;
                count = 0;
                children = new LinkedList<TrieNode<T>>();
        }

        /**
         * <p>
         * Constructor. Creates a new TrieNode. The symbol must not be null.
         * </p>
         * 
         * @param symbol
         *            symbol associated with the trie node
         */
        TrieNode(T symbol) {
                if (symbol == null) {
                        throw new InvalidParameterException(
                                        "symbol must not be null. null is reserved for root node!");
                }
                this.symbol = symbol;
                count = 0;
                children = new LinkedList<TrieNode<T>>();
        }

        /**
         * <p>
         * Copy-Constructor. Creates a new TrieNode as copy of other. Other must not
         * be null.
         * </p>
         * 
         * @param other
         */
        TrieNode(TrieNode<T> other) {
                if (other == null) {
                        throw new InvalidParameterException("other must not be null");
                }
                symbol = other.symbol;
                count = other.count;
                children = new LinkedList<TrieNode<T>>();
                for (TrieNode<T> child : other.children) {
                        children.add(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 (!symbol.equals(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 occurences of the sequence represented by the node.
         * </p>
         * 
         * @return number of occurences 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);
                        children.add(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) {
                for (TrieNode<T> child : children) {
                        if (child.getSymbol().equals(symbol)) {
                                return child;
                        }
                }
                return null;
        }

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

        /**
         * <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 a 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) {
                        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 = symbol.toString() + " #" + count;
                if (!children.isEmpty()) {
                        str += StringTools.ENDLINE + children.toString();
                }
                return str;
        }

        /**
         * <p>
         * Generates a {@link Tree} represenation 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) {
                        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) {
                        stringBuilder.append(" " + hashCode() + " -> "
                                        + childNode.hashCode() + ";" + StringTools.ENDLINE);
                }
                for (TrieNode<T> childNode : children) {
                        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 methods 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) {
                        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) {
                        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.
         * </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 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.equals(((TrieNode) 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;
        }
}