array_deque/
stack_array_deque.rs

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

array_deque/
stack_array_deque.rs
