Struct radix_trie::Trie

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

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.

Methods

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

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

Create an empty Trie.

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

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: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where
    K: Borrow<Q>,
    Q: TrieKey, 

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: ?Sized>(&mut self, key: &Q) -> Option<V> where
    K: Borrow<Q>,
    Q: TrieKey, 

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: ?Sized>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>> where
    K: Borrow<Q>,
    Q: TrieKey, 

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: ?Sized>(
    &'a mut self,
    key: &Q
) -> Option<SubTrieMut<'a, K, V>> where
    K: Borrow<Q>,
    Q: TrieKey, 

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: ?Sized>(&'a self, key: &Q) -> Option<SubTrie<'a, K, V>> where
    K: Borrow<Q>,
    Q: TrieKey, 

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: ?Sized>(&self, key: &Q) -> Option<&V> where
    K: Borrow<Q>,
    Q: TrieKey, 

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: ?Sized>(&'a self, key: &Q) -> SubTrie<'a, K, V> where
    K: Borrow<Q>,
    Q: TrieKey, 

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: ?Sized>(
    &'a self,
    key: &Q
) -> Option<SubTrie<'a, K, V>> where
    K: Borrow<Q>,
    Q: TrieKey, 

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

Creates a value from an iterator.

impl<K, V> PartialEq 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 !=.

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

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.

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

fn fmt(&self, __arg_0: &mut Formatter) -> Result

Formats the value using the given formatter.