qp_trie/
iter.rs

1use alloc::{vec, vec::Vec};
2
3use node::Node;
4
5/// An iterator over the keys and values in a QP-trie.
6#[derive(Clone, Debug)]
7pub struct IntoIter<K, V> {
8    stack: Vec<Node<K, V>>,
9}
10
11impl<K, V> IntoIter<K, V> {
12    pub(crate) fn new(node: Node<K, V>) -> IntoIter<K, V> {
13        IntoIter { stack: vec![node] }
14    }
15}
16
17impl<K, V> Default for IntoIter<K, V> {
18    fn default() -> Self {
19        IntoIter { stack: vec![] }
20    }
21}
22
23impl<K, V> Iterator for IntoIter<K, V> {
24    type Item = (K, V);
25
26    fn next(&mut self) -> Option<Self::Item> {
27        match self.stack.pop() {
28            Some(Node::Leaf(leaf)) => Some((leaf.key, leaf.val)),
29            Some(Node::Branch(branch)) => {
30                self.stack.extend(branch.into_iter().rev());
31                self.next()
32            }
33            None => None,
34        }
35    }
36}
37
38/// An iterator over immutable references to keys and values in a QP-trie.
39#[derive(Clone, Debug)]
40pub struct Iter<'a, K: 'a, V: 'a> {
41    stack: Vec<&'a Node<K, V>>,
42}
43
44impl<'a, K, V> Iter<'a, K, V> {
45    pub fn new(node: &'a Node<K, V>) -> Iter<'a, K, V> {
46        Iter { stack: vec![node] }
47    }
48}
49
50impl<'a, K, V> Default for Iter<'a, K, V> {
51    fn default() -> Self {
52        Iter { stack: vec![] }
53    }
54}
55
56impl<'a, K: 'a, V: 'a> Iterator for Iter<'a, K, V> {
57    type Item = (&'a K, &'a V);
58
59    fn next(&mut self) -> Option<Self::Item> {
60        match self.stack.pop() {
61            Some(Node::Leaf(leaf)) => Some((&leaf.key, &leaf.val)),
62            Some(Node::Branch(branch)) => {
63                self.stack.extend(branch.iter().rev());
64                self.next()
65            }
66            None => None,
67        }
68    }
69}
70
71/// An iterator over immutable references to keys and mutable references to values in a QP-trie.
72#[derive(Debug)]
73pub struct IterMut<'a, K: 'a, V: 'a> {
74    stack: Vec<&'a mut Node<K, V>>,
75}
76
77impl<'a, K, V> IterMut<'a, K, V> {
78    pub fn new(node: &'a mut Node<K, V>) -> IterMut<'a, K, V> {
79        IterMut { stack: vec![node] }
80    }
81}
82
83impl<'a, K, V> Default for IterMut<'a, K, V> {
84    fn default() -> Self {
85        IterMut { stack: vec![] }
86    }
87}
88
89impl<'a, K: 'a, V: 'a> Iterator for IterMut<'a, K, V> {
90    type Item = (&'a K, &'a mut V);
91
92    fn next(&mut self) -> Option<Self::Item> {
93        match self.stack.pop() {
94            Some(&mut Node::Leaf(ref mut leaf)) => Some((&leaf.key, &mut leaf.val)),
95            Some(&mut Node::Branch(ref mut branch)) => {
96                self.stack.extend(branch.iter_mut().rev());
97                self.next()
98            }
99            None => None,
100        }
101    }
102}
103
104/// An iterator over immutable references to the keys in the QP-trie.
105#[derive(Clone, Debug)]
106pub struct Keys<'a, K: 'a, V: 'a> {
107    stack: Vec<&'a Node<K, V>>,
108}
109
110impl<'a, K, V> Keys<'a, K, V> {
111    pub fn new(node: &'a Node<K, V>) -> Keys<'a, K, V> {
112        Keys { stack: vec![node] }
113    }
114}
115
116impl<'a, K, V> Default for Keys<'a, K, V> {
117    fn default() -> Self {
118        Keys { stack: vec![] }
119    }
120}
121
122impl<'a, K: 'a, V: 'a> Iterator for Keys<'a, K, V> {
123    type Item = &'a K;
124
125    fn next(&mut self) -> Option<Self::Item> {
126        match self.stack.pop() {
127            Some(Node::Leaf(leaf)) => Some(&leaf.key),
128            Some(Node::Branch(branch)) => {
129                self.stack.extend(branch.iter().rev());
130                self.next()
131            }
132            None => None,
133        }
134    }
135}
136
137/// An iterator over immutable references to the values in the QP-trie.
138#[derive(Clone, Debug)]
139pub struct Values<'a, K: 'a, V: 'a> {
140    stack: Vec<&'a Node<K, V>>,
141}
142
143impl<'a, K, V> Values<'a, K, V> {
144    pub fn new(node: &'a Node<K, V>) -> Values<'a, K, V> {
145        Values { stack: vec![node] }
146    }
147}
148
149impl<'a, K, V> Default for Values<'a, K, V> {
150    fn default() -> Self {
151        Values { stack: vec![] }
152    }
153}
154
155impl<'a, K: 'a, V: 'a> Iterator for Values<'a, K, V> {
156    type Item = &'a V;
157
158    fn next(&mut self) -> Option<Self::Item> {
159        match self.stack.pop() {
160            Some(Node::Leaf(leaf)) => Some(&leaf.val),
161            Some(Node::Branch(branch)) => {
162                self.stack.extend(branch.iter().rev());
163                self.next()
164            }
165            None => None,
166        }
167    }
168}
169
170/// An iterator over mutable references to the values in the QP-trie.
171#[derive(Debug)]
172pub struct ValuesMut<'a, K: 'a, V: 'a> {
173    stack: Vec<&'a mut Node<K, V>>,
174}
175
176impl<'a, K, V> ValuesMut<'a, K, V> {
177    pub fn new(node: &'a mut Node<K, V>) -> ValuesMut<'a, K, V> {
178        ValuesMut { stack: vec![node] }
179    }
180}
181
182impl<'a, K, V> Default for ValuesMut<'a, K, V> {
183    fn default() -> Self {
184        ValuesMut { stack: vec![] }
185    }
186}
187
188impl<'a, K: 'a, V: 'a> Iterator for ValuesMut<'a, K, V> {
189    type Item = &'a mut V;
190
191    fn next(&mut self) -> Option<Self::Item> {
192        match self.stack.pop() {
193            Some(&mut Node::Leaf(ref mut leaf)) => Some(&mut leaf.val),
194            Some(&mut Node::Branch(ref mut branch)) => {
195                self.stack.extend(branch.iter_mut().rev());
196                self.next()
197            }
198            None => None,
199        }
200    }
201}
qp_trie/iter.rs

qp_trie/
iter.rs
