Class Index | File Index

Classes


Class LazyTrie


Defined in: LazyPatricia.js.

Class Summary
Constructor Attributes Constructor Name and Description
 
LazyTrie(rootURL, chunkTempl)
  Implements a lazy PATRICIA tree.
Method Summary
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)
 
 
 
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

Documentation generated by JsDoc Toolkit 2.4.0 on Thu Jun 14 2012 17:43:46 GMT-0400 (EDT)