Struct radix_trie::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,

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

Create an empty Trie.

pub 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.

pub 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.

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

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

pub 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.

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

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

pub 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.

pub 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.

pub 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.

pub 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.

pub 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

pub 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

pub 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: Clone, V: Clone> Clone for Trie<K, V>

fn clone(&self) -> Trie<K, V>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

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

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

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

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)>,

Creates a value from an iterator.

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

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

This method tests for self and other values to be equal, and is used by ==.

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

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

impl<'a, K, V: 'a> TrieCommon<'a, K, V> for &'a Trie<K, V>where
    K: TrieKey + 'a,

fn len(self) -> usize

Number of key/value pairs stored in this trie.

fn children(self) -> Children<'a, K, V>

Return an iterator over the child subtries of this node.

fn key(self) -> Option<&'a K>

Get the key stored at this node, if any.

fn value(self) -> Option<&'a V>

Get the value stored at this node, if any.

fn is_empty(self) -> bool

Determine if the Trie contains 0 key-value pairs.

fn is_leaf(self) -> bool

Determine if the trie is a leaf node (has no children).

fn iter(self) -> Iter<'a, K, V>

Return an iterator over the keys and values of the Trie.

fn keys(self) -> Keys<'a, K, V>

Return an iterator over the keys of the Trie.

fn values(self) -> Values<'a, K, V>

Return an iterator over the values of the Trie.

fn prefix(self) -> &'a Nibblet

Get the prefix of this node.