nodedb_spatial/rtree/
delete.rs

1//! R-tree entry deletion with underflow handling.
2
3use super::node::{EntryId, NodeKind, RTreeEntry};
4use super::tree::{RTree, collect_entries_owned};
5
6impl RTree {
7    /// Delete an entry by ID. Returns true if found and removed.
8    pub fn delete(&mut self, id: EntryId) -> bool {
9        let removed = delete_entry(&mut self.nodes, self.root, id);
10        if let Some(orphans) = removed {
11            self.len -= 1;
12            for entry in orphans {
13                self.reinsert_entry(entry);
14            }
15            self.condense_root();
16            true
17        } else {
18            false
19        }
20    }
21}
22
23/// Recursively delete entry, returning orphaned entries on underflow.
24fn delete_entry(
25    nodes: &mut Vec<super::node::Node>,
26    node_idx: usize,
27    id: EntryId,
28) -> Option<Vec<RTreeEntry>> {
29    let is_leaf = nodes[node_idx].is_leaf();
30
31    if is_leaf {
32        if let NodeKind::Leaf { entries } = &nodes[node_idx].kind {
33            let pos = entries.iter().position(|e| e.id == id);
34            if let Some(pos) = pos {
35                if let NodeKind::Leaf { entries } = &mut nodes[node_idx].kind {
36                    entries.remove(pos);
37                }
38                nodes[node_idx].recompute_bbox();
39                return Some(Vec::new());
40            }
41        }
42        return None;
43    }
44
45    // Internal node — recurse into children.
46    let child_indices: Vec<usize> = if let NodeKind::Internal { children } = &nodes[node_idx].kind {
47        children.iter().map(|c| c.node_idx).collect()
48    } else {
49        return None;
50    };
51
52    for child_idx in child_indices {
53        if let Some(mut orphans) = delete_entry(nodes, child_idx, id) {
54            // Update child bbox in parent.
55            let child_bbox = nodes[child_idx].bbox;
56            if let NodeKind::Internal { children } = &mut nodes[node_idx].kind {
57                for c in children.iter_mut() {
58                    if c.node_idx == child_idx {
59                        c.bbox = child_bbox;
60                        break;
61                    }
62                }
63            }
64            nodes[node_idx].recompute_bbox();
65
66            // Check underflow.
67            if nodes[child_idx].is_underflow() {
68                let mut collected = Vec::new();
69                collect_entries_owned(nodes, child_idx, &mut collected);
70                if let NodeKind::Internal { children } = &mut nodes[node_idx].kind {
71                    children.retain(|c| c.node_idx != child_idx);
72                }
73                nodes[node_idx].recompute_bbox();
74                orphans.extend(collected);
75            }
76
77            return Some(orphans);
78        }
79    }
80    None
81}
nodedb_spatial/rtree/delete.rs

nodedb_spatial/rtree/
delete.rs
