4 releases
Uses old Rust 2015
0.1.3 | May 5, 2017 |
---|---|
0.1.2 | Mar 23, 2017 |
0.1.1 | Mar 9, 2017 |
0.1.0 | Mar 8, 2017 |
#24 in #parent
27 downloads per month
14KB
282 lines
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.