radix_trie/
trie_common.rs

Help
1use crate::iter::*;
2use crate::TrieNode;
3use crate::{SubTrie, SubTrieMut, Trie, TrieKey};
4
5use nibble_vec::Nibblet;
6
7/// Common functionality available for tries and subtries.
8pub trait TrieCommon<'a, K: 'a, V: 'a>: ContainsTrieNode<'a, K, V>
9where
10    K: TrieKey,
11    Self: Sized,
12{
13    /// Get the key stored at this node, if any.
14    #[inline]
15    fn key(self) -> Option<&'a K> {
16        self.trie_node().key()
17    }
18
19    /// Get the value stored at this node, if any.
20    #[inline]
21    fn value(self) -> Option<&'a V> {
22        self.trie_node().value()
23    }
24
25    /// Number of key/value pairs stored in this trie.
26    fn len(self) -> usize;
27
28    /// Determine if the Trie contains 0 key-value pairs.
29    #[inline]
30    fn is_empty(self) -> bool {
31        self.len() == 0
32    }
33
34    /// Determine if the trie is a leaf node (has no children).
35    #[inline]
36    fn is_leaf(self) -> bool {
37        self.trie_node().child_count == 0
38    }
39
40    /// Return an iterator over the keys and values of the Trie.
41    #[inline]
42    fn iter(self) -> Iter<'a, K, V> {
43        Iter::new(self.trie_node())
44    }
45
46    /// Return an iterator over the keys of the Trie.
47    #[inline]
48    fn keys(self) -> Keys<'a, K, V> {
49        Keys::new(self.iter())
50    }
51
52    /// Return an iterator over the values of the Trie.
53    #[inline]
54    fn values(self) -> Values<'a, K, V> {
55        Values::new(self.iter())
56    }
57
58    /// Return an iterator over the child subtries of this node.
59    fn children(self) -> Children<'a, K, V>;
60
61    /// Get the prefix of this node.
62    #[inline]
63    fn prefix(self) -> &'a Nibblet {
64        &self.trie_node().key
65    }
66}
67
68/// Helper trait for Trie/SubTrie/SubTrieMut, which all contain a trie node.
69pub trait ContainsTrieNode<'a, K: 'a, V: 'a>
70where
71    K: TrieKey,
72{
73    fn trie_node(self) -> &'a TrieNode<K, V>;
74}
75
76/// Regular trie.
77impl<'a, K: 'a, V: 'a> ContainsTrieNode<'a, K, V> for &'a Trie<K, V>
78where
79    K: TrieKey,
80{
81    #[inline]
82    fn trie_node(self) -> &'a TrieNode<K, V> {
83        &self.node
84    }
85}
86
87impl<'a, K: 'a, V: 'a> TrieCommon<'a, K, V> for &'a Trie<K, V>
88where
89    K: TrieKey,
90{
91    #[inline]
92    fn len(self) -> usize {
93        self.length
94    }
95    #[inline]
96    fn children(self) -> Children<'a, K, V> {
97        Children::new(self.node.key.clone(), &self.node)
98    }
99}
100
101/// Subtrie.
102impl<'a: 'b, 'b, K: 'a, V: 'a> ContainsTrieNode<'a, K, V> for &'b SubTrie<'a, K, V>
103where
104    K: TrieKey,
105{
106    #[inline]
107    fn trie_node(self) -> &'a TrieNode<K, V> {
108        self.node
109    }
110}
111
112impl<'a: 'b, 'b, K: 'a, V: 'a> TrieCommon<'a, K, V> for &'b SubTrie<'a, K, V>
113where
114    K: TrieKey,
115{
116    #[inline]
117    fn len(self) -> usize {
118        self.node.compute_size()
119    }
120    #[inline]
121    fn children(self) -> Children<'a, K, V> {
122        Children::new(self.prefix.clone(), self.node)
123    }
124}
125
126/// Mutable subtrie *by value* (consumes the subtrie).
127impl<'a, K: 'a, V: 'a> ContainsTrieNode<'a, K, V> for SubTrieMut<'a, K, V>
128where
129    K: TrieKey,
130{
131    #[inline]
132    fn trie_node(self) -> &'a TrieNode<K, V> {
133        self.node
134    }
135}
136
137impl<'a, K: 'a, V: 'a> TrieCommon<'a, K, V> for SubTrieMut<'a, K, V>
138where
139    K: TrieKey,
140{
141    /// **Computes** from scratch.
142    #[inline]
143    fn len(self) -> usize {
144        self.node.compute_size()
145    }
146    #[inline]
147    fn children(self) -> Children<'a, K, V> {
148        Children::new(self.prefix.clone(), self.node)
149    }
150}
151
152/// Mutable subtrie *by reference* (doesn't consume the subtrie, but limited).
153impl<'a: 'b, 'b, K: 'a, V: 'a> ContainsTrieNode<'b, K, V> for &'b SubTrieMut<'a, K, V>
154where
155    K: TrieKey,
156{
157    #[inline]
158    fn trie_node(self) -> &'b TrieNode<K, V> {
159        self.node
160    }
161}
162
163impl<'a: 'b, 'b, K: 'a, V: 'a> TrieCommon<'b, K, V> for &'b SubTrieMut<'a, K, V>
164where
165    K: TrieKey,
166{
167    #[inline]
168    fn len(self) -> usize {
169        self.node.compute_size()
170    }
171    #[inline]
172    fn children(self) -> Children<'b, K, V> {
173        Children::new(self.prefix.clone(), self.node)
174    }
175}
radix_trie/trie_common.rs

radix_trie/
trie_common.rs
