Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_data/src/stack.rs

4.1 KiB, 3 runs

created by r1870400018:274, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1use oxedyne_fe2o3_core::prelude::*;
2
3use std::{
4 sync::Arc,
5};
6
7/// The immutable, thread-safe stack from [Learning Rust with Entirely Too Many Lists](https://rust-unofficial.github.io/too-many-lists/third-final.html).
8#[derive(Clone, Debug, PartialEq)]
9pub struct Stack<T> {
10 head: Link<T>,
11}
12
13type Link<T> = Option<Arc<Node<T>>>;
14
15#[derive(Clone, Debug, PartialEq)]
16struct Node<T> {
17 data: T,
18 next: Link<T>,
19}
20
21impl<T> Stack<T> {
22 pub fn new() -> Self {
23 Stack {
24 head: None,
25 }
26 }
27
28 /// Append to the head of the stack.
29 // stack1 -> A ---+ stack1 = A -> B -> C -> D
30 // |
31 // v
32 // stack2 ------> B -> C -> D stack2 = tail(stack1) = B -> C -> D
33 // ^
34 // |
35 // stack3 -> X ---+ stack3 = push(stack2, X) = X -> B -> C -> D
36 pub fn push(&self, data: T) -> Self {
37 Stack {
38 head: Some(Arc::new(Node {
39 data: data,
40 next: self.head.clone(),
41 }))
42 }
43 }
44
45 /// Snip off head and return the tail.
46 pub fn tail(&self) -> Self {
47 Stack {
48 //head: self.head.as_ref().and_then(|node| node.next.clone())
49 head: match self.head.as_ref() {
50 Some(node) => node.next.clone(),
51 None => None,
52 },
53 }
54 }
55
56 pub fn head(&self) -> Option<&T> {
57 //self.head.as_ref().map(|node| &node.data)
58 match self.head.as_ref() {
59 Some(node) => Some(&node.data),
60 None => None,
61 }
62 }
63
64 pub fn iter(&self) -> StackIter<'_, T> {
65 StackIter {
66 //next: self.head.as_ref().map(|node| &**node)
67 next: match self.head.as_ref() {
68 Some(node) => Some(&**node),
69 None => None,
70 }
71 }
72 }
73
74 //pub fn peek(&self) -> Option<&T> {
75 // self.head.as_ref().map(|node| {
76 // &node.data
77 // })
78 //}
79}
80
81impl<T> Drop for Stack<T> {
82 fn drop(&mut self) {
83 let mut head = self.head.take();
84 while let Some(node) = head {
85 if let Ok(mut node) = Arc::try_unwrap(node) {
86 head = node.next.take();
87 } else {
88 break;
89 }
90 }
91 }
92}
93
94pub struct StackIter<'a, T> {
95 next: Option<&'a Node<T>>,
96}
97
98impl<'a, T> Iterator for StackIter<'a, T> {
99 type Item = &'a T;
100
101 fn next(&mut self) -> Option<Self::Item> {
102 //self.next.map(|node| {
103 // self.next = node.next.as_ref().map(|node| &**node);
104 // &node.data
105 //})
106 match self.next {
107 Some(node) => {
108 self.next = match node.next.as_ref() {
109 Some(node) => Some(&**node),
110 None => None,
111 };
112 Some(&node.data)
113 },
114 None => None,
115 }
116 }
117}
118
119#[cfg(test)]
120mod test {
121 use super::Stack;
122
123 #[test]
124 fn test_stack_basics() {
125 let list = Stack::new();
126 assert_eq!(list.head(), None);
127
128 let list = list.push(1).push(2).push(3);
129 assert_eq!(list.head(), Some(&3));
130
131 let list = list.tail();
132 assert_eq!(list.head(), Some(&2));
133
134 let list = list.tail();
135 assert_eq!(list.head(), Some(&1));
136
137 let list = list.tail();
138 assert_eq!(list.head(), None);
139
140 // Make sure empty tail works
141 let list = list.tail();
142 assert_eq!(list.head(), None);
143 }
144
145 #[test]
146 fn test_stack_iter() {
147 let list = Stack::new().push(1).push(2).push(3);
148
149 let mut iter = list.iter();
150 assert_eq!(iter.next(), Some(&3));
151 assert_eq!(iter.next(), Some(&2));
152 assert_eq!(iter.next(), Some(&1));
153 }
154
155 #[test]
156 fn test_stack_tuple_iter() {
157 let mut list = Stack::<(u8, u8)>::new();
158 list = list.push((42, 1)).push((6, 2)).push((17, 3));
159
160
161 let mut iter = list.iter();
162 assert_eq!(iter.next(), Some(&(17, 3)));
163 assert_eq!(iter.next(), Some(&(6, 2)));
164 assert_eq!(iter.next(), Some(&(42, 1)));
165 assert_eq!(iter.next(), None);
166 }
167}