scopegraphs_prust_lib/
deque.rs

1use crate::RefCounter;
2
3use super::list;
4
5pub struct Deque<T> {
6    head: list::List<T>,
7    tail: list::List<T>,
8}
9
10impl<T> Clone for Deque<T> {
11    fn clone(&self) -> Self {
12        Self {
13            head: self.head.clone(),
14            tail: self.tail.clone(),
15        }
16    }
17}
18
19impl<T> Deque<T> {
20    pub fn empty() -> Self {
21        Self {
22            head: list::List::empty(),
23            tail: list::List::empty(),
24        }
25    }
26}
27
28impl<T> Deque<T> {
29    pub fn push_front(&self, value: T) -> Self {
30        Self {
31            head: self.head.push_front(value),
32            tail: self.tail.clone(),
33        }
34        .balance()
35    }
36
37    pub fn push_back(&self, value: T) -> Self {
38        Self {
39            head: self.head.clone(),
40            tail: self.tail.push_front(value),
41        }
42        .balance()
43    }
44
45    pub fn pop_front(&self) -> Option<(&T, Self)> {
46        if self.is_empty() {
47            None
48        } else if self.head.is_empty() {
49            let (a, b) = self.tail.pop_front().unwrap();
50            Some((
51                a,
52                Self {
53                    head: self.head.clone(),
54                    tail: b,
55                },
56            ))
57        } else {
58            let (a, b) = self.head.pop_front().unwrap();
59            Some((
60                a,
61                Self {
62                    head: b,
63                    tail: self.tail.clone(),
64                },
65            ))
66        }
67    }
68
69    pub fn pop_back(&self) -> Option<(&T, Self)> {
70        if self.is_empty() {
71            None
72        } else if self.tail.is_empty() {
73            let (a, b) = self.head.pop_front().unwrap();
74            Some((
75                a,
76                Self {
77                    head: b,
78                    tail: self.tail.clone(),
79                },
80            ))
81        } else {
82            let (a, b) = self.tail.pop_front().unwrap();
83            Some((
84                a,
85                Self {
86                    head: self.head.clone(),
87                    tail: b,
88                },
89            ))
90        }
91    }
92
93    fn balance(&self) -> Self {
94        if self.head.is_empty() {
95            let (tail, rev_head) = self.tail.split();
96            let head = rev_head.reverse();
97            Self { head, tail }
98        } else if self.tail.is_empty() {
99            let (head, rev_tail) = self.head.split();
100            let tail = rev_tail.reverse();
101            Self { head, tail }
102        } else {
103            self.clone()
104        }
105    }
106
107    fn is_empty(&self) -> bool {
108        self.length() == 0
109    }
110
111    fn length(&self) -> usize {
112        self.head.length() + self.tail.length()
113    }
114
115    pub fn iter(&self) -> DequeIterator<T> {
116        DequeIterator {
117            head_iter: self.head.iter(),
118            tail_iter: self.tail.reverse().iter(),
119        }
120    }
121}
122
123pub struct DequeIterator<T> {
124    head_iter: list::ListIterator<T>,
125    tail_iter: list::ListIterator<T>,
126}
127
128impl<T> Iterator for DequeIterator<T> {
129    type Item = RefCounter<T>;
130
131    fn next(&mut self) -> Option<Self::Item> {
132        match self.head_iter.next() {
133            Some(value) => Some(value),
134            None => self.tail_iter.next(),
135        }
136    }
137}
138
139#[cfg(test)]
140mod tests {
141    use super::*;
142
143    #[test]
144    fn test_deque_push_pop() {
145        let deque: Deque<i32> = Deque::empty();
146        let deque = deque.push_front(1).push_back(2).push_front(0).push_back(3);
147        assert_eq!(deque.length(), 4);
148
149        let (value, deque) = deque.pop_front().unwrap();
150        assert_eq!(*value, 0);
151        let (value, deque) = deque.pop_back().unwrap();
152        assert_eq!(*value, 3);
153        let (value, deque) = deque.pop_front().unwrap();
154        assert_eq!(*value, 1);
155        let (value, deque) = deque.pop_back().unwrap();
156        assert_eq!(*value, 2);
157
158        assert_eq!(deque.length(), 0);
159        assert!(deque.pop_front().is_none());
160        assert!(deque.pop_back().is_none());
161    }
162
163    #[test]
164    fn test_deque_iter() {
165        let deque: Deque<String> = Deque::empty();
166        let deque = deque
167            .push_front("World".to_string())
168            .push_front("Hello".to_string());
169        let mut iter = deque.iter();
170        assert_eq!(iter.next(), Some(RefCounter::new("Hello".to_string())));
171        assert_eq!(iter.next(), Some(RefCounter::new("World".to_string())));
172        assert_eq!(iter.next(), None);
173    }
174    #[test]
175    fn demonstrate_readme() {
176        // deque: [2, 1]
177        let deque: Deque<i32> = Deque::empty().push_front(1).push_front(2);
178
179        // Even with pop_back, deque is still unaltered, since it's immutable
180        let (value, _) = deque.pop_back().unwrap();
181        assert_eq!(*value, 1);
182        assert_eq!(deque.length(), 2);
183
184        // The "new" deque with pop_back is returned as part of the call
185        let (value, deque_updated) = deque.pop_front().unwrap();
186        assert_eq!(*value, 2);
187        assert_eq!(deque_updated.length(), 1);
188    }
189}
scopegraphs_prust_lib/deque.rs

scopegraphs_prust_lib/
deque.rs
