geometry_rtree/
values.rs

1//! Iteration over all values stored in an R-tree.
2//!
3//! Mirrors the value walk behind Boost.Geometry's R-tree `begin()` and
4//! `end()` iterators. The Rust API exposes it through
5//! [`Rtree::iter`](crate::Rtree::iter) and `IntoIterator` for `&Rtree`.
6
7use alloc::vec::Vec;
8use core::iter::FusedIterator;
9
10use crate::node::Node;
11
12/// A depth-first iterator over every value in an R-tree.
13pub struct Values<'a, T> {
14    stack: Vec<&'a Node<T>>,
15    leaf: core::slice::Iter<'a, T>,
16    remaining: usize,
17}
18
19impl<'a, T> Values<'a, T> {
20    pub(crate) fn new(root: &'a Node<T>, len: usize, height: usize, max_fanout: usize) -> Self {
21        let capacity = height.saturating_sub(1) * max_fanout.saturating_sub(1) + max_fanout;
22        let mut stack = Vec::with_capacity(capacity);
23        stack.push(root);
24        Self {
25            stack,
26            leaf: [].iter(),
27            remaining: len,
28        }
29    }
30}
31
32impl<'a, T> Iterator for Values<'a, T> {
33    type Item = &'a T;
34
35    fn next(&mut self) -> Option<Self::Item> {
36        loop {
37            if let Some(value) = self.leaf.next() {
38                self.remaining -= 1;
39                return Some(value);
40            }
41            match self.stack.pop()? {
42                Node::Leaf(values) => self.leaf = values.iter(),
43                Node::Branch(children) => {
44                    for (_, child) in children.iter().rev() {
45                        self.stack.push(child);
46                    }
47                }
48            }
49        }
50    }
51
52    fn size_hint(&self) -> (usize, Option<usize>) {
53        (self.remaining, Some(self.remaining))
54    }
55}
56
57impl<T> ExactSizeIterator for Values<'_, T> {}
58impl<T> FusedIterator for Values<'_, T> {}
geometry_rtree/values.rs

geometry_rtree/
values.rs
