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

/// module containing nodes
pub mod nodes {
    #[derive(Debug, Clone)]
    /// structure for a specific node inside of a stack
    pub struct Node<T>
    where
        T: Clone,
    {
        pub next: Box<Option<Node<T>>>,
        pub prev: Box<Option<Node<T>>>,
        pub val: T,
    }

    impl<T: std::clone::Clone> Node<T> {
        /// create a new node
        ///
        /// # Arguments
        ///
        /// * `next`: the next node
        /// * `prev`: the previews node
        /// * `val`: the value of the node
        ///
        /// # Returns
        ///
        /// this function returns a new Node built with the specified parameters
        pub fn new(next: Option<Node<T>>, prev: Option<Node<T>>, val: T) -> Node<T> {
            Node {
                next: Box::new(next),
                prev: Box::new(prev),
                val,
            }
        }
    }
}

/// module containing stacks
pub mod stacks {
    use crate::stack::nodes::Node;

    #[derive(Debug, Clone)]
    /// structure representing a stack
    ///
    /// A stack is handled as a collection of nodes.
    /// we specify the top node who himself specifies the previous node and so on.
    pub struct Stack<T: std::clone::Clone> {
        top: Node<T>,
    }

    impl<T: std::clone::Clone> Stack<T> {
        /// create a new stack
        ///
        /// # Arguments
        ///
        /// * `val`: the value to use
        ///
        /// # Returns
        ///
        /// this function returns a new stack with one node that has the value of `val`
        pub fn new(val: T) -> Stack<T> {
            Stack {
                top: Node::new(None, None, val),
            }
        }

        /// push a new element to the stack. This will return a new stack
        ///
        /// # Arguments
        ///
        /// `val`: the value for the new element to have
        ///
        /// # Returns
        /// this function returns a new stack with the element that has been added
        ///
        /// # Examples
        ///
        /// ```rust
        /// use stacking::stacks::Stack;
        ///
        /// let mut stack: Stack<i32> = Stack::new(0);
        /// stack = stack.push(4);
        /// assert_eq!(stack.pop(), Some(4));
        /// ```
        pub fn push(self, val: T) -> Stack<T> {
            let new_top: Node<T> = Node::new(None, Some(self.top.clone()), val);
            Stack { top: new_top }
        }

        /// pop the top element of the stack.
        /// Note that a stack must always have at least one element.
        /// Therefore if you initialize a stack with one value and then add another value
        /// and pop twice the first one will succeed but the second one will fail
        ///
        ///
        /// # Returns
        ///
        /// an `Option<T>` for the value that the element had
        ///
        /// # Examples
        ///
        /// ```rust
        /// use stacking::stacks::Stack;
        ///
        /// let mut stack: Stack<i32> = Stack::new(0);
        /// stack = stack.push(4);
        /// stack = stack.push(5);
        /// assert_eq!(stack.pop(), Some(5));
        /// assert_eq!(stack.pop(), Some(4));
        /// ```
        pub fn pop(&mut self) -> Option<T> {
            let retval = self.top.val.clone();
            if let None = *self.top.prev {
                return None;
            }
            let mut new_top = self.top.clone().prev.unwrap();
            new_top.next = Box::new(None);
            self.top = new_top;
            Some(retval)
        }
    }
}