Ignore:
Timestamp:
04/11/11 15:42:42 (13 years ago)
Author:
sherbold
Message:
  • Cleanup of PPM and Trie
File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r5 r6  
    2121public class Trie<T> { 
    2222         
    23         // Children of the Trie root 
    24         // should contain counts of all elements 
    25         private List<TrieNode<T>> children = new LinkedList<TrieNode<T>>(); 
     23        private final TrieNode<T> rootNode; 
     24         
     25        public Trie() { 
     26                rootNode = new TrieNode<T>(); 
     27        } 
    2628         
    2729 
    … …  
    3032                        subsequence = new LinkedList<T>(subsequence);  // defensive copy! 
    3133                        T firstSymbol = subsequence.get(0); 
    32                         getChildCreate(firstSymbol).add(subsequence); 
     34                        TrieNode<T> node = getChildCreate(firstSymbol); 
     35                        node.add(subsequence); 
    3336                } 
    3437        } 
    3538 
    36         // FIXME clones of TrieNode.getChildCreate 
    3739        protected TrieNode<T>  getChildCreate(T symbol) { 
    38                 TrieNode<T> node = getChild(symbol); 
    39                 if( node==null ) { 
    40                         node = new TrieNode<T>(symbol); 
    41                         children.add(node); 
    42                 } 
    43                 return node; 
     40                return rootNode.getChildCreate(symbol); 
    4441        } 
    4542         
    46         // FIXME clones of TrieNode.getChild 
    4743        protected TrieNode<T> getChild(T symbol) { 
    48                 for( TrieNode<T> child : children ) { 
    49                         if( child.getSymbol().equals(symbol) ) { 
    50                                 return child; 
    51                         } 
    52                 } 
    53                 return null; 
     44                return rootNode.getChild(symbol); 
    5445        } 
    5546 
    … …  
    7364         
    7465        public TrieNode<T> find(List<T> sequence) { 
     66                if( sequence==null || sequence.isEmpty() ) { 
     67                        return rootNode; 
     68                } 
    7569                List<T> sequenceCopy = new LinkedList<T>(sequence); 
    7670                TrieNode<T> result = null; 
    77                 if( !sequenceCopy.isEmpty() ) { 
    78                         TrieNode<T> node = getChild(sequenceCopy.get(0)); 
    79                         if( node!=null ) { 
    80                                 sequenceCopy.remove(0); 
    81                                 result = node.find(sequenceCopy); 
    82                         } 
     71                TrieNode<T> node = getChild(sequenceCopy.get(0)); 
     72                if( node!=null ) { 
     73                        sequenceCopy.remove(0); 
     74                        result = node.find(sequenceCopy); 
    8375                } 
    8476                return result; 
    … …  
    8880        public List<T> getFollowingSymbols(List<T> sequence) { 
    8981                List<T> result = new LinkedList<T>(); 
    90                 if( sequence==null || sequence.isEmpty() ) { 
    91                         for( TrieNode<T> child : children ) { 
    92                                 result.add(child.getSymbol()); 
    93                         } 
    94                 } else { 
    95                         TrieNode<T> node = find(sequence); 
    96                         if( node!=null ) { 
    97                                 result = node.getFollowingSymbols(); 
    98                         } 
     82                TrieNode<T> node = find(sequence); 
     83                if( node!=null ) { 
     84                        result = node.getFollowingSymbols(); 
    9985                } 
    10086                return result; 
    … …  
    10288         
    10389        // longest suffix of context, that is contained in the tree and whose children are leaves 
     90        // possibly already deprecated 
    10491        public List<T> getContextSuffix(List<T> context) { 
    10592                List<T> contextSuffix = new LinkedList<T>(context); // defensive copy 
    … …  
    140127        private Tree<TrieVertex, Edge> getGraph() { 
    141128                DelegateTree<TrieVertex, Edge> graph = new DelegateTree<TrieVertex, Edge>(); 
    142                  
    143                 TrieVertex root = new TrieVertex("root"); 
    144                 graph.addVertex(root); 
    145                                  
    146                 for( TrieNode<T> node : children ) { 
    147                         node.getGraph(root, graph); 
    148                 } 
    149                  
     129                rootNode.getGraph(null, graph); 
    150130                return graph; 
    151131        } 
    … …  
    181161        @Override 
    182162        public String toString() { 
    183                 return children.toString(); 
     163                return rootNode.toString(); 
    184164        } 
    185165} 
Note: See TracChangeset for help on using the changeset viewer.