Changeset 5 for trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java

Timestamp:

04/11/11 14:43:03 (13 years ago)

Author:

sherbold

Message:

• major debugging of PPM and Trie. Results are now correct, but both classes need major refactorings

File:

• trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java (modified) (7 diffs)

trunk/EventBenchCore/src/de/ugoe/cs/eventbench/ppm/Trie.java

@@ -1 +1 @@
 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>>();
         
@@ -11 +28 @@
         public void add(List<T> subsequence) {
                 if( !subsequence.isEmpty() ) {
-                        subsequence = new LinkedList<T>(subsequence);  // copy list!
+                        subsequence = new LinkedList<T>(subsequence);  // defensive copy!
                         T firstSymbol = subsequence.get(0);
                         getChildCreate(firstSymbol).add(subsequence);
@@ -37 +54 @@
         }
 
+        // get the count of "sequence"
         public int getCount(List<T> sequence) {
                 int count = 0;
@@ -46 +64 @@
         }
         
+        // get the count of "sequence,follower"
         public int getCount(List<T> sequence, T follower) {
                 List<T> tmpSequence = new LinkedList<T>(sequence);
@@ -54 +73 @@
         
         public TrieNode<T> find(List<T> sequence) {
+                List<T> sequenceCopy = new LinkedList<T>(sequence);
                 TrieNode<T> result = null;
-                if( !sequence.isEmpty() ) {
-                        TrieNode<T> node = getChild(sequence.get(0));
+                if( !sequenceCopy.isEmpty() ) {
+                        TrieNode<T> node = getChild(sequenceCopy.get(0));
                         if( node!=null ) {
-                                result = node.find(sequence);
+                                sequenceCopy.remove(0);
+                                result = node.find(sequenceCopy);
                         }
                 }
@@ -64 +85 @@
         }
         
+        // returns all symbols that follow the defined sequence
         public List<T> getFollowingSymbols(List<T> sequence) {
-                List<T> result = null;
-                TrieNode<T> node = find(sequence);
-                if( node!=null ) {
-                        result = node.getFollowingSymbols();
+                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);
+                List<T> contextSuffix = new LinkedList<T>(context); // defensive copy
                 boolean suffixFound = false;
                 
@@ -87 +116 @@
                                         }
                                 }
-                                contextSuffix.remove(0);
+                                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);
         }