xtri/iter/
leaves.rs

1use crate::tree::RadixNode;
2
3/// Iterator for traversing only the leaf nodes of a radix tree.
4///
5/// A leaf node is defined as a node that has a value but no children,
6/// representing the end of a key path with no further extensions.
7/// This iterator performs lazy traversal using a stack-based approach.
8/// Memory usage is O(tree depth) storing only node references and child indices.
9pub struct LeavesIterator<'a, T> {
10    // Stack of (node, child_index, current_key) pairs for traversal state
11    stack: Vec<(&'a RadixNode<T>, usize, Vec<u8>)>,
12}
13
14impl<'a, T> LeavesIterator<'a, T> {
15    pub(crate) fn new(root: &'a RadixNode<T>) -> Self {
16        let mut iterator = Self { stack: Vec::new() };
17
18        // Start traversal from the root with empty key
19        iterator.stack.push((root, 0, Vec::new()));
20        iterator
21    }
22}
23
24impl<'a, T> Iterator for LeavesIterator<'a, T> {
25    type Item = (Vec<u8>, &'a T);
26
27    fn next(&mut self) -> Option<Self::Item> {
28        loop {
29            let (node, child_index, current_key) = self.stack.pop()?;
30
31            // If this is the first visit to this node (child_index == 0), check if it's a leaf
32            if child_index == 0 {
33                // A leaf node has a value and no children
34                if let Some(ref value) = node.value {
35                    if node.children.is_empty() {
36                        // This is a leaf node - return it
37                        return Some((current_key.clone(), value));
38                    }
39                }
40
41                // Not a leaf or no value, start processing children
42                if !node.children.is_empty() {
43                    self.stack.push((node, 1, current_key));
44                }
45                continue;
46            }
47
48            // Processing children: child_index - 1 is the current child being processed
49            let current_child_idx = child_index - 1;
50
51            if current_child_idx < node.children.len() {
52                // Push the next child index for this node
53                if current_child_idx + 1 < node.children.len() {
54                    self.stack
55                        .push((node, child_index + 1, current_key.clone()));
56                }
57
58                // Push the current child to be processed
59                let (_, child) = &node.children[current_child_idx];
60                let mut child_key = current_key;
61                child_key.extend_from_slice(&child.key);
62
63                self.stack.push((child, 0, child_key));
64            }
65        }
66    }
67}
xtri/iter/leaves.rs

xtri/iter/
leaves.rs
