Expand description
Immutable cactus stack implementation.
Other terms for cactus stack include parent pointer tree, spaghetti stack, and saguaro stack. See Wikipedia for more information.
// Quickstart
extern crate kaktus;
// the trait `Stack` needs to be importet for `Stack`/`VStack` to work
use kaktus::{Stack, Stack};
let root = Stack::root(0);
let one = root.push(1);
assert_eq!(*one.pop().unwrap(), 0);
assert_eq!(*one, 1);§Overview
The stacks described in this crate differ from traditional stacks in one decisive point, they are immutable. This means that a value in itself represents the stack:
let root = Stack::root(0);
let one = root.push(1);
let two = root.push(2);
assert_eq!(*two, 2);Further, popping a value from the stack just returns the parent – the originial value (and thus the stack it represents) remains valid:
let one_ = two.pop().unwrap();
assert_eq!(*one_, 1);
// `two` is still valid
assert_eq!(*two, 2);For comparison, this shows how stacks are often implemented instead:
// traditional stack
let mut stack = vec![0];
stack.push(1);
stack.push(2);
let two = stack.pop().unwrap();
let one = stack.pop().unwrap();§Cactus stacks
Due to the immutable property, it is possible to spawn off multiple values from the same parent, making it effecively a tree:
// tree structure:
// 0 -- 1 -- 2
// \
// 3 -- 4 -- 5
let root = Stack::root(0);
let two = root.push(1).push(2);
let five = root.push(3).push(4).push(5);
assert_eq!(*two, 2);
assert_eq!(*five, 5);Crate Content
This crate provides two stack implementations:
Stack and VStack. In short:
Stack uses a recursive (pointer) architecture, whilst VStackc uses a
vector to store the stack’s data.