ternary-tree-wasm

这是一个Rust ternary-tree crate的WebAssembly绑定。

三叉搜索树（TST）是一种数据结构，它以树的形式存储键/值对。键是一个字符串，其字符放置在树节点中。每个节点可能有三个子节点（因此得名）：一个 左 子节点，一个 中 子节点和一个 右 子节点。

在TST中进行搜索时，会将键中的当前字符与当前节点的字符进行比较

• 如果两者匹配，搜索会遍历中间子节点，并继续到键中的下一个字符
• 如果键字符小于节点字符，搜索将简单地通过左子节点进行，并继续寻找相同的键字符
• 相应地，如果键字符大于节点字符，搜索将简单地通过右子节点进行

数据结构和其算法在Dr.Dobb's Ternary Search Trees文章中解释得很好。

以下树是在按照以下顺序插入以下键后得到的TST："aba"，"ab"，"bc"，"ac"，"abc"，"a"，"b"，"aca"，"caa"，"cbc"，"bac"，"c"，"cca"，"aab"，"abb"，"aa"（参见下面代码生成的tst.dot）

带有勾选框 "☑" 的节点表示存储了值的节点（它对应于键的最后一个字符）。空框 "☐" 表示节点没有值。

TST可以用作映射，但它允许更灵活的方式检索与键关联的值。此包提供了四种基本方式来遍历TST的值

• 使用tree.visit(closure, direction)对树中存储的所有值应用闭包（与常规映射相同）。请参阅原始的iter文档 🦀
• 使用tree.complete(prefix, closure, direction)对以某些前缀开始的值应用闭包（即 完成 某个前缀）。请参阅原始的iter_complete文档 🦀
• 对所有键值接近某些字符串（汉明距离）的值应用闭包，使用 tree.neighbor(target, range, closure, direction)。查看原始的 iter_neighbor 文档 🦀
• 使用 tree.crossword(pattern, joker, closure, direction) 对与字符串匹配的某些占位符（例如 "a?c"）的值应用闭包。查看原始的 iter_crossword 文档 🦀

查看 文档 以了解带有实时示例的快速 API 演示。以下代码也可能让您对该软件包有所了解。

//Load the package from npm through Unpkg.
//You need init, Tst and Direction.
import init, {Tst, Direction} from
    "https://unpkg.com/ternary-tree-wasm/ternary_tree_wasm.js";

//Use it in an async function. Do not forget to call init.
async function run() {

    await init();

    //Create a new empty ternary search tree.
    let tree = Tst.new();
    let go = Direction;

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

    //Add 'matching' key value couples by deriving 'abc' strings.
    for (const d of data) {
        tree.insert("🗝" + d, "📦" + d);
    }

    let count = tree.count(); //count should be 16

    //Use 'get' to retrieve the value of some key.
    //value should be "📦abc"
    let value = tree.get("🗝abc");

    //Use 'remove' to delete a key ; if the key exists, the value
    //associated with the key is returned.
    value = tree.remove("🗝abc"); //value should be "📦abc"
    count = tree.count(); //count should be 15

    //Request for a key that does not exist returns null.
    value = tree.get("🗝abc"); //value should be null

    let array = [];

    //Create a closure that will be called for all key value pairs
    let push_all_items = function(key, value) {
        array.push(`${key}=${value}`);
    };

    //If seeing more key value pairs is not needed, returning true
    //from the closure will stop walking the tree.
    let push_two_items = function(key, value) {
        array.push(`${key}=${value}`);

        let should_break = array.length >= 2;

        return should_break;
    };

    //Use visit to call the closure on all key value pairs.
    //Use Forward to get keys in alphabetical order and Backward to get
    //them in reverse order.
    tree.visit(push_all_items, go.Forward);

    //array should contain all keys and values in alphabetical order :
    //"🗝a=📦a","🗝aa=📦aa", [...], "🗝cbc=📦cbc","🗝cca=📦cca"

    array = [];

    //Use Backaward to get the last two items of the tree.
    tree.visit(push_two_items, go.Backward);

    //array should be "🗝cca=📦cca","🗝cbc=📦cbc"

    array = [];

    //Use complete with some prefix string to call the closure on all
    //keys beginning with this prefix.
    tree.complete("🗝ab", push_all_items, go.Forward);

    //array should contain "🗝aba=📦aba", "🗝abb=📦abb"
    //Note that "🗝ab=📦ab" is not present because there is nothing to
    //complete (a prefix of some key can not be the whole key).

    array = [];

    //Use neighbor with some "target" key and a "range" to call the
    //closure on all keys close to the target key (think of range as the
    //number of errors allowed).
    tree.neighbor("🗝abc", 1, push_all_items, go.Forward);

    //array should be
    //"🗝ab=📦ab", "🗝aba=📦aba", "🗝abb=📦abb", "🗝cbc=📦cbc"

    array = [];

    //Use crossword with some joker in the key to call the closure on
    //all matching keys. You choose the joker character, and it will
    //match excatly one key character.
    tree.crossword("🗝?a?", "?", push_all_items, go.Forward);

    //array should be "🗝aab=📦aab", "🗝bac=📦bac", "🗝caa=📦caa"

    //Use pretty_print to generate a dot description of the tree.
    let tree_dot = tree.pretty_print();

    //tee_dot should contain a dot (from Graphviz tools) description of
    //the tree.

    //Use clear to remove all keys and values.
    tree.clear();

    count = tree.count(); //count should be 0
}

run();

许可证：BSD-3-Clause