Struct Trie

Source

pub struct Trie<K: Eq + Ord + Clone, V> { /* private fields */ }

Expand description

Prefix tree object, contains 1 field for the root node of the tree

Implementations§

Source §

impl<K: Eq + Ord + Clone, V: Clone> Trie<K, V>

Source

pub fn new() -> Self

Creates a new Trie object

§Example

use ptrie::Trie;

let t = Trie::<char, String>::new();

Source

pub fn contains_key<I: Iterator<Item = K>>(&self, key: I) -> bool

Looks for the key in trie

§Example

use ptrie::Trie;

let mut t = Trie::new();
let data = "test".bytes();
let another_data = "notintest".bytes();
assert!(!t.contains_key(data.clone()));
t.insert(data.clone(), 42);

assert!(!t.is_empty());
assert!(t.contains_key(data));
assert!(!t.contains_key(another_data));

Source

pub fn get<I: Iterator<Item = K>>(&self, key: I) -> Option<&V>

Gets the value from the tree by key

§Example

use ptrie::Trie;

let mut t = Trie::new();
let data = "test".bytes();
let another_data = "notintest".bytes();
assert_eq!(t.get(data.clone()), None);
t.insert(data.clone(), 42);

assert_eq!(t.get(data), Some(42).as_ref());
assert_eq!(t.get(another_data), None);

Source

pub fn get_mut<I: Iterator<Item = K>>(&mut self, key: I) -> Option<&mut V>

Gets the mutable value from the tree by key

§Example

use ptrie::Trie;

let mut t = Trie::new();
let data = "test".bytes();
let another_data = "notintest".bytes();
assert_eq!(t.get_mut(data.clone()), None);
t.insert(data.clone(), 42);
if let Some(value) = t.get_mut(data.clone()) {
  *value += 1;
}
assert_eq!(t.get_mut(data), Some(43).as_mut());

Source

pub fn set_value<I: Iterator<Item = K>>( &mut self, key: I, value: V, ) -> Result<(), TrieError>

Sets the value pointed by a key

§Example

use ptrie::Trie;

let mut t = Trie::new();
let data = "test".bytes();
let another_data = "notintest".bytes();

t.insert(data.clone(), 42);

assert_eq!(t.get(data.clone()), Some(42).as_ref());
assert!(t.set_value(data.clone(), 43).is_ok());
assert_eq!(t.get(data), Some(43).as_ref());
assert!(t.set_value(another_data, 39)
    .map_err(|e| assert!(e.to_string().starts_with("Key not found")))
    .is_err());

Source

pub fn find_prefixes<I: Iterator<Item = K>>(&self, key: I) -> Vec<&V>

Returns a list of all prefixes in the trie for a given string, ordered from smaller to longer.

§Example

use ptrie::Trie;

let mut trie = Trie::new();
trie.insert("abc".bytes(), "ABC");
trie.insert("abcd".bytes(), "ABCD");
trie.insert("abcde".bytes(), "ABCDE");

let prefixes = trie.find_prefixes("abcd".bytes());
assert_eq!(prefixes, vec![&"ABC", &"ABCD"]);
assert_eq!(trie.find_prefixes("efghij".bytes()), Vec::<&&str>::new());
assert_eq!(trie.find_prefixes("abz".bytes()), Vec::<&&str>::new());

Source

pub fn find_longest_prefix<I: Iterator<Item = K>>(&self, key: I) -> Option<&V>

Finds the longest prefix in the Trie for a given string.

§Example

use ptrie::Trie;

let mut trie = Trie::default();
assert_eq!(trie.find_longest_prefix("http://purl.obolibrary.org/obo/DOID_1234".bytes()), None);
trie.insert("http://purl.obolibrary.org/obo/DOID_".bytes(), "doid");
trie.insert("http://purl.obolibrary.org/obo/".bytes(), "obo");

assert_eq!(trie.find_longest_prefix("http://purl.obolibrary.org/obo/DOID_1234".bytes()), Some("doid").as_ref());
assert_eq!(trie.find_longest_prefix("http://purl.obolibrary.org/obo/1234".bytes()), Some("obo").as_ref());
assert_eq!(trie.find_longest_prefix("notthere".bytes()), None.as_ref());
assert_eq!(trie.find_longest_prefix("httno".bytes()), None.as_ref());

Source

pub fn find_longest_prefix_len<I: Iterator<Item = K>>( &self, key: I, ) -> Option<(usize, &V)>

Finds the longest prefix and it’s length in the Trie for a given string.

§Example

use ptrie::Trie;

let mut trie = Trie::default();
assert_eq!(trie.find_longest_prefix_len("http://purl.obolibrary.org/obo/DOID_1234".bytes()), None);
trie.insert("http://purl.obolibrary.org/obo/DOID_".bytes(), "doid");
trie.insert("http://purl.obolibrary.org/obo/".bytes(), "obo");

assert_eq!(trie.find_longest_prefix_len("http://purl.obolibrary.org/obo/DOID_1234".bytes()), Some((36, &"doid")));
assert_eq!(trie.find_longest_prefix_len("http://purl.obolibrary.org/obo/1234".bytes()), Some((31, &"obo")));
assert_eq!(trie.find_longest_prefix_len("notthere".bytes()), None);
assert_eq!(trie.find_longest_prefix_len("httno".bytes()), None);

Source

pub fn find_postfixes<I: Iterator<Item = K>>(&self, prefix: I) -> Vec<&V>

Returns a list of all strings in the Trie that start with the given prefix.

§Example

use ptrie::Trie;

let mut trie = Trie::new();
trie.insert("app".bytes(), "App");
trie.insert("apple".bytes(), "Apple");
trie.insert("applet".bytes(), "Applet");
trie.insert("apricot".bytes(), "Apricot");

let strings = trie.find_postfixes("app".bytes());
assert_eq!(strings, vec![&"App", &"Apple", &"Applet"]);
assert_eq!(trie.find_postfixes("bpp".bytes()), Vec::<&&str>::new());
assert_eq!(trie.find_postfixes("apzz".bytes()), Vec::<&&str>::new());

Source

pub fn is_empty(&self) -> bool

Checks if the Trie is empty

§Example

use ptrie::Trie;

let t = Trie::<char, f64>::new();
assert!(t.is_empty());

Source

pub fn clear(&mut self)

Clears the trie

§Example

use ptrie::Trie;

let mut t = Trie::new();
let data = "test".bytes();

t.insert(data, String::from("test"));
t.clear();
assert!(t.is_empty());

Source

pub fn insert<I: Iterator<Item = K>>(&mut self, key: I, value: V)

Adds a new key to the Trie

§Example

use ptrie::Trie;

let mut t = Trie::new();
let data = "test".bytes();
t.insert(data.clone(), 42);
t.insert(data, 42);
t.insert("test2".bytes(), 43);
assert!(!t.is_empty());

Source

pub fn remove<I: Iterator<Item = K>>(&mut self, key: I) -> Option<V>

Removes a key from the trie, if it exists.

§Example

use ptrie::Trie;

let mut t = Trie::new();
let data = "test".bytes();
t.insert(data.clone(), 42);
assert!(t.contains_key(data.clone()));

t.remove(data.clone());
assert!(!t.contains_key(data));
t.remove("toto".bytes());

Source

pub fn iter(&self) -> TrieIterator<'_, K, V> ⓘ

Iterate the nodes in the Trie

§Example

use ptrie::Trie;

let mut t = Trie::new();
let test = "test".bytes();
let tes = "tes".bytes();

t.insert(test.clone(), String::from("test"));
t.insert(tes.clone(), String::from("tes"));
for (k, v) in t.iter() {
    assert!(std::str::from_utf8(&k).unwrap().starts_with("tes"));
    assert!(v.starts_with("tes"));
}