geometry_rtree/
nearest_iter.rs

1//! Unbounded nearest-first streaming — the search behind
2//! [`Rtree::nearest_iter`](crate::rtree::Rtree::nearest_iter).
3//!
4//! A best-first stream over this crate's
5//! `SearchFrontier`: separate node and value frontiers keep each entry
6//! to a distance plus one reference. Each [`next`](Iterator::next)
7//! expands nodes until the closest pending value is no farther than the
8//! closest unexpanded node, then yields that value. No best-k
9//! pruning happens because no `k` exists; the bounded
10//! [`Rtree::nearest`](crate::rtree::Rtree::nearest) keeps the pruned
11//! path for the fixed-k case.
12
13use core::iter::FusedIterator;
14
15#[cfg(test)]
16use alloc::vec::Vec;
17
18use crate::indexable::Indexable;
19use crate::node::Node;
20use crate::search_frontier::SearchFrontier;
21
22#[cfg(test)]
23use crate::search_frontier::FrontierMetrics;
24
25/// Default inline entry capacity of a nearest iterator's node frontier.
26pub const DEFAULT_NODE_INLINE_CAPACITY: usize = 32;
27
28/// Default inline entry capacity of a nearest iterator's value frontier.
29pub const DEFAULT_VALUE_INLINE_CAPACITY: usize = 64;
30
31/// A lazy iterator over ALL values in the tree in exact non-decreasing
32/// distance order from a query point — an unbounded ordered stream.
33///
34/// Created by [`Rtree::nearest_iter`](crate::rtree::Rtree::nearest_iter).
35/// The consumer supplies its own bound via
36/// [`take`](Iterator::take); consuming to exhaustion drains the whole
37/// tree in distance order. The default inline capacities can be
38/// overridden through
39/// [`Rtree::nearest_iter_with_inline_capacities`](crate::rtree::Rtree::nearest_iter_with_inline_capacities)
40/// when caller-specific measurements justify the stack/spill trade-off.
41pub struct NearestIter<
42    'a,
43    T,
44    const NODE_INLINE_CAPACITY: usize = DEFAULT_NODE_INLINE_CAPACITY,
45    const VALUE_INLINE_CAPACITY: usize = DEFAULT_VALUE_INLINE_CAPACITY,
46> {
47    query: [f64; 2],
48    nodes: SearchFrontier<DistanceEntry<'a, Node<T>>, NODE_INLINE_CAPACITY>,
49    values: SearchFrontier<DistanceEntry<'a, T>, VALUE_INLINE_CAPACITY>,
50    #[cfg(test)]
51    branch_expansions: usize,
52    #[cfg(test)]
53    leaf_expansions: usize,
54    #[cfg(test)]
55    node_pushes: usize,
56    #[cfg(test)]
57    value_pushes: usize,
58    #[cfg(test)]
59    pending_nodes: usize,
60    #[cfg(test)]
61    pending_values: usize,
62    #[cfg(test)]
63    node_high_water: usize,
64    #[cfg(test)]
65    value_high_water: usize,
66    #[cfg(test)]
67    combined_high_water: usize,
68    #[cfg(test)]
69    yielded_by_leaf: Vec<usize>,
70}
71
72#[cfg(test)]
73#[derive(Clone, Copy, Debug)]
74pub(crate) struct NearestMetrics {
75    pub(crate) frontier: FrontierMetrics,
76    pub(crate) branch_expansions: usize,
77    pub(crate) leaf_expansions: usize,
78    pub(crate) node_pushes: usize,
79    pub(crate) value_pushes: usize,
80    pub(crate) node_pops: usize,
81    pub(crate) value_pops: usize,
82    pub(crate) contributing_leaves: usize,
83    pub(crate) max_yields_per_leaf: usize,
84    pub(crate) node_high_water: usize,
85    pub(crate) value_high_water: usize,
86}
87
88impl<'a, T, const NODE_INLINE_CAPACITY: usize, const VALUE_INLINE_CAPACITY: usize>
89    NearestIter<'a, T, NODE_INLINE_CAPACITY, VALUE_INLINE_CAPACITY>
90{
91    pub(crate) fn new(root: &'a Node<T>, query: [f64; 2]) -> Self {
92        let mut nodes = SearchFrontier::new();
93        nodes.push(DistanceEntry {
94            dist: 0.0,
95            item: root,
96            #[cfg(test)]
97            source_leaf: None,
98        });
99        Self {
100            query,
101            nodes,
102            values: SearchFrontier::new(),
103            #[cfg(test)]
104            branch_expansions: 0,
105            #[cfg(test)]
106            leaf_expansions: 0,
107            #[cfg(test)]
108            node_pushes: 1,
109            #[cfg(test)]
110            value_pushes: 0,
111            #[cfg(test)]
112            pending_nodes: 1,
113            #[cfg(test)]
114            pending_values: 0,
115            #[cfg(test)]
116            node_high_water: 1,
117            #[cfg(test)]
118            value_high_water: 0,
119            #[cfg(test)]
120            combined_high_water: 1,
121            #[cfg(test)]
122            yielded_by_leaf: Vec::new(),
123        }
124    }
125
126    #[cfg(test)]
127    pub(crate) fn metrics(&self) -> NearestMetrics {
128        let nodes = self.nodes.metrics();
129        let values = self.values.metrics();
130        NearestMetrics {
131            frontier: FrontierMetrics {
132                pushes: nodes.pushes + values.pushes,
133                pops: nodes.pops + values.pops,
134                high_water: self.combined_high_water,
135            },
136            branch_expansions: self.branch_expansions,
137            leaf_expansions: self.leaf_expansions,
138            node_pushes: self.node_pushes,
139            value_pushes: self.value_pushes,
140            node_pops: nodes.pops,
141            value_pops: values.pops,
142            contributing_leaves: self
143                .yielded_by_leaf
144                .iter()
145                .filter(|&&yielded| yielded != 0)
146                .count(),
147            max_yields_per_leaf: self.yielded_by_leaf.iter().copied().max().unwrap_or(0),
148            node_high_water: self.node_high_water,
149            value_high_water: self.value_high_water,
150        }
151    }
152
153    #[cfg(test)]
154    fn yielded_by_leaf(&self) -> &[usize] {
155        &self.yielded_by_leaf
156    }
157}
158
159impl<'a, T: Indexable, const NODE_INLINE_CAPACITY: usize, const VALUE_INLINE_CAPACITY: usize>
160    Iterator for NearestIter<'a, T, NODE_INLINE_CAPACITY, VALUE_INLINE_CAPACITY>
161{
162    type Item = &'a T;
163
164    /// Correctness of the yield order: a child's box is contained in
165    /// its parent's, so every entry pushed by an expansion is at least
166    /// as far as the node it came from — a value that pops is nearer
167    /// than everything still unexpanded.
168    fn next(&mut self) -> Option<&'a T> {
169        loop {
170            let node_dist = self.nodes.peek().map(DistanceEntry::dist);
171            let value_dist = self.values.peek().map(DistanceEntry::dist);
172            if value_dist
173                .is_some_and(|value| node_dist.is_none_or(|node| value.total_cmp(&node).is_le()))
174            {
175                let value = self
176                    .values
177                    .pop()
178                    .expect("a distance was just read from the value frontier");
179                #[cfg(test)]
180                {
181                    self.pending_values -= 1;
182                    self.yielded_by_leaf[value
183                        .source_leaf
184                        .expect("only value entries enter the value frontier")] += 1;
185                }
186                return Some(value.item);
187            }
188
189            let node = self.nodes.pop()?;
190            match node.item {
191                Node::Leaf(values) => {
192                    #[cfg(test)]
193                    let source_leaf = {
194                        self.pending_nodes -= 1;
195                        self.leaf_expansions += 1;
196                        self.value_pushes += values.len();
197                        self.pending_values += values.len();
198                        self.value_high_water = self.value_high_water.max(self.pending_values);
199                        self.combined_high_water = self
200                            .combined_high_water
201                            .max(self.pending_nodes + self.pending_values);
202                        self.yielded_by_leaf.push(0);
203                        self.yielded_by_leaf.len() - 1
204                    };
205                    let query = self.query;
206                    self.values.extend(values.iter().map(|value| DistanceEntry {
207                        dist: value.bounds().comparable_min_distance_to(query),
208                        item: value,
209                        #[cfg(test)]
210                        source_leaf: Some(source_leaf),
211                    }));
212                }
213                Node::Branch(children) => {
214                    #[cfg(test)]
215                    {
216                        self.pending_nodes -= 1;
217                        self.branch_expansions += 1;
218                        self.node_pushes += children.len();
219                        self.pending_nodes += children.len();
220                        self.node_high_water = self.node_high_water.max(self.pending_nodes);
221                        self.combined_high_water = self
222                            .combined_high_water
223                            .max(self.pending_nodes + self.pending_values);
224                    }
225                    let query = self.query;
226                    self.nodes
227                        .extend(children.iter().map(|(bounds, child)| DistanceEntry {
228                            dist: bounds.comparable_min_distance_to(query),
229                            item: child,
230                            #[cfg(test)]
231                            source_leaf: None,
232                        }));
233                }
234            }
235        }
236    }
237}
238
239impl<T: Indexable, const NODE_INLINE_CAPACITY: usize, const VALUE_INLINE_CAPACITY: usize>
240    FusedIterator for NearestIter<'_, T, NODE_INLINE_CAPACITY, VALUE_INLINE_CAPACITY>
241{
242}
243
244/// A node or value keyed by its squared minimum distance to the query.
245struct DistanceEntry<'a, T> {
246    dist: f64,
247    item: &'a T,
248    #[cfg(test)]
249    source_leaf: Option<usize>,
250}
251
252impl<T> DistanceEntry<'_, T> {
253    fn dist(&self) -> f64 {
254        self.dist
255    }
256}
257
258impl<T> PartialEq for DistanceEntry<'_, T> {
259    fn eq(&self, other: &Self) -> bool {
260        self.dist().total_cmp(&other.dist()).is_eq()
261    }
262}
263
264impl<T> Eq for DistanceEntry<'_, T> {}
265
266impl<T> PartialOrd for DistanceEntry<'_, T> {
267    fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
268        Some(self.cmp(other))
269    }
270}
271
272impl<T> Ord for DistanceEntry<'_, T> {
273    /// Reversed so the max-first [`SearchFrontier`] pops the SMALLEST
274    /// distance first.
275    fn cmp(&self, other: &Self) -> core::cmp::Ordering {
276        other.dist().total_cmp(&self.dist())
277    }
278}
279
280#[cfg(test)]
281mod tests {
282    use super::{DEFAULT_NODE_INLINE_CAPACITY, DEFAULT_VALUE_INLINE_CAPACITY, NearestMetrics};
283    use crate::{AsymmetricQuadratic, AsymmetricRStarSplit, Bounds, Rtree, SplitParameters};
284    use core::mem::size_of;
285    use rstar::primitives::GeomWithData;
286    use rstar::{ParentNode, PointDistance, RTree, RTreeNode};
287    use std::collections::BinaryHeap;
288
289    const FIELD: f64 = 50_000.0;
290    const CLUSTER_COUNT: usize = 16;
291    const CLUSTER_RADIUS: f64 = 100.0;
292    const N: usize = 50_000;
293    const Q: usize = 100;
294    const K: usize = 8;
295
296    type RstarValue = GeomWithData<[f64; 2], u32>;
297
298    struct RstarEntry<'a> {
299        node: &'a RTreeNode<RstarValue>,
300        dist: f64,
301    }
302
303    impl PartialEq for RstarEntry<'_> {
304        fn eq(&self, other: &Self) -> bool {
305            self.dist.total_cmp(&other.dist).is_eq()
306        }
307    }
308
309    impl Eq for RstarEntry<'_> {}
310
311    impl PartialOrd for RstarEntry<'_> {
312        fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
313            Some(self.cmp(other))
314        }
315    }
316
317    impl Ord for RstarEntry<'_> {
318        fn cmp(&self, other: &Self) -> core::cmp::Ordering {
319            other.dist.total_cmp(&self.dist)
320        }
321    }
322
323    #[derive(Default)]
324    struct RstarMetrics {
325        pushes: usize,
326        parent_pushes: usize,
327        leaf_pushes: usize,
328        pops: usize,
329        parent_expansions: usize,
330        leaf_parent_expansions: usize,
331        leaf_yields: usize,
332        high_water: usize,
333    }
334
335    fn extend_rstar<'a>(
336        parent: &'a ParentNode<RstarValue>,
337        query: &[f64; 2],
338        heap: &mut BinaryHeap<RstarEntry<'a>>,
339        metrics: &mut RstarMetrics,
340    ) {
341        for node in parent.children() {
342            match node {
343                RTreeNode::Parent(_) => metrics.parent_pushes += 1,
344                RTreeNode::Leaf(_) => metrics.leaf_pushes += 1,
345            }
346        }
347        heap.extend(parent.children().iter().map(|node| {
348            let dist = match node {
349                RTreeNode::Parent(parent) => parent.envelope().distance_2(query),
350                RTreeNode::Leaf(value) => value.distance_2(query),
351            };
352            RstarEntry { node, dist }
353        }));
354        metrics.pushes += parent.children().len();
355        metrics.high_water = metrics.high_water.max(heap.len());
356    }
357
358    fn measure_rstar(tree: &RTree<RstarValue>, query: [f64; 2]) -> RstarMetrics {
359        let mut metrics = RstarMetrics::default();
360        let mut heap = BinaryHeap::new();
361        extend_rstar(tree.root(), &query, &mut heap, &mut metrics);
362        while metrics.leaf_yields < K {
363            let current = heap.pop().expect("fixture tree contains K values");
364            metrics.pops += 1;
365            match current.node {
366                RTreeNode::Parent(parent) => {
367                    metrics.parent_expansions += 1;
368                    if parent
369                        .children()
370                        .first()
371                        .is_some_and(|child| matches!(child, RTreeNode::Leaf(_)))
372                    {
373                        metrics.leaf_parent_expansions += 1;
374                    }
375                    extend_rstar(parent, &query, &mut heap, &mut metrics);
376                }
377                RTreeNode::Leaf(_) => metrics.leaf_yields += 1,
378            }
379        }
380        metrics
381    }
382
383    struct Lcg {
384        state: u64,
385    }
386
387    impl Lcg {
388        fn new() -> Self {
389            Self {
390                state: 0x9E37_79B9_7F4A_7C15,
391            }
392        }
393
394        #[allow(
395            clippy::cast_precision_loss,
396            reason = "state >> 11 keeps 53 bits, exact in f64"
397        )]
398        fn next_f64(&mut self) -> f64 {
399            self.state = self
400                .state
401                .wrapping_mul(6_364_136_223_846_793_005)
402                .wrapping_add(1_442_695_040_888_963_407);
403            (self.state >> 11) as f64 / (1u64 << 53) as f64
404        }
405    }
406
407    fn uniform(n: usize) -> Vec<[f64; 2]> {
408        let mut lcg = Lcg::new();
409        (0..n)
410            .map(|_| [lcg.next_f64() * FIELD, lcg.next_f64() * FIELD])
411            .collect()
412    }
413
414    fn clustered(n: usize) -> Vec<[f64; 2]> {
415        let mut lcg = Lcg::new();
416        let centers: Vec<[f64; 2]> = (0..CLUSTER_COUNT)
417            .map(|_| [lcg.next_f64() * FIELD, lcg.next_f64() * FIELD])
418            .collect();
419        (0..n)
420            .map(|i| {
421                let center = centers[i % CLUSTER_COUNT];
422                [
423                    center[0] + lcg.next_f64() * 2.0 * CLUSTER_RADIUS - CLUSTER_RADIUS,
424                    center[1] + lcg.next_f64() * 2.0 * CLUSTER_RADIUS - CLUSTER_RADIUS,
425                ]
426            })
427            .collect()
428    }
429
430    fn queries(q: usize) -> Vec<[f64; 2]> {
431        let mut lcg = Lcg::new();
432        (0..q)
433            .map(|_| {
434                let x = lcg.next_f64() * FIELD;
435                lcg.next_f64();
436                let y = lcg.next_f64() * FIELD;
437                [x, y]
438            })
439            .collect()
440    }
441
442    fn measure<Params: SplitParameters>() -> (usize, usize, usize, usize, usize) {
443        let tree: Rtree<(Bounds, u32), Params> = uniform(N)
444            .into_iter()
445            .enumerate()
446            .map(|(i, point)| (Bounds::point(point), u32::try_from(i).expect("N fits u32")))
447            .collect();
448        let mut total_pushes = 0;
449        let mut total_pops = 0;
450        let mut max_high_water = 0;
451        let mut branch_expansions = 0;
452        let mut leaf_expansions = 0;
453        for query in queries(Q) {
454            let mut nearest = tree.nearest_iter(query);
455            assert_eq!(nearest.by_ref().take(K).count(), K);
456            let NearestMetrics {
457                frontier,
458                branch_expansions: branches,
459                leaf_expansions: leaves,
460                ..
461            } = nearest.metrics();
462            total_pushes += frontier.pushes;
463            total_pops += frontier.pops;
464            max_high_water = max_high_water.max(frontier.high_water);
465            branch_expansions += branches;
466            leaf_expansions += leaves;
467        }
468        (
469            total_pushes,
470            total_pops,
471            max_high_water,
472            branch_expansions,
473            leaf_expansions,
474        )
475    }
476
477    #[test]
478    fn asymmetric_fanout_reduces_knn_frontier_work() {
479        let baseline = measure::<crate::Quadratic<32, 9>>();
480        let default = measure::<AsymmetricRStarSplit<6, 2, 12, 4, 4, 4>>();
481        assert!(
482            default.0 < baseline.0 * 7 / 10,
483            "default asymmetric fanout must cut frontier pushes by at least 30%: baseline={baseline:?}, default={default:?}"
484        );
485        assert!(default.2 < baseline.2);
486        eprintln!(
487            "[rtree-asymmetric-fanout] config=branch32_leaf32 expected_high_water=267 observed={baseline:?}"
488        );
489        for (name, observed) in [
490            (
491                "branch6_leaf32",
492                measure::<AsymmetricQuadratic<6, 2, 32, 9>>(),
493            ),
494            ("default_insert6_leaf12_bulk4_4", default),
495            (
496                "branch12_leaf32",
497                measure::<AsymmetricQuadratic<12, 4, 32, 9>>(),
498            ),
499            (
500                "branch16_leaf32",
501                measure::<AsymmetricQuadratic<16, 4, 32, 9>>(),
502            ),
503        ] {
504            eprintln!(
505                "[rtree-asymmetric-fanout] config={name} expected_pushes_below={} observed={observed:?}",
506                baseline.0 * 7 / 10
507            );
508        }
509        for (name, observed) in [
510            (
511                "branch8_leaf6",
512                measure::<AsymmetricQuadratic<8, 3, 6, 2>>(),
513            ),
514            (
515                "branch8_leaf8",
516                measure::<AsymmetricQuadratic<8, 3, 8, 3>>(),
517            ),
518            (
519                "branch8_leaf12",
520                measure::<AsymmetricQuadratic<8, 3, 12, 4>>(),
521            ),
522            (
523                "branch8_leaf16",
524                measure::<AsymmetricQuadratic<8, 3, 16, 4>>(),
525            ),
526            (
527                "branch8_leaf24",
528                measure::<AsymmetricQuadratic<8, 3, 24, 7>>(),
529            ),
530            ("branch8_leaf32", default),
531        ] {
532            eprintln!("[rtree-leaf-fanout] config={name} observed={observed:?}");
533        }
534    }
535
536    #[test]
537    fn records_rstar_iterator_shape_comparison() {
538        for (distribution, points) in [("uniform", uniform(N)), ("clustered", clustered(N))] {
539            let boost: Rtree<(Bounds, u32), AsymmetricRStarSplit<8, 3, 32, 9>> = points
540                .iter()
541                .copied()
542                .enumerate()
543                .map(|(i, point)| (Bounds::point(point), u32::try_from(i).expect("N fits u32")))
544                .collect();
545            let rstar = RTree::bulk_load(
546                points
547                    .into_iter()
548                    .enumerate()
549                    .map(|(i, point)| {
550                        GeomWithData::new(point, u32::try_from(i).expect("N fits u32"))
551                    })
552                    .collect(),
553            );
554
555            let mut boost_pushes = 0;
556            let mut boost_pops = 0;
557            let mut boost_branches = 0;
558            let mut boost_leaves = 0;
559            let mut boost_node_pushes = 0;
560            let mut boost_value_pushes = 0;
561            let mut boost_node_pops = 0;
562            let mut boost_value_pops = 0;
563            let mut boost_contributing_leaves = 0;
564            let mut boost_max_yields_per_leaf = 0;
565            let mut boost_leaf_yield_histogram = [0usize; K + 1];
566            let mut boost_leaf_expansions_per_query = Vec::with_capacity(Q);
567            let mut boost_node_high_water = 0;
568            let mut boost_value_high_water = 0;
569            let mut rstar_pushes = 0;
570            let mut rstar_parent_pushes = 0;
571            let mut rstar_leaf_pushes = 0;
572            let mut rstar_pops = 0;
573            let mut rstar_parents = 0;
574            let mut rstar_leaf_parents = 0;
575            let mut rstar_high_water = 0;
576
577            for query in queries(Q) {
578                let mut nearest = boost.nearest_iter(query);
579                assert_eq!(nearest.by_ref().take(K).count(), K);
580                let metrics = nearest.metrics();
581                boost_pushes += metrics.frontier.pushes;
582                boost_pops += metrics.frontier.pops;
583                boost_branches += metrics.branch_expansions;
584                boost_leaves += metrics.leaf_expansions;
585                boost_node_pushes += metrics.node_pushes;
586                boost_value_pushes += metrics.value_pushes;
587                boost_node_pops += metrics.node_pops;
588                boost_value_pops += metrics.value_pops;
589                boost_contributing_leaves += metrics.contributing_leaves;
590                boost_max_yields_per_leaf =
591                    boost_max_yields_per_leaf.max(metrics.max_yields_per_leaf);
592                boost_leaf_expansions_per_query.push(metrics.leaf_expansions);
593                for &yielded in nearest.yielded_by_leaf() {
594                    boost_leaf_yield_histogram[yielded] += 1;
595                }
596                boost_node_high_water = boost_node_high_water.max(metrics.node_high_water);
597                boost_value_high_water = boost_value_high_water.max(metrics.value_high_water);
598
599                let metrics = measure_rstar(&rstar, query);
600                assert_eq!(metrics.leaf_yields, K);
601                rstar_pushes += metrics.pushes;
602                rstar_parent_pushes += metrics.parent_pushes;
603                rstar_leaf_pushes += metrics.leaf_pushes;
604                rstar_pops += metrics.pops;
605                rstar_parents += metrics.parent_expansions;
606                rstar_leaf_parents += metrics.leaf_parent_expansions;
607                rstar_high_water = rstar_high_water.max(metrics.high_water);
608            }
609
610            boost_leaf_expansions_per_query.sort_unstable();
611            eprintln!(
612                "[rtree-leaf-release] distribution={distribution} expected_yields={} observed_value_pushes={boost_value_pushes} observed_value_pops={boost_value_pops} observed_leaf_expansions={boost_leaves} observed_leaf_expansions_p50={} observed_leaf_expansions_p95={} observed_leaf_expansions_max={} observed_contributing_leaves={boost_contributing_leaves} observed_max_yields_per_leaf={boost_max_yields_per_leaf} observed_leaf_yield_histogram={boost_leaf_yield_histogram:?}",
613                Q * K,
614                boost_leaf_expansions_per_query[Q / 2],
615                boost_leaf_expansions_per_query[Q * 95 / 100],
616                boost_leaf_expansions_per_query[Q - 1],
617            );
618            eprintln!(
619                "[rtree-rstar-iterator-shape] distribution={distribution} boost_pushes={boost_pushes} boost_pops={boost_pops} boost_branches={boost_branches} boost_leaves={boost_leaves} boost_node_pushes={boost_node_pushes} boost_value_pushes={boost_value_pushes} boost_node_pops={boost_node_pops} boost_value_pops={boost_value_pops} boost_node_high_water={boost_node_high_water} boost_value_high_water={boost_value_high_water} rstar_pushes={rstar_pushes} rstar_parent_pushes={rstar_parent_pushes} rstar_leaf_pushes={rstar_leaf_pushes} rstar_pops={rstar_pops} rstar_parents={rstar_parents} rstar_leaf_parents={rstar_leaf_parents} rstar_high_water={rstar_high_water}"
620            );
621        }
622    }
623
624    #[test]
625    fn records_split_frontier_capacity_distribution() {
626        for (distribution, points) in [("uniform", uniform(N)), ("clustered", clustered(N))] {
627            let tree: Rtree<(Bounds, u32), AsymmetricRStarSplit<8, 3, 32, 9>> = points
628                .into_iter()
629                .enumerate()
630                .map(|(i, point)| (Bounds::point(point), u32::try_from(i).expect("N fits u32")))
631                .collect();
632            let mut node_high_waters = Vec::with_capacity(Q);
633            let mut value_high_waters = Vec::with_capacity(Q);
634            for query in queries(Q) {
635                let mut nearest = tree.nearest_iter(query);
636                assert_eq!(nearest.by_ref().take(K).count(), K);
637                let metrics = nearest.metrics();
638                node_high_waters.push(metrics.node_high_water);
639                value_high_waters.push(metrics.value_high_water);
640            }
641            node_high_waters.sort_unstable();
642            value_high_waters.sort_unstable();
643            let node_spills = Q - node_high_waters
644                .partition_point(|&water| water <= DEFAULT_NODE_INLINE_CAPACITY);
645            let value_spills = Q - value_high_waters
646                .partition_point(|&water| water <= DEFAULT_VALUE_INLINE_CAPACITY);
647            let spills_at = |high_waters: &[usize], capacity| {
648                Q - high_waters.partition_point(|&water| water <= capacity)
649            };
650            let release_entry_bytes = size_of::<f64>() + size_of::<&(Bounds, u32)>();
651            eprintln!(
652                "[rtree-split-frontier] distribution={distribution} expected_node_capacity={DEFAULT_NODE_INLINE_CAPACITY} observed_node_spills={node_spills}/{Q} observed_node_p50={} observed_node_p95={} observed_node_max={} observed_node_spills_64_96_128={}/{}/{} expected_value_capacity={DEFAULT_VALUE_INLINE_CAPACITY} observed_value_spills={value_spills}/{Q} observed_value_p50={} observed_value_p95={} observed_value_max={} observed_value_spills_128_160_192_256={}/{}/{}/{} observed_entry_bytes={} observed_total_inline_bytes={}",
653                node_high_waters[Q / 2],
654                node_high_waters[Q * 95 / 100],
655                node_high_waters[Q - 1],
656                spills_at(&node_high_waters, 64),
657                spills_at(&node_high_waters, 96),
658                spills_at(&node_high_waters, 128),
659                value_high_waters[Q / 2],
660                value_high_waters[Q * 95 / 100],
661                value_high_waters[Q - 1],
662                spills_at(&value_high_waters, 128),
663                spills_at(&value_high_waters, 160),
664                spills_at(&value_high_waters, 192),
665                spills_at(&value_high_waters, 256),
666                release_entry_bytes,
667                (DEFAULT_NODE_INLINE_CAPACITY + DEFAULT_VALUE_INLINE_CAPACITY)
668                    * release_entry_bytes,
669            );
670        }
671    }
672
673    #[test]
674    fn caller_selected_inline_capacities_preserve_distance_order() {
675        let tree: Rtree<(Bounds, u32)> = uniform(2_000)
676            .into_iter()
677            .enumerate()
678            .map(|(i, point)| (Bounds::point(point), u32::try_from(i).expect("N fits u32")))
679            .collect();
680        let query = [12_345.0, 23_456.0];
681        let mut expected: Vec<f64> = tree
682            .nearest_iter(query)
683            .take(64)
684            .map(|(bounds, _)| bounds.comparable_min_distance_to(query))
685            .collect();
686        let actual: Vec<f64> = tree
687            .nearest_iter_with_inline_capacities::<0, 0>(query)
688            .take(64)
689            .map(|(bounds, _)| bounds.comparable_min_distance_to(query))
690            .collect();
691
692        expected.sort_by(f64::total_cmp);
693        assert_eq!(
694            actual, expected,
695            "the all-spill configuration must stay exact"
696        );
697    }
698}
geometry_rtree/nearest_iter.rs

geometry_rtree/
nearest_iter.rs
