1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140
#![feature(associated_type_defaults)] //! Immutable __cactus stack__ implementation. //! //! Other terms for cactus stack include __parent pointer tree__, //! __spaghetti stack__, and __saguaro stack__. See //! [Wikipedia](https://en.wikipedia.org/wiki/Parent_pointer_tree) for more //! information. //! //! ```ignore //! // 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: //! //! ```ignore //! 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: //! //! ```ignore //! 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: //! //! ```ignore //! // 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: //! //! ```ignore //! // 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`](struct.Stack.html) and [`VStack`](struct.VStack.html). In short: //! `Stack` uses a recursive (pointer) architecture, whilst `VStackc` uses a //! vector to store the stack's data. //! use std::ops::Deref; use std::rc::Rc; struct StackNode<T> { value: T, parent: Option<Stack<T>>, } /// Recursive Stack /// /// A **recursive** implementation for ``Stack``. /// /// ```rust,ignore /// pub struct StackNode<T> { /// value: T, /// parent: Option<Stack<T>>, /// } /// ``` /// pub struct Stack<T>(Rc<StackNode<T>>); impl<T> Clone for Stack<T> { fn clone(&self) -> Self { Stack(self.0.clone()) } } impl<T> Stack<T> { pub fn root(val: T) -> Self { Stack(Rc::from(StackNode { value: val, parent: None, })) } pub fn push(&self, val: T) -> Self { Stack(Rc::from(StackNode { value: val, parent: Some(Stack(self.0.clone())), })) } pub fn pop(&self) -> Option<Self> { match self.0.parent { None => None, Some(ref p) => Some(p.clone()), } } } impl<T> Deref for Stack<T> { type Target = T; fn deref(&self) -> &T { &self.0.deref().value } }