set-trie

基于 trie 的快速子集和超集查询。如果你有基于查找的查询， K -> V，但不是寻找与 K 的完全匹配，而是想要所有是查询的子集或超集的 K，那么就无需再寻找了。

use set_trie::SetTrie;

fn main() {
    let mut employees = SetTrie::new();
    employees.insert(&["accounting", "banking"], "Daniels");
    employees.insert(&["accounting", "banking", "crime"], "Stevens");

    assert_eq!(employees.subsets(&[&"accounting", &"banking", &"crime"]).collect::<Vec<_>>(), vec![&"Daniels", &"Stevens"]);
    assert_eq!(employees.subsets(&[&"accounting", &"banking"]).collect::<Vec<_>>(), vec![&"Daniels"]);
    assert_eq!(employees.supersets(&[&"accounting"]).collect::<Vec<_>>(), vec![&"Daniels", &"Stevens"]);
}

限制

尽管当前类型系统中没有实现，因为缺少排序迭代器的 trait 约束，集合 trie 需要所有查询都是排序的。未对查询或键进行排序将导致结果无意义

use set_trie::SetTrie;

fn main() {
    let mut trie = SetTrie::new();
    trie.insert(&[2, 3], "Foo");
    trie.insert(&[1, 2], "Bar");

    // although we'd expect this to contain &"Bar".
    assert_eq!(trie.subsets(&[&2, &1]).collect::<Vec<_>>(), Vec::<&&str>::new()); 
}

特性

• 子集和超集通过迭代 DFS 算法进行懒加载评估。
• 方便的 entry API。

待办事项

• 实现基准测试（优先级低，欢迎PR）
• 记住已看到的键以节省 1 次二分搜索（需要基准测试以比较性能）