Struct sequence_trie::SequenceTrie

pub struct SequenceTrie<K, V, S = RandomState> where
    K: TrieKey,
    S: BuildHasher + Default,  { /* fields omitted */ }

A SequenceTrie is recursively defined as a value and a map containing child Tries.

Typically, Tries are used to store strings, which can be thought of as lists of chars. Generalising this to any key type, a Trie is a data structure storing values for keys which are themselves lists. Let the parts of such a list-key be called "key fragments". In our representation of a Trie, K denotes the type of the key fragments.

The nesting of child Tries creates a tree structure which can be traversed by mapping key fragments onto nodes. The structure is similar to a k-ary tree, except that the children are stored in HashMaps, and there is no bound on the number of children a single node may have (effectively k = ∞). In a SequenceTrie with char key fragments, the key ['a', 'b', 'c'] might correspond to something like this:

SequenceTrie {
    value: Some(0),
    children: 'a' => SequenceTrie {
        value: Some(1),
        children: 'b' => SequenceTrie {
            value: None,
            children: 'c' => SequenceTrie {
                value: Some(3),
                children: Nil
            }
        }
    }
}

Values are stored optionally at each node because inserting a value for a list-key only inserts a value for the last fragment of the key. The intermediate prefix nodes are created with value None if they do not exist already.

The above SequenceTrie could be created using the following sequence of operations:

let mut trie: SequenceTrie<char, i32> = SequenceTrie::new();
trie.insert(&['a', 'b', 'c'], 3);
trie.insert(&[], 0);
trie.insert(&['a'], 1);

The order of insertion is never important.

One interesting thing about Tries is that every key is a descendant of the root, which itself has no key fragment. Although this is a rather trivial observation, it means that every key corresponds to a non-empty sequence of prefix nodes in the tree. This observation is the motivation for the get_prefix_nodes method, which returns the nodes corresponding to the longest prefix of a given key.

The empty list key, [], always corresponds to the root node of the Trie.

The Sequence Trie Invariant

All leaf nodes have non-trivial values (not equal to None). This invariant is maintained by the insertion and removal methods and can be relied upon.

Implementations

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

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

Creates a new SequenceTrie node with no value and an empty child map.

impl<K, V, S> SequenceTrie<K, V, S> where
    K: TrieKey,
    S: BuildHasher + Default + Clone, 

pub fn with_hasher(hash_builder: S) -> SequenceTrie<K, V, S>

impl<K, V, S> SequenceTrie<K, V, S> where
    K: TrieKey,
    S: BuildHasher + Default + Clone, 

pub fn value(&self) -> Option<&V>

Retrieve the value stored at this node.

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

Retrieve a mutable reference to the value stored at this node.

pub fn is_empty(&self) -> bool

Checks if this node is empty.

A node is considered empty when it has no value and no children.

pub fn is_leaf(&self) -> bool

Checks if this node has no descendants.

pub fn insert<'key, I, Q: 'key + ?Sized>(
    &mut self,
    key: I,
    value: V
) -> Option<V> where
    I: IntoIterator<Item = &'key Q>,
    Q: ToOwned<Owned = K>,
    K: Borrow<Q>, 

Inserts a key and value into the SequenceTrie.

Returns None if the key did not already correspond to a value, otherwise the old value is returned.

pub fn insert_owned<I>(&mut self, key: I, value: V) -> Option<V> where
    I: IntoIterator<Item = K>, 

Version of insert that takes an owned sequence of key fragments.

This function is used internally by insert.

pub fn get<'key, I, Q: ?Sized>(&self, key: I) -> Option<&V> where
    I: IntoIterator<Item = &'key Q>,
    K: Borrow<Q>,
    Q: TrieKey + 'key, 

Finds a reference to a key's value, if it has one.

pub fn get_node<'key, I, Q: ?Sized>(
    &self,
    key: I
) -> Option<&SequenceTrie<K, V, S>> where
    I: IntoIterator<Item = &'key Q>,
    K: Borrow<Q>,
    Q: TrieKey + 'key, 

Finds a reference to a key's node, if it has one.

pub fn get_mut<'key, I, Q: ?Sized>(&mut self, key: I) -> Option<&mut V> where
    I: IntoIterator<Item = &'key Q>,
    K: Borrow<Q>,
    Q: TrieKey + 'key, 

Finds a mutable reference to a key's value, if it has one.

pub fn get_node_mut<'key, I, Q: ?Sized>(
    &mut self,
    key: I
) -> Option<&mut SequenceTrie<K, V, S>> where
    I: IntoIterator<Item = &'key Q>,
    K: Borrow<Q>,
    Q: TrieKey + 'key, 

Finds a mutable reference to a key's node, if it has one.

pub fn get_prefix_nodes<'key, I, Q: ?Sized>(
    &self,
    key: I
) -> Vec<&SequenceTrie<K, V, S>> where
    I: 'key + IntoIterator<Item = &'key Q>,
    K: Borrow<Q>,
    Q: TrieKey + 'key, 

Finds the longest prefix of nodes which match the given key.

pub fn get_ancestor<'key, I, Q: ?Sized>(&self, key: I) -> Option<&V> where
    I: 'key + IntoIterator<Item = &'key Q>,
    K: Borrow<Q>,
    Q: TrieKey + 'key, 

Finds the value of the nearest ancestor with a non-empty value, if one exists.

If all ancestors have empty (None) values, None is returned.

pub fn get_ancestor_node<'key, I, Q: ?Sized>(
    &self,
    key: I
) -> Option<&SequenceTrie<K, V, S>> where
    I: 'key + IntoIterator<Item = &'key Q>,
    K: Borrow<Q>,
    Q: TrieKey + 'key, 

Finds the nearest ancestor with a non-empty value, if one exists.

If all ancestors have empty (None) values, None is returned.

pub fn remove<'key, I, Q: ?Sized>(&mut self, key: I) where
    I: IntoIterator<Item = &'key Q>,
    K: Borrow<Q>,
    Q: TrieKey + 'key, 

Removes the node corresponding to the given key.

This operation is like the reverse of insert in that it also deletes extraneous nodes on the path from the root.

If the key node has children, its value is set to None and no further action is taken. If the key node is a leaf, then it and its ancestors with empty values and no other children are deleted. Deletion proceeds up the tree from the key node until a node with a non-empty value or children is reached.

If the key doesn't match a node in the Trie, no action is taken.

pub fn map<F>(&mut self, f: F) where
    F: Fn(&Self) -> Option<V>, 

Recursively apply a function to every node in the trie.

Nodes are visited "bottom-up" (children before parent). If f returns a value, it replaces the value at that node. Otherwise, the node's value remains unchanged.

pub fn iter(&self) -> Iter<'_, K, V, S>

Returns an iterator over all the key-value pairs in the collection.

pub fn keys(&self) -> Keys<'_, K, V, S>

Returns an iterator over all the keys in the trie.

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

Returns an iterator over all the values stored in the trie.

pub fn prefix_iter<'trie, 'key, I, Q: ?Sized>(
    &'trie self,
    key: I
) -> PrefixIter<'trie, 'key, K, V, Q, I::IntoIter, S> where
    I: IntoIterator<Item = &'key Q>,
    K: Borrow<Q>,
    Q: TrieKey + 'key, 

Returns an iterator over the longest prefix of nodes which match the given key.

pub fn children(&self) -> Vec<&Self>

Return all the children of this node, in an arbitrary order.

pub fn children_with_keys<'a>(&'a self) -> Vec<(&'a K, &'a Self)>

Children of this node, with their associated keys in arbitrary order.

Trait Implementations

impl<K: Clone, V: Clone, S: Clone> Clone for SequenceTrie<K, V, S> where
    K: TrieKey,
    S: BuildHasher + Default, 

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<K: Debug, V: Debug, S: Debug> Debug for SequenceTrie<K, V, S> where
    K: TrieKey,
    S: BuildHasher + Default, 

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

Formats the value using the given formatter.

impl<K, V, S> Default for SequenceTrie<K, V, S> where
    K: TrieKey,
    S: BuildHasher + Default + Clone, 

fn default() -> Self

Returns the "default value" for a type.

impl<K, V, S> Eq for SequenceTrie<K, V, S> where
    K: TrieKey,
    V: Eq,
    S: BuildHasher + Default, 

impl<K, V, S> PartialEq<SequenceTrie<K, V, S>> for SequenceTrie<K, V, S> where
    K: TrieKey,
    V: PartialEq,
    S: BuildHasher + Default, 

fn eq(&self, other: &Self) -> bool

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

#[must_use]fn ne(&self, other: &Rhs) -> bool

This method tests for !=.