dsa_rust/hierarchies/arena_gentree.rs
1/*! A safe, indexed, n-ary tree implementation
2
3# About
4This module explores using arena allocation for fewer allocations and simpler reference munging via indexes. This implementation includes several critical compromises over the link-based approach. See the Drawbacks below for more details.
5
6Compromises over the link-based tree include being less spatially efficient as the arena's growth algorithm logically shifts "pointers" to Nodes in the arena.
7
8# Design
9The implementation stores all `Node` values in a `Vec`-backed arena. For small trees (fewer than ~100 nodes), it is marginally slower than the `Rc<RefCell>`-based design due to fixed arena management overhead. However, for larger trees (starting around 1,000–10,000 nodes), it improves construction speed by roughly 20–25%, primarily from reduced heap allocations and better cache locality.
10
11## Drawbacks
12The Vec-backed design is intended to provide a more ergonomic design over the heavy-handed syntax and semantics of reference counting and interior mutability over the pointer-backed version of this general tree. Unfortunately, this Vec-backed design also comes with its own compromises, which may prove to be more impactful. The Vec-backed design is less spatially efficient due to the structure's growth. As the tree gets mutated, it also potentially loses cache locality.
13
14# Example
15
16```rust
17
18```
19
20*/
21
22//type Position = usize;
23#[derive(Debug, PartialEq)]
24pub struct Position {
25 pub ptr: usize,
26}
27impl Position {
28 pub fn new(position: usize) -> Position {
29 Position { ptr: position }
30 }
31
32 fn get(&self) -> usize {
33 self.ptr
34 }
35}
36impl Clone for Position {
37 fn clone(&self) -> Self {
38 Position { ptr: self.ptr }
39 }
40}
41
42#[derive(Debug)]
43struct Node<T> {
44 parent: Option<Position>,
45 children: Vec<Position>,
46 data: Option<T>,
47}
48impl<T> Node<T> {
49 fn _get_parent(&self) -> Option<&Position> {
50 self.parent.as_ref()
51 }
52 fn get_children(&self) -> &Vec<Position> {
53 &self.children
54 }
55}
56
57#[derive(Debug)]
58pub struct GenTree<T> {
59 arena: Vec<Node<T>>,
60 size: usize,
61 root: Position,
62 free_list: Vec<usize>,
63}
64impl<T> Default for GenTree<T> {
65 fn default() -> Self {
66 Self::new()
67 }
68}
69impl<T> GenTree<T> {
70 /// Creates a new, zero-sized `GenTree`.
71 pub fn new() -> GenTree<T> {
72 GenTree {
73 arena: Vec::new(),
74 size: 0,
75 root: Position::new(0),
76 free_list: Vec::new(),
77 }
78 }
79
80 /// Creates a new `GenTree` that pre-allocates to the given capacity.
81 pub fn new_with_capacity(capacity: usize) -> GenTree<T> {
82 GenTree {
83 arena: Vec::with_capacity(capacity),
84 size: 0,
85 root: Position::new(0),
86 free_list: Vec::new(),
87 }
88 }
89
90 /// Returns the `Position` to the tree's root node.
91 pub fn root(&self) -> Position {
92 self.root.clone()
93 }
94
95 pub fn mut_root(&mut self, data: T) {
96 self.arena[0].data = Some(data);
97 }
98
99 // Unnecessary, implementing all functions on GenTree with no mutable borrows
100 // pub fn cursor_mut(&mut self) -> CursorMut<'_, T>
101 // pub fn cursor_from(&mut self, position: Position<T>) -> CursorMut<'_, T>
102
103 /// Indicates whether the given `Position` is the tree's root.
104 pub fn is_root(&self, position: &Position) -> bool {
105 position.ptr == self.root.ptr
106 }
107
108 /// Indicates whether the given `Position` contains data.
109 pub fn is_some(&self, position: &Position) -> bool {
110 self.arena[position.get()].data.is_some()
111 }
112
113 /// Indicates whether the given `Position` contains data.
114 pub fn is_none(&self, position: &Position) -> bool {
115 self.arena[position.ptr].data.is_none()
116 }
117
118 /// Indicates whether the tree is empty.
119 pub fn is_empty(&self) -> bool {
120 self.size == 0
121 }
122
123 /// Returns the number of live nodes in the tree.
124 pub fn size(&self) -> usize {
125 self.size
126 }
127
128 /// Returns the number of children for a `Node` at the given `Position`.
129 pub fn num_children(&self, position: &Position) -> usize {
130 self.arena[position.get()].children.len()
131 }
132
133 /// WARNING: Unimplemented
134 pub fn depth(&mut self, _node: &Position) -> usize {
135 0
136 }
137
138 /// WARNING: Unimplemented
139 pub fn height(&mut self, _node: &Position) -> usize {
140 0
141 }
142
143 ///// Returns the given `Position`'s parent, if Some.
144 //pub fn get_parent(&self, position: &Position) -> Option<Position> {
145 // let mut pos = Position::new(0);
146 // if position.ptr < self.arena.len() {
147 // let val = self.arena[position.ptr].parent.clone().unwrap().ptr;
148 // pos.ptr = val;
149 // Some(pos)
150 // } else { None }
151 //}
152
153 //pub fn jump(&self, position: Position) {}
154
155 // /// Returns a list of the given `Position`'s children.
156 // pub fn get_children(&self) -> Vec<Position> {}
157
158 /// Returns an immutable reference to the data at the given `Position`, if Some.
159 pub fn get_data(&self, position: &Position) -> Option<&T> {
160 self.arena[position.get()].data.as_ref()
161 }
162
163 /// Returns an immutable reference to the data at the given `Position`, if Some.
164 pub fn get_for_pos(&self, position: &Position) -> Option<&T> {
165 if position.ptr < self.arena.len() {
166 self.arena[position.get()].data.as_ref()
167 } else {
168 panic!("Error: index out-of-bounds")
169 }
170 }
171
172 /// Adds a child to the given `Position` and returns its `Position`.
173 pub fn add_child(&mut self, position: &Position, data: T) -> Position {
174 // Creates a new Node
175 let node = Node {
176 parent: if self.arena.is_empty() {
177 None
178 } else {
179 Some(position.clone())
180 },
181 children: Vec::new(),
182 data: Some(data),
183 };
184
185 // Finds the appropriate index to insert the node;
186 // If there are unused indexes in the free list, push there,
187 // if there are no free indexes, append the list and set the index at
188 // the end of the arena
189 let index = if let Some(reuse) = self.free_list.pop() {
190 self.arena[reuse] = node;
191 reuse
192 } else {
193 self.arena.push(node);
194 self.arena.len() - 1
195 };
196
197 // Push the new Node's index to the parent's list of children;
198 // If the position has no parent, add to root's list of children
199 if self.arena.len() == 1 {
200 // No-op: The Node being pushed is the only node
201 } else {
202 self.arena[position.get()]
203 .children
204 .push(Position::new(index))
205 };
206
207 // Increase the size of the tree's size counter and returns the new Node's index
208 self.size += 1;
209 Position::new(index)
210 }
211
212 /// Returns a reference to the list of child `Position`s for the given `Position`.
213 //pub fn children(&self, position: &Position) -> Option<&Vec<Position>> {
214 // if position.ptr < self.arena.len() {
215 // Some(self.arena[position.get()].get_children())
216 // } else { None }
217 //}
218 pub fn children(&self, position: &Position) -> &Vec<Position> {
219 self.arena[position.get()].get_children()
220 }
221
222 #[allow(clippy::style)]
223 /// Removes a node at the given `Position` and returns its data.
224 /// If the removed `Position` has a parent, all the deleted node's children
225 /// get pushed to the deleted `Position`'s parent. If the deleted `Position`
226 /// has no parent (root) _a new parent is designated as the first child of
227 /// the deleted node_, e.g. this is a tree, not a forest. Ordering for the
228 /// designation of the new root is not guaranteed, and depends on when child
229 /// `Position`s were added. For this reason, caution is advised when
230 /// potentially deleting root nodes.
231 ///
232 /// Runs in `O(s + c)` time where:
233 /// - `s` is the number of the deleted node's siblings (i.e. the number of
234 /// its parent's children),
235 /// - `c` is the number of the deleted node's children.
236 ///
237 /// Precondition:
238 /// ```text
239 /// 3
240 /// / \
241 /// 5 9 (marked for deleteion)
242 /// / \ / \
243 /// 8 12 11 14
244 ///
245 /// ```
246 ///
247 /// Postcondition:
248 /// ```text
249 /// 3
250 /// / | \
251 /// 5 11 14
252 /// / \
253 /// 8 12
254 ///
255 /// ```
256 ///
257 /// Precondition:
258 /// ```text
259 /// 3 (marked for deletion)
260 /// / | \
261 /// 5 11 14
262 /// / \
263 /// 8 12
264 ///
265 /// ```
266 ///
267 /// Postcondition:
268 /// ```text
269 /// 5
270 /// / / \ \
271 /// 8 12 11 14
272 ///
273 /// ```
274 ///
275 /// Precondition:
276 /// ```text
277 /// 3 (marked for deletion)
278 /// / \
279 /// 9 5
280 /// / \ / \
281 /// 8 12 11 14
282 ///
283 /// ```
284 ///
285 /// Postcondition:
286 /// ```text
287 /// 9
288 /// / | \
289 /// 8 12 5
290 /// / \
291 /// 11 14
292 /// ```
293 pub fn remove(&mut self, position: Position) -> Option<T> {
294 // Gets the data out of the deleted Node, leaving None in its place
295 let data = self.arena[position.ptr].data.take();
296
297 // Adds deleted Position to the free list
298 self.free_list.push(position.ptr);
299
300 // Gets the deleted Node's parent's position
301 let parent_pos = self.arena[position.ptr].parent.clone();
302
303 // Decrease the size of the tree
304 self.size -= 1;
305
306 // Move all of the deleted Node's children up a generation, if theres a parent
307 if let Some(parent_node) = parent_pos {
308 // Alter the parent's children to exclude the deleted node
309 self.arena[parent_node.ptr]
310 .children
311 .retain(|p| *p != position);
312
313 // Push the deleted node's children to the parent node's children
314 //let children: Vec<_> = self.arena[position.ptr].children.to_vec();
315 let children = std::mem::take(&mut self.arena[position.ptr].children);
316 for child in children {
317 self.arena[parent_node.get()].children.push(child.clone());
318 self.arena[child.ptr].parent = Some(parent_node.clone());
319 }
320 data
321 }
322 // If the deleted Node has no parent (root), make the first child the new
323 // root (if it has children), and add old siblings as children
324 else {
325 if !self.arena[position.ptr].children.is_empty() {
326 // Remove and promote the first child as new root
327 let new_root = self.arena[position.ptr].children.remove(0);
328 self.root = new_root.clone();
329
330 // Move the remaining children vector out of the node to avoid cloning each element
331 let remaining_children = std::mem::take(&mut self.arena[position.ptr].children);
332
333 // Extend the new root's children with the remaining children (skipping the removed root)
334 self.arena[new_root.ptr].children.extend(remaining_children);
335 } // If the list only contains the root, then the free list should allow the position
336 // to be overwritten
337 data
338 }
339 }
340
341 /// Returns the `Position` of a given `Position`'s parent, if Some.
342 pub fn parent(&mut self, position: &Position) -> Option<Position> {
343 #[allow(clippy::manual_map)]
344 if let Some(parent) = self.arena[position.get()].parent.clone() {
345 Some(parent)
346 } else {
347 None
348 }
349 //self.arena[position.get()].parent.clone()
350 }
351}
352
353#[cfg(test)]
354mod tests {
355
356 #[test]
357 /// TODO: actually test the structure's members!
358 fn atomic() {
359 use super::GenTree;
360 use crate::hierarchies::arena_gentree_builder::Heading;
361
362 let mut tree = GenTree::new();
363 assert_eq!(tree.size(), 0);
364 assert!(tree.is_empty());
365 let root = tree.root().clone();
366 let mut cursor = tree.add_child(
367 &root,
368 Heading {
369 level: 2,
370 title: "Landlocked".to_string(),
371 },
372 );
373 assert_eq!(tree.size(), 1);
374 assert!(!tree.is_empty());
375
376 cursor = tree.add_child(
377 &cursor,
378 Heading {
379 level: 3,
380 title: "Switzerland".to_string(),
381 },
382 );
383 cursor = tree.add_child(
384 &cursor,
385 Heading {
386 level: 4,
387 title: "Geneva".to_string(),
388 },
389 );
390 cursor = tree.add_child(
391 &cursor,
392 Heading {
393 level: 5,
394 title: "Old Town".to_string(),
395 },
396 );
397 cursor = tree.parent(&cursor).expect(""); // Geneva
398 cursor = tree.parent(&cursor).expect(""); // Switzerland
399 tree.add_child(
400 &cursor,
401 Heading {
402 level: 3,
403 title: "Botswana".to_string(),
404 },
405 );
406 assert_eq!(tree.size(), 5);
407
408 //eprintln!("{tree:#?}");
409 //panic!("MANUAL TEST FAILURE");
410 }
411
412 #[test]
413 fn dangle() {
414 use crate::hierarchies::arena_gentree_builder::{construct, Heading};
415
416 use super::GenTree;
417 let one = vec![
418 Heading {
419 level: 1,
420 title: "Landlocked".to_string(),
421 },
422 Heading {
423 level: 2,
424 title: "Switzerland".to_string(),
425 },
426 ];
427 let two = vec![
428 Heading {
429 level: 1,
430 title: "Bolivia".to_string(),
431 },
432 Heading {
433 level: 2,
434 title: "Zimbabwe".to_string(),
435 },
436 ];
437
438 // Creates a tree, Position, and CursorMut
439 let outer_tree: GenTree<Heading> = construct(0, one);
440 //let outer_tree: GenTree<Heading> = construct_from(one);
441 let mut _pos = outer_tree.root();
442
443 {
444 let inner_tree: GenTree<Heading> = construct(0, two);
445 //let inner_tree: GenTree<Heading> = construct_from(two);
446 _pos = inner_tree.root();
447 } // inner_tree dropped here
448
449 // No UB (not possible) because inner_tree and _pos is already dropped
450 //let _oopsie = outer_tree.get_data(_pos);
451 }
452}