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

package de.ugoe.cs.eventbench.ppm;

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

import javax.swing.JFrame;

import org.apache.commons.collections15.Transformer;

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> {
        
        // Children of the Trie root
        // should contain counts of all elements
        private List<TrieNode<T>> children = new LinkedList<TrieNode<T>>();
        

        public void add(List<T> subsequence) {
                if( !subsequence.isEmpty() ) {
                        subsequence = new LinkedList<T>(subsequence);  // defensive copy!
                        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;
        }

        // 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) {
                List<T> sequenceCopy = new LinkedList<T>(sequence);
                TrieNode<T> result = null;
                if( !sequenceCopy.isEmpty() ) {
                        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>();
                if( sequence==null || sequence.isEmpty() ) {
                        for( TrieNode<T> child : children ) {
                                result.add(child.getSymbol());
                        }
                } else {
                        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
        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>();
                
                TrieVertex root = new TrieVertex("root");
                graph.addVertex(root);
                                
                for( TrieNode<T> node : children ) {
                        node.getGraph(root, 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 children.toString();
        }
}