Class LazyTrie
Defined in: LazyPatricia.js.
Constructor Attributes | Constructor Name and Description |
---|---|
LazyTrie(rootURL, chunkTempl)
Implements a lazy PATRICIA tree. |
Method Attributes | Method Name and Description |
---|---|
binarySearch(a, firstChar)
|
|
chunkUrl(prefix)
|
|
exactMatch(key, callback)
|
|
findNode(query, callback)
|
|
findPath(query, callback)
|
|
mappingsFromNode(prefix, node)
|
|
mappingsFromPrefix(query, callback)
|
|
pathToPrefix(path)
|
|
valuesFromNode(node)
|
|
valuesFromPrefix(query, callback)
|
Class Detail
LazyTrie(rootURL, chunkTempl)
Implements a lazy PATRICIA tree. This class is a map where the keys are strings. The map supports fast queries by key string prefix ("show me all the values for keys that start with "abc"). It also supports lazily loading subtrees. Each edge is labeled with a substring of a key string. Each node in the tree has one or more children, each of which represents a potential completion of the string formed by concatenating all of the edge strings from that node up to the root. Nodes also have zero or one data items. Leaves have zero or one data items. Each loaded node is an array. element 0 is the edge string; element 1 is the data item, or null if there is none; any further elements are the child nodes, sorted lexicographically by their edge string Each lazy node is an array where the first element is the number of data items in the subtree rooted at that node, and the second element is the edge string for that node. when the lazy node is loaded, the lazy array gets replaced with a loaded node array; lazy nodes and loaded nodes can be distinguished by: "string" == typeof loaded_node[0] "number" == typeof lazy_node[0] e.g., for the mappings: abc => 0 abcd => 1 abce => "baz" abfoo => [3, 4] abbar (subtree to be loaded lazily) the structure is: [, , ["ab", , [3, "bar"], ["c", 0, ["d", 1], ["e", "baz"]], ["foo", [3, 4]] ] ] The main goals for this structure were to minimize the JSON size on the wire (so, no type tags in the JSON to distinguish loaded nodes, lazy nodes, and leaves) while supporting lazy loading and reasonably fast lookups.
- Parameters:
- rootURL
- chunkTempl
Method Detail
binarySearch(a, firstChar)
- Parameters:
- a
- firstChar
chunkUrl(prefix)
- Parameters:
- prefix
exactMatch(key, callback)
- Parameters:
- key
- callback
findNode(query, callback)
- Parameters:
- query
- callback
findPath(query, callback)
- Parameters:
- query
- callback
mappingsFromNode(prefix, node)
- Parameters:
- prefix
- node
mappingsFromPrefix(query, callback)
- Parameters:
- query
- callback
pathToPrefix(path)
- Parameters:
- path
valuesFromNode(node)
- Parameters:
- node
valuesFromPrefix(query, callback)
- Parameters:
- query
- callback