Struct sequence_trie::SequenceTrie

pub struct SequenceTrie<K, V> where
    K: TrieKey,  { /* 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.

Methods

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

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

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

fn is_empty(&self) -> bool

Checks if this node is empty.

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

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.

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.

fn get<'key, I>(&self, key: I) -> Option<&V> where
    I: IntoIterator<Item = &'key K>, 

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

fn get_node<'key, I>(&self, key: I) -> Option<&SequenceTrie<K, V>> where
    I: IntoIterator<Item = &'key K>, 

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

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

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

fn get_node_mut<'key, I>(&mut self, key: I) -> Option<&mut SequenceTrie<K, V>> where
    I: IntoIterator<Item = &'key K>, 

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

fn get_prefix_nodes<'key, I>(&self, key: I) -> Vec<&SequenceTrie<K, V>> where
    I: 'key + IntoIterator<Item = &'key K>, 

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

fn get_ancestor<'key, I>(&self, key: I) -> Option<&V> where
    I: 'key + IntoIterator<Item = &'key K>, 

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.

fn get_ancestor_node<'key, I>(&self, key: I) -> Option<&SequenceTrie<K, V>> where
    I: 'key + IntoIterator<Item = &'key K>, 

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

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

fn remove<'key, I>(&mut self, key: I) where
    I: IntoIterator<Item = &'key K>, 

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.

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

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

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

Returns an iterator over all the keys in the trie.

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

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

fn prefix_iter<'trie, 'key, I>(
    &'trie self,
    key: I
) -> PrefixIter<'trie, 'key, K, V, I::IntoIter> where
    I: 'key + IntoIterator<Item = &'key K>, 

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

Trait Implementations

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

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

Formats the value using the given formatter.

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

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

Returns a copy of the value.

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

Performs copy-assignment from source.

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

fn eq(&self, other: &Self) -> 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<K, V> Eq for SequenceTrie<K, V> where
    K: TrieKey,
    V: Eq, 

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

fn default() -> Self

Returns the "default value" for a type.