Struct Trie

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

Data-structure for storing and querying string-like keys and associated values.

Any keys which share a common prefix are stored below a single copy of that prefix. This saves space, and also allows the longest prefix of any given key to be found.

You can read more about Radix Tries on Wikipedia.

Lots of the methods on Trie return optional values - they can be composed nicely using Option::and_then.

Implementations

impl<K, V> Trie<K, V> where K: TrieKey,

fn new() -> Trie<K, V>

Create an empty Trie.

fn get<Q>(&self, key: &Q) -> Option<&V>
where
    K: Borrow<Q>,
    Q: TrieKey + ?Sized,

Fetch a reference to the given key's corresponding value, if any.

The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.

fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
where
    K: Borrow<Q>,
    Q: TrieKey + ?Sized,

Fetch a mutable reference to the given key's corresponding value, if any.

The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.

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

Insert the given key-value pair, returning any previous value associated with the key.

fn remove<Q>(&mut self, key: &Q) -> Option<V>
where
    K: Borrow<Q>,
    Q: TrieKey + ?Sized,

Remove the value associated with the given key.

The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.

fn value_mut(&mut self) -> Option<&mut V>

Get a mutable reference to the value stored at this node, if any.

fn subtrie<'a, Q>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>>
where
    K: Borrow<Q>,
    Q: TrieKey + ?Sized,

Fetch a reference to the subtrie for a given key.

The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.

fn subtrie_mut<'a, Q>(&'a mut self, key: &Q) -> Option<SubTrieMut<'a, K, V>>
where
    K: Borrow<Q>,
    Q: TrieKey + ?Sized,

Fetch a mutable reference to the subtrie for a given key.

The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.

fn get_ancestor<'a, Q>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>>
where
    K: Borrow<Q>,
    Q: TrieKey + ?Sized,

Fetch a reference to the closest ancestor node of the given key.

If key is encoded as byte-vector b, return the node n in the tree such that n's key's byte-vector is the longest possible prefix of b, and n has a value.

Invariant: result.is_some() => result.key_value.is_some().

The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.

fn get_ancestor_value<Q>(&self, key: &Q) -> Option<&V>
where
    K: Borrow<Q>,
    Q: TrieKey + ?Sized,

Fetch the closest ancestor value for a given key.

See get_ancestor for precise semantics, this is just a shortcut.

The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type.

fn get_raw_ancestor<'a, Q>(&'a self, key: &Q) -> SubTrie<'a, K, V>
where
    K: Borrow<Q>,
    Q: TrieKey + ?Sized,

The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type

fn get_raw_descendant<'a, Q>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>>
where
    K: Borrow<Q>,
    Q: TrieKey + ?Sized,

Fetch the closest descendant for a given key.

If the key is in the trie, this is the same as subtrie.

The key may be any borrowed form of the trie's key type, but TrieKey on the borrowed form must match those for the key type

fn map_with_default<F>(&mut self, key: K, f: F, default: V)
where
    F: Fn(&mut V),

Take a function f and apply it to the value stored at key.

If no value is stored at key, store default.

Trait Implementations

impl<K, V> FromIterator<(K, V)> for Trie<K, V> where K: TrieKey,

fn from_iter<T>(iter: T) -> Trie<K, V>
where
    T: IntoIterator<Item = (K, V)>,

impl<K, V> PartialEq for Trie<K, V> where K: TrieKey, V: PartialEq,

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

impl<K: Clone, V: Clone> Clone for Trie<K, V>

fn clone(&self) -> Self

impl<K: Debug, V: Debug> Debug for Trie<K, V>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

impl<K: TrieKey, V> Default for Trie<K, V>

fn default() -> Self

Auto Trait Implementations

impl<K, V> Freeze for Trie<K, V> where TrieNode<K, V>: Freeze,

impl<K, V> RefUnwindSafe for Trie<K, V> where TrieNode<K, V>: RefUnwindSafe,

impl<K, V> Send for Trie<K, V> where TrieNode<K, V>: Send,

impl<K, V> Sync for Trie<K, V> where TrieNode<K, V>: Sync,

impl<K, V> Unpin for Trie<K, V> where TrieNode<K, V>: Unpin,

impl<K, V> UnsafeUnpin for Trie<K, V> where TrieNode<K, V>: UnsafeUnpin,

impl<K, V> UnwindSafe for Trie<K, V> where TrieNode<K, V>: UnwindSafe,

Blanket Implementations

impl<T> Any for Trie<K, V> where T: 'static + ?Sized,

fn type_id(&self) -> TypeId

impl<T> Borrow<T> for Trie<K, V> where T: ?Sized,

fn borrow(&self) -> &T

impl<T> BorrowMut<T> for Trie<K, V> where T: ?Sized,

fn borrow_mut(&mut self) -> &mut T

impl<T> CloneToUninit for Trie<K, V> where T: Clone,

unsafe fn clone_to_uninit(&self, dest: *mut u8)

impl<T> From<T> for Trie<K, V>

fn from(t: T) -> T

Returns the argument unchanged.

impl<T> ToOwned for Trie<K, V> where T: Clone,

type Owned = T;
fn to_owned(&self) -> T
fn clone_into(&self, target: &mut T)

impl<T, U> Into<U> for Trie<K, V> where U: From<T>,

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of [From]<T> for U chooses to do.

impl<T, U> TryFrom<U> for Trie<K, V> where U: Into<T>,

type Error = never;
fn try_from(value: U) -> Result<T, never>

impl<T, U> TryInto<U> for Trie<K, V> where U: TryFrom<T>,

type Error = <U as TryFrom<T>>::Error;
fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>