Struct jupiter::idb::trie::Trie

pub struct Trie<T> { /* private fields */ }

Represents a trie to map strings to values of type T.

Implementations

impl<T> Trie<T>

pub fn new() -> Self

Creates a new and empty trie.

Example

let trie : Trie<i32> = Trie::new();

assert_eq!(trie.num_nodes(), 0);
assert_eq!(trie.num_entries(), 0);

pub fn insert(&mut self, key: &str, value: T)

Inserts the given value for the given key.

Note that this is optimized for performance. Therefore this doesn’t check if the value is already present for the key. If the exactly same was already present it will still be added again. See Trie::insert_unique for a way of only inserting entries once.

Example

let mut trie = Trie::new();

trie.insert("a", 1);
assert_eq!(trie.num_nodes(), 1);
assert_eq!(trie.num_entries(), 1);

// Duplicate values can be inserted...
trie.insert("a", 1);
assert_eq!(trie.num_nodes(), 1);
assert_eq!(trie.num_entries(), 2);

// The tree grows as required...
trie.insert("ab", 1);
assert_eq!(trie.num_nodes(), 2);
assert_eq!(trie.num_entries(), 3);

pub fn query_values(&self, query: impl AsRef<str>) -> Option<&Vec<T>>

Retrieves the values stored for a given string.

Note that Trie::query provides a boilerplate API which directly returns an iterator and therefore doesn’t require unwrapping the Option.

Example

let mut trie = Trie::new();

// A simple value can be retrieved...
trie.insert("a", 1);
assert_eq!(trie.query_values("a").unwrap()[0], 1);

// A duplicate value can be retrieved...
trie.insert("a", 2);
assert_eq!(trie.query_values("a").unwrap()[0], 1);
assert_eq!(trie.query_values("a").unwrap()[1], 2);

// A "child-entry" can be retrieved and leaves the actual entries intact...
trie.insert("ab", 3);
assert_eq!(trie.query_values("a").unwrap()[0], 1);
assert_eq!(trie.query_values("a").unwrap()[1], 2);
assert_eq!(trie.query_values("ab").unwrap()[0], 3);

pub fn query(&self, query: impl AsRef<str>) -> OptionalIter<'_, T>

Provides a boilerplate way of querying values.

Example

let mut trie = Trie::new();

trie.insert("a", 1);
assert_eq!(trie.query("a").next().unwrap(), &1);
assert_eq!(trie.query("unknown").next().is_none(), true);

pub fn prefix_query(&self, prefix: &str) -> PrefixIter<'_, T>

Returns an iterator which performs a depth first search yielding the complete sub tree below the given prefix.

Example

let mut trie = Trie::new();
trie.insert("abc", 1);
trie.insert("abc", 2);
trie.insert("abcd", 3);

let results: Vec<&i32> = trie.prefix_query("abc").collect();
assert_eq!(results, vec![&1, &2, &3]);

pub fn allocated_size(&self) -> usize

Returns the amount of memory (in bytes) used by this trie.

pub fn num_entries(&self) -> usize

Returns the number of entries stored in this trie.

Example

let mut trie = Trie::new();

trie.insert("a", 1);
assert_eq!(trie.num_entries(), 1);

// Duplicate values can be inserted and are counted as extra entry.
trie.insert("a", 1);
assert_eq!(trie.num_entries(), 2);

pub fn num_nodes(&self) -> usize

Returns the number of nodes in this trie.

Example

let mut trie = Trie::new();

// A node per character is created...
trie.insert("abc", 1);
assert_eq!(trie.num_nodes(), 3);

// Re-using an existing path won't add new nodes.
trie.insert("abc", 1);
assert_eq!(trie.num_nodes(), 3);

pub fn scan<C>(&self, callback: &mut C)

where C: FnMut(&str, &T),

Performs a depth first walk and invokes the callback for each entry in the Trie.

Note that this might be quite a long running task and there is no way of interrupting it (as no iterator is used). Therefore this is should only be used for data management tasks and not for lookups of any kind.

Also note that this uses a stack based recursion. Therefore this must not be used if keys in this Trie are unhealthy long.

Example

let mut trie = Trie::new();

// A node per character is created...
trie.insert("abc", 1);
trie.insert("abcd", 2);

let mut counter = 0;
trie.scan(&mut |_,_| counter += 1);
assert_eq!(counter, 2);

impl<T: PartialEq> Trie<T>

pub fn insert_unique(&mut self, key: &str, value: T)

Inserts the given value for the given key.

In contrast to Trie::insert this checks if the value is already present for the key and won’t insert a duplicate. again.

Example

let mut trie = Trie::new();

trie.insert_unique("a", 1);
assert_eq!(trie.num_nodes(), 1);
assert_eq!(trie.num_entries(), 1);

// Duplicate values will not be inserted...
trie.insert_unique("a", 1);
assert_eq!(trie.num_nodes(), 1);
assert_eq!(trie.num_entries(), 1);

Trait Implementations

impl<T> Default for Trie<T>

fn default() -> Self

Returns the “default value” for a type.