cactus/lib.rs
1//! An immutable parent pointer tree -- also called a cactus stack.
2//!
3//! A cactus stack is a (possibly empty) node with a (possibly null) pointer to a parent node. Any
4//! given node has a unique path back to the root node. Rather than mutably updating the stack, one
5//! creates and obtains access to immutable nodes (when a node becomes unreachable its memory is
6//! automatically reclaimed). A new child node pointing to a parent can be created via the `child`
7//! function (analogous to the normal `push`) and a parent can be retrieved via the `parent`
8//! function (analogous to the normal `pop`).
9//!
10//! ```
11//! use cactus::Cactus;
12//! let c = Cactus::new();
13//! assert!(c.is_empty());
14//! let c2 = c.child(1);
15//! assert_eq!(c2.len(), 1);
16//! assert_eq!(*c2.val().unwrap(), 1);
17//! let c3 = c2.parent().unwrap();
18//! assert!(c3.is_empty());
19//! ```
20//!
21//! From a given node one can create multiple sub-stacks:
22//!
23//! ```
24//! use cactus::Cactus;
25//! let c = Cactus::new().child(1);
26//! let c2 = c.child(2);
27//! let c3 = c.child(3);
28//! assert!(c2 != c3);
29//! assert_eq!(c2.vals().cloned().collect::<Vec<_>>(), [2, 1]);
30//! assert_eq!(c3.vals().cloned().collect::<Vec<_>>(), [3, 1]);
31//! ```
32//!
33//! There are two flavours of cactus:
34//!
35//! * The standard [`Cactus`](struct.Cactus.html) uses
36//! [`Rc`](https://doc.rust-lang.org/std/rc/struct.Rc.html) internally which makes it well suited
37//! to single-threaded programs but unsuited to multi-threaded programs.
38//!
39//! * The alternative [`ArcCactus`](struct.ArcCactus.html) uses
40//! [`Arc`](https://doc.rust-lang.org/std/sync/struct.Arc.html) internally which makes it suitable
41//! for multi-threaded programs but potentially slower on single-threaded programs.
42//!
43//! Both flavours can be used within a single program.
44
45mod arc_cactus;
46mod rc_cactus;
47
48pub use arc_cactus::Cactus as ArcCactus;
49pub use rc_cactus::Cactus;