array_deque/
array_deque.rs

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

array_deque/
array_deque.rs
