array_deque/
stack_array_deque.rs

1use core::fmt;
2use core::mem::MaybeUninit;
3use core::ops::{Index, IndexMut};
4
5#[cfg(feature = "serde")]
6use serde::{Deserialize, Deserializer, Serialize, Serializer};
7
8/// A fixed-capacity, stack-allocated double-ended queue backed by a circular buffer.
9///
10/// `StackArrayDeque<T, N>` stores up to `N` elements inline on the stack with no heap
11/// allocation. All insertions and removals at either end run in O(1) time. Once full,
12/// further `push_back` calls will overwrite the oldest front element, and
13/// `push_front` calls will overwrite the oldest back element (FIFO overwrite behavior).
14///
15/// # Examples
16///
17/// ```rust
18/// use array_deque::StackArrayDeque;
19///
20/// let mut dq: StackArrayDeque<i32, 3> = StackArrayDeque::new();
21/// dq.push_back(10);
22/// dq.push_back(20);
23/// dq.push_front(5);
24/// assert_eq!(dq.len(), 3);
25/// assert_eq!(dq[0], 5);
26/// assert_eq!(dq[2], 20);
27///
28/// // Overflow: overwrites the front (5)
29/// dq.push_back(30);
30/// assert_eq!(dq.pop_front(), Some(10));
31/// ```
32pub struct StackArrayDeque<T, const N: usize> {
33    data: [MaybeUninit<T>; N],
34    len: usize,
35    idx: usize,
36}
37
38impl<T, const N: usize> StackArrayDeque<T, N> {
39    /// Creates a new empty `StackArrayDeque`.
40    ///
41    /// # Examples
42    ///
43    /// ```
44    /// use array_deque::StackArrayDeque;
45    ///
46    /// let deque: StackArrayDeque<i32, 10> = StackArrayDeque::new();
47    /// assert_eq!(deque.capacity(), 10);
48    /// assert!(deque.is_empty());
49    /// ```
50    pub const fn new() -> Self {
51        assert!(N > 0, "StackArrayDeque capacity must be greater than 0");
52        Self {
53            data: unsafe { MaybeUninit::uninit().assume_init() },
54            len: 0,
55            idx: 0,
56        }
57    }
58
59    /// Appends an element to the back of the deque.
60    ///
61    /// If the deque is at capacity, this will overwrite the front element
62    /// and advance the front pointer.
63    ///
64    /// # Arguments
65    ///
66    /// * `value` - The element to append
67    ///
68    /// # Examples
69    ///
70    /// ```
71    /// use array_deque::StackArrayDeque;
72    ///
73    /// let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
74    /// deque.push_back(1);
75    /// deque.push_back(2);
76    /// assert_eq!(deque.len(), 2);
77    /// ```
78    pub fn push_back(&mut self, value: T) {
79        let write_idx = (self.idx + self.len) % N;
80        self.data[write_idx].write(value);
81
82        if self.len == N {
83            self.idx = (self.idx + 1) % N;
84        } else {
85            self.len += 1;
86        }
87    }
88
89    /// Prepends an element to the front of the deque.
90    ///
91    /// If the deque is at capacity, this will overwrite the back element.
92    ///
93    /// # Arguments
94    ///
95    /// * `value` - The element to prepend
96    ///
97    /// # Examples
98    ///
99    /// ```
100    /// use array_deque::StackArrayDeque;
101    ///
102    /// let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
103    /// deque.push_front(1);
104    /// deque.push_front(2);
105    /// assert_eq!(deque[0], 2);
106    /// assert_eq!(deque[1], 1);
107    /// ```
108    pub fn push_front(&mut self, value: T) {
109        self.idx = (self.idx + N - 1) % N;
110
111        if self.len == N {
112            let drop_idx = (self.idx + self.len) % N;
113            unsafe {
114                self.data[drop_idx].assume_init_drop();
115            }
116        } else {
117            self.len += 1;
118        }
119
120        self.data[self.idx].write(value);
121    }
122
123    /// Removes and returns the last element from the deque.
124    ///
125    /// # Returns
126    ///
127    /// `Some(T)` if the deque is not empty, `None` otherwise.
128    ///
129    /// # Examples
130    ///
131    /// ```
132    /// use array_deque::StackArrayDeque;
133    ///
134    /// let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
135    /// deque.push_back(1);
136    /// deque.push_back(2);
137    /// assert_eq!(deque.pop_back(), Some(2));
138    /// assert_eq!(deque.pop_back(), Some(1));
139    /// assert_eq!(deque.pop_back(), None);
140    /// ```
141    pub fn pop_back(&mut self) -> Option<T> {
142        if self.len == 0 {
143            return None;
144        }
145        let tail_idx = (self.idx + self.len - 1) % N;
146        self.len -= 1;
147        Some(unsafe { self.data[tail_idx].assume_init_read() })
148    }
149
150    /// Removes and returns the first element from the deque.
151    ///
152    /// # Returns
153    ///
154    /// `Some(T)` if the deque is not empty, `None` otherwise.
155    ///
156    /// # Examples
157    ///
158    /// ```
159    /// use array_deque::StackArrayDeque;
160    ///
161    /// let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
162    /// deque.push_back(1);
163    /// deque.push_back(2);
164    /// assert_eq!(deque.pop_front(), Some(1));
165    /// assert_eq!(deque.pop_front(), Some(2));
166    /// assert_eq!(deque.pop_front(), None);
167    /// ```
168    pub fn pop_front(&mut self) -> Option<T> {
169        if self.len == 0 {
170            return None;
171        }
172        let front_idx = self.idx;
173        self.idx = (self.idx + 1) % N;
174        self.len -= 1;
175        Some(unsafe { self.data[front_idx].assume_init_read() })
176    }
177
178    /// Returns a reference to the front element without removing it.
179    ///
180    /// # Examples
181    ///
182    /// ```
183    /// use array_deque::StackArrayDeque;
184    ///
185    /// let mut dq: StackArrayDeque<i32, 3> = StackArrayDeque::new();
186    /// assert_eq!(dq.front(), None);
187    /// dq.push_back(42);
188    /// assert_eq!(dq.front(), Some(&42));
189    /// ```
190    pub fn front(&self) -> Option<&T> {
191        if self.is_empty() {
192            None
193        } else {
194            Some(unsafe { self.data[self.idx].assume_init_ref() })
195        }
196    }
197
198    /// Returns a reference to the back element without removing it.
199    ///
200    /// # Examples
201    ///
202    /// ```
203    /// use array_deque::StackArrayDeque;
204    ///
205    /// let mut dq: StackArrayDeque<i32, 3> = StackArrayDeque::new();
206    /// dq.push_back(1);
207    /// dq.push_back(2);
208    /// assert_eq!(dq.back(), Some(&2));
209    /// ```
210    pub fn back(&self) -> Option<&T> {
211        if self.is_empty() {
212            None
213        } else {
214            let back_idx = (self.idx + self.len - 1) % N;
215            Some(unsafe { self.data[back_idx].assume_init_ref() })
216        }
217    }
218
219    /// Returns an iterator over the elements of the deque.
220    ///
221    /// The iterator yields elements from front to back.
222    ///
223    /// # Examples
224    ///
225    /// ```
226    /// use array_deque::StackArrayDeque;
227    ///
228    /// let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
229    /// deque.push_back(1);
230    /// deque.push_back(2);
231    /// deque.push_back(3);
232    ///
233    /// let mut iter = deque.iter();
234    /// assert_eq!(iter.next(), Some(&1));
235    /// assert_eq!(iter.next(), Some(&2));
236    /// assert_eq!(iter.next(), Some(&3));
237    /// assert_eq!(iter.next(), None);
238    /// ```
239    pub fn iter(&self) -> impl Iterator<Item = &T> {
240        (0..self.len).map(move |i| {
241            let idx = (self.idx + i) % N;
242            unsafe { self.data[idx].assume_init_ref() }
243        })
244    }
245
246    /// Returns the maximum capacity of the deque.
247    ///
248    /// # Examples
249    ///
250    /// ```
251    /// use array_deque::StackArrayDeque;
252    ///
253    /// let deque: StackArrayDeque<i32, 10> = StackArrayDeque::new();
254    /// assert_eq!(deque.capacity(), 10);
255    /// ```
256    pub const fn capacity(&self) -> usize {
257        N
258    }
259
260    /// Returns the number of elements currently in the deque.
261    ///
262    /// # Examples
263    ///
264    /// ```
265    /// use array_deque::StackArrayDeque;
266    ///
267    /// let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
268    /// assert_eq!(deque.len(), 0);
269    /// deque.push_back(1);
270    /// assert_eq!(deque.len(), 1);
271    /// ```
272    pub const fn len(&self) -> usize {
273        self.len
274    }
275
276    /// Returns `true` if the deque contains no elements.
277    ///
278    /// # Examples
279    ///
280    /// ```
281    /// use array_deque::StackArrayDeque;
282    ///
283    /// let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
284    /// assert!(deque.is_empty());
285    /// deque.push_back(1);
286    /// assert!(!deque.is_empty());
287    /// ```
288    pub const fn is_empty(&self) -> bool {
289        self.len == 0
290    }
291
292    /// Returns `true` if the deque has reached its maximum capacity.
293    ///
294    /// # Examples
295    ///
296    /// ```
297    /// use array_deque::StackArrayDeque;
298    ///
299    /// let mut deque: StackArrayDeque<i32, 2> = StackArrayDeque::new();
300    /// assert!(!deque.is_full());
301    /// deque.push_back(1);
302    /// deque.push_back(2);
303    /// assert!(deque.is_full());
304    /// ```
305    pub const fn is_full(&self) -> bool {
306        self.len == N
307    }
308
309    /// Removes all elements from the deque.
310    ///
311    /// This operation properly drops all contained elements and resets
312    /// the deque to an empty state.
313    ///
314    /// # Examples
315    ///
316    /// ```
317    /// use array_deque::StackArrayDeque;
318    ///
319    /// let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
320    /// deque.push_back(1);
321    /// deque.push_back(2);
322    /// deque.clear();
323    /// assert!(deque.is_empty());
324    /// assert_eq!(deque.len(), 0);
325    /// ```
326    pub fn clear(&mut self) {
327        for i in 0..self.len {
328            let idx = (self.idx + i) % N;
329            unsafe {
330                self.data[idx].assume_init_drop();
331            }
332        }
333        self.len = 0;
334        self.idx = 0;
335    }
336}
337
338impl<T, const N: usize> Drop for StackArrayDeque<T, N> {
339    /// Properly drops all contained elements.
340    fn drop(&mut self) {
341        self.clear();
342    }
343}
344
345impl<T, const N: usize> Default for StackArrayDeque<T, N> {
346    /// Creates an empty deque.
347    fn default() -> Self {
348        Self::new()
349    }
350}
351
352impl<T: fmt::Debug, const N: usize> fmt::Debug for StackArrayDeque<T, N> {
353    /// Formats the deque as a debug list showing all elements from front to back.
354    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
355        f.debug_list().entries(self.iter()).finish()
356    }
357}
358
359impl<T: Clone, const N: usize> Clone for StackArrayDeque<T, N> {
360    /// Creates a deep copy of the deque with the same capacity and elements.
361    fn clone(&self) -> Self {
362        let mut new = StackArrayDeque::new();
363        for item in self.iter() {
364            new.push_back(item.clone());
365        }
366        new
367    }
368}
369
370impl<T: PartialEq, const N: usize> PartialEq for StackArrayDeque<T, N> {
371    /// Compares two deques for equality based on their elements and order.
372    fn eq(&self, other: &Self) -> bool {
373        self.len == other.len && self.iter().eq(other.iter())
374    }
375}
376
377impl<T: Eq, const N: usize> Eq for StackArrayDeque<T, N> {}
378
379impl<T, const N: usize> Index<usize> for StackArrayDeque<T, N> {
380    type Output = T;
381
382    /// Provides indexed access to elements in the deque.
383    ///
384    /// Index 0 corresponds to the front element, index 1 to the second element, etc.
385    ///
386    /// # Panics
387    ///
388    /// Panics if the index is out of bounds (>= len()).
389    fn index(&self, i: usize) -> &Self::Output {
390        assert!(i < self.len);
391        let idx = (self.idx + i) % N;
392        unsafe { self.data[idx].assume_init_ref() }
393    }
394}
395
396impl<T, const N: usize> IndexMut<usize> for StackArrayDeque<T, N> {
397    /// Provides mutable indexed access to elements in the deque.
398    ///
399    /// # Panics
400    ///
401    /// Panics if the index is out of bounds (>= len()).
402    fn index_mut(&mut self, i: usize) -> &mut Self::Output {
403        assert!(i < self.len);
404        let idx = (self.idx + i) % N;
405        unsafe { self.data[idx].assume_init_mut() }
406    }
407}
408
409#[cfg(feature = "serde")]
410impl<T: Serialize, const N: usize> Serialize for StackArrayDeque<T, N> {
411    /// Serializes the deque as a sequence of its elements from front to back.
412    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
413    where
414        S: Serializer,
415    {
416        use serde::ser::SerializeSeq;
417        let mut seq = serializer.serialize_seq(Some(self.len))?;
418        for item in self.iter() {
419            seq.serialize_element(item)?;
420        }
421        seq.end()
422    }
423}
424
425#[cfg(feature = "serde")]
426impl<'de, T: Deserialize<'de>, const N: usize> Deserialize<'de> for StackArrayDeque<T, N> {
427    /// Deserializes a sequence into a `StackArrayDeque`, erroring if it exceeds capacity.
428    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
429    where
430        D: Deserializer<'de>,
431    {
432        let vec: Vec<T> = Vec::deserialize(deserializer)?;
433        if vec.len() > N {
434            return Err(serde::de::Error::custom(
435                "Too many elements for StackArrayDeque capacity",
436            ));
437        }
438        let mut deque = StackArrayDeque::new();
439        for item in vec {
440            deque.push_back(item);
441        }
442        Ok(deque)
443    }
444}
445
446impl<T, const N: usize> Extend<T> for StackArrayDeque<T, N> {
447    /// Extends the deque with items from an iterator, pushing to the back.
448    ///
449    /// # Examples
450    ///
451    /// ```
452    /// use array_deque::StackArrayDeque;
453    ///
454    /// let mut dq: StackArrayDeque<i32, 5> = StackArrayDeque::new();
455    /// dq.extend([1,2,3]);
456    /// assert_eq!(dq.len(), 3);
457    /// ```
458    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
459        for item in iter {
460            self.push_back(item);
461        }
462    }
463}
464
465impl<T, const N: usize> FromIterator<T> for StackArrayDeque<T, N> {
466    /// Creates a deque by collecting an iterator into its back, up to capacity.
467    ///
468    /// # Examples
469    ///
470    /// ```
471    /// use array_deque::StackArrayDeque;
472    ///
473    /// let dq: StackArrayDeque<_, 4> = (0..3).collect();
474    /// assert_eq!(dq.len(), 3);
475    /// ```
476    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
477        let mut dq = StackArrayDeque::new();
478        dq.extend(iter);
479        dq
480    }
481}
482
483/// An owning iterator that moves elements out of a `StackArrayDeque`.
484///
485/// This is returned by `into_iter()`.
486pub struct StackArrayDequeIntoIter<T, const N: usize> {
487    deque: StackArrayDeque<T, N>,
488    pos: usize,
489}
490
491impl<T, const N: usize> Iterator for StackArrayDequeIntoIter<T, N> {
492    type Item = T;
493    /// Advances and returns the next element, front to back.
494    fn next(&mut self) -> Option<T> {
495        if self.pos >= self.deque.len {
496            None
497        } else {
498            // read element at front+pos
499            let idx = (self.deque.idx + self.pos) % N;
500            self.pos += 1;
501            // safety: we know these slots were initialized
502            Some(unsafe { self.deque.data[idx].assume_init_read() })
503        }
504    }
505}
506
507impl<T, const N: usize> IntoIterator for StackArrayDeque<T, N> {
508    type Item = T;
509    type IntoIter = StackArrayDequeIntoIter<T, N>;
510    /// Consumes the deque and returns an iterator over its elements.
511    fn into_iter(self) -> Self::IntoIter {
512        StackArrayDequeIntoIter {
513            deque: self,
514            pos: 0,
515        }
516    }
517}
518
519/// A borrowed iterator over `&T` from a `StackArrayDeque`.
520///
521/// This is returned by `iter()` and `&deque.into_iter()`.
522pub struct StackArrayDequeIter<'a, T, const N: usize> {
523    deque: &'a StackArrayDeque<T, N>,
524    pos: usize,
525}
526
527impl<'a, T, const N: usize> Iterator for StackArrayDequeIter<'a, T, N> {
528    type Item = &'a T;
529    /// Advances and returns the next reference, front to back.
530    fn next(&mut self) -> Option<&'a T> {
531        if self.pos >= self.deque.len {
532            None
533        } else {
534            let idx = (self.deque.idx + self.pos) % N;
535            self.pos += 1;
536            Some(unsafe { self.deque.data[idx].assume_init_ref() })
537        }
538    }
539}
540
541impl<'a, T, const N: usize> IntoIterator for &'a StackArrayDeque<T, N> {
542    type Item = &'a T;
543    type IntoIter = StackArrayDequeIter<'a, T, N>;
544    /// Borrows the deque and returns an iterator over `&T`.
545    fn into_iter(self) -> Self::IntoIter {
546        StackArrayDequeIter {
547            deque: self,
548            pos: 0,
549        }
550    }
551}
552
553#[cfg(test)]
554mod tests {
555    use super::*;
556
557    #[test]
558    fn push_pop() {
559        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
560        deque.push_back(1);
561        deque.push_back(2);
562        deque.push_back(3);
563        assert_eq!(deque.pop_front(), Some(1));
564        assert_eq!(deque.pop_back(), Some(3));
565        assert_eq!(deque.pop_front(), Some(2));
566        assert_eq!(deque.pop_front(), None);
567    }
568
569    #[test]
570    fn push_front_back() {
571        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
572        deque.push_front(1);
573        deque.push_front(2);
574        deque.push_back(3);
575        assert_eq!(deque.pop_front(), Some(2));
576        assert_eq!(deque.pop_back(), Some(3));
577        assert_eq!(deque.pop_front(), Some(1));
578        assert_eq!(deque.pop_front(), None);
579    }
580
581    #[test]
582    fn iter() {
583        let mut deque: StackArrayDeque<i32, 5> = StackArrayDeque::new();
584        deque.push_back(1);
585        deque.push_back(2);
586        deque.push_back(3);
587        let mut iter = deque.iter();
588        assert_eq!(iter.next(), Some(&1));
589        assert_eq!(iter.next(), Some(&2));
590        assert_eq!(iter.next(), Some(&3));
591        assert_eq!(iter.next(), None);
592    }
593
594    #[test]
595    fn clear() {
596        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
597        deque.push_back(1);
598        deque.push_back(2);
599        deque.clear();
600        assert!(deque.is_empty());
601        assert_eq!(deque.len(), 0);
602    }
603
604    #[test]
605    fn capacity() {
606        let deque: StackArrayDeque<i32, 5> = StackArrayDeque::new();
607        assert_eq!(deque.capacity(), 5);
608        assert!(deque.is_empty());
609    }
610
611    #[test]
612    fn clone() {
613        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
614        deque.push_back(1);
615        deque.push_back(2);
616        let cloned_deque = deque.clone();
617        assert_eq!(cloned_deque.len(), 2);
618        assert_eq!(cloned_deque[0], 1);
619        assert_eq!(cloned_deque[1], 2);
620    }
621
622    #[test]
623    fn index() {
624        let mut deque: StackArrayDeque<i32, 5> = StackArrayDeque::new();
625        deque.push_back(1);
626        deque.push_back(2);
627        deque.push_back(3);
628        assert_eq!(deque[0], 1);
629        assert_eq!(deque[1], 2);
630        assert_eq!(deque[2], 3);
631        assert!(
632            std::panic::catch_unwind(|| {
633                let _ = deque[3];
634            })
635            .is_err()
636        );
637    }
638
639    #[test]
640    fn index_mut() {
641        let mut deque: StackArrayDeque<i32, 5> = StackArrayDeque::new();
642        deque.push_back(1);
643        deque.push_back(2);
644        deque.push_back(3);
645        deque[0] = 10;
646        assert_eq!(deque[0], 10);
647        assert_eq!(deque[1], 2);
648        assert_eq!(deque[2], 3);
649        assert!(
650            std::panic::catch_unwind(|| {
651                let _ = deque[3];
652            })
653            .is_err()
654        );
655    }
656
657    #[test]
658    fn iter_empty() {
659        let deque: StackArrayDeque<i32, 5> = StackArrayDeque::new();
660        let mut iter = deque.iter();
661        assert_eq!(iter.next(), None);
662    }
663
664    #[test]
665    fn iter_full() {
666        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
667        deque.push_back(1);
668        deque.push_back(2);
669        deque.push_back(3);
670        let mut iter = deque.iter();
671        assert_eq!(iter.next(), Some(&1));
672        assert_eq!(iter.next(), Some(&2));
673        assert_eq!(iter.next(), Some(&3));
674        assert_eq!(iter.next(), None);
675    }
676
677    #[test]
678    fn iter_partial() {
679        let mut deque: StackArrayDeque<i32, 5> = StackArrayDeque::new();
680        deque.push_back(1);
681        deque.push_back(2);
682        let mut iter = deque.iter();
683        assert_eq!(iter.next(), Some(&1));
684        assert_eq!(iter.next(), Some(&2));
685        assert_eq!(iter.next(), None);
686    }
687
688    #[test]
689    fn is_empty() {
690        let deque: StackArrayDeque<i32, 5> = StackArrayDeque::new();
691        assert!(deque.is_empty());
692        assert_eq!(deque.len(), 0);
693    }
694
695    #[test]
696    fn is_full() {
697        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
698        assert!(!deque.is_full());
699        deque.push_back(1);
700        deque.push_back(2);
701        assert!(!deque.is_full());
702        deque.push_back(3);
703        assert!(deque.is_full());
704    }
705
706    #[test]
707    fn clear_empty() {
708        let mut deque: StackArrayDeque<(), 3> = StackArrayDeque::new();
709        deque.clear();
710        assert!(deque.is_empty());
711        assert_eq!(deque.len(), 0);
712    }
713
714    #[test]
715    fn clear_non_empty() {
716        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
717        deque.push_back(1);
718        deque.push_back(2);
719        deque.clear();
720        assert!(deque.is_empty());
721        assert_eq!(deque.len(), 0);
722    }
723
724    #[test]
725    fn overflow_behavior_push_back() {
726        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
727        deque.push_back(1);
728        deque.push_back(2);
729        deque.push_back(3);
730        assert!(deque.is_full());
731
732        // This should overwrite the front element (1)
733        deque.push_back(4);
734        assert_eq!(deque.len(), 3);
735        assert_eq!(deque[0], 2);
736        assert_eq!(deque[1], 3);
737        assert_eq!(deque[2], 4);
738    }
739
740    #[test]
741    fn overflow_behavior_push_front() {
742        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
743        deque.push_back(1);
744        deque.push_back(2);
745        deque.push_back(3);
746        assert!(deque.is_full());
747
748        // This should overwrite the back element (3)
749        deque.push_front(0);
750        assert_eq!(deque.len(), 3);
751        assert_eq!(deque[0], 0);
752        assert_eq!(deque[1], 1);
753        assert_eq!(deque[2], 2);
754    }
755
756    #[test]
757    fn default() {
758        let deque: StackArrayDeque<i32, 5> = StackArrayDeque::default();
759        assert!(deque.is_empty());
760        assert_eq!(deque.capacity(), 5);
761    }
762
763    #[test]
764    fn debug_format() {
765        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
766        deque.push_back(1);
767        deque.push_back(2);
768        let debug_str = format!("{:?}", deque);
769        assert_eq!(debug_str, "[1, 2]");
770    }
771
772    #[test]
773    fn partial_eq() {
774        let mut deque1: StackArrayDeque<i32, 3> = StackArrayDeque::new();
775        let mut deque2: StackArrayDeque<i32, 3> = StackArrayDeque::new();
776
777        assert_eq!(deque1, deque2);
778
779        deque1.push_back(1);
780        deque1.push_back(2);
781
782        deque2.push_back(1);
783        deque2.push_back(2);
784
785        assert_eq!(deque1, deque2);
786
787        deque2.push_back(3);
788        assert_ne!(deque1, deque2);
789    }
790
791    #[test]
792    fn circular_behavior() {
793        let mut deque: StackArrayDeque<i32, 3> = StackArrayDeque::new();
794
795        // Fill the deque
796        deque.push_back(1);
797        deque.push_back(2);
798        deque.push_back(3);
799
800        // Remove from front and add to back (should wrap around)
801        assert_eq!(deque.pop_front(), Some(1));
802        deque.push_back(4);
803
804        assert_eq!(deque[0], 2);
805        assert_eq!(deque[1], 3);
806        assert_eq!(deque[2], 4);
807
808        // Remove from back and add to front (should wrap around)
809        assert_eq!(deque.pop_back(), Some(4));
810        deque.push_front(0);
811
812        assert_eq!(deque[0], 0);
813        assert_eq!(deque[1], 2);
814        assert_eq!(deque[2], 3);
815    }
816
817    #[test]
818    fn mixed_operations() {
819        let mut deque: StackArrayDeque<i32, 4> = StackArrayDeque::new();
820
821        deque.push_back(1);
822        deque.push_front(0);
823        deque.push_back(2);
824        deque.push_front(-1);
825
826        assert_eq!(deque.len(), 4);
827        assert!(deque.is_full());
828
829        assert_eq!(deque[0], -1);
830        assert_eq!(deque[1], 0);
831        assert_eq!(deque[2], 1);
832        assert_eq!(deque[3], 2);
833
834        assert_eq!(deque.pop_front(), Some(-1));
835        assert_eq!(deque.pop_back(), Some(2));
836        assert_eq!(deque.len(), 2);
837
838        assert_eq!(deque[0], 0);
839        assert_eq!(deque[1], 1);
840    }
841
842    #[test]
843    fn single_capacity() {
844        let mut deque: StackArrayDeque<i32, 1> = StackArrayDeque::new();
845        assert_eq!(deque.capacity(), 1);
846
847        deque.push_back(1);
848        assert_eq!(deque.len(), 1);
849        assert!(deque.is_full());
850        assert_eq!(deque[0], 1);
851
852        // Pushing another element should overwrite
853        deque.push_back(2);
854        assert_eq!(deque.len(), 1);
855        assert_eq!(deque[0], 2);
856
857        assert_eq!(deque.pop_front(), Some(2));
858        assert!(deque.is_empty());
859    }
860}
array_deque/stack_array_deque.rs

array_deque/
stack_array_deque.rs
