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

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;


class TrieNode<T> implements Serializable {
        
        /**
         * Id for object serialization.
         */
        private static final long serialVersionUID = 1L;
        
        private int count;
        private final T symbol;
        
        private Collection<TrieNode<T>> children;
        
        TrieNode() {
                this.symbol = null;
                count = 0;
                children = new LinkedList<TrieNode<T>>();
        }
        
        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<TrieNode<T>>();
        }

        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);
                        }
                }
        }
        
        public T getSymbol() {
                return symbol;
        }
        
        public int getCount() {
                return count;
        }
        
        protected TrieNode<T>  getChildCreate(T symbol) {
                TrieNode<T> node = getChild(symbol);
                if( node==null ) {
                        node = new TrieNode<T>(symbol);
                        children.add(node);
                }
                return node;
        }
        
        protected TrieNode<T> getChild(T symbol) {
                for( TrieNode<T> child : children ) {
                        if( child.getSymbol().equals(symbol) ) {
                                return child;
                        }
                }
                return null;
        }
        

        
        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;
        }
        
        // returns all symbols that follow this node
        public Collection<T> getFollowingSymbols() {
                Collection<T> followingSymbols = new LinkedList<T>();
                for( TrieNode<T> child : children ) {
                        followingSymbols.add(child.getSymbol());
                }
                return followingSymbols;
        }
        
        @Override
        public String toString() {
                String str = symbol.toString()+" #"+count;
                if( !children.isEmpty() ) {
                        str += StringTools.ENDLINE + children.toString();
                }
                return str; 
        }

        public void getGraph(TrieVertex parent, DelegateTree<TrieVertex, Edge> graph) {
                TrieVertex currentVertex;
                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 ) {
                        node.getGraph(currentVertex, graph);
                }               
        }
        
        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<T> childNode : children ) {
                        stringBuilder.append(" "+hashCode()+" -> " + childNode.hashCode() + ";" + StringTools.ENDLINE);
                }
                for( TrieNode<T> childNode : children ) {
                        childNode.appendDotRepresentation(stringBuilder);
                }
        }
}