ternary-tree-wasm

A WebAssembly binding to Rust ternary-tree crate.

A Ternary Search Tree (TST) is a data structure which stores key/value pairs in a tree. The key is a string, and its characters are placed in the tree nodes. Each node may have three children (hence the name): a left child, a middle child and a right child.

A search in a TST compares the current character in the key with the character of the current node:

• If both matches, the search traverses the middle child, and proceed to the next character in the key
• If the key character is less than the node one, the search simply goes through the left child, and keep looking for the same key character
• Respectively, if the key character is greater than the node one, the search simply goes through the right child

The data structure and its algorithm are explained very well in Dr.Dobb's Ternary Search Trees article.

The following tree is the TST we get after inserting the following keys in order: "aba", "ab", "bc", "ac", "abc", "a", "b", "aca", "caa", "cbc", "bac", "c", "cca", "aab", "abb", "aa" (see tst.dot produced by code below)

A checked box "☑" denotes a node which stores a value (it corresponds to the last character of a key). An empty box "☐" means that the node has no value.

A TST can be used as a map, but it allows more flexible ways to retrieve values associated with keys. This package provides four basic ways to iterate over the values of a TST:

• Apply a closure to all values stored in the tree (same as a regular map) with tree.visit(<closure>, <direction>). See original iter doc 🦀
• Apply a closure to all values whose keys begin with some prefix (i.e. complete some prefix) with tree.complete(<prefix>, <closure>, <direction>). See original iter_complete doc 🦀
• Apply a closure to all values whose keys are close to some string (Hamming distance) with tree.neighbor(<neighbor_key>, <range>, <closure>, <direction>). See original iter_neighbor doc 🦀
• Apply a closure to all values whose keys match a string with some joker (e.g. "a?c") with tree.crossword(<pattern>, <joker>, <closure>, <direction>). See original iter_crossword doc 🦀

The closure receives two arguments, the key and value of found nodes, and is applied to each matching node in alphabetical order with Direction.Forward and reverse order with Direction.Backward. If for some reason, there is no need to iterate anymore, returning true ends the process. A typical closure looks like this :

```js let array = [];

    let push_two_items = function (key, value) {

            array.push(`${key}=${value}`);

            let should_break = array.length >= 2;

            return should_break;
    };

```

The following lines may give you a foretaste of this package

```js const rust = import('./pkg');

rust.then( m => {

    let data = ["aba", "ab", "bc", "ac", "abc", "a", "b", "aca",
        "caa", "cbc", "bac", "c", "cca", "aab", "abb", "aa"];

    let tree = m.Tst.new();

    for (const d of data) {

            tree.insert('🗝'+d, '📦'+d);
    }

    let array = [];

    let push_two_items = function (key, value) {

            array.push(`${key}=${value}`);

            let should_break = array.length >= 2;

            return should_break;
    };

    res = tree.visit(push_two_items, m.Direction.Forward);
    //array should be ['🗝a=📦a','🗝aa=📦aa']

    array = [];
    res = tree.visit(push_two_items, m.Direction.Backward);
    //array should be ['🗝cca=📦cca','🗝cbc=📦cbc']);

})

See also this package Github Page for more examples. ```

License: BSD-3-Clause