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 java.util.Set; 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; /** *
* 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 */ public 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* 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* 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 (symbol == null) { 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(); } /** ** 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(Set