graph_collections/
deque.rs

1use std::collections::VecDeque;
2
3/// A double-ended queue (deque) backed by [`VecDeque`].
4///
5/// Provides O(1) push and pop from **both** ends. Iteration order is
6/// front-to-back by default; use `.iter().rev()` or [`Deque::iter_back`]
7/// for back-to-front traversal.
8///
9/// # Differences from [`crate::Queue`]
10///
11/// [`crate::Queue`] is FIFO — elements enter at the back and leave at the front only.
12/// `Deque` relaxes that: you can push and pop from either end independently,
13/// making it suitable for sliding-window algorithms, palindrome checks,
14/// work-stealing schedulers, and undo/redo stacks.
15///
16/// # Examples
17///
18/// ```
19/// use graph_collections::Deque;
20///
21/// let mut deque: Deque<u32> = Deque::new();
22///
23/// deque.push_back(2);
24/// deque.push_front(1);
25/// deque.push_back(3);
26///
27/// // front → back: [1, 2, 3]
28/// assert_eq!(deque.front(), Some(&1));
29/// assert_eq!(deque.back(),  Some(&3));
30///
31/// assert_eq!(deque.pop_front(), Some(1));
32/// assert_eq!(deque.pop_back(),  Some(3));
33/// assert_eq!(deque.len(), 1);
34/// ```
35#[derive(Debug, Clone, PartialEq, Eq)]
36pub struct Deque<T> {
37    data: VecDeque<T>,
38}
39
40// ── Construction ──────────────────────────────────────────────────────────────
41
42impl<T> Default for Deque<T> {
43    fn default() -> Self {
44        Self {
45            data: VecDeque::new(),
46        }
47    }
48}
49
50impl<T> Deque<T> {
51    /// Creates a new, empty deque.
52    ///
53    /// # Examples
54    ///
55    /// ```
56    /// use graph_collections::Deque;
57    ///
58    /// let deque: Deque<u32> = Deque::new();
59    /// assert!(deque.is_empty());
60    /// ```
61    pub fn new() -> Self {
62        Self::default()
63    }
64
65    /// Creates a new, empty deque with at least the given capacity
66    /// pre-allocated, avoiding reallocations for the first `capacity` pushes.
67    ///
68    /// # Examples
69    ///
70    /// ```
71    /// use graph_collections::Deque;
72    ///
73    /// let deque: Deque<u32> = Deque::with_capacity(32);
74    /// assert!(deque.is_empty());
75    /// ```
76    pub fn with_capacity(capacity: usize) -> Self {
77        Self {
78            data: VecDeque::with_capacity(capacity),
79        }
80    }
81}
82
83// ── State queries ─────────────────────────────────────────────────────────────
84
85impl<T> Deque<T> {
86    /// Returns `true` if the deque contains no elements.
87    ///
88    /// # Examples
89    ///
90    /// ```
91    /// use graph_collections::Deque;
92    ///
93    /// let mut deque: Deque<u32> = Deque::new();
94    /// assert!(deque.is_empty());
95    /// deque.push_back(1);
96    /// assert!(!deque.is_empty());
97    /// ```
98    #[inline]
99    pub fn is_empty(&self) -> bool {
100        self.data.is_empty()
101    }
102
103    /// Returns the number of elements in the deque.
104    ///
105    /// # Examples
106    ///
107    /// ```
108    /// use graph_collections::Deque;
109    ///
110    /// let mut deque: Deque<u32> = Deque::new();
111    /// assert_eq!(deque.len(), 0);
112    /// deque.push_back(1);
113    /// deque.push_front(0);
114    /// assert_eq!(deque.len(), 2);
115    /// ```
116    #[must_use]
117    #[inline]
118    pub fn len(&self) -> usize {
119        self.data.len()
120    }
121}
122
123// ── Peek (non-consuming access) ───────────────────────────────────────────────
124
125impl<T> Deque<T> {
126    /// Returns a reference to the **front** element, or `None` if empty.
127    ///
128    /// Does not remove the element.
129    ///
130    /// # Examples
131    ///
132    /// ```
133    /// use graph_collections::Deque;
134    ///
135    /// let mut deque: Deque<u32> = Deque::new();
136    /// assert_eq!(deque.front(), None);
137    /// deque.push_back(1);
138    /// deque.push_back(2);
139    /// assert_eq!(deque.front(), Some(&1));
140    /// assert_eq!(deque.len(), 2); // unchanged
141    /// ```
142    #[must_use]
143    #[inline]
144    pub fn front(&self) -> Option<&T> {
145        self.data.front()
146    }
147
148    /// Returns a mutable reference to the **front** element, or `None` if empty.
149    ///
150    /// # Examples
151    ///
152    /// ```
153    /// use graph_collections::Deque;
154    ///
155    /// let mut deque: Deque<u32> = Deque::new();
156    /// deque.push_back(1);
157    /// if let Some(v) = deque.front_mut() {
158    ///     *v = 99;
159    /// }
160    /// assert_eq!(deque.front(), Some(&99));
161    /// ```
162    #[must_use]
163    #[inline]
164    pub fn front_mut(&mut self) -> Option<&mut T> {
165        self.data.front_mut()
166    }
167
168    /// Returns a reference to the **back** element, or `None` if empty.
169    ///
170    /// Does not remove the element.
171    ///
172    /// # Examples
173    ///
174    /// ```
175    /// use graph_collections::Deque;
176    ///
177    /// let mut deque: Deque<u32> = Deque::new();
178    /// assert_eq!(deque.back(), None);
179    /// deque.push_back(1);
180    /// deque.push_back(2);
181    /// assert_eq!(deque.back(), Some(&2));
182    /// assert_eq!(deque.len(), 2); // unchanged
183    /// ```
184    #[must_use]
185    #[inline]
186    pub fn back(&self) -> Option<&T> {
187        self.data.back()
188    }
189
190    /// Returns a mutable reference to the **back** element, or `None` if empty.
191    ///
192    /// # Examples
193    ///
194    /// ```
195    /// use graph_collections::Deque;
196    ///
197    /// let mut deque: Deque<u32> = Deque::new();
198    /// deque.push_back(1);
199    /// if let Some(v) = deque.back_mut() {
200    ///     *v = 42;
201    /// }
202    /// assert_eq!(deque.back(), Some(&42));
203    /// ```
204    #[must_use]
205    #[inline]
206    pub fn back_mut(&mut self) -> Option<&mut T> {
207        self.data.back_mut()
208    }
209
210    /// Returns a reference to the element at `index` (front = 0), or `None`
211    /// if `index` is out of bounds.
212    ///
213    /// # Examples
214    ///
215    /// ```
216    /// use graph_collections::Deque;
217    ///
218    /// let deque: Deque<u32> = (10..=14).collect();
219    /// assert_eq!(deque.get(0), Some(&10));
220    /// assert_eq!(deque.get(2), Some(&12));
221    /// assert_eq!(deque.get(9), None);
222    /// ```
223    #[must_use]
224    #[inline]
225    pub fn get(&self, index: usize) -> Option<&T> {
226        self.data.get(index)
227    }
228}
229
230// ── Push (inserting elements) ─────────────────────────────────────────────────
231
232impl<T> Deque<T> {
233    /// Appends `element` to the **back** of the deque.
234    ///
235    /// # Examples
236    ///
237    /// ```
238    /// use graph_collections::Deque;
239    ///
240    /// let mut deque: Deque<u32> = Deque::new();
241    /// deque.push_back(1);
242    /// deque.push_back(2);
243    /// assert_eq!(deque.back(), Some(&2));
244    /// ```
245    #[inline]
246    pub fn push_back(&mut self, element: T) {
247        self.data.push_back(element);
248    }
249
250    /// Prepends `element` to the **front** of the deque.
251    ///
252    /// # Examples
253    ///
254    /// ```
255    /// use graph_collections::Deque;
256    ///
257    /// let mut deque: Deque<u32> = Deque::new();
258    /// deque.push_front(2);
259    /// deque.push_front(1);
260    /// assert_eq!(deque.front(), Some(&1));
261    /// ```
262    #[inline]
263    pub fn push_front(&mut self, element: T) {
264        self.data.push_front(element);
265    }
266}
267
268// ── Pop (removing elements) ───────────────────────────────────────────────────
269
270impl<T> Deque<T> {
271    /// Removes and returns the **front** element, or `None` if empty.
272    ///
273    /// # Examples
274    ///
275    /// ```
276    /// use graph_collections::Deque;
277    ///
278    /// let mut deque: Deque<u32> = Deque::new();
279    /// assert_eq!(deque.pop_front(), None);
280    /// deque.push_back(1);
281    /// deque.push_back(2);
282    /// assert_eq!(deque.pop_front(), Some(1));
283    /// assert_eq!(deque.pop_front(), Some(2));
284    /// assert_eq!(deque.pop_front(), None);
285    /// ```
286    #[inline]
287    pub fn pop_front(&mut self) -> Option<T> {
288        self.data.pop_front()
289    }
290
291    /// Removes and returns the **back** element, or `None` if empty.
292    ///
293    /// # Examples
294    ///
295    /// ```
296    /// use graph_collections::Deque;
297    ///
298    /// let mut deque: Deque<u32> = Deque::new();
299    /// assert_eq!(deque.pop_back(), None);
300    /// deque.push_back(1);
301    /// deque.push_back(2);
302    /// assert_eq!(deque.pop_back(), Some(2));
303    /// assert_eq!(deque.pop_back(), Some(1));
304    /// assert_eq!(deque.pop_back(), None);
305    /// ```
306    #[inline]
307    pub fn pop_back(&mut self) -> Option<T> {
308        self.data.pop_back()
309    }
310
311    /// Removes all elements from the deque.
312    ///
313    /// # Examples
314    ///
315    /// ```
316    /// use graph_collections::Deque;
317    ///
318    /// let mut deque: Deque<u32> = (1..=5).collect();
319    /// assert_eq!(deque.len(), 5);
320    /// deque.clear();
321    /// assert!(deque.is_empty());
322    /// ```
323    #[inline]
324    pub fn clear(&mut self) {
325        self.data.clear();
326    }
327}
328
329// ── Rotation ──────────────────────────────────────────────────────────────────
330
331impl<T> Deque<T> {
332    /// Rotates the deque `n` steps to the **left**: moves the front `n` elements
333    /// to the back.
334    ///
335    /// Equivalent to calling `push_back(pop_front())` n times, but O(n) not O(n²).
336    ///
337    /// # Panics
338    ///
339    /// Panics if `n > self.len()`.
340    ///
341    /// # Examples
342    ///
343    /// ```
344    /// use graph_collections::Deque;
345    ///
346    /// let mut deque: Deque<u32> = (1..=5).collect();
347    /// deque.rotate_left(2);
348    /// // was [1,2,3,4,5], now [3,4,5,1,2]
349    /// assert_eq!(deque.front(), Some(&3));
350    /// assert_eq!(deque.back(),  Some(&2));
351    /// ```
352    #[inline]
353    pub fn rotate_left(&mut self, n: usize) {
354        self.data.rotate_left(n);
355    }
356
357    /// Rotates the deque `n` steps to the **right**: moves the back `n` elements
358    /// to the front.
359    ///
360    /// Equivalent to calling `push_front(pop_back())` n times, but O(n) not O(n²).
361    ///
362    /// # Panics
363    ///
364    /// Panics if `n > self.len()`.
365    ///
366    /// # Examples
367    ///
368    /// ```
369    /// use graph_collections::Deque;
370    ///
371    /// let mut deque: Deque<u32> = (1..=5).collect();
372    /// deque.rotate_right(2);
373    /// // was [1,2,3,4,5], now [4,5,1,2,3]
374    /// assert_eq!(deque.front(), Some(&4));
375    /// assert_eq!(deque.back(),  Some(&3));
376    /// ```
377    #[inline]
378    pub fn rotate_right(&mut self, n: usize) {
379        self.data.rotate_right(n);
380    }
381}
382
383// ── Iteration ─────────────────────────────────────────────────────────────────
384
385impl<T> Deque<T> {
386    /// Returns a front-to-back iterator over references to the elements.
387    ///
388    /// The deque is not modified.
389    ///
390    /// # Examples
391    ///
392    /// ```
393    /// use graph_collections::Deque;
394    ///
395    /// let deque: Deque<u32> = (1..=4).collect();
396    /// let values: Vec<u32> = deque.iter().copied().collect();
397    /// assert_eq!(values, [1, 2, 3, 4]);
398    /// ```
399    #[inline]
400    pub fn iter(&self) -> std::collections::vec_deque::Iter<'_, T> {
401        self.data.iter()
402    }
403
404    /// Returns a **back-to-front** iterator over references to the elements.
405    ///
406    /// Convenience wrapper around `self.iter().rev()`. Because [`std::collections::vec_deque::Iter`]
407    /// implements [`DoubleEndedIterator`], reversing is O(1) setup with O(1)
408    /// per element — no allocation.
409    ///
410    /// # Examples
411    ///
412    /// ```
413    /// use graph_collections::Deque;
414    ///
415    /// let deque: Deque<u32> = (1..=4).collect();
416    /// let values: Vec<u32> = deque.iter_back().copied().collect();
417    /// assert_eq!(values, [4, 3, 2, 1]);
418    /// ```
419    #[inline]
420    pub fn iter_back(&self) -> std::iter::Rev<std::collections::vec_deque::Iter<'_, T>> {
421        self.data.iter().rev()
422    }
423}
424
425// ── FromIterator / Extend ─────────────────────────────────────────────────────
426
427impl<T> FromIterator<T> for Deque<T> {
428    /// Builds a `Deque` from any iterator. Elements are pushed to the back
429    /// in iteration order — front of the iterator becomes front of the deque.
430    ///
431    /// # Examples
432    ///
433    /// ```
434    /// use graph_collections::Deque;
435    ///
436    /// let deque: Deque<u32> = (1..=4).collect();
437    /// assert_eq!(deque.front(), Some(&1));
438    /// assert_eq!(deque.back(),  Some(&4));
439    /// assert_eq!(deque.len(),   4);
440    /// ```
441    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
442        Self {
443            data: VecDeque::from_iter(iter),
444        }
445    }
446}
447
448impl<T> Extend<T> for Deque<T> {
449    /// Pushes all elements produced by the iterator to the **back** of the deque.
450    ///
451    /// # Examples
452    ///
453    /// ```
454    /// use graph_collections::Deque;
455    ///
456    /// let mut deque: Deque<u32> = Deque::new();
457    /// deque.push_back(1);
458    /// deque.extend([2, 3, 4]);
459    /// assert_eq!(deque.len(),  4);
460    /// assert_eq!(deque.back(), Some(&4));
461    /// ```
462    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
463        self.data.extend(iter);
464    }
465}
466
467// ── IntoIterator ──────────────────────────────────────────────────────────────
468
469/// Consuming iterator: `for x in deque`
470impl<T> IntoIterator for Deque<T> {
471    type Item = T;
472    type IntoIter = std::collections::vec_deque::IntoIter<T>;
473
474    /// Consumes the deque and yields elements front-to-back.
475    ///
476    /// # Examples
477    ///
478    /// ```
479    /// use graph_collections::Deque;
480    ///
481    /// let deque: Deque<u32> = (1..=3).collect();
482    /// let values: Vec<u32> = deque.into_iter().collect();
483    /// assert_eq!(values, [1, 2, 3]);
484    /// ```
485    fn into_iter(self) -> Self::IntoIter {
486        self.data.into_iter()
487    }
488}
489
490/// Borrowing iterator: `for x in &deque`
491impl<'a, T> IntoIterator for &'a Deque<T> {
492    type Item = &'a T;
493    type IntoIter = std::collections::vec_deque::Iter<'a, T>;
494
495    /// Iterates over references to elements front-to-back without consuming the deque.
496    ///
497    /// # Examples
498    ///
499    /// ```
500    /// use graph_collections::Deque;
501    ///
502    /// let deque: Deque<u32> = (1..=3).collect();
503    /// let sum: u32 = (&deque).into_iter().sum();
504    /// assert_eq!(sum, 6);
505    /// assert_eq!(deque.len(), 3); // deque is still alive
506    /// ```
507    fn into_iter(self) -> Self::IntoIter {
508        self.data.iter()
509    }
510}
graph_collections/deque.rs

graph_collections/
deque.rs
