5 releases
0.2.3 | Feb 16, 2021 |
---|---|
0.2.2 | Feb 15, 2021 |
0.2.1 | Feb 15, 2021 |
0.2.0 | Feb 15, 2021 |
0.1.0 | Feb 11, 2021 |
#1813 in Data structures
21 downloads per month
30KB
626 lines
set-trie
Fast subset and superset queries based on tries. If you have lookup-based queries, K -> V
, but instead of looking for
an exact match with K, you want all K
's which are a subset or superset of your query, then look no further.
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"]);
}
Restrictions
Although currently not implemented in the type system, due to a lack of a trait bound over sorted iterators, set tries require all queries to be sorted. Failing to sort the query or key will result in nonsensical results:
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());
}
Features
- Subsets and supersets are lazily evaluated, through an iterative DFS algorithm.
- Convenient
entry
API.
TODO
- Implement benchmarks (low priority, PR welcome)
- Memorize seen keys to save 1 binary search (requires benchmarks to compare performance)
No runtime deps
~0–1.3MB
~17K SLoC