11 releases
0.5.1 | Jul 29, 2023 |
---|---|
0.5.0 | Oct 24, 2022 |
0.4.1 | Oct 7, 2022 |
0.3.3 | Sep 23, 2022 |
0.1.0 | Oct 22, 2021 |
#1055 in Data structures
245KB
1K
SLoC
trying
Provides a simple Trie implementation for storing "keys" composed of "atoms".
The trie imposes restrictions on the key, atom and value types:
- keys must be: Clone + Default + Ord + FromIterator (aggregate trait: TrieKey)
- atoms must be: Copy + Default + PartialEq + Ord (aggregate trait: TrieAtom)
- values must be: Default (aggregate trait: TrieValue)
(where A represents the Atom type that the key will be represented as)
With these restrictions in place, the trie implements a reasonably efficient mechanism for:
- prefix matching
- representing large quantities of data with common prefixes
- finding shortest unique prefix
- finding alternative values
- finding longest common prefixes
For Example:
use trying::trie::TrieVec;
use unicode_segmentation::UnicodeSegmentation;
// Declare a trie which will store &str keys
// with usize values.
let mut trie = TrieVec::<&str, usize>::new();
let s = "a̐éö̲\r\n";
let input = s.graphemes(true);
// Insert our graphemes into the trie
trie.insert(input.clone());
// Anything which implements IntoIterator<Item=&str> can now be used
// to interact with our Trie
assert!(trie.contains(input.clone()));
assert!(trie.remove(input.clone()).is_none());
assert!(!trie.contains(input));
If you don't need prefix matching, then a HashMap is almost always a better choice than a trie...
Installation
[dependencies]
trying = "0.5"
License
Apache 2.0 licensed. See LICENSE for details.