Module safe_linked_gentree

A safe, linked, n-ary tree implementation

About

Following classical DSA curricula, this implementation relies on pointers for the structure’s composition and navigation. This module explores the use of reference counting and interior mutability through the Rc and RefCell types (respectively) for a safe, positional implementation that avoids dangling pointers and reference cycles for proper Drop semantics.

Reference counting provides a synchronous, deterministic form of memory management that acts like a garbage collector and prevents dangling pointers by automatically managing lifetimes. The structure is able to keep objects alive until their reference count hits zero, potentially even after they’ve gone out of their original scope. To avoid memory leaks caused by reference cycles, tree nodes use strong Rc pointers for children and Weak pointers for parent links. This ensures the tree can be correctly dropped recursively from the top down.

Using smart pointers to manage reference counting and interior mutability to skirt multiple mutable references is an elegant solution to the linked desgin, but its still a bit painful, and potentially overkill for many applications. The good news is that there are much easier ways to accomplish similar goals. To wit, this library also includes a Vec-backed tree structure with a similar API. For more polished levels of functionality with the same arena-style backing structure concepts see id_tree. It is worth noting that id_tree uses a hash map to store node IDs, so it may not be as performanat as either a pointer-backed or simple indexed tree structure for smaller, short-lived tree structures.

Design

The base GenTree structure is sparse and only contains basic operations for constructors and metadata retrieval. Most of the magic happens in the CursorMut struct. Both structs rely on a Position struct which provides a safe handle to all the reference-counted pointers required to make tree go brrr.

Example

This section presents an algorithm that builds a tree from a Vec of custom Heading objects that contain a level and a heading value. Assume the inputs to the algorithm start at level 1 with the first (and lowest) level in the Vec<Heading> list being 2. The result is a single, empty root node represented by [].

    []
    │
    ├── Landlocked
    │   ├── Switzerland
    │   │   └── Geneva
    │   │       └── Old Town
    │   │           └── Cathédrale Saint-Pierre
    │   └── Bolivia
    │       └── []
    │           └── []
    │               ├── Puerta del Sol
    │               └── Puerta de la Luna
    └── Islands
        ├── Marine
        │   └── Australia
        └── Fresh Water

    use dsa_rust::hierarchies::safe_linked_gentree::GenTree;

    struct Heading {
        level: usize,
        title: String,
    }
    impl Heading {
        fn new(title: String, level: usize) -> Heading {
            Heading { level, title }
        }
    }

    pub fn construct(mut cur_level: usize, data: Vec<Heading>) -> GenTree<Heading> {
        // Instantiates a Tree with a generic root and traversal positioning
        let mut tree: GenTree<Heading> = GenTree::<Heading>::new();
        let mut cursor = tree.cursor_mut(); // Sets cursor to tree.root

        // Constructs tree from Vec<T>
        for heading in data {
            let data_level = heading.level;

            // Case 1: Adds a child to the current parent and sets level cursor
            if data_level == cur_level + 1 {
                cursor.add_child(heading);
                cur_level += 1;
            }
            // Case 2: Adds a child with multi-generational skips
            else if data_level > cur_level {
                let diff = data_level - cur_level;
                for _ in 1..diff {
                    let empty = Heading::new("[]".to_string(), 0);
                    cursor.add_child(empty);
                    cur_level += 1;
                }
                cursor.add_child(heading);
                cur_level += 1;
            }
            // Case 3: Adds sibling to current parent
            else if data_level == cur_level {
                cursor.ascend().ok();
                cursor.add_child(heading);
            }
            // Case 4: Adds a child to the appropriate ancestor,
            // ensuring proper generational skips
            else {
                let diff = cur_level - data_level;
                for _ in 0..=diff {
                    cursor.ascend().ok();
                    cur_level -= 1;
                }
                cursor.add_child(heading);
                cur_level += 1;
            }
        }
        tree
    }

Structs

CursorMut

A cursor over mutable Node data with safe, reference-counted Position handles.

GenTree

The GenTree struct represents a positional, linked-based general tree structure that contains a pointer to the root node and the structure’s size. The genericity of the struct means you’ll have to explicitly type the tree at instantiation.

Position

The Position struct provides a safe, lightweight handle to Node data. All meaningful accessors and mutators appear on the CursorMut struct.