source: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java @ 1

package de.ugoe.cs.eventbench.ppm;

import java.util.LinkedList;
import java.util.List;

public class Trie<T> {
        
        private List<TrieNode<T>> children = new LinkedList<TrieNode<T>>();
        

        public void add(List<T> subsequence) {
                if( !subsequence.isEmpty() ) {
                        subsequence = new LinkedList<T>(subsequence);  // copy list!
                        T firstSymbol = subsequence.get(0);
                        getChildCreate(firstSymbol).add(subsequence);
                }
        }

        // FIXME clones of TrieNode.getChildCreate
        protected TrieNode<T>  getChildCreate(T symbol) {
                TrieNode<T> node = getChild(symbol);
                if( node==null ) {
                        node = new TrieNode<T>(symbol);
                        children.add(node);
                }
                return node;
        }
        
        // FIXME clones of TrieNode.getChild
        protected TrieNode<T> getChild(T symbol) {
                for( TrieNode<T> child : children ) {
                        if( child.getSymbol().equals(symbol) ) {
                                return child;
                        }
                }
                return null;
        }

        public int getCount(List<T> sequence) {
                int count = 0;
                TrieNode<T> node = find(sequence);
                if( node!=null ) {
                        count = node.getCount();
                }
                return count;
        }
        
        public int getCount(List<T> sequence, T follower) {
                List<T> tmpSequence = new LinkedList<T>(sequence);
                tmpSequence.add(follower);
                return getCount(tmpSequence);
                
        }
        
        public TrieNode<T> find(List<T> sequence) {
                TrieNode<T> result = null;
                if( !sequence.isEmpty() ) {
                        TrieNode<T> node = getChild(sequence.get(0));
                        if( node!=null ) {
                                result = node.find(sequence);
                        }
                }
                return result;
        }
        
        public List<T> getFollowingSymbols(List<T> sequence) {
                List<T> result = null;
                TrieNode<T> node = find(sequence);
                if( node!=null ) {
                        result = node.getFollowingSymbols();
                }
                return result;
        }
        
        public List<T> getContextSuffix(List<T> context) {
                List<T> contextSuffix = new LinkedList<T>(context);
                boolean suffixFound = false;
                
                while(!suffixFound) {
                        if( contextSuffix.isEmpty() ) {
                                suffixFound = true; // suffix is the empty word
                        } else {
                                TrieNode<T> node = find(contextSuffix);
                                if( node!=null ) {
                                        if( !node.getFollowingSymbols().isEmpty() ) {
                                                suffixFound = true;
                                        }
                                }
                                contextSuffix.remove(0);
                        }
                }
                
                return contextSuffix;
        }
        
        @Override
        public String toString() {
                return children.toString();
        }
}