Struct GenericTrie

pub struct GenericTrie<K, V> { /* private fields */ }

A trie for mapping sequences of keys to values.

Example

use rust_dsa::GenericTrie;

// First, we create a new trie.
let mut trie = GenericTrie::new();

// Then we can insert keys and items.
trie.insert([1, 2, 3], "foo");
trie.insert([1, 2, 4], "bar");
trie.insert([1, 2, 4, 0], "baz");

assert!(trie.contains_key(&[1, 2, 3]));
assert!(trie.contains_key(&[1, 2, 4]));
assert!(trie.contains_key(&[1, 2, 4, 0]));

// We can get the values.
assert_eq!(trie.get(&[1, 2, 3]), Some(&"foo"));
assert_eq!(trie.get(&[1, 2, 4]), Some(&"bar"));
assert_eq!(trie.get(&[1, 2]), None);

// We can iterate over the values with a given prefix.
use std::collections::HashSet;
let get_prefix: HashSet<_> = trie.get_prefix(&[1, 2, 4]).collect();
assert_eq!(get_prefix, HashSet::from([&"bar", &"baz"]));

// We can remove values.
let removed = trie.remove(&[1, 2, 3]);

assert_eq!(removed, Some("foo"));
assert!(!trie.contains_key(&[1, 2, 3]));

assert_eq!(trie.len(), 2);

Implementations

impl<K, V> GenericTrie<K, V>

pub fn new() -> GenericTrie<K, V>

Creates a new trie.

pub fn insert<I>(&mut self, key: I, value: V) -> Option<V>

where I: IntoIterator<Item = K>, K: Hash + Eq,

Inserts the key value pair into the trie, cloning each element in the key.

Returns the previous value, if it exists.

Example

use rust_dsa::GenericTrie;

let mut trie = GenericTrie::new();

trie.insert(['c', 'a', 'b'], 0);
trie.insert(['c', 'a', 'r'], 0);
trie.insert(['c'], 0);

assert!(trie.contains_key(&['c', 'a', 'b']));
assert!(trie.contains_key(&['c', 'a', 'r']));
assert!(trie.contains_key(&['c']));

pub fn insert_iterator( &mut self, key: &mut dyn Iterator<Item = K>, value: V, ) -> Option<V>

where K: Hash + Eq,

pub fn get(&self, key: &[K]) -> Option<&V>

where K: Hash + Eq,

Returns a reference to the value associated with the key, if one exists.

Example

use rust_dsa::GenericTrie;

let mut trie = GenericTrie::new();

trie.insert(['c', 'a', 'b'], 1);
trie.insert(['c', 'a', 'r'], 2);

assert_eq!(trie.get(&['c', 'a', 'b']), Some(&1));
assert_eq!(trie.get(&['c', 'a', 'r']), Some(&2));
assert_eq!(trie.get(&['c', 'a', 't']), None);

pub fn remove(&mut self, key: &[K]) -> Option<V>

where K: Hash + Eq,

Removes and returns the value associated with the key, if it exists.

Example

use rust_dsa::GenericTrie;

let mut trie = GenericTrie::new();

trie.insert([1, 2, 3], 'a');
trie.insert([1, 2, 4], 'b');

assert_eq!(trie.get(&[1, 2, 3]), Some(&'a'));
assert_eq!(trie.get(&[1, 2, 4]), Some(&'b'));

let removed = trie.remove(&[1, 2, 3]);

assert_eq!(removed, Some('a'));
assert!(!trie.contains_key(&[1, 2, 3]));

pub fn get_prefix(&self, prefix: &[K]) -> Values<'_, V>

where K: Hash + Eq,

Returns an iterator over the values whose associated keys begin with prefix.

Example

use rust_dsa::GenericTrie;

let mut trie = GenericTrie::new();

trie.insert([1, 2, 3], 'a');
trie.insert([1, 2, 3, 4], 'b');
trie.insert([1, 2], 'c');
trie.insert([1], 'd');

use std::collections::HashSet;
assert_eq!(
    trie.get_prefix(&[1, 2]).collect::<HashSet<_>>(),
    HashSet::from([&'a', &'b', &'c'])
);

pub fn contains_key(&self, key: &[K]) -> bool

where K: Hash + Eq,

Returns true if the trie contains key.

Example

use rust_dsa::GenericTrie;

let mut trie = GenericTrie::new();
trie.insert([true, true, false], 0);

assert!(trie.contains_key(&[true, true, false]));
assert!(!trie.contains_key(&[true, false]));

pub fn contains_prefix(&self, prefix: &[K]) -> bool

where K: Hash + Eq,

Returns true if the trie contains a key with the given prefix.

Example

use rust_dsa::GenericTrie;

let mut trie = GenericTrie::new();
trie.insert([true, true, false], 0);

assert!(trie.contains_prefix(&[true, true, false]));
assert!(trie.contains_prefix(&[true, true]));
assert!(trie.contains_prefix(&[true]));
assert!(!trie.contains_prefix(&[false]));
assert!(!trie.contains_prefix(&[true, false]));

pub fn len(&self) -> usize

Returns the number of elements in the trie.

Example

use rust_dsa::GenericTrie;

let mut trie = GenericTrie::new();
trie.insert([1, 2, 3], 'a');
trie.insert([1, 2], 'b');
trie.insert([1, 2, 3], 'c');

assert_eq!(trie.len(), 2);

trie.remove(&[1, 2]);

assert_eq!(trie.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the trie is empty.

Example

use rust_dsa::GenericTrie;

let mut trie = GenericTrie::new();
trie.insert([1, 2, 3], 'a');
trie.insert([1, 2], 'b');

assert!(!trie.is_empty());

trie.clear();

assert!(trie.is_empty());

pub fn clear(&mut self)

Clears the trie.

Example

use rust_dsa::GenericTrie;

let mut trie = GenericTrie::new();
trie.insert([1, 2, 3], 'a');
trie.insert([1, 2], 'b');

assert!(!trie.is_empty());

trie.clear();

assert!(trie.is_empty());

pub fn values(&self) -> Values<'_, V>

Returns an iterator over the trie’s values.

Example

use rust_dsa::GenericTrie;

let mut trie = GenericTrie::new();

trie.insert([1, 2, 3], 'a');
trie.insert([1, 2, 3, 4], 'b');
trie.insert([1, 2], 'c');
trie.insert([1], 'd');

use std::collections::HashSet;
assert_eq!(
    trie.values().collect::<HashSet<_>>(),
    HashSet::from([&'a', &'b', &'c', &'d'])
);

Trait Implementations

impl<K, V> Default for GenericTrie<K, V>

fn default() -> GenericTrie<K, V>

Returns the “default value” for a type.

impl<K, V> PartialEq for GenericTrie<K, V>

where K: Hash + Eq, V: PartialEq,

fn eq(&self, other: &GenericTrie<K, V>) -> bool

Returns true if the tries are equal.

Example

use rust_dsa::GenericTrie;

let mut a = GenericTrie::new();
a.insert(['a', 'b', 'c'], 1);
a.insert(['a', 'x'], 2);

let mut b = GenericTrie::new();
b.insert(['a', 'b', 'c'], 1);
b.insert(['a', 'x'], 2);
b.insert(['z'], 3);

assert!(a != b);

b.remove(&['z']);

assert!(a == b);

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K, V> Eq for GenericTrie<K, V>

where K: Hash + Eq, V: Eq,