source: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/TrieNode.java @ 5

package de.ugoe.cs.eventbench.ppm;

import java.security.InvalidParameterException;
import java.util.LinkedList;
import java.util.List;

import de.ugoe.cs.eventbench.ppm.Trie.Edge;
import de.ugoe.cs.eventbench.ppm.Trie.TrieVertex;
import de.ugoe.cs.util.StringTools;
import edu.uci.ics.jung.graph.DelegateTree;


class TrieNode<T> {
        
        private int count;
        private final T symbol;
        
        private List<TrieNode<T>> children;
        
        public TrieNode(T symbol) {
                if( symbol==null ) {
                        throw new InvalidParameterException("symbol must not be null.");
                }
                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 List<T> getFollowingSymbols() {
                List<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 vertex = new TrieVertex(getSymbol().toString()+"#"+getCount());
                graph.addChild( new Edge() , parent, vertex );
                for( TrieNode<T> node : children ) {
                        node.getGraph(vertex, graph);
                }               
        }

}