nodedb_spatial/rtree/
delete.rs

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

nodedb_spatial/rtree/
delete.rs
