1 // MODEL
  2 
  3 /**
  4 <pre>
  5   Implements a lazy PATRICIA tree.
  6 
  7   This class is a map where the keys are strings.  The map supports fast
  8   queries by key string prefix ("show me all the values for keys that
  9   start with "abc").  It also supports lazily loading subtrees.
 10 
 11   Each edge is labeled with a substring of a key string.
 12   Each node in the tree has one or more children, each of which represents
 13     a potential completion of the string formed by concatenating all of the
 14     edge strings from that node up to the root.
 15     Nodes also have zero or one data items.
 16   Leaves have zero or one data items.
 17 
 18   Each loaded node is an array.
 19     element 0 is the edge string;
 20     element 1 is the data item, or null if there is none;
 21     any further elements are the child nodes, sorted lexicographically
 22       by their edge string
 23 
 24   Each lazy node is an array where the first element is the number of
 25   data items in the subtree rooted at that node, and the second element
 26   is the edge string for that node.
 27     when the lazy node is loaded, the lazy array gets replaced with
 28     a loaded node array; lazy nodes and loaded nodes can be distinguished by:
 29     "string" == typeof loaded_node[0]
 30     "number" == typeof lazy_node[0]
 31 
 32   e.g., for the mappings:
 33     abc   => 0
 34     abcd  => 1
 35     abce  => "baz"
 36     abfoo => [3, 4]
 37     abbar (subtree to be loaded lazily)
 38 
 39   the structure is:
 40 
 41   [, , ["ab", ,
 42         [3, "bar"],
 43         ["c", 0, ["d", 1],
 44          ["e", "baz"]],
 45         ["foo", [3, 4]]
 46         ]
 47    ]
 48 
 49   The main goals for this structure were to minimize the JSON size on
 50   the wire (so, no type tags in the JSON to distinguish loaded nodes,
 51   lazy nodes, and leaves) while supporting lazy loading and reasonably
 52   fast lookups.
 53 </pre>
 54 
 55 @class
 56 
 57 */
 58 
 59 function LazyTrie(rootURL, chunkTempl) {
 60     this.rootURL = rootURL;
 61     this.chunkTempl = chunkTempl;
 62     var trie = this;
 63 
 64     dojo.xhrGet({url: rootURL,
 65                  handleAs: "json",
 66                  load: function(o) {
 67                      if (!o) {
 68                          console.log("failed to load trie");
 69                          return;
 70                      }
 71                      trie.root = o;
 72                      trie.extra = o[0];
 73                      if (trie.deferred) {
 74                          trie.deferred.callee.apply(trie, trie.deferred);
 75                          delete trie.deferred;
 76                      }
 77                  }
 78         });
 79 }
 80 
 81 LazyTrie.prototype.chunkUrl = function(prefix) {
 82     var chunkUrl = this.chunkTempl.replace("\{Chunk\}", prefix);
 83     return Util.resolveUrl(this.rootURL, chunkUrl);
 84 };
 85 
 86 LazyTrie.prototype.pathToPrefix = function(path) {
 87     var node = this.root;
 88     var result = "";
 89     loop: for (var i = 0; i < path.length; i++) {
 90         switch(typeof node[path[i]][0]) {
 91         case 'string': // regular node
 92             result += node[path[i]][0];
 93             break;
 94         case 'number': // lazy node
 95             result += node[path[i]][1];
 96             break loop;
 97         }
 98         node = node[path[i]];
 99     }
100     return result;
101 };
102 
103 LazyTrie.prototype.valuesFromPrefix = function(query, callback) {
104     var trie = this;
105     this.findNode(query, function(prefix, node) {
106             callback(trie.valuesFromNode(node));
107         });
108 };
109 
110 LazyTrie.prototype.mappingsFromPrefix = function(query, callback) {
111     var trie = this;
112     this.findNode(query, function(prefix, node) {
113             callback(trie.mappingsFromNode(prefix, node));
114         });
115 };
116 
117 LazyTrie.prototype.mappingsFromNode = function(prefix, node) {
118     var results = [];
119     if (node[1] !== null)
120         results.push([prefix, node[1]]);
121     for (var i = 2; i < node.length; i++) {
122         if ("string" == typeof node[i][0]) {
123             results = results.concat(this.mappingsFromNode(prefix + node[i][0],
124                                                            node[i]));
125         }
126     }
127     return results;
128 };
129 
130 LazyTrie.prototype.valuesFromNode = function(node) {
131     var results = [];
132     if (node[1] !== null)
133         results.push(node[1]);
134     for (var i = 2; i < node.length; i++)
135         results = results.concat(this.valuesFromNode(node[i]));
136     return results;
137 };
138 
139 LazyTrie.prototype.exactMatch = function(key, callback) {
140     var trie = this;
141     this.findNode(key, function(prefix, node) {
142             if ((prefix.toLowerCase() == key.toLowerCase()) && node[1])
143                 callback(node[1]);
144         });
145 };
146 
147 LazyTrie.prototype.findNode = function(query, callback) {
148     var trie = this;
149     this.findPath(query, function(path) {
150         var node = trie.root;
151         for (i = 0; i < path.length; i++)
152             node = node[path[i]];
153         var foundPrefix = trie.pathToPrefix(path);
154         callback(foundPrefix, node);
155     });
156 };
157 
158 LazyTrie.prototype.findPath = function(query, callback) {
159     if (!this.root) {
160         this.deferred = arguments;
161         return;
162     }
163     query = query.toLowerCase();
164     var node = this.root;
165     var qStart = 0;
166     var childIndex;
167 
168     var path = [];
169 
170     while(true) {
171         childIndex = this.binarySearch(node, query.charAt(qStart));
172         if (childIndex < 0) return;
173         path.push(childIndex);
174 
175         if ("number" == typeof node[childIndex][0]) {
176             // lazy node
177             var trie = this;
178             dojo.xhrGet({url: this.chunkUrl(this.pathToPrefix(path)),
179                          handleAs: "json",
180                          load: function(o) {
181                              node[childIndex] = o;
182                              trie.findPath(query, callback);
183                          }
184                         });
185             return;
186         }
187 
188         node = node[childIndex];
189 
190         // if the current edge string doesn't match the
191         // relevant part of the query string, then there's no
192         // match
193         if (query.substr(qStart, node[0].length)
194             != node[0].substr(0, Math.min(node[0].length,
195                                           query.length - qStart)))
196             return;
197 
198         qStart += node[0].length;
199         if (qStart >= query.length) {
200             // we've reached the end of the query string, and we
201             // have some matches
202             callback(path);
203             return;
204         }
205     }
206 };
207 
208 LazyTrie.prototype.binarySearch = function(a, firstChar) {
209     var low = 2; // skip edge string (in 0) and data item (in 1)
210     var high = a.length - 1;
211     var mid, midVal;
212     while (low <= high) {
213         mid = (low + high) >>> 1;
214         switch(typeof a[mid][0]) {
215         case 'string': // regular node
216             midVal = a[mid][0].charAt(0);
217             break;
218         case 'number': // lazy node
219             midVal = a[mid][1].charAt(0);
220             break;
221         }
222 
223         if (midVal < firstChar) {
224             low = mid + 1;
225         } else if (midVal > firstChar) {
226             high = mid - 1;
227         } else {
228             return mid; // key found
229         }
230     }
231 
232     return -(low + 1);  // key not found.
233 };
234 
235 /*
236 
237 Copyright (c) 2007-2009 The Evolutionary Software Foundation
238 
239 Created by Mitchell Skinner <mitch_skinner@berkeley.edu>
240 
241 This package and its accompanying libraries are free software; you can
242 redistribute it and/or modify it under the terms of the LGPL (either
243 version 2.1, or at your option, any later version) or the Artistic
244 License 2.0.  Refer to LICENSE for the full license text.
245 
246 */
247