Changeset 1251 for trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/TrieNode.java

Timestamp:

07/12/13 16:45:53 (11 years ago)

Author:

pharms

Message:

• improved performance of the trie for large alphabets by using the symbol map. This is an improved list of symbols that allows a more efficient lookup for symbols using buckets of symbol as an initial search order

File:

• trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/TrieNode.java (modified) (12 diffs)

trunk/autoquest-core-usageprofiles/src/main/java/de/ugoe/cs/autoquest/usageprofiles/TrieNode.java

@@ -67 +67 @@
      * </p>
      */
-    private Collection<TrieNode<T>> children;
-
+    private SymbolMap<T, TrieNode<T>> children;
+    
     /**
      * <p>
@@ -115 +115 @@
         this.symbol = null;
         count = 0;
-        children = new LinkedList<TrieNode<T>>();
+        children = new SymbolMap<T, TrieNode<T>>(this.comparator);
     }
 
@@ -140 +140 @@
 
         count = 0;
-        children = new LinkedList<TrieNode<T>>();
+        children = new SymbolMap<T, TrieNode<T>>(this.comparator);
     }
 
@@ -157 +157 @@
         count = other.count;
         comparator = other.comparator;
-        children = new LinkedList<TrieNode<T>>();
-        for (TrieNode<T> child : other.children) {
-            children.add(new TrieNode<T>(child));
+        children = new SymbolMap<T, TrieNode<T>>(this.comparator);
+        
+        for (TrieNode<T> child : other.children.getValues()) {
+            children.addSymbol(child.getSymbol(), new TrieNode<T>(child));
         }
     }
@@ -224 +225 @@
         if (node == null) {
             node = new TrieNode<T>(symbol, comparator);
-            children.add(node);
+            children.addSymbol(symbol, node);
         }
         return node;
@@ -240 +241 @@
      */
     protected TrieNode<T> getChild(T symbol) {
-        for (TrieNode<T> child : children) {
-            if (comparator.equals(child.getSymbol(), symbol)) {
-                return child;
-            }
-        }
-        return null;
+        return children.getValue(symbol);
     }
 
@@ -256 +252 @@
      */
     protected Collection<TrieNode<T>> getChildren() {
-        return children;
+        return children.getValues();
     }
 
@@ -296 +292 @@
     public Collection<T> getFollowingSymbols() {
         Collection<T> followingSymbols = new LinkedList<T>();
-        for (TrieNode<T> child : children) {
+        for (TrieNode<T> child : children.getValues()) {
             followingSymbols.add(child.getSymbol());
         }
@@ -346 +342 @@
             graph.addChild(new Edge(), parent, currentVertex);
         }
-        for (TrieNode<T> node : children) {
+        for (TrieNode<T> node : children.getValues()) {
             node.getGraph(currentVertex, graph);
         }
@@ -370 +366 @@
         stringBuilder.append(" " + hashCode() + " [label=\"" + thisSaneId + "\"];" +
             StringTools.ENDLINE);
-        for (TrieNode<T> childNode : children) {
+        for (TrieNode<T> childNode : children.getValues()) {
             stringBuilder.append(" " + hashCode() + " -> " + childNode.hashCode() + ";" +
                 StringTools.ENDLINE);
         }
-        for (TrieNode<T> childNode : children) {
+        for (TrieNode<T> childNode : children.getValues()) {
             childNode.appendDotRepresentation(stringBuilder);
         }
@@ -412 +408 @@
     protected void getLeafAncestors(List<TrieNode<T>> ancestors) {
         boolean isAncestor = false;
-        for (TrieNode<T> child : children) {
+        for (TrieNode<T> child : children.getValues()) {
             child.getLeafAncestors(ancestors);
             isAncestor |= child.isLeaf();
@@ -431 +427 @@
     protected int getNumLeafs() {
         int numLeafs = 0;
-        for (TrieNode<T> child : children) {
+        for (TrieNode<T> child : children.getValues()) {
             if (child.isLeaf()) {
                 numLeafs++;