source: trunk/EventBenchCore/src/de/ugoe/cs/eventbench/models/Trie.java @ 23

package de.ugoe.cs.eventbench.models;

import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import edu.uci.ics.jung.graph.DelegateTree;
import edu.uci.ics.jung.graph.Tree;

public class Trie<T> {
        
        private Set<T> knownSymbols;
        
        private final TrieNode<T> rootNode;
        
        public Trie() {
                rootNode = new TrieNode<T>();
                knownSymbols = new LinkedHashSet<T>();
        }
        
        public Set<T> getKnownSymbols() {
                return new LinkedHashSet<T>(knownSymbols);
        }
        
        // trains the current Trie using the given sequence and adds all subsequence of length trieOrder
        public void train(List<T> sequence, int maxOrder) {
                IncompleteMemory<T> latestActions = new IncompleteMemory<T>(maxOrder);
                int i=0;
                for(T currentEvent : sequence) {
                        latestActions.add(currentEvent);
                        knownSymbols.add(currentEvent);
                        i++;
                        if( i>=maxOrder ) {
                                add(latestActions.getLast(maxOrder));
                        }
                }
                int sequenceLength = sequence.size();
                for( int j=maxOrder-1 ; j>0 ; j-- ) {
                        add(sequence.subList(sequenceLength-j, sequenceLength));
                }
        }
        

        // increases the counters for each symbol in the subsequence
        public void add(List<T> subsequence) {
                if( subsequence!=null && !subsequence.isEmpty() ) {
                        knownSymbols.addAll(subsequence);
                        subsequence = new LinkedList<T>(subsequence);  // defensive copy!
                        T firstSymbol = subsequence.get(0);
                        TrieNode<T> node = getChildCreate(firstSymbol);
                        node.add(subsequence);
                }
        }

        protected TrieNode<T>  getChildCreate(T symbol) {
                return rootNode.getChildCreate(symbol);
        }
        
        protected TrieNode<T> getChild(T symbol) {
                return rootNode.getChild(symbol);
        }

        // get the count of "sequence"
        public int getCount(List<T> sequence) {
                int count = 0;
                TrieNode<T> node = find(sequence);
                if( node!=null ) {
                        count = node.getCount();
                }
                return count;
        }
        
        // get the count of "sequence,follower"
        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) {
                if( sequence==null || sequence.isEmpty() ) {
                        return rootNode;
                }
                List<T> sequenceCopy = new LinkedList<T>(sequence);
                TrieNode<T> result = null;
                TrieNode<T> node = getChild(sequenceCopy.get(0));
                if( node!=null ) {
                        sequenceCopy.remove(0);
                        result = node.find(sequenceCopy);
                }
                return result;
        }
        
        // returns all symbols that follow the defined sequence
        public List<T> getFollowingSymbols(List<T> sequence) {
                List<T> result = new LinkedList<T>();
                TrieNode<T> node = find(sequence);
                if( node!=null ) {
                        result = node.getFollowingSymbols();
                }
                return result;
        }
        
        // longest suffix of context, that is contained in the tree and whose children are leaves
        // possibly already deprecated
        public List<T> getContextSuffix(List<T> context) {
                List<T> contextSuffix = new LinkedList<T>(context); // defensive copy
                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;
                                        }
                                }
                                if( !suffixFound ) {
                                        contextSuffix.remove(0);
                                }
                        }
                }
                
                return contextSuffix;
        }
        
        
        static public class Edge{}
        
        static public class TrieVertex {
                private String id;
                protected TrieVertex(String id) {
                        this.id = id;
                }
                public String toString() {
                        return id;
                }
        }
        
        protected Tree<TrieVertex, Edge> getGraph() {
                DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>();
                rootNode.getGraph(null, graph);
                return graph;
        }
        
        @Override
        public String toString() {
                return rootNode.toString();
        }
}