Struct sequence_trie::SequenceTrie
[-] [+]
[src]
pub struct SequenceTrie<K, V> where K: TrieKey {
pub value: Option<V>,
pub children: HashMap<K, SequenceTrie<K, V>>,
}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 (warning: not real code).
SequenceTrie { value: Some(0u), children: 'a' => SequenceTrie { value: Some(1u), children: 'b' => SequenceTrie { value: None, children: 'c' => SequenceTrie { value: Some(3u), 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 trie: SequenceTrie<char, uint> = SequenceTrie::new(); trie.insert(['a', 'b', 'c'], 3u); trie.insert([], 0u); trie.insert(['a'], 1u);
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.
Fields
value | Node value. |
children | Node children as a hashmap keyed by key fragments. |
Methods
impl<K, V> SequenceTrie<K, V> where K: TrieKey
fn new() -> SequenceTrie<K, V>
Create a new SequenceTrie node with no value and an empty child map.
fn insert(&mut self, key: &[K], value: V) -> bool
Insert a key and value into the SequenceTrie.
Returns true if the key did not already correspond to a value.
fn get(&self, key: &[K]) -> Option<&V>
Find a reference to a key's value, if it has one.
fn get_node(&self, key: &[K]) -> Option<&SequenceTrie<K, V>>
Find a reference to a key's node, if it has one.
fn get_mut(&mut self, key: &[K]) -> Option<&mut V>
Find a mutable reference to a key's value, if it has one.
fn get_mut_node(&mut self, key: &[K]) -> Option<&mut SequenceTrie<K, V>>
Find a mutable reference to a key's node, if it has one.
fn get_prefix_nodes(&self, key: &[K]) -> Vec<&SequenceTrie<K, V>>
Find the longest prefix of nodes which match the given key.
fn get_ancestor(&self, key: &[K]) -> Option<&V>
Find 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(&self, key: &[K]) -> Option<&SequenceTrie<K, V>>
Find the nearest ancestor with a non-empty value, if one exists.
If all ancestors have empty (None) values, None is returned.
fn remove(&mut self, key: &[K])
Remove 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<'a>(&'a self) -> Iter<'a, K, V>
Return an iterator over all the key-value pairs in the collection.
fn keys<'a>(&'a self) -> Keys<'a, K, V>
Return an iterator over all the keys in the trie.
fn values<'a>(&'a self) -> Values<'a, K, V>
Return an iterator over all the values stored in the trie.