std.prototype 1.0.1

• Index

Contents

• Objects
• Metamethods
• Module Functions

Modules

• std.prototype
• std.prototype.container
• std.prototype.object
• std.prototype.set
• std.prototype.strbuf
• std.prototype.trie

Module std.prototype.trie

Trie Prototype.

This module returns a table of trie operators, as well as the prototype for a Trie container object.

This is not a search tree, but rather a radix tree to efficiently store and retrieve values stored with a path as a key, such as a multi-key keytable. Although it does have iterators for walking the trie with various algorithms.

In addition to the functionality described here, Trie containers also have all the methods and metamethods of the prototype.container.prototype (except where overridden here),

Prototype Chain

table
 `-> Container
      `-> Trie

Objects

prototype

Trie prototype object.

Metamethods

prototype:__index (i)	Deep retrieval.
prototype:__newindex (i[, v])	Deep insertion.

Module Functions

clone (tr, nometa)	Make a deep copy of a trie or table, including any metatables.
ileaves (tr)	Trie iterator which returns just numbered leaves, in order.
inodes (tr)	Trie iterator over numbered nodes, in order.
leaves (t)	Trie iterator which returns just leaves.
merge (t, u)	Destructively deep-merge one trie into another.
nodes (tr)	Trie iterator over all nodes.

Objects

prototype

Trie prototype object.

Fields:

• _type string object name (default "Trie")

See also:

prototype.container.prototype

Usage:

 local trie = require "std.prototype.trie"
 local Trie = trie.prototype
 local tr = Trie {}
 tr[{"branch1", 1}] = "leaf1"
 tr[{"branch1", 2}] = "leaf2"
 tr[{"branch2", 1}] = "leaf3"
 print (tr[{"branch1"}])      --> Trie {leaf1, leaf2}
 print (tr[{"branch1", 2}])   --> leaf2
 print (tr[{"branch1", 3}])   --> nil
 --> leaf1	leaf2	leaf3
 for leaf in trie.leaves (tr) do
   io.write (leaf .. "\t")
 end

Metamethods

prototype:__index (i)

Deep retrieval.

Parameters:

• i non-table, or list of keys {i1, ...i_n}

Returns:

tr[i1]...[i_n] if i is a key list, tr[i] otherwise

Usage:

del_other_window = keymap[{"C-x", "4", KEY_DELETE}]

prototype:__newindex (i[, v])

Deep insertion.

Parameters:

• i non-table, or list of keys {i1, ...i_n}
• v value (optional)

Usage:

function bindkey (keylist, fn) keymap[keylist] = fn end

Module Functions

clone (tr, nometa)

Make a deep copy of a trie or table, including any metatables.

Parameters:

• tr table trie or trie-like table
• nometa boolean if non-nil don't copy metatables

Returns:

prototype or table a deep copy of tr

See also:

prototype.object.clone

Usage:

 tr = {"one", {two=2}, {{"three"}, four=4}}
 copy = clone (tr)
 copy[2].two=5
 assert (tr[2].two == 2)

ileaves (tr)

Trie iterator which returns just numbered leaves, in order.

Parameters:

• tr prototype or table trie or trie-like table

Returns:

1. function iterator function
2. prototype or table the trie tr

See also:

• inodes
• leaves

Usage:

 --> t = {"one", "three", "five"}
 for leaf in ileaves {"one", {two=2}, {{"three"}, four=4}}, foo="bar", "five"}
 do
   t[#t + 1] = leaf
 end

inodes (tr)

Trie iterator over numbered nodes, in order.

The iterator function behaves like nodes, but only traverses the array part of the nodes of tr, ignoring any others.

Parameters:

• tr prototype or table trie or trie-like table to iterate over

Returns:

1. function iterator function
2. trie or table the trie, tr

See also:

nodes

leaves (t)

Trie iterator which returns just leaves.

Parameters:

• t table trie or trie-like table

Returns:

1. function iterator function
2. table t

See also:

• ileaves
• nodes

Usage:

 for leaf in leaves {"one", {two=2}, {{"three"}, four=4}}, foo="bar", "five"}
 do
   t[#t + 1] = leaf
 end
 --> t = {2, 4, "five", "foo", "one", "three"}
 table.sort (t, lambda "=tostring(_1) < tostring(_2)")

merge (t, u)

Destructively deep-merge one trie into another.

Parameters:

• t table destination trie
• u table table with nodes to merge

Returns:

table t with nodes from u merged in

Usage:

merge (dest, {{exists=1}, {{not = {present = { inside = "dest" }}}}})

nodes (tr)

Trie iterator over all nodes.

The returned iterator function performs a depth-first traversal of tr, and at each node it returns {node-type, trie-path, trie-node} where node-type is branch, join or leaf; trie-path is a list of keys used to reach this node, and trie-node is the current node.

Note that the trie-path reuses the same table on each iteration, so you must table.clone a copy if you want to take a snap-shot of the current state of the trie-path list before the next iteration changes it.

Parameters:

• tr prototype or table trie or trie-like table to iterate over

Returns:

1. function iterator function
2. prototype or table the trie, tr

See also:

inodes

Usage:

 -- trie = +-- node1
 --        |    +-- leaf1
 --        |    '-- leaf2
 --        '-- leaf 3
 trie = Trie { Trie { "leaf1", "leaf2"}, "leaf3" }
 for node_type, path, node in nodes (trie) do
   print (node_type, path, node)
 end
 --> "branch"   {}      {{"leaf1", "leaf2"}, "leaf3"}
 --> "branch"   {1}     {"leaf1", "leaf2")
 --> "leaf"     {1,1}   "leaf1"
 --> "leaf"     {1,2}   "leaf2"
 --> "join"     {1}     {"leaf1", "leaf2"}
 --> "leaf"     {2}     "leaf3"
 --> "join"     {}      {{"leaf1", "leaf2"}, "leaf3"}
 os.exit (0)