project/datastructures/linear/
llstack.rs

1use std::fmt::Debug;
2use std::ptr;
3
4use crate::datastructures::linear::LL;
5use crate::datastructures::nodes::DNode;
6
7/// Implementation of a Stack based on a Linked List.
8///
9/// Stacks are LIFO structures and supposed to be used with:
10/// - [LLStack::push()] which calls [LL::insert_head()]
11/// - [LLStack::pop()] which calls [LL::delete_head()]
12pub struct LLStack<T> {
13    len: usize,
14    head: *mut DNode<T>,
15    tail: *mut DNode<T>,
16}
17
18impl<T> Default for LLStack<T> {
19    fn default() -> Self {
20        Self { len: 0, head: ptr::null_mut(), tail: ptr::null_mut() }
21    }
22}
23
24impl<T> From<Box<DNode<T>>> for LLStack<T> {
25    fn from(node: Box<DNode<T>>) -> Self {
26        let node = Box::into_raw(node);
27
28        unsafe {
29            (*node).set_next(ptr::null_mut());
30            (*node).set_prev(ptr::null_mut());
31        }
32
33        Self { len: 1, head: node, tail: node }
34    }
35}
36
37impl<T> LLStack<T> {
38    /// Push `data` into the stack.
39    pub fn push(&mut self, data: T) {
40        self.insert_head(data);
41    }
42
43    /// Pop the top of the stack.
44    pub fn pop(&mut self) -> Option<T> {
45        self.delete_head()
46    }
47}
48
49impl<T> LL<T> for LLStack<T> {
50    fn insert_tail(&mut self, _: T) {
51        unimplemented!("Not available in {}", stringify!(LLStack));
52    }
53
54    fn delete_tail(&mut self) -> Option<T> {
55        unimplemented!("Not available in {}", stringify!(LLStack));
56    }
57
58    fn len(&self) -> usize {
59        self.len
60    }
61
62    fn head(&self) -> *mut DNode<T> {
63        self.head
64    }
65
66    fn tail(&self) -> *mut DNode<T> {
67        self.tail
68    }
69
70    fn delete_at_index(&mut self, index: usize) -> Option<T> {
71        let len = self.len();
72
73        if len == 0 {
74            None
75        } else if index < len {
76            let mut current_prev = ptr::null_mut();
77            let mut current = self.head;
78
79            for _ in 0..index {
80                current_prev = current;
81                current = unsafe { (*current).get_next() };
82            }
83
84            let (current_data, current_next, _) =
85                unsafe { Box::from_raw(current) }.unpack();
86
87            if !current_prev.is_null() {
88                unsafe { (*current_prev).set_next(current_next) };
89            }
90
91            if index == 0 {
92                self.head = current_next;
93            } else if index == len - 1 {
94                self.tail = current_prev;
95            }
96
97            self.len -= 1;
98
99            Some(current_data)
100        } else {
101            panic!("deletion index (is {index}) should be < len (is {len})");
102        }
103    }
104
105    fn insert(&mut self, data: T, index: usize) {
106        let len = self.len;
107
108        if len == 0 {
109            let node = Box::into_raw(Box::new(DNode::from(data)));
110
111            self.head = node;
112            self.tail = node;
113            self.len += 1;
114        } else if index < len {
115            let mut current_prev = ptr::null_mut();
116            let mut current = self.head;
117
118            for _ in 0..index {
119                current_prev = current;
120                current = unsafe { (*current).get_next() };
121            }
122
123            let node = Box::into_raw(Box::new(DNode::from((
124                data,
125                current,
126                ptr::null_mut(),
127            ))));
128
129            match index {
130                0 => {
131                    self.head = node;
132                },
133                _ => unsafe {
134                    (*current_prev).set_next(node);
135                },
136            }
137
138            self.len += 1;
139        } else if index == len {
140            let node = Box::into_raw(Box::new(DNode::from((
141                data,
142                ptr::null_mut(),
143                ptr::null_mut(),
144            ))));
145
146            unsafe { (*self.tail).set_next(node) };
147
148            self.tail = node;
149            self.len += 1;
150        } else {
151            panic!("insertion index (is {index}) should be <= len (is {len})");
152        }
153    }
154
155    fn print_addresses(&self)
156    where
157        T: Debug,
158    {
159        let mut current = self.head();
160
161        for _ in 0..self.len() {
162            let data = unsafe { (*current).get_data() };
163            let next = unsafe { (*current).get_next() };
164            let prev = unsafe { (*current).get_prev() };
165            println!("{current:?} | data={data:?} next={next:?} prev={prev:?}");
166
167            assert!(!current.is_null());
168            // assert!(prev.is_null() || unsafe { (*prev).get_next() } ==
169            // current); assert!(next.is_null() || unsafe {
170            // (*next).get_prev() } == current);
171
172            current = unsafe { (*current).get_next() };
173        }
174    }
175}
176
177#[cfg(test)]
178mod tests {
179    use super::LLStack;
180    use super::LL;
181    use crate::datastructures::nodes::DNode;
182
183    #[test]
184    fn test() {
185        let mut ll = LLStack::default();
186
187        ll.push(1);
188        assert_eq!(ll.iter_once().collect::<Vec<&usize>>(), &[&1]);
189
190        ll.push(4);
191        assert_eq!(ll.iter_once().collect::<Vec<&usize>>(), &[&4, &1]);
192
193        ll.push(2);
194        assert_eq!(ll.iter_once().collect::<Vec<&usize>>(), &[&2, &4, &1]);
195        assert!(!ll.is_sorted());
196
197        ll.tail();
198        ll.print();
199
200        assert_eq!(ll.pop(), Some(2));
201        assert_eq!(ll.iter_once().collect::<Vec<&usize>>(), &[&4, &1]);
202
203        assert_eq!(ll.pop(), Some(4));
204        assert_eq!(ll.iter_once().collect::<Vec<&usize>>(), &[&1]);
205
206        ll.clear();
207        assert_eq!(ll.iter_once().count(), 0);
208
209        let ll = LLStack::from(Box::new(DNode::from(0)));
210        assert_eq!(ll.len(), 1);
211    }
212}
project/datastructures/linear/llstack.rs

project/datastructures/linear/
llstack.rs
