Recursively group child node indices into internal nodes.
(nodes: &mut Vec<Node>, child_indices: Vec<usize>)
| 108 | |
| 109 | /// Recursively group child node indices into internal nodes. |
| 110 | fn pack_internal(nodes: &mut Vec<Node>, child_indices: Vec<usize>) -> usize { |
| 111 | if child_indices.len() <= INTERNAL_CAPACITY { |
| 112 | let level = nodes[child_indices[0]].level + 1; |
| 113 | let mut node = Node::new_internal(level); |
| 114 | if let NodeKind::Internal { children } = &mut node.kind { |
| 115 | for idx in child_indices { |
| 116 | children.push(ChildRef { |
| 117 | bbox: nodes[idx].bbox, |
| 118 | node_idx: idx, |
| 119 | }); |
| 120 | } |
| 121 | } |
| 122 | node.recompute_bbox(); |
| 123 | let idx = nodes.len(); |
| 124 | nodes.push(node); |
| 125 | return idx; |
| 126 | } |
| 127 | |
| 128 | let mut new_children = Vec::new(); |
| 129 | for chunk in child_indices.chunks(INTERNAL_CAPACITY) { |
| 130 | let level = nodes[chunk[0]].level + 1; |
| 131 | let mut node = Node::new_internal(level); |
| 132 | if let NodeKind::Internal { children } = &mut node.kind { |
| 133 | for &idx in chunk { |
| 134 | children.push(ChildRef { |
| 135 | bbox: nodes[idx].bbox, |
| 136 | node_idx: idx, |
| 137 | }); |
| 138 | } |
| 139 | } |
| 140 | node.recompute_bbox(); |
| 141 | let idx = nodes.len(); |
| 142 | nodes.push(node); |
| 143 | new_children.push(idx); |
| 144 | } |
| 145 | |
| 146 | pack_internal(nodes, new_children) |
| 147 | } |
| 148 | |
| 149 | #[cfg(test)] |
| 150 | mod tests { |
no test coverage detected