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 SetTrie;
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 SetTrie;
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)