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.