Struct Trie

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

A trie for mapping strs to values.

Example

use rust_dsa::Trie;

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

// Then we can insert keys and items.
trie.insert("foo", 1);
trie.insert("bar", 2);
trie.insert("ba", 3);

assert!(trie.contains_key("foo"));
assert!(trie.contains_key("bar"));
assert!(trie.contains_key("ba"));

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

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

// We can remove values.
let removed = trie.remove("ba");

assert_eq!(removed, Some(3));
assert!(!trie.contains_key("ba"));

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

Implementations

impl<V> Trie<V>

pub fn new() -> Trie<V>

Creates a new trie.

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

Inserts the key value pair into the trie.

Returns the previous value, if it exists.

Example

use rust_dsa::Trie;

let mut trie = Trie::new();

trie.insert("cab", 0);
trie.insert("car", 0);
trie.insert("c", 0);

assert!(trie.contains_key("cab"));
assert!(trie.contains_key("car"));
assert!(trie.contains_key("c"));

pub fn get(&self, key: &str) -> Option<&V>

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

Example

use rust_dsa::Trie;

let mut trie = Trie::new();

trie.insert("cab", 1);
trie.insert("car", 2);

assert_eq!(trie.get("cab"), Some(&1));
assert_eq!(trie.get("car"), Some(&2));
assert_eq!(trie.get("cat"), None);

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

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

Example

use rust_dsa::Trie;

let mut trie = Trie::new();

trie.insert("foo", 1);
trie.insert("bar", 2);

assert_eq!(trie.get("foo"), Some(&1));
assert_eq!(trie.get("bar"), Some(&2));

let removed = trie.remove("foo");

assert_eq!(removed, Some(1));
assert!(!trie.contains_key("foo"));

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

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

Example

use rust_dsa::Trie;

let mut trie = Trie::new();

trie.insert("abc", 1);
trie.insert("abcd", 2);
trie.insert("ab", 3);
trie.insert("a", 4);

use std::collections::HashSet;
assert_eq!(
    trie.get_prefix("ab").collect::<HashSet<_>>(),
    HashSet::from([&1, &2, &3])
);

pub fn contains_key(&self, key: &str) -> bool

Returns true if the trie contains key.

Example

use rust_dsa::Trie;

let mut trie = Trie::new();
trie.insert("cat", 0);

assert!(trie.contains_key("cat"));
assert!(!trie.contains_key("ca"));

pub fn contains_prefix(&self, prefix: &str) -> bool

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

Example

use rust_dsa::Trie;

let mut trie = Trie::new();
trie.insert("xyz", 0);

assert!(trie.contains_prefix("xyz"));
assert!(trie.contains_prefix("xy"));
assert!(trie.contains_prefix("x"));
assert!(!trie.contains_prefix("y"));
assert!(!trie.contains_prefix("xz"));

pub fn len(&self) -> usize

Returns the number of elements in the trie.

Example

use rust_dsa::Trie;

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

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

trie.remove("ab");

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

pub fn is_empty(&self) -> bool

Returns true if the trie is empty.

Example

use rust_dsa::Trie;

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

assert!(!trie.is_empty());

trie.clear();

assert!(trie.is_empty());

pub fn clear(&mut self)

Clears the trie.

Example

use rust_dsa::Trie;

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

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::Trie;

let mut trie = Trie::new();

trie.insert("abc", 1);
trie.insert("abcd", 2);
trie.insert("ab", 3);
trie.insert("a", 4);

use std::collections::HashSet;
assert_eq!(
    trie.values().collect::<HashSet<_>>(),
    HashSet::from([&1, &2, &3, &4])
);

Trait Implementations

impl<V> Default for Trie<V>

fn default() -> Trie<V>

Returns the “default value” for a type.

impl<V, const N: usize> From<[(&'static str, V); N]> for Trie<V>

fn from(array: [(&'static str, V); N]) -> Trie<V>

Creates a trie from an array of key value pairs.

Example

use rust_dsa::Trie;

let trie = Trie::from([("foo", 1), ("bar", 2), ("baz", 3)]);
assert_eq!(trie.get("foo"), Some(&1));
assert_eq!(trie.get("bar"), Some(&2));
assert_eq!(trie.get("baz"), Some(&3));
assert_eq!(trie.get("boo"), None);

impl<V> FromIterator<(&'static str, V)> for Trie<V>

fn from_iter<T: IntoIterator<Item = (&'static str, V)>>(iter: T) -> Trie<V>

Creates a value from an iterator.

impl<V> PartialEq for Trie<V>

where V: PartialEq,

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

Tests for self and other values to be equal, and is used by ==.

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<V> Eq for Trie<V>

where V: Eq,