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