// 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; /** *
* 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. *
* * @author Steffen Herbold * * @param* Id for object serialization. *
*/ private static final long serialVersionUID = 1L; /** ** Counter for the number of occurences of the sequence. *
*/ private int count; /** ** Symbol associated with the node. *
*/ private final T symbol; /** ** Child nodes of this node. If the node is a leaf this collection is empty. *
*/ private Collection
* Constructor. Creates a new TrieNode without a symbol associated.
* This constructor should only be used to create the root node of the trie!
*
* Constructor. Creates a new TrieNode. The symbol must not be null. *
* * @param symbol * symbol associated with the trie node */ TrieNode(T symbol) { if (symbol == null) { throw new IllegalArgumentException( "symbol must not be null. null is reserved for root node!"); } this.symbol = symbol; count = 0; children = new LinkedList* Copy-Constructor. Creates a new TrieNode as copy of other. Other must not be null. *
* * @param other */ TrieNode(TrieNode* Adds a given subsequence to the trie and increases the counters accordingly. *
* * @param subsequence * subsequence whose counters are increased * @see Trie#add(List) */ public void add(List* Returns the symbol associated with the node. *
* * @return symbol associated with the node */ public T getSymbol() { return symbol; } /** ** Returns the number of occurences of the sequence represented by the node. *
* * @return number of occurences of the sequence represented by the node */ public int getCount() { return count; } /** ** Returns the child of the node associated with the given symbol or creates it if it does not * exist yet. *
* * @param symbol * symbol whose node is required * @return node associated with the symbol * @see Trie#getChildCreate(Object) */ protected TrieNode* Returns the child of the node associated with the given symbol or null if it does not exist. *
* * @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* Returns all children of this node. *
* * @return children of this node */ protected Collection* 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. *
* * @param sequence * sequence that is searched for * @return node associated with the sequence * @see Trie#find(List) */ public TrieNode* Returns a collection of all symbols that follow a this node, i.e., the symbols associated * with the children of this node. *
* * @return symbols follow this node * @see TrieNode#getFollowingSymbols() */ public Collection* The string representation of a node is {@code symbol.toString()#count} *
* * @see java.lang.Object#toString() */ @Override public String toString() { String str = symbol.toString() + " #" + count; if (!children.isEmpty()) { str += StringTools.ENDLINE + children.toString(); } return str; } /** ** Generates a {@link Tree} represenation of the trie. *
* * @param parent * parent vertex in the generated tree * @param graph * complete tree */ void getGraph(TrieVertex parent, DelegateTree* Appends the current node to the dot representation of the trie. *
* * @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* Checks if the node is a leaf. *
* * @return true if the node is a leaf, false otherwise. */ protected boolean isLeaf() { return children.isEmpty(); } /** ** Checks if the node is the root. *
* * @return true if the node is the root of the trie, false otherwise */ protected boolean isRoot() { return symbol == null; } /** ** Recursive methods that collects all nodes that are ancestors of leafs and stores them in the * set. *
* * @param ancestors * set of all ancestors of leafs */ protected void getLeafAncestors(List* 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. *
* * @return number of leafs in this sub-trie */ protected int getNumLeafs() { int numLeafs = 0; for (TrieNode* Sets the {@link #count} of this node. *
** This function should only be used sparingly and very carefully! The count is usually * maintained automatically by the training procedures. *
* * @param count * new count */ protected void setCount(int count) { this.count = count; } /** ** Two TrieNodes are defined as equal, if their {@link #count}, {@link #symbol}, and * {@link #children} are equal. *
* * @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; } }