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 { panic!("Error: index out-of-bounds") }
168 }
169
170 /// Adds a child to the given `Position` and returns its `Position`.
171 pub fn add_child(&mut self, position: &Position, data: T) -> Position {
172 // Creates a new Node
173 let node = Node {
174 parent: if self.arena.is_empty() {
175 None
176 } else {
177 Some(position.clone())
178 },
179 children: Vec::new(),
180 data: Some(data),
181 };
182
183 // Finds the appropriate index to insert the node;
184 // If there are unused indexes in the free list, push there,
185 // if there are no free indexes, append the list and set the index at
186 // the end of the arena
187 let index = if let Some(reuse) = self.free_list.pop() {
188 self.arena[reuse] = node;
189 reuse
190 } else {
191 self.arena.push(node);
192 self.arena.len() - 1
193 };
194
195 // Push the new Node's index to the parent's list of children;
196 // If the position has no parent, add to root's list of children
197 if self.arena.len() == 1 {
198 // No-op: The Node being pushed is the only node
199 } else {
200 self.arena[position.get()]
201 .children
202 .push(Position::new(index))
203 };
204
205 // Increase the size of the tree's size counter and returns the new Node's index
206 self.size += 1;
207 Position::new(index)
208 }
209
210 /// Returns a reference to the list of child `Position`s for the given `Position`.
211 //pub fn children(&self, position: &Position) -> Option<&Vec<Position>> {
212 // if position.ptr < self.arena.len() {
213 // Some(self.arena[position.get()].get_children())
214 // } else { None }
215 //}
216 pub fn children(&self, position: &Position) -> &Vec<Position> {
217 self.arena[position.get()].get_children()
218 }
219
220 #[allow(clippy::style)]
221 /// Removes a node at the given `Position` and returns its data.
222 /// If the removed `Position` has a parent, all the deleted node's children
223 /// get pushed to the deleted `Position`'s parent. If the deleted `Position`
224 /// has no parent (root) _a new parent is designated as the first child of
225 /// the deleted node_, e.g. this is a tree, not a forest. Ordering for the
226 /// designation of the new root is not guaranteed, and depends on when child
227 /// `Position`s were added. For this reason, caution is advised when
228 /// potentially deleting root nodes.
229 ///
230 /// Runs in `O(s + c)` time where:
231 /// - `s` is the number of the deleted node's siblings (i.e. the number of
232 /// its parent's children),
233 /// - `c` is the number of the deleted node's children.
234 ///
235 /// Precondition:
236 /// ```text
237 /// 3
238 /// / \
239 /// 5 9 (marked for deleteion)
240 /// / \ / \
241 /// 8 12 11 14
242 ///
243 /// ```
244 ///
245 /// Postcondition:
246 /// ```text
247 /// 3
248 /// / | \
249 /// 5 11 14
250 /// / \
251 /// 8 12
252 ///
253 /// ```
254 ///
255 /// Precondition:
256 /// ```text
257 /// 3 (marked for deletion)
258 /// / | \
259 /// 5 11 14
260 /// / \
261 /// 8 12
262 ///
263 /// ```
264 ///
265 /// Postcondition:
266 /// ```text
267 /// 5
268 /// / / \ \
269 /// 8 12 11 14
270 ///
271 /// ```
272 ///
273 /// Precondition:
274 /// ```text
275 /// 3 (marked for deletion)
276 /// / \
277 /// 9 5
278 /// / \ / \
279 /// 8 12 11 14
280 ///
281 /// ```
282 ///
283 /// Postcondition:
284 /// ```text
285 /// 9
286 /// / | \
287 /// 8 12 5
288 /// / \
289 /// 11 14
290 /// ```
291 pub fn remove(&mut self, position: Position) -> Option<T> {
292 // Gets the data out of the deleted Node, leaving None in its place
293 let data = self.arena[position.ptr].data.take();
294
295 // Adds deleted Position to the free list
296 self.free_list.push(position.ptr);
297
298 // Gets the deleted Node's parent's position
299 let parent_pos = self.arena[position.ptr].parent.clone();
300
301 // Decrease the size of the tree
302 self.size -= 1;
303
304 // Move all of the deleted Node's children up a generation, if theres a parent
305 if let Some(parent_node) = parent_pos {
306 // Alter the parent's children to exclude the deleted node
307 self.arena[parent_node.ptr]
308 .children
309 .retain(|p| *p != position);
310
311 // Push the deleted node's children to the parent node's children
312 //let children: Vec<_> = self.arena[position.ptr].children.to_vec();
313 let children = std::mem::take(&mut self.arena[position.ptr].children);
314 for child in children {
315 self.arena[parent_node.get()].children.push(child.clone());
316 self.arena[child.ptr].parent = Some(parent_node.clone());
317 }
318 data
319 }
320 // If the deleted Node has no parent (root), make the first child the new
321 // root (if it has children), and add old siblings as children
322 else {
323 if !self.arena[position.ptr].children.is_empty() {
324 // Remove and promote the first child as new root
325 let new_root = self.arena[position.ptr].children.remove(0);
326 self.root = new_root.clone();
327
328 // Move the remaining children vector out of the node to avoid cloning each element
329 let remaining_children = std::mem::take(&mut self.arena[position.ptr].children);
330
331 // Extend the new root's children with the remaining children (skipping the removed root)
332 self.arena[new_root.ptr].children.extend(remaining_children);
333 } // If the list only contains the root, then the free list should allow the position
334 // to be overwritten
335 data
336 }
337 }
338
339 /// Returns the `Position` of a given `Position`'s parent, if Some.
340 pub fn parent(&mut self, position: &Position) -> Option<Position> {
341 #[allow(clippy::manual_map)]
342 if let Some(parent) = self.arena[position.get()].parent.clone() {
343 Some(parent)
344 } else { None }
345 //self.arena[position.get()].parent.clone()
346 }
347}
348
349#[cfg(test)]
350mod tests {
351
352 #[test]
353 /// TODO: actually test the structure's members!
354 fn atomic() {
355
356 use super::GenTree;
357 use crate::hierarchies::arena_gentree_builder::Heading;
358
359 let mut tree = GenTree::new();
360 assert_eq!(tree.size(), 0);
361 assert!(tree.is_empty());
362 let root = tree.root().clone();
363 let mut cursor = tree.add_child(&root, Heading {
364 level: 2,
365 title: "Landlocked".to_string(),
366 },
367 );
368 assert_eq!(tree.size(), 1);
369 assert!(!tree.is_empty());
370
371 cursor = tree.add_child(&cursor, Heading {
372 level: 3,
373 title: "Switzerland".to_string(),
374 },
375 );
376 cursor = tree.add_child(&cursor, Heading {
377 level: 4,
378 title: "Geneva".to_string(),
379 },
380 );
381 cursor = tree.add_child(&cursor, Heading {
382 level: 5,
383 title: "Old Town".to_string(),
384 },
385 );
386 cursor = tree.parent(&cursor).expect(""); // Geneva
387 cursor = tree.parent(&cursor).expect(""); // Switzerland
388 tree.add_child(&cursor, Heading {
389 level: 3,
390 title: "Botswana".to_string(),
391 },
392 );
393 assert_eq!(tree.size(), 5);
394
395 //eprintln!("{tree:#?}");
396 //panic!("MANUAL TEST FAILURE");
397 }
398
399 #[test]
400 fn dangle() {
401 use crate::hierarchies::arena_gentree_builder::{Heading, construct};
402
403 use super::GenTree;
404 let one = vec![
405 Heading {
406 level: 1,
407 title: "Landlocked".to_string(),
408 },
409 Heading {
410 level: 2,
411 title: "Switzerland".to_string(),
412 },
413 ];
414 let two = vec![
415 Heading {
416 level: 1,
417 title: "Bolivia".to_string(),
418 },
419 Heading {
420 level: 2,
421 title: "Zimbabwe".to_string(),
422 },
423 ];
424
425 // Creates a tree, Position, and CursorMut
426 let outer_tree: GenTree<Heading> = construct(0, one);
427 //let outer_tree: GenTree<Heading> = construct_from(one);
428 let mut _pos = outer_tree.root();
429
430 {
431 let inner_tree: GenTree<Heading> = construct(0, two);
432 //let inner_tree: GenTree<Heading> = construct_from(two);
433 _pos = inner_tree.root();
434 } // inner_tree dropped here
435
436 // No UB (not possible) because inner_tree and _pos is already dropped
437 //let _oopsie = outer_tree.get_data(_pos);
438 }
439}