8 stable releases

1.0.7 Feb 16, 2024
1.0.6 Jun 11, 2020
1.0.5 Nov 21, 2019
1.0.4 Dec 18, 2018
0.1.0 Jul 31, 2017

#152 in Data structures

Download history 2217/week @ 2024-11-16 1631/week @ 2024-11-23 2953/week @ 2024-11-30 2644/week @ 2024-12-07 2530/week @ 2024-12-14 1897/week @ 2024-12-21 3669/week @ 2024-12-28 5572/week @ 2025-01-04 5169/week @ 2025-01-11 5279/week @ 2025-01-18 2904/week @ 2025-01-25 3903/week @ 2025-02-01 6381/week @ 2025-02-08 3387/week @ 2025-02-15 3372/week @ 2025-02-22 3830/week @ 2025-03-01

18,182 downloads per month
Used in 14 crates (3 directly)

Apache-2.0/MIT

16KB
234 lines

Cactus

This library provides an immutable cactus stack (also called a spaghetti stack or parent pointer tree). A cactus stack is a (possibly empty) node with a (possibly null) pointer to a parent node. Any given node has a unique path back to the root node. Rather than mutably updating the stack, one creates and obtains access to immutable nodes (when a node becomes unreachable its memory is automatically reclaimed). A new child node pointing to a parent can be created via the child function (analogous to the normal push) and a parent can be retrieved via the parent function (analogous to the normal pop).

use cactus::Cactus;
let c = Cactus::new();
assert!(c.is_empty());
let c2 = c.child(1);
assert_eq!(c2.len(), 1);
assert_eq!(*c2.val().unwrap(), 1);
let c3 = c2.parent().unwrap();
assert!(c3.is_empty());

From a given node one can create multiple sub-stacks:

use cactus::Cactus;
let c = Cactus::new().child(1);
let c2 = c.child(2);
let c3 = c.child(3);
assert!(c2 != c3);
assert_eq!(c2.vals().cloned().collect::<Vec<_>>(), [2, 1]);
assert_eq!(c3.vals().cloned().collect::<Vec<_>>(), [3, 1]);

No runtime deps