Changeset 106 for trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java

Timestamp:

07/05/11 15:18:56 (13 years ago)

Author:

sherbold

Message:

• code documentation

File:

• trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java (modified) (7 diffs)

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/TrieNode.java

@@ -11 +11 @@
 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;
@@ -30 +68 @@
                 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
+         */
         public TrieNode(T symbol) {
-                if( symbol==null ) {
-                        throw new InvalidParameterException("symbol must not be null. null is reserved for root node!");
+                if (symbol == null) {
+                        throw new InvalidParameterException(
+                                        "symbol must not be null. null is reserved for root node!");
                 }
                 this.symbol = symbol;
@@ -40 +87 @@
         }
 
+        /**
+         * <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!
+                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() ) {
+                        if (!subsequence.isEmpty()) {
                                 T nextSymbol = subsequence.get(0);
                                 getChildCreate(nextSymbol).add(subsequence);
@@ -53 +112 @@
                 }
         }
-        
+
+        /**
+         * <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;
         }
-        
-        protected TrieNode<T>  getChildCreate(T symbol) {
+
+        /**
+         * <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 ) {
+                if (node == null) {
                         node = new TrieNode<T>(symbol);
                         children.add(node);
@@ -70 +154 @@
                 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) ) {
+                for (TrieNode<T> child : children) {
+                        if (child.getSymbol().equals(symbol)) {
                                 return child;
                         }
@@ -79 +174 @@
                 return null;
         }
-        
-
-        
+
+        /**
+         * <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() ) {
+                if (subsequence.isEmpty()) {
                         result = this;
                 } else {
                         TrieNode<T> node = getChild(subsequence.get(0));
-                        if( node!=null ) {
+                        if (node != null) {
                                 subsequence.remove(0);
                                 result = node.find(subsequence);
@@ -95 +199 @@
                 return result;
         }
-        
-        // returns all symbols that follow this node
+
+        /**
+         * <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 ) {
+                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() ) {
+                String str = symbol.toString() + " #" + count;
+                if (!children.isEmpty()) {
                         str += StringTools.ENDLINE + children.toString();
                 }
-                return str; 
-        }
-
-        public void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) {
+                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( symbol==null ){
+                if (symbol == null) {
                         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 ) {
+                        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( symbol==null ) {
+                if (symbol == null) {
                         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 ) {
+                        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);
                 }