1use std::collections::LinkedList;
2
3use collection::{Collection, Disposable};
4
5use crate::traits::{DequeLike, QueueLike};
6
7#[derive(Debug, Default)]
8pub struct LinkedDeque<T> {
9 elements: LinkedList<T>,
10 disposed: bool,
11}
12
13impl<T> LinkedDeque<T> {
14 pub fn new() -> Self {
15 Self {
16 elements: LinkedList::new(),
17 disposed: false,
18 }
19 }
20}
21
22impl<T> QueueLike<T> for LinkedDeque<T> {
23 fn front(&self) -> Option<&T> {
24 self.elements.front()
25 }
26
27 fn enqueue(&mut self, element: T) {
28 self.elements.push_back(element);
29 }
30
31 fn dequeue(&mut self) -> Option<T> {
32 self.elements.pop_front()
33 }
34
35 fn replace_front(&mut self, new_back: T) -> Option<T> {
36 let removed = self.elements.pop_front();
37 self.elements.push_back(new_back);
38 removed
39 }
40}
41
42impl<T> DequeLike<T> for LinkedDeque<T> {
43 fn back(&self) -> Option<&T> {
44 self.elements.back()
45 }
46
47 fn enqueue_front(&mut self, element: T) {
48 self.elements.push_front(element);
49 }
50
51 fn dequeue_back(&mut self) -> Option<T> {
52 self.elements.pop_back()
53 }
54
55 fn replace_back(&mut self, new_front: T) -> Option<T> {
56 let removed = self.elements.pop_back();
57 self.elements.push_front(new_front);
58 removed
59 }
60}
61
62impl<T> Collection for LinkedDeque<T> {
63 type Item = T;
64 type Iter<'a>
65 = std::collections::linked_list::Iter<'a, T>
66 where
67 Self: 'a;
68
69 fn iter(&self) -> Self::Iter<'_> {
70 self.elements.iter()
71 }
72
73 fn size(&self) -> usize {
74 self.elements.len()
75 }
76
77 fn clear(&mut self) {
78 self.elements.clear();
79 }
80
81 fn retain<F>(&mut self, mut f: F) -> usize
82 where
83 F: FnMut(&Self::Item) -> bool,
84 {
85 let before = self.elements.len();
86 if before == 0 {
87 return 0;
88 }
89
90 let mut kept = LinkedList::new();
91 while let Some(element) = self.elements.pop_front() {
92 if f(&element) {
93 kept.push_back(element);
94 }
95 }
96
97 let removed = before - kept.len();
98 self.elements = kept;
99 removed
100 }
101}
102
103impl<T> Disposable for LinkedDeque<T> {
104 fn dispose(&mut self) {
105 self.disposed = true;
106 self.elements.clear();
107 }
108
109 fn is_disposed(&self) -> bool {
110 self.disposed
111 }
112}
113
114impl<'a, T> IntoIterator for &'a LinkedDeque<T> {
115 type Item = &'a T;
116 type IntoIter = std::collections::linked_list::Iter<'a, T>;
117
118 fn into_iter(self) -> Self::IntoIter {
119 self.elements.iter()
120 }
121}
122
123#[cfg(test)]
124mod tests {
125 use collection::{Collection, Disposable};
126
127 use crate::traits::{DequeLike, QueueLike};
128
129 use super::LinkedDeque;
130
131 fn drain_front(q: &mut LinkedDeque<i32>) -> Vec<i32> {
132 let mut out = Vec::new();
133 while let Some(x) = q.dequeue() {
134 out.push(x);
135 }
136 out
137 }
138
139 #[test]
140 fn queue_like_should_work() {
141 let mut q = LinkedDeque::new();
142
143 assert_eq!(q.front(), None);
144 assert_eq!(q.back(), None);
145 assert_eq!(q.dequeue(), None);
146
147 q.enqueues([1, 2, 3]);
148 assert_eq!(q.front(), Some(&1));
149 assert_eq!(q.back(), Some(&3));
150
151 assert_eq!(q.dequeue(), Some(1));
152 assert_eq!(q.dequeue(), Some(2));
153 assert_eq!(q.dequeue(), Some(3));
154 assert_eq!(q.dequeue(), None);
155 }
156
157 #[test]
158 fn deque_like_should_work() {
159 let mut q = LinkedDeque::new();
160
161 q.enqueue_front(2);
162 q.enqueue_front(1);
163 q.enqueue(3);
164 q.enqueue(4);
165
166 assert_eq!(q.front(), Some(&1));
167 assert_eq!(q.back(), Some(&4));
168 assert_eq!(q.dequeue_back(), Some(4));
169 assert_eq!(q.dequeue_back(), Some(3));
170 assert_eq!(q.dequeue_back(), Some(2));
171 assert_eq!(q.dequeue_back(), Some(1));
172 assert_eq!(q.dequeue_back(), None);
173 }
174
175 #[test]
176 fn replace_front_should_follow_queue_contract() {
177 let mut q = LinkedDeque::new();
178
179 assert_eq!(q.replace_front(10), None);
180 assert_eq!(drain_front(&mut q), vec![10]);
181
182 q.enqueues([1, 2, 3]);
183 assert_eq!(q.replace_front(4), Some(1));
184 assert_eq!(drain_front(&mut q), vec![2, 3, 4]);
185 }
186
187 #[test]
188 fn replace_back_should_follow_deque_contract() {
189 let mut q = LinkedDeque::new();
190
191 assert_eq!(q.replace_back(10), None);
192 assert_eq!(drain_front(&mut q), vec![10]);
193
194 q.enqueues([1, 2, 3]);
195 assert_eq!(q.replace_back(0), Some(3));
196 assert_eq!(drain_front(&mut q), vec![0, 1, 2]);
197 }
198
199 #[test]
200 fn enqueues_front_default_impl_should_keep_reverse_input_order() {
201 let mut q = LinkedDeque::new();
202 q.enqueues([3, 4]);
203 q.enqueues_front([1, 2]);
204
205 assert_eq!(drain_front(&mut q), vec![2, 1, 3, 4]);
206 }
207
208 #[test]
209 fn retain_should_filter_and_report_removed_count() {
210 let mut q = LinkedDeque::new();
211 q.enqueues(1..=8);
212
213 assert_eq!(q.retain(|x| *x % 2 == 0), 4);
214 assert_eq!(drain_front(&mut q), vec![2, 4, 6, 8]);
215
216 assert_eq!(q.retain(|_| true), 0);
217 assert_eq!(q.retain(|_| false), 0);
218 }
219
220 #[test]
221 fn collection_contract_should_work() {
222 let mut q = LinkedDeque::new();
223 q.enqueues([3, 1, 2]);
224
225 assert_eq!(Collection::size(&q), 3);
226 assert_eq!(Collection::count(&q, |x| *x >= 2), 2);
227 assert_eq!(Collection::collect(&q), vec![3, 1, 2]);
228
229 let mut out = Vec::new();
230 Collection::collect_into(&q, &mut out);
231 assert_eq!(out, vec![3, 1, 2]);
232
233 Collection::clear(&mut q);
234 assert!(Collection::is_empty(&q));
235 }
236
237 #[test]
238 fn iterable_should_be_complete() {
239 let mut q = LinkedDeque::new();
240 q.enqueues([7, 8, 9]);
241
242 let a: Vec<i32> = q.iter().copied().collect();
243 assert_eq!(a, vec![7, 8, 9]);
244
245 let b: Vec<i32> = (&q).into_iter().copied().collect();
246 assert_eq!(b, vec![7, 8, 9]);
247 }
248
249 #[test]
250 fn dispose_should_clear_and_mark_disposed() {
251 let mut q = LinkedDeque::new();
252 q.enqueues([1, 2, 3]);
253
254 assert!(!q.is_disposed());
255 q.dispose();
256 assert!(q.is_disposed());
257 assert!(q.is_empty());
258 }
259}