File trie.lua

Functions

insertFileCummulative (trie, file) Insert into a trie all sub-strings starting at position 1 of the lines read from a file.
insertFileFull (trie, file) Insert into a trie all sub-strings of the lines read from a file.
insertFileSingle (trie, file) Insert into a trie all plain lines of a file.
insertListCummulative (trie, list) Insert into a trie all sub-strings starting at position 1 of a list of strings.
insertListFull (trie, list) Insert into a trie all sub-strings of a list of strings.
insertListSingle (trie, list) Insert into a trie a list of plain strings.
insertStringCummulative (trie, s, value) Insert into a trie all sub-strings of a string starting at position 1 (there are n = len(s) of them).
insertStringFull (trie, s, value) Insert into a trie all sub-strings of a string (there are n = len(s) * ( len(s) + 1 ) / 2 of them).
insertStringSingle (trie, s, value) Insert into a trie a plain string (not taking sub-strings into account) with an associated value.
matchStringCummulative (trie, s) Match all sub-strings of a string starting at position 1 against a trie.
matchStringFull (trie, s) Match all sub-strings of a string against a trie.
matchStringSingle (trie, s) Search for a plain string in a trie.
newTrieNode () Create a new empty trie node.
showTrie (trie, compact) Print all strings stored in a trie.
showTrie__ (node, s, compact) This function recursively advances through the trie.


Functions

insertFileCummulative (trie, file)
Insert into a trie all sub-strings starting at position 1 of the lines read from a file.

Parameters:

  • trie: A trie to insert strings into.
  • file: File to read from. All strings are associated with a value true.
insertFileFull (trie, file)
Insert into a trie all sub-strings of the lines read from a file.

Parameters:

  • trie: A trie to insert strings into.
  • file: File to read from. All strings are associated with a value true.
insertFileSingle (trie, file)
Insert into a trie all plain lines of a file.

Parameters:

  • trie: A trie to insert lines into.
  • file: File to read from. All strings are associated with a value true.
insertListCummulative (trie, list)
Insert into a trie all sub-strings starting at position 1 of a list of strings.

Parameters:

  • trie: A trie to insert strings into.
  • list: A list with strings. All sub-strings are associated with a value true.
insertListFull (trie, list)
Insert into a trie all sub-strings of a list of strings.

Parameters:

  • trie: A trie to insert strings into.
  • list: A list with strings. All sub-strings are associated with a value true.
insertListSingle (trie, list)
Insert into a trie a list of plain strings.

Parameters:

  • trie: A trie to insert strings into.
  • list: A list with strings. All strings are associated with a value true.
insertStringCummulative (trie, s, value)
Insert into a trie all sub-strings of a string starting at position 1 (there are n = len(s) of them). Example: insert(t, "Hello", value) inserts strings "H", "He", "Hel", "Hell", "Hello" with associated values value[1], value[2], ..., value[5] into trie t. Any existing values are replaced.

Parameters:

  • trie: The trie object to insert the string into.
  • s: The string to insert.
  • value: A table of length len(s), containing non-nil values associated with the sub-strings. Alternatively, value can be any non-table expression. This value is then associated with all sub-strings.
insertStringFull (trie, s, value)
Insert into a trie all sub-strings of a string (there are n = len(s) * ( len(s) + 1 ) / 2 of them). Example: insert(t, "Hello") inserts strings "H", "He", "Hel", "Hell", "Hello" with associated values value[1][1], value[1][2], ..., value[1][5], strings "e", "el", "ell", "ello" with associated values value[2][1], value[2][2], ..., value[2][4], etc into trie t. Any existing values will be replaced. If there are identical sub-strings, the final associated value is not determined.

Parameters:

  • trie: The trie object to insert the string into.
  • s: The string to insert.
  • value: A triangular table of length len(s), containing tables of non-nil values associated with the sub-strings. Alternatively, value can be a non-table type expression. This value is then associated with all sub-strings.
insertStringSingle (trie, s, value)
Insert into a trie a plain string (not taking sub-strings into account) with an associated value. An existing value is replaced.

Parameters:

  • trie: The trie object to insert the string into.
  • s: The string to insert.
  • value: A non-nil value associated with the string.
matchStringCummulative (trie, s)
Match all sub-strings of a string starting at position 1 against a trie.

Parameters:

  • trie: The trie object.
  • s: String to search for.

Return value:

    If sub-strings have been identified, return a list with values associated with the matching strings. If no matching sub-strings have been identified, return nil.
matchStringFull (trie, s)
Match all sub-strings of a string against a trie.

Parameters:

  • trie: The trie object.
  • s: String to search for.

Return value:

    If sub-strings have been identified, return a list with values associated with the matching strings. If no matching sub-strings have been identified, return nil.
matchStringSingle (trie, s)
Search for a plain string in a trie.

Parameters:

  • trie: The trie object.
  • s: String to search for.

Return value:

    If the strings is found, return the associated value. If the string could not be found, return nil.
newTrieNode ()
Create a new empty trie node. An empty node is a table { next = {}, value = nil }.

Return value:

    An empty trie node.
showTrie (trie, compact)
Print all strings stored in a trie. An exclamation mark indicates identified strings.

Parameters:

  • trie: The trie object to show.
  • compact: boolean flag: Print strings in compact format?

See also:

showTrie__ (node, s, compact)
This function recursively advances through the trie. It prints all characters valid at a node. An underscore indicates the end of an identified string.

Parameters:

  • node: A trie object.
  • s: String of characters preceeding the current node.
  • compact: boolean flag: Print patterns in compact format?

Usage:

    Internal function.

See also:

Valid XHTML 1.0!