Struct sequence_trie::SequenceTrie
source · pub struct SequenceTrie<K, V, S = RandomState>where
K: TrieKey,
S: BuildHasher + Default,{ /* private fields */ }
Expand description
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 char
s.
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 HashMap
s, 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§
source§impl<K, V> SequenceTrie<K, V>where
K: TrieKey,
impl<K, V> SequenceTrie<K, V>where
K: TrieKey,
sourcepub fn new() -> SequenceTrie<K, V>
pub fn new() -> SequenceTrie<K, V>
Creates a new SequenceTrie
node with no value and an empty child map.
source§impl<K, V, S> SequenceTrie<K, V, S>where
K: TrieKey,
S: BuildHasher + Default + Clone,
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>
source§impl<K, V, S> SequenceTrie<K, V, S>where
K: TrieKey,
S: BuildHasher + Default + Clone,
impl<K, V, S> SequenceTrie<K, V, S>where
K: TrieKey,
S: BuildHasher + Default + Clone,
sourcepub fn value_mut(&mut self) -> Option<&mut V>
pub fn value_mut(&mut self) -> Option<&mut V>
Retrieve a mutable reference to the value stored at this node.
sourcepub fn is_empty(&self) -> bool
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.
sourcepub fn insert<'key, I, Q>(&mut self, key: I, value: V) -> Option<V>where
I: IntoIterator<Item = &'key Q>,
Q: ToOwned<Owned = K> + 'key + ?Sized,
K: Borrow<Q>,
pub fn insert<'key, I, Q>(&mut self, key: I, value: V) -> Option<V>where
I: IntoIterator<Item = &'key Q>,
Q: ToOwned<Owned = K> + 'key + ?Sized,
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.
sourcepub fn insert_owned<I>(&mut self, key: I, value: V) -> Option<V>where
I: IntoIterator<Item = K>,
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
.
sourcepub fn get<'key, I, Q>(&self, key: I) -> Option<&V>where
I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
pub fn get<'key, I, Q>(&self, key: I) -> Option<&V>where
I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
Finds a reference to a key’s value, if it has one.
sourcepub fn get_node<'key, I, Q>(&self, key: I) -> Option<&SequenceTrie<K, V, S>>where
I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
pub fn get_node<'key, I, Q>(&self, key: I) -> Option<&SequenceTrie<K, V, S>>where
I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
Finds a reference to a key’s node, if it has one.
sourcepub fn get_mut<'key, I, Q>(&mut self, key: I) -> Option<&mut V>where
I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
pub fn get_mut<'key, I, Q>(&mut self, key: I) -> Option<&mut V>where
I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
Finds a mutable reference to a key’s value, if it has one.
sourcepub fn get_node_mut<'key, I, Q>(
&mut self,
key: I
) -> Option<&mut SequenceTrie<K, V, S>>where
I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
pub fn get_node_mut<'key, I, Q>(
&mut self,
key: I
) -> Option<&mut SequenceTrie<K, V, S>>where
I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
Finds a mutable reference to a key’s node, if it has one.
sourcepub fn get_prefix_nodes<'key, I, Q>(&self, key: I) -> Vec<&SequenceTrie<K, V, S>>where
I: 'key + IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
pub fn get_prefix_nodes<'key, I, Q>(&self, key: I) -> Vec<&SequenceTrie<K, V, S>>where
I: 'key + IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
Finds the longest prefix of nodes which match the given key.
sourcepub fn get_ancestor<'key, I, Q>(&self, key: I) -> Option<&V>where
I: 'key + IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
pub fn get_ancestor<'key, I, Q>(&self, key: I) -> Option<&V>where
I: 'key + IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
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.
sourcepub fn get_ancestor_node<'key, I, Q>(
&self,
key: I
) -> Option<&SequenceTrie<K, V, S>>where
I: 'key + IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
pub fn get_ancestor_node<'key, I, Q>(
&self,
key: I
) -> Option<&SequenceTrie<K, V, S>>where
I: 'key + IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
Finds the nearest ancestor with a non-empty value, if one exists.
If all ancestors have empty (None
) values, None
is returned.
sourcepub fn remove<'key, I, Q>(&mut self, key: I)where
I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
pub fn remove<'key, I, Q>(&mut self, key: I)where
I: IntoIterator<Item = &'key Q>,
K: Borrow<Q>,
Q: TrieKey + 'key + ?Sized,
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.
sourcepub fn map<F>(&mut self, f: F)where
F: Fn(&Self) -> Option<V>,
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.
sourcepub fn iter(&self) -> Iter<'_, K, V, S> ⓘ
pub fn iter(&self) -> Iter<'_, K, V, S> ⓘ
Returns an iterator over all the key-value pairs in the collection.
sourcepub fn values(&self) -> Values<'_, K, V, S> ⓘ
pub fn values(&self) -> Values<'_, K, V, S> ⓘ
Returns an iterator over all the values stored in the trie.
sourcepub fn prefix_iter<'trie, 'key, I, Q>(
&'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 + ?Sized,
pub fn prefix_iter<'trie, 'key, I, Q>(
&'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 + ?Sized,
Returns an iterator over the longest prefix of nodes which match the given key.
sourcepub fn children(&self) -> Vec<&Self>
pub fn children(&self) -> Vec<&Self>
Return all the children of this node, in an arbitrary order.
sourcepub fn children_with_keys<'a>(&'a self) -> Vec<(&'a K, &'a Self)>
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§
source§impl<K, V: Clone, S> Clone for SequenceTrie<K, V, S>where
K: TrieKey + Clone,
S: BuildHasher + Default + Clone,
impl<K, V: Clone, S> Clone for SequenceTrie<K, V, S>where
K: TrieKey + Clone,
S: BuildHasher + Default + Clone,
source§fn clone(&self) -> SequenceTrie<K, V, S>
fn clone(&self) -> SequenceTrie<K, V, S>
1.0.0 · source§fn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read more