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

#433 in Data structures

Apache-2.0

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:

(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...

Crates.io

API Docs

Installation

[dependencies]
trying = "0.5"

Features are available.

License

Apache 2.0 licensed. See LICENSE for details.

Dependencies