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

package de.ugoe.cs.eventbench.models;

import java.awt.Dimension;
import java.awt.Rectangle;
import java.awt.Shape;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

import javax.swing.JFrame;

import org.apache.commons.collections15.Transformer;

import de.ugoe.cs.eventbench.markov.IncompleteMemory;

import edu.uci.ics.jung.algorithms.layout.Layout;
import edu.uci.ics.jung.algorithms.layout.TreeLayout;
import edu.uci.ics.jung.graph.DelegateTree;
import edu.uci.ics.jung.graph.Tree;
import edu.uci.ics.jung.visualization.BasicVisualizationServer;
import edu.uci.ics.jung.visualization.decorators.ToStringLabeller;
import edu.uci.ics.jung.visualization.renderers.Renderer.VertexLabel.Position;

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 maxOrder
        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;
                }
        }
        
        private Tree<TrieVertex, Edge> getGraph() {
                DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>();
                rootNode.getGraph(null, graph);
                return graph;
        }
        
        public void display() {
                Tree<TrieVertex, Edge> graph = this.getGraph();
                Layout<TrieVertex, Edge> layout = new TreeLayout<TrieVertex, Edge>(graph, 60);
                // The BasicVisualizationServer<V,E> is parameterized by the edge types
                BasicVisualizationServer<TrieVertex,Edge> vv =
                new BasicVisualizationServer<TrieVertex,Edge>(layout);
                vv.setPreferredSize(new Dimension(1100,850)); //Sets the viewing area size
                
                
                final Rectangle rect = new Rectangle(40, 20);
                        
                Transformer<TrieVertex, Shape> vertexShapeTransformer =
                        new Transformer<TrieVertex, Shape>() {
                                public Shape transform(TrieVertex s) {
                                        return rect;
                                }
                };
                vv.getRenderer().getVertexLabelRenderer().setPosition(Position.CNTR);
                vv.getRenderContext().setVertexShapeTransformer(vertexShapeTransformer);
                vv.getRenderContext().setVertexLabelTransformer(new ToStringLabeller<TrieVertex>());
                
                JFrame frame = new JFrame("Trie");
                frame.setDefaultCloseOperation(JFrame.DISPOSE_ON_CLOSE);
                frame.getContentPane().add(vv);
                frame.pack();
                frame.setVisible(true);
        }
        
        @Override
        public String toString() {
                return rootNode.toString();
        }
}