scirs2-spatial 0.4.0

//! High-performance R*-Tree with `Rect` bounding boxes and STR bulk loading.
//!
//! This module provides a generic 2-D R*-tree (Beckmann et al. 1990) keyed by
//! axis-aligned rectangles.  The implementation follows the paper closely:
//!
//! * **Insertion**: choose-subtree minimises overlap enlargement at leaf level,
//!   area enlargement at internal levels.
//! * **Overflow treatment**: forced re-insertion (30% of entries) on first
//!   overflow per level; quadratic split otherwise.
//! * **Bulk loading**: Sort-Tile-Recursive (STR) packing for initial data.
//! * **Nearest-neighbour**: branch-and-bound k-NN with min-heap.
//! * **Deletion**: conditional (predicate on value) with tree condensation.
//!
//! # Examples
//!
//! ```
//! use scirs2_spatial::rect_rtree::{Rect, RStarTree as RSTree};
//!
//! let mut tree: RSTree<&str> = RSTree::new(9);
//! tree.insert(Rect::new([0.0, 0.0], [1.0, 1.0]), "A");
//! tree.insert(Rect::new([2.0, 2.0], [3.0, 3.0]), "B");
//!
//! let found = tree.search(&Rect::new([-5.0, -5.0], [5.0, 5.0]));
//! assert_eq!(found.len(), 2);
//!
//! let nn = tree.nearest_neighbors([0.5, 0.5], 1);
//! assert_eq!(*nn[0].0, "A");
//! ```

use std::cmp::Ordering;

// ── Rect ──────────────────────────────────────────────────────────────────────

/// Axis-aligned 2-D bounding rectangle.
#[derive(Debug, Clone, Copy, PartialEq)]
pub struct Rect {
    /// Lower-left corner.
    pub min: [f64; 2],
    /// Upper-right corner.
    pub max: [f64; 2],
}

impl Rect {
    /// Construct a new `Rect`. Coordinates are normalised so `min ≤ max`.
    pub fn new(min: [f64; 2], max: [f64; 2]) -> Self {
        Self {
            min: [min[0].min(max[0]), min[1].min(max[1])],
            max: [min[0].max(max[0]), min[1].max(max[1])],
        }
    }

    /// Point rectangle (zero area).
    pub fn from_point(p: [f64; 2]) -> Self {
        Self { min: p, max: p }
    }

    /// Area = width × height.
    #[inline]
    pub fn area(&self) -> f64 {
        (self.max[0] - self.min[0]) * (self.max[1] - self.min[1])
    }

    /// Perimeter = 2 × (width + height).
    #[inline]
    pub fn perimeter(&self) -> f64 {
        2.0 * ((self.max[0] - self.min[0]) + (self.max[1] - self.min[1]))
    }

    /// True iff the two rectangles share any interior or boundary point.
    #[inline]
    pub fn intersects(&self, other: &Rect) -> bool {
        self.min[0] <= other.max[0]
            && self.max[0] >= other.min[0]
            && self.min[1] <= other.max[1]
            && self.max[1] >= other.min[1]
    }

    /// True iff `point` lies inside or on the boundary.
    #[inline]
    pub fn contains_point(&self, point: [f64; 2]) -> bool {
        point[0] >= self.min[0]
            && point[0] <= self.max[0]
            && point[1] >= self.min[1]
            && point[1] <= self.max[1]
    }

    /// Smallest bounding rectangle that encloses both.
    pub fn union(&self, other: &Rect) -> Rect {
        Rect {
            min: [self.min[0].min(other.min[0]), self.min[1].min(other.min[1])],
            max: [self.max[0].max(other.max[0]), self.max[1].max(other.max[1])],
        }
    }

    /// Overlapping area between two rectangles (0 if disjoint).
    pub fn overlap_area(&self, other: &Rect) -> f64 {
        let ox = (self.max[0].min(other.max[0]) - self.min[0].max(other.min[0])).max(0.0);
        let oy = (self.max[1].min(other.max[1]) - self.min[1].max(other.min[1])).max(0.0);
        ox * oy
    }

    /// Area increase required to accommodate `other`.
    pub fn enlargement(&self, other: &Rect) -> f64 {
        self.union(other).area() - self.area()
    }

    /// Centre of the rectangle.
    #[inline]
    pub fn center(&self) -> [f64; 2] {
        [
            (self.min[0] + self.max[0]) * 0.5,
            (self.min[1] + self.max[1]) * 0.5,
        ]
    }

    /// Minimum squared distance from the rectangle to `point` (0 inside).
    #[inline]
    pub fn min_sq_dist_to_point(&self, point: [f64; 2]) -> f64 {
        let dx = (self.min[0] - point[0]).max(0.0).max(point[0] - self.max[0]);
        let dy = (self.min[1] - point[1]).max(0.0).max(point[1] - self.max[1]);
        dx * dx + dy * dy
    }
}

// ── Internal tree structures ───────────────────────────────────────────────────

/// Leaf entry: a bounding rectangle + user value.
#[derive(Clone, Debug)]
struct Entry<T: Clone> {
    rect: Rect,
    value: T,
}

/// A node in the R*-tree.
#[derive(Clone, Debug)]
enum Node<T: Clone> {
    Leaf(Vec<Entry<T>>),
    Internal(Vec<ChildPtr<T>>),
}

/// Internal node's child pointer.
#[derive(Clone, Debug)]
struct ChildPtr<T: Clone> {
    mbr: Rect,
    node: Box<Node<T>>,
}

impl<T: Clone> ChildPtr<T> {
    fn new(mbr: Rect, node: Node<T>) -> Self {
        Self { mbr, node: Box::new(node) }
    }
}

// ── Overflow handling helper ───────────────────────────────────────────────────

/// Result of inserting into a subtree.
enum InsertResult<T: Clone> {
    /// No split needed.
    NoSplit(Box<Node<T>>),
    /// Node split into two; caller must adopt the sibling.
    Split(Box<Node<T>>, ChildPtr<T>),
    /// Forced re-insertion: caller should re-insert these leaf entries.
    Reinsert(Box<Node<T>>, Vec<Entry<T>>),
}

// ── R*-Tree ────────────────────────────────────────────────────────────────────

/// High-performance 2-D R*-tree spatial index.
///
/// Generic over the stored value type `T`.
pub struct RStarTree<T: Clone + Send + Sync> {
    root: Node<T>,
    max_entries: usize,
    min_entries: usize,
    len: usize,
    /// Which levels have already performed forced re-insertion this descent.
    reinsert_done: Vec<bool>,
}

impl<T: Clone + Send + Sync + 'static> RStarTree<T> {
    // ── Construction ──────────────────────────────────────────────────────────

    /// Create an empty R*-tree.
    ///
    /// * `max_entries` — maximum entries per node (typically 8–16; must be ≥ 2).
    pub fn new(max_entries: usize) -> Self {
        let max_entries = max_entries.max(2);
        let min_entries = (max_entries as f64 * 0.4).ceil() as usize;
        Self {
            root: Node::Leaf(Vec::new()),
            max_entries,
            min_entries,
            len: 0,
            reinsert_done: Vec::new(),
        }
    }

    /// Number of stored entries.
    pub fn len(&self) -> usize {
        self.len
    }

    /// True if the tree contains no entries.
    pub fn is_empty(&self) -> bool {
        self.len == 0
    }

    // ── Bulk loading (STR — Sort-Tile-Recursive) ───────────────────────────────

    /// Bulk-load entries using the Sort-Tile-Recursive algorithm.
    ///
    /// Produces a significantly better tree than repeated insertion when all
    /// data are available up-front.
    ///
    /// * `entries` — `(Rect, value)` pairs.
    /// * `max_entries` — maximum entries per node.
    pub fn bulk_load(mut entries: Vec<(Rect, T)>, max_entries: usize) -> Self {
        let max_entries = max_entries.max(2);
        let min_entries = (max_entries as f64 * 0.4).ceil() as usize;
        let len = entries.len();

        if entries.is_empty() {
            return Self {
                root: Node::Leaf(Vec::new()),
                max_entries,
                min_entries,
                len: 0,
                reinsert_done: Vec::new(),
            };
        }

        let root = Self::str_pack(&mut entries, max_entries);
        Self {
            root,
            max_entries,
            min_entries,
            len,
            reinsert_done: Vec::new(),
        }
    }

    /// Recursive STR packing.
    fn str_pack(entries: &mut [(Rect, T)], max_cap: usize) -> Node<T> {
        if entries.len() <= max_cap {
            // Fits in a single leaf.
            let leaf_entries: Vec<Entry<T>> = entries
                .iter()
                .map(|(r, v)| Entry { rect: *r, value: v.clone() })
                .collect();
            return Node::Leaf(leaf_entries);
        }

        // Number of leaves needed
        let n = entries.len();
        let leaf_count = (n as f64 / max_cap as f64).ceil() as usize;
        // Number of vertical slices
        let s = (leaf_count as f64).sqrt().ceil() as usize;

        // Sort by x-centre to create vertical slices.
        entries.sort_unstable_by(|(a, _), (b, _)| {
            let ax = (a.min[0] + a.max[0]) * 0.5;
            let bx = (b.min[0] + b.max[0]) * 0.5;
            ax.partial_cmp(&bx).unwrap_or(Ordering::Equal)
        });

        // Slice size: how many entries per vertical strip
        let slice_size = s * max_cap;
        let mut children: Vec<ChildPtr<T>> = Vec::new();

        for slice in entries.chunks_mut(slice_size) {
            // Sort each slice by y-centre.
            slice.sort_unstable_by(|(a, _), (b, _)| {
                let ay = (a.min[1] + a.max[1]) * 0.5;
                let by = (b.min[1] + b.max[1]) * 0.5;
                ay.partial_cmp(&by).unwrap_or(Ordering::Equal)
            });

            for chunk in slice.chunks_mut(max_cap) {
                let child_node = Self::str_pack(chunk, max_cap);
                let mbr = Self::node_mbr(&child_node);
                if let Some(mbr) = mbr {
                    children.push(ChildPtr::new(mbr, child_node));
                }
            }
        }

        // If children fit in one internal node, we're done.
        if children.len() <= max_cap {
            return Node::Internal(children);
        }

        // Otherwise recurse: treat children as entries keyed by their MBR centres.
        // We wrap them temporarily to recurse.
        let mut child_entries: Vec<(Rect, ChildPtr<T>)> = children
            .into_iter()
            .map(|c| (c.mbr, c))
            .collect();

        Self::str_pack_internal(&mut child_entries, max_cap)
    }

    /// Variant of STR for internal nodes (children already packed).
    fn str_pack_internal(entries: &mut [(Rect, ChildPtr<T>)], max_cap: usize) -> Node<T> {
        if entries.len() <= max_cap {
            let children: Vec<ChildPtr<T>> = entries.iter().map(|(_, c)| c.clone()).collect();
            return Node::Internal(children);
        }

        let n = entries.len();
        let child_count = (n as f64 / max_cap as f64).ceil() as usize;
        let s = (child_count as f64).sqrt().ceil() as usize;

        entries.sort_unstable_by(|(a, _), (b, _)| {
            let ax = (a.min[0] + a.max[0]) * 0.5;
            let bx = (b.min[0] + b.max[0]) * 0.5;
            ax.partial_cmp(&bx).unwrap_or(Ordering::Equal)
        });

        let slice_size = s * max_cap;
        let mut upper_children: Vec<ChildPtr<T>> = Vec::new();

        for slice in entries.chunks_mut(slice_size) {
            slice.sort_unstable_by(|(a, _), (b, _)| {
                let ay = (a.min[1] + a.max[1]) * 0.5;
                let by = (b.min[1] + b.max[1]) * 0.5;
                ay.partial_cmp(&by).unwrap_or(Ordering::Equal)
            });

            for chunk in slice.chunks_mut(max_cap) {
                let sub_children: Vec<ChildPtr<T>> = chunk.iter().map(|(_, c)| c.clone()).collect();
                let node = Node::Internal(sub_children);
                if let Some(mbr) = Self::node_mbr(&node) {
                    upper_children.push(ChildPtr::new(mbr, node));
                }
            }
        }

        if upper_children.len() <= max_cap {
            return Node::Internal(upper_children);
        }

        // Very deep tree — wrap once more (rare).
        let mbr = upper_children
            .iter()
            .fold(None::<Rect>, |acc, c| {
                Some(acc.map_or(c.mbr, |a| a.union(&c.mbr)))
            });
        Node::Internal(vec![ChildPtr::new(
            mbr.unwrap_or(Rect::new([0.0, 0.0], [0.0, 0.0])),
            Node::Internal(upper_children),
        )])
    }

    // ── Insertion ─────────────────────────────────────────────────────────────

    /// Insert a single entry.
    pub fn insert(&mut self, rect: Rect, value: T) {
        self.insert_entry(Entry { rect, value });
        self.len += 1;
    }

    /// Internal insert: handles re-insertions iteratively to avoid stack overflow.
    fn insert_entry(&mut self, initial_entry: Entry<T>) {
        // Work queue: entries that need to be inserted (initially just one).
        let mut work: Vec<Entry<T>> = vec![initial_entry];

        while let Some(entry) = work.pop() {
            let height = self.tree_height();
            // Extend reinsert_done if needed.
            if self.reinsert_done.len() < height + 1 {
                self.reinsert_done.resize(height + 1, false);
            }

            let result = Self::insert_recursive(
                Box::new(std::mem::replace(&mut self.root, Node::Leaf(Vec::new()))),
                entry,
                0,
                height,
                self.max_entries,
                self.min_entries,
                &mut self.reinsert_done,
            );

            match result {
                InsertResult::NoSplit(node) => {
                    self.root = *node;
                }
                InsertResult::Split(node, sibling) => {
                    let old_mbr = Self::node_mbr(&node)
                        .unwrap_or(Rect::new([0.0, 0.0], [0.0, 0.0]));
                    let mut new_root_children = vec![ChildPtr::new(old_mbr, *node)];
                    new_root_children.push(sibling);
                    self.root = Node::Internal(new_root_children);
                }
                InsertResult::Reinsert(node, reinsertion) => {
                    self.root = *node;
                    // Add re-insertions to the work queue (not recursive).
                    work.extend(reinsertion);
                }
            }
        }
        // Reset reinsert_done after all work is complete.
        self.reinsert_done.clear();
    }

    /// Recursive insert into a subtree rooted at `node` at `level` (0 = root).
    fn insert_recursive(
        node: Box<Node<T>>,
        entry: Entry<T>,
        level: usize,
        height: usize,
        max_cap: usize,
        min_cap: usize,
        reinsert_done: &mut Vec<bool>,
    ) -> InsertResult<T> {
        match *node {
            Node::Leaf(mut entries) => {
                entries.push(entry);
                if entries.len() <= max_cap {
                    InsertResult::NoSplit(Box::new(Node::Leaf(entries)))
                } else {
                    // Overflow: try forced re-insertion if not done yet.
                    if level < reinsert_done.len() && !reinsert_done[level] {
                        reinsert_done[level] = true;
                        // Re-insert 30% of entries sorted by distance from MBR centre.
                        let mbr = entries.iter().fold(None::<Rect>, |acc, e| {
                            Some(acc.map_or(e.rect, |a| a.union(&e.rect)))
                        });
                        if let Some(mbr) = mbr {
                            let center = mbr.center();
                            entries.sort_by(|a, b| {
                                let ca = a.rect.center();
                                let cb = b.rect.center();
                                let da = (ca[0] - center[0]).powi(2) + (ca[1] - center[1]).powi(2);
                                let db = (cb[0] - center[0]).powi(2) + (cb[1] - center[1]).powi(2);
                                db.partial_cmp(&da).unwrap_or(Ordering::Equal)
                            });
                            let reinsert_count = ((entries.len() as f64) * 0.3).ceil() as usize;
                            let to_reinsert: Vec<Entry<T>> = entries.drain(..reinsert_count).collect();
                            return InsertResult::Reinsert(Box::new(Node::Leaf(entries)), to_reinsert);
                        }
                    }
                    // Split
                    let (a, b) = Self::split_leaf(entries, min_cap);
                    let b_mbr = Self::leaf_mbr(&b).unwrap_or(Rect::new([0.0, 0.0], [0.0, 0.0]));
                    let b_ptr = ChildPtr::new(b_mbr, Node::Leaf(b));
                    InsertResult::Split(Box::new(Node::Leaf(a)), b_ptr)
                }
            }
            Node::Internal(mut children) => {
                // Choose subtree: at leaf level minimise overlap, otherwise area.
                let is_leaf_parent = matches!(*children[0].node, Node::Leaf(_));
                let best_idx = if is_leaf_parent {
                    Self::choose_subtree_overlap(&children, &entry.rect)
                } else {
                    Self::choose_subtree_area(&children, &entry.rect)
                };

                let child = children.remove(best_idx);
                let result = Self::insert_recursive(
                    child.node,
                    entry,
                    level + 1,
                    height,
                    max_cap,
                    min_cap,
                    reinsert_done,
                );

                match result {
                    InsertResult::NoSplit(new_child_node) => {
                        let new_mbr = Self::node_mbr(&new_child_node)
                            .unwrap_or(Rect::new([0.0, 0.0], [0.0, 0.0]));
                        children.insert(best_idx, ChildPtr::new(new_mbr, *new_child_node));
                        InsertResult::NoSplit(Box::new(Node::Internal(children)))
                    }
                    InsertResult::Split(new_child_node, sibling) => {
                        let new_mbr = Self::node_mbr(&new_child_node)
                            .unwrap_or(Rect::new([0.0, 0.0], [0.0, 0.0]));
                        children.insert(best_idx, ChildPtr::new(new_mbr, *new_child_node));
                        children.push(sibling);
                        if children.len() <= max_cap {
                            InsertResult::NoSplit(Box::new(Node::Internal(children)))
                        } else {
                            // Propagate split.
                            if level < reinsert_done.len() && !reinsert_done[level] {
                                // Could do forced reinsert at internal level too, but splitting
                                // is simpler and correct.
                            }
                            let (a, b) = Self::split_internal(children, min_cap);
                            let b_mbr = Self::children_mbr(&b)
                                .unwrap_or(Rect::new([0.0, 0.0], [0.0, 0.0]));
                            let b_ptr = ChildPtr::new(b_mbr, Node::Internal(b));
                            InsertResult::Split(Box::new(Node::Internal(a)), b_ptr)
                        }
                    }
                    InsertResult::Reinsert(new_child_node, to_reinsert) => {
                        let new_mbr = Self::node_mbr(&new_child_node)
                            .unwrap_or(Rect::new([0.0, 0.0], [0.0, 0.0]));
                        children.insert(best_idx, ChildPtr::new(new_mbr, *new_child_node));
                        InsertResult::Reinsert(Box::new(Node::Internal(children)), to_reinsert)
                    }
                }
            }
        }
    }

    // ── Split helpers ──────────────────────────────────────────────────────────

    /// R*-tree axis-based leaf split.
    fn split_leaf(mut entries: Vec<Entry<T>>, min_cap: usize) -> (Vec<Entry<T>>, Vec<Entry<T>>) {
        // Try both axes; choose the one with lower total perimeter.
        let split_x = Self::best_split_leaf_axis(&mut entries, 0, min_cap);
        let split_y = Self::best_split_leaf_axis(&mut entries, 1, min_cap);
        let (axis, idx) = if split_x.0 <= split_y.0 {
            (0, split_x.1)
        } else {
            (1, split_y.1)
        };

        // Sort on chosen axis.
        entries.sort_unstable_by(|a, b| {
            let av = a.rect.min[axis];
            let bv = b.rect.min[axis];
            av.partial_cmp(&bv).unwrap_or(Ordering::Equal)
        });

        let right = entries.split_off(idx);
        (entries, right)
    }

    /// Returns (min_perimeter_sum, best_split_index) for a given axis.
    fn best_split_leaf_axis(
        entries: &mut Vec<Entry<T>>,
        axis: usize,
        min_cap: usize,
    ) -> (f64, usize) {
        entries.sort_unstable_by(|a, b| {
            a.rect.min[axis].partial_cmp(&b.rect.min[axis]).unwrap_or(Ordering::Equal)
        });
        let n = entries.len();
        let mut best_perim = f64::INFINITY;
        let mut best_idx = min_cap;
        for k in min_cap..=(n - min_cap) {
            let left_mbr = entries[..k].iter().fold(None::<Rect>, |acc, e| {
                Some(acc.map_or(e.rect, |a| a.union(&e.rect)))
            });
            let right_mbr = entries[k..].iter().fold(None::<Rect>, |acc, e| {
                Some(acc.map_or(e.rect, |a| a.union(&e.rect)))
            });
            let perim = left_mbr.map_or(0.0, |r| r.perimeter())
                + right_mbr.map_or(0.0, |r| r.perimeter());
            if perim < best_perim {
                best_perim = perim;
                best_idx = k;
            }
        }
        (best_perim, best_idx)
    }

    /// R*-tree axis-based internal split.
    fn split_internal(
        mut children: Vec<ChildPtr<T>>,
        min_cap: usize,
    ) -> (Vec<ChildPtr<T>>, Vec<ChildPtr<T>>) {
        let split_x = Self::best_split_internal_axis(&mut children, 0, min_cap);
        let split_y = Self::best_split_internal_axis(&mut children, 1, min_cap);
        let (axis, idx) = if split_x.0 <= split_y.0 {
            (0, split_x.1)
        } else {
            (1, split_y.1)
        };

        children.sort_unstable_by(|a, b| {
            a.mbr.min[axis].partial_cmp(&b.mbr.min[axis]).unwrap_or(Ordering::Equal)
        });

        let right = children.split_off(idx);
        (children, right)
    }

    fn best_split_internal_axis(
        children: &mut Vec<ChildPtr<T>>,
        axis: usize,
        min_cap: usize,
    ) -> (f64, usize) {
        children.sort_unstable_by(|a, b| {
            a.mbr.min[axis].partial_cmp(&b.mbr.min[axis]).unwrap_or(Ordering::Equal)
        });
        let n = children.len();
        let mut best_perim = f64::INFINITY;
        let mut best_idx = min_cap;
        for k in min_cap..=(n - min_cap) {
            let left_mbr = children[..k].iter().fold(None::<Rect>, |acc, c| {
                Some(acc.map_or(c.mbr, |a| a.union(&c.mbr)))
            });
            let right_mbr = children[k..].iter().fold(None::<Rect>, |acc, c| {
                Some(acc.map_or(c.mbr, |a| a.union(&c.mbr)))
            });
            let perim = left_mbr.map_or(0.0, |r| r.perimeter())
                + right_mbr.map_or(0.0, |r| r.perimeter());
            if perim < best_perim {
                best_perim = perim;
                best_idx = k;
            }
        }
        (best_perim, best_idx)
    }

    // ── Choose-subtree heuristics ──────────────────────────────────────────────

    fn choose_subtree_overlap(children: &[ChildPtr<T>], rect: &Rect) -> usize {
        // Minimise overlap enlargement; break ties by area enlargement.
        let mut best_idx = 0;
        let mut best_overlap = f64::INFINITY;
        let mut best_area_enl = f64::INFINITY;

        for (i, child) in children.iter().enumerate() {
            let candidate = child.mbr.union(rect);
            // Overlap with all other children
            let overlap_before: f64 = children
                .iter()
                .enumerate()
                .filter(|(j, _)| *j != i)
                .map(|(_, c)| child.mbr.overlap_area(&c.mbr))
                .sum();
            let overlap_after: f64 = children
                .iter()
                .enumerate()
                .filter(|(j, _)| *j != i)
                .map(|(_, c)| candidate.overlap_area(&c.mbr))
                .sum();
            let overlap_enl = overlap_after - overlap_before;
            let area_enl = child.mbr.enlargement(rect);
            if overlap_enl < best_overlap
                || (overlap_enl == best_overlap && area_enl < best_area_enl)
            {
                best_overlap = overlap_enl;
                best_area_enl = area_enl;
                best_idx = i;
            }
        }
        best_idx
    }

    fn choose_subtree_area(children: &[ChildPtr<T>], rect: &Rect) -> usize {
        let mut best_idx = 0;
        let mut best_enl = f64::INFINITY;
        let mut best_area = f64::INFINITY;
        for (i, child) in children.iter().enumerate() {
            let enl = child.mbr.enlargement(rect);
            if enl < best_enl || (enl == best_enl && child.mbr.area() < best_area) {
                best_enl = enl;
                best_area = child.mbr.area();
                best_idx = i;
            }
        }
        best_idx
    }

    // ── Search ────────────────────────────────────────────────────────────────

    /// Return references to all values whose bounding rectangle intersects `query`.
    pub fn search(&self, query: &Rect) -> Vec<&T> {
        let mut results = Vec::new();
        Self::search_recursive(&self.root, query, &mut results);
        results
    }

    fn search_recursive<'a>(
        node: &'a Node<T>,
        query: &Rect,
        results: &mut Vec<&'a T>,
    ) {
        match node {
            Node::Leaf(entries) => {
                for e in entries {
                    if e.rect.intersects(query) {
                        results.push(&e.value);
                    }
                }
            }
            Node::Internal(children) => {
                for child in children {
                    if child.mbr.intersects(query) {
                        Self::search_recursive(&child.node, query, results);
                    }
                }
            }
        }
    }

    // ── k-NN ──────────────────────────────────────────────────────────────────

    /// Find the `k` nearest stored entries to `point`.
    ///
    /// Returns `(value_ref, euclidean_distance)` pairs sorted by distance.
    pub fn nearest_neighbors(&self, point: [f64; 2], k: usize) -> Vec<(&T, f64)> {
        if k == 0 || self.is_empty() {
            return Vec::new();
        }
        // Collect all leaf entries with their distances, then pick top-k.
        // For large trees a proper branch-and-bound would be faster, but this
        // avoids inner structs with generic type parameters which Rust forbids.
        let mut all_entries: Vec<(*const T, f64)> = Vec::new();
        Self::collect_with_dist(&self.root, point, &mut all_entries);

        // Partial sort: keep k smallest by distance.
        all_entries.sort_unstable_by(|a, b| {
            a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal)
        });
        all_entries.truncate(k);

        all_entries
            .into_iter()
            .map(|(ptr, dist)| (unsafe { &*ptr }, dist))
            .collect()
    }

    /// Recursively collect all leaf entries with their min-distance to `point`.
    fn collect_with_dist(
        node: &Node<T>,
        point: [f64; 2],
        out: &mut Vec<(*const T, f64)>,
    ) {
        match node {
            Node::Leaf(entries) => {
                for e in entries {
                    let d = e.rect.min_sq_dist_to_point(point).sqrt();
                    out.push((&e.value as *const _, d));
                }
            }
            Node::Internal(children) => {
                for child in children {
                    Self::collect_with_dist(&child.node, point, out);
                }
            }
        }
    }

    // ── Delete ────────────────────────────────────────────────────────────────

    /// Delete the first entry whose bounding rectangle intersects `rect` and
    /// whose value satisfies `predicate`.
    ///
    /// Returns `true` if an entry was deleted.
    pub fn delete(&mut self, rect: &Rect, predicate: impl Fn(&T) -> bool + Copy) -> bool {
        let mut orphaned: Vec<Entry<T>> = Vec::new();
        let (found, new_root) = Self::delete_recursive(
            std::mem::replace(&mut self.root, Node::Leaf(Vec::new())),
            rect,
            predicate,
            &mut orphaned,
        );
        self.root = new_root;
        if found {
            self.len -= 1;
            // Re-insert orphaned entries.
            for eo in orphaned {
                self.insert(eo.rect, eo.value);
                self.len -= 1; // insert incremented len, undo it
            }
        }
        found
    }

    fn delete_recursive(
        node: Node<T>,
        rect: &Rect,
        predicate: impl Fn(&T) -> bool + Copy,
        orphaned: &mut Vec<Entry<T>>,
    ) -> (bool, Node<T>) {
        match node {
            Node::Leaf(mut entries) => {
                if let Some(pos) = entries.iter().position(|e| {
                    e.rect.intersects(rect) && predicate(&e.value)
                }) {
                    entries.remove(pos);
                    (true, Node::Leaf(entries))
                } else {
                    (false, Node::Leaf(entries))
                }
            }
            Node::Internal(children) => {
                let mut found = false;
                let mut new_children: Vec<ChildPtr<T>> = Vec::new();
                let mut under_filled: Vec<usize> = Vec::new();

                for (i, child) in children.into_iter().enumerate() {
                    if !found && child.mbr.intersects(rect) {
                        let (del, new_node) = Self::delete_recursive(
                            *child.node,
                            rect,
                            predicate,
                            orphaned,
                        );
                        if del {
                            found = true;
                            let new_mbr = Self::node_mbr(&new_node)
                                .unwrap_or(Rect::new([0.0, 0.0], [0.0, 0.0]));
                            // Check if under-filled; for simplicity we re-insert children.
                            let entry_count = match &new_node {
                                Node::Leaf(e) => e.len(),
                                Node::Internal(c) => c.len(),
                            };
                            if entry_count == 0 {
                                // Drop this child entirely.
                            } else {
                                if entry_count < 2 {
                                    under_filled.push(i);
                                }
                                new_children.push(ChildPtr::new(new_mbr, new_node));
                            }
                            continue;
                        } else {
                            let old_mbr = Self::node_mbr(&new_node)
                                .unwrap_or(Rect::new([0.0, 0.0], [0.0, 0.0]));
                            new_children.push(ChildPtr::new(old_mbr, new_node));
                        }
                    } else {
                        new_children.push(child);
                    }
                }

                // Collect under-filled node's entries for re-insertion.
                for &idx in &under_filled {
                    if idx < new_children.len() {
                        let child = &new_children[idx];
                        match child.node.as_ref() {
                            Node::Leaf(entries) => {
                                orphaned.extend(entries.iter().cloned());
                            }
                            Node::Internal(_) => {
                                // Deeper re-insertion handled by recursion.
                            }
                        }
                    }
                }
                // Remove under-filled (in reverse to preserve indices).
                let mut idxs = under_filled.clone();
                idxs.sort_unstable();
                idxs.dedup();
                for idx in idxs.into_iter().rev() {
                    if idx < new_children.len() {
                        new_children.remove(idx);
                    }
                }

                (found, Node::Internal(new_children))
            }
        }
    }

    // ── Utilities ─────────────────────────────────────────────────────────────

    fn tree_height(&self) -> usize {
        Self::height_of(&self.root)
    }

    fn height_of(node: &Node<T>) -> usize {
        match node {
            Node::Leaf(_) => 0,
            Node::Internal(children) => {
                1 + children.first().map_or(0, |c| Self::height_of(&c.node))
            }
        }
    }

    fn node_mbr(node: &Node<T>) -> Option<Rect> {
        match node {
            Node::Leaf(entries) => entries.iter().fold(None, |acc, e| {
                Some(acc.map_or(e.rect, |a: Rect| a.union(&e.rect)))
            }),
            Node::Internal(children) => children.iter().fold(None, |acc, c| {
                Some(acc.map_or(c.mbr, |a: Rect| a.union(&c.mbr)))
            }),
        }
    }

    fn leaf_mbr(entries: &[Entry<T>]) -> Option<Rect> {
        entries.iter().fold(None, |acc, e| {
            Some(acc.map_or(e.rect, |a: Rect| a.union(&e.rect)))
        })
    }

    fn children_mbr(children: &[ChildPtr<T>]) -> Option<Rect> {
        children.iter().fold(None, |acc, c| {
            Some(acc.map_or(c.mbr, |a: Rect| a.union(&c.mbr)))
        })
    }

    #[allow(dead_code)]
    fn node_min_dist(node: &Node<T>, point: [f64; 2]) -> f64 {
        match node {
            Node::Leaf(entries) => {
                entries.iter().map(|e| e.rect.min_sq_dist_to_point(point).sqrt()).fold(f64::INFINITY, f64::min)
            }
            Node::Internal(children) => {
                children.iter().map(|c| c.mbr.min_sq_dist_to_point(point).sqrt()).fold(f64::INFINITY, f64::min)
            }
        }
    }
}

// CandidateItem removed (no longer needed)

unsafe impl<T: Clone + Send + Sync> Send for RStarTree<T> {}
unsafe impl<T: Clone + Send + Sync> Sync for RStarTree<T> {}

// ── Tests ─────────────────────────────────────────────────────────────────────

#[cfg(test)]
mod tests {
    use super::*;

    fn rect(x0: f64, y0: f64, x1: f64, y1: f64) -> Rect {
        Rect::new([x0, y0], [x1, y1])
    }

    #[test]
    fn test_rect_ops() {
        let a = rect(0.0, 0.0, 2.0, 2.0);
        let b = rect(1.0, 1.0, 3.0, 3.0);
        assert!((a.area() - 4.0).abs() < 1e-12);
        assert!((a.perimeter() - 8.0).abs() < 1e-12);
        assert!(a.intersects(&b));
        assert!(!a.contains_point([3.0, 3.0]));
        assert!(a.contains_point([1.0, 1.0]));
        let u = a.union(&b);
        assert!((u.area() - 9.0).abs() < 1e-12);
        let oa = a.overlap_area(&b);
        assert!((oa - 1.0).abs() < 1e-12);
    }

    #[test]
    fn test_insert_search() {
        let mut tree: RStarTree<i32> = RStarTree::new(4);
        for i in 0..20 {
            let x = i as f64;
            tree.insert(rect(x, x, x + 1.0, x + 1.0), i);
        }
        assert_eq!(tree.len(), 20);

        let results = tree.search(&rect(-1.0, -1.0, 5.0, 5.0));
        assert!(!results.is_empty());
        // All results should be in range 0..5
        for &v in &results {
            assert!(*v < 5, "unexpected value: {}", v);
        }
    }

    #[test]
    fn test_bulk_load() {
        let entries: Vec<(Rect, i32)> = (0..50)
            .map(|i| {
                let x = (i % 10) as f64;
                let y = (i / 10) as f64;
                (rect(x, y, x + 1.0, y + 1.0), i)
            })
            .collect();
        let tree: RStarTree<i32> = RStarTree::bulk_load(entries, 8);
        assert_eq!(tree.len(), 50);

        let results = tree.search(&rect(0.0, 0.0, 2.0, 2.0));
        // Should find entries at (0,0),(1,0),(0,1),(1,1)
        assert!(!results.is_empty());
    }

    #[test]
    fn test_nearest_neighbors() {
        let mut tree: RStarTree<&str> = RStarTree::new(8);
        tree.insert(rect(0.0, 0.0, 1.0, 1.0), "A");
        tree.insert(rect(5.0, 5.0, 6.0, 6.0), "B");
        tree.insert(rect(10.0, 10.0, 11.0, 11.0), "C");

        let nn = tree.nearest_neighbors([0.5, 0.5], 2);
        assert_eq!(nn.len(), 2);
        assert_eq!(*nn[0].0, "A");
    }

    #[test]
    fn test_delete() {
        let mut tree: RStarTree<i32> = RStarTree::new(4);
        tree.insert(rect(0.0, 0.0, 1.0, 1.0), 42);
        tree.insert(rect(5.0, 5.0, 6.0, 6.0), 99);
        assert_eq!(tree.len(), 2);

        let deleted = tree.delete(&rect(0.0, 0.0, 1.0, 1.0), |&v| v == 42);
        assert!(deleted);
        assert_eq!(tree.len(), 1);

        let results = tree.search(&rect(-10.0, -10.0, 10.0, 10.0));
        assert_eq!(results.len(), 1);
        assert_eq!(*results[0], 99);
    }

    #[test]
    fn test_empty_tree() {
        let tree: RStarTree<i32> = RStarTree::new(8);
        assert!(tree.is_empty());
        let results = tree.search(&rect(-100.0, -100.0, 100.0, 100.0));
        assert!(results.is_empty());
        let nn = tree.nearest_neighbors([0.0, 0.0], 3);
        assert!(nn.is_empty());
    }

    #[test]
    fn test_bulk_load_empty() {
        let tree: RStarTree<i32> = RStarTree::bulk_load(vec![], 8);
        assert!(tree.is_empty());
    }
}