Recursively delete entry, returning orphaned entries on underflow.
(
nodes: &mut Vec<super::node::Node>,
node_idx: usize,
id: EntryId,
)
| 24 | |
| 25 | /// Recursively delete entry, returning orphaned entries on underflow. |
| 26 | fn 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 | } |
no test coverage detected