arraydeque/lib.rs
1//! A circular buffer with fixed capacity.
2//! Requires Rust 1.59+
3//!
4//! It can be stored directly on the stack if needed.
5//!
6//! This queue has `O(1)` amortized inserts and removals from both ends of the
7//! container. It also has `O(1)` indexing like a vector. The contained elements
8//! are not required to be copyable
9//!
10//! This crate is inspired by [**bluss/arrayvec**](https://github.com/bluss/arrayvec)
11//!
12//! # Feature Flags
13//! The **arraydeque** crate has the following cargo feature flags:
14//!
15//! - `std`
16//! - Optional, enabled by default
17//! - Conversions between `ArrayDeque` and `Vec`
18//! - Use libstd
19//!
20//! # Usage
21//!
22//! First, add the following to your `Cargo.toml`:
23//!
24//! ```toml
25//! [dependencies]
26//! arraydeque = "0.5"
27//! ```
28//!
29//! Next, add this to your crate root:
30//!
31//! ```
32//! extern crate arraydeque;
33//! ```
34//!
35//! Currently arraydeque by default links to the standard library, but if you would
36//! instead like to use arraydeque in a `#![no_std]` situation or crate you can
37//! request this via:
38//!
39//! ```toml
40//! [dependencies]
41//! arraydeque = { version = "0.4", default-features = false }
42//! ```
43//!
44//! # Behaviors
45//!
46//! `ArrayDeque` provides two different behaviors, `Saturating` and `Wrapping`,
47//! determining whether to remove existing element automatically when pushing
48//! to a full deque.
49//!
50//! See the [behavior module documentation](behavior/index.html) for more.
51
52#![cfg_attr(not(any(feature = "std", test)), no_std)]
53#![deny(missing_docs)]
54
55#[cfg(not(any(feature = "std", test)))]
56extern crate core as std;
57
58use std::cmp;
59use std::cmp::Ordering;
60use std::fmt;
61use std::hash::{Hash, Hasher};
62use std::iter::FromIterator;
63use std::marker;
64use std::mem::MaybeUninit;
65use std::ops::Index;
66use std::ops::IndexMut;
67use std::ptr;
68
69use behavior::Behavior;
70
71pub mod behavior;
72mod error;
73mod range;
74
75pub use behavior::{Saturating, Wrapping};
76pub use error::CapacityError;
77pub use range::RangeArgument;
78
79/// A fixed capacity ring buffer.
80///
81/// It can be stored directly on the stack if needed.
82///
83/// The "default" usage of this type as a queue is to use `push_back` to add to
84/// the queue, and `pop_front` to remove from the queue. Iterating over `ArrayDeque` goes front
85/// to back.
86pub struct ArrayDeque<T, const CAP: usize, B: Behavior = Saturating> {
87 xs: MaybeUninit<[T; CAP]>,
88 tail: usize,
89 len: usize,
90 marker: marker::PhantomData<B>,
91}
92
93impl<T, const CAP: usize> ArrayDeque<T, CAP, Saturating> {
94 /// Add an element to the front of the deque.
95 ///
96 /// Return `Ok(())` if the push succeeds, or return `Err(CapacityError { *element* })`
97 /// if the vector is full.
98 ///
99 /// # Examples
100 ///
101 /// ```
102 /// // 1 -(+)-> [_, _, _] => [1, _, _] -> Ok(())
103 /// // 2 -(+)-> [1, _, _] => [2, 1, _] -> Ok(())
104 /// // 3 -(+)-> [2, 1, _] => [3, 2, 1] -> Ok(())
105 /// // 4 -(+)-> [3, 2, 1] => [3, 2, 1] -> Err(CapacityError { element: 4 })
106 ///
107 /// use arraydeque::{ArrayDeque, CapacityError};
108 ///
109 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
110 ///
111 /// buf.push_front(1);
112 /// buf.push_front(2);
113 /// buf.push_front(3);
114 ///
115 /// let overflow = buf.push_front(4);
116 ///
117 /// assert_eq!(overflow, Err(CapacityError { element: 4 }));
118 /// assert_eq!(buf.back(), Some(&1));
119 /// ```
120 pub fn push_front(&mut self, element: T) -> Result<(), CapacityError<T>> {
121 if !self.is_full() {
122 unsafe {
123 self.push_front_unchecked(element);
124 }
125 Ok(())
126 } else {
127 Err(CapacityError { element })
128 }
129 }
130
131 /// Add an element to the back of the deque.
132 ///
133 /// Return `Ok(())` if the push succeeds, or return `Err(CapacityError { *element* })`
134 /// if the vector is full.
135 ///
136 /// # Examples
137 ///
138 /// ```
139 /// // [_, _, _] <-(+)- 1 => [_, _, 1] -> Ok(())
140 /// // [_, _, 1] <-(+)- 2 => [_, 1, 2] -> Ok(())
141 /// // [_, 1, 2] <-(+)- 3 => [1, 2, 3] -> Ok(())
142 /// // [1, 2, 3] <-(+)- 4 => [1, 2, 3] -> Err(CapacityError { element: 4 })
143 ///
144 /// use arraydeque::{ArrayDeque, CapacityError};
145 ///
146 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
147 ///
148 /// buf.push_back(1);
149 /// buf.push_back(2);
150 /// buf.push_back(3);
151 ///
152 /// let overflow = buf.push_back(4);
153 ///
154 /// assert_eq!(overflow, Err(CapacityError { element: 4 }));
155 /// assert_eq!(buf.back(), Some(&3));
156 /// ```
157 pub fn push_back(&mut self, element: T) -> Result<(), CapacityError<T>> {
158 if !self.is_full() {
159 unsafe {
160 self.push_back_unchecked(element);
161 }
162 Ok(())
163 } else {
164 Err(CapacityError { element })
165 }
166 }
167
168 /// Inserts an element at `index` within the `ArrayDeque`. Whichever
169 /// end is closer to the insertion point will be moved to make room,
170 /// and all the affected elements will be moved to new positions.
171 ///
172 /// Return `Ok(())` if the push succeeds, or return `Err(CapacityError { *element* })`
173 /// if the vector is full.
174 ///
175 /// Element at index 0 is the front of the queue.
176 ///
177 /// # Panics
178 ///
179 /// Panics if `index` is greater than `ArrayDeque`'s length
180 ///
181 /// # Examples
182 ///
183 /// ```
184 /// // [_, _, _] <-(#0)- 3 => [3, _, _] -> Ok(())
185 /// // [3, _, _] <-(#0)- 1 => [1, 3, _] -> Ok(())
186 /// // [1, 3, _] <-(#1)- 2 => [1, 2, 3] -> Ok(())
187 /// // [1, 2, 3] <-(#1)- 4 => [1, 2, 3] -> Err(CapacityError { element: 4 })
188 ///
189 /// use arraydeque::{ArrayDeque, CapacityError};
190 ///
191 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
192 ///
193 /// buf.insert(0, 3);
194 /// buf.insert(0, 1);
195 /// buf.insert(1, 2);
196 ///
197 /// let overflow = buf.insert(1, 4);
198 ///
199 /// assert_eq!(overflow, Err(CapacityError { element: 4 }));
200 /// assert_eq!(buf.back(), Some(&3));
201 /// ```
202 #[track_caller]
203 #[inline]
204 pub fn insert(&mut self, index: usize, element: T) -> Result<(), CapacityError<T>> {
205 assert!(index <= self.len(), "index out of bounds");
206
207 if self.is_full() {
208 return Err(CapacityError { element });
209 }
210
211 unsafe {
212 self.insert_unchecked(index, element);
213 }
214
215 Ok(())
216 }
217
218 /// Extend deque from front with the contents of an iterator.
219 ///
220 /// Does not extract more items than there is space for.
221 /// No error occurs if there are more iterator elements.
222 ///
223 /// # Examples
224 ///
225 /// ```
226 /// // [9, 8, 7] -(+)-> [_, _, _, _, _, _, _] => [7, 8, 9, _, _, _, _]
227 /// // [6, 5, 4] -(+)-> [7, 8, 9, _, _, _, _] => [4, 5, 6, 7, 8, 9, _]
228 /// // [3, 2, 1] -(+)-> [4, 5, 6, 7, 8, 9, _] => [3, 4, 5, 6, 7, 8, 9]
229 ///
230 /// use arraydeque::ArrayDeque;
231 ///
232 /// let mut buf: ArrayDeque<_, 7> = ArrayDeque::new();
233 ///
234 /// buf.extend_front([9, 8, 7].into_iter());
235 /// buf.extend_front([6, 5, 4].into_iter());
236 ///
237 /// assert_eq!(buf.len(), 6);
238 ///
239 /// // max capacity reached
240 /// buf.extend_front([3, 2, 1].into_iter());
241 ///
242 /// assert_eq!(buf.len(), 7);
243 /// assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9].into());
244 /// ```
245 #[allow(unused_must_use)]
246 pub fn extend_front<I>(&mut self, iter: I)
247 where
248 I: IntoIterator<Item = T>,
249 {
250 let take = self.capacity() - self.len();
251 for element in iter.into_iter().take(take) {
252 self.push_front(element);
253 }
254 }
255
256 /// Extend deque from back with the contents of an iterator.
257 ///
258 /// Does not extract more items than there is space for.
259 /// No error occurs if there are more iterator elements.
260 ///
261 /// # Examples
262 ///
263 /// ```
264 /// // [_, _, _, _, _, _, _] <-(+)- [1, 2, 3] => [_, _, _, _, 1, 2, 3]
265 /// // [_, _, _, _, 1, 2, 3] <-(+)- [4, 5, 6] => [_, 1, 2, 3, 4, 5, 6]
266 /// // [_, 1, 2, 3, 4, 5, 6] <-(+)- [7, 8, 9] => [1, 2, 3, 4, 5, 6, 7]
267 ///
268 /// use arraydeque::ArrayDeque;
269 ///
270 /// let mut buf: ArrayDeque<_, 7> = ArrayDeque::new();
271 ///
272 /// buf.extend_back([1, 2, 3].into_iter());
273 /// buf.extend_back([4, 5, 6].into_iter());
274 ///
275 /// assert_eq!(buf.len(), 6);
276 ///
277 /// // max capacity reached
278 /// buf.extend_back([7, 8, 9].into_iter());
279 ///
280 /// assert_eq!(buf.len(), 7);
281 /// assert_eq!(buf, [1, 2, 3, 4, 5, 6, 7].into());
282 /// ```
283 #[allow(unused_must_use)]
284 pub fn extend_back<I>(&mut self, iter: I)
285 where
286 I: IntoIterator<Item = T>,
287 {
288 let take = self.capacity() - self.len();
289 for element in iter.into_iter().take(take) {
290 self.push_back(element);
291 }
292 }
293}
294
295#[allow(unused_must_use)]
296impl<T, const CAP: usize> Extend<T> for ArrayDeque<T, CAP, Saturating> {
297 fn extend<I>(&mut self, iter: I)
298 where
299 I: IntoIterator<Item = T>,
300 {
301 self.extend_back(iter);
302 }
303}
304
305impl<T, const CAP: usize> FromIterator<T> for ArrayDeque<T, CAP, Saturating> {
306 fn from_iter<I>(iter: I) -> Self
307 where
308 I: IntoIterator<Item = T>,
309 {
310 let mut array: ArrayDeque<_, CAP, Saturating> = ArrayDeque::new();
311 array.extend_back(iter);
312 array
313 }
314}
315
316impl<T, const CAP: usize> Clone for ArrayDeque<T, CAP, Saturating>
317where
318 T: Clone,
319{
320 fn clone(&self) -> Self {
321 self.iter().cloned().collect()
322 }
323}
324
325impl<T, const CAP: usize> ArrayDeque<T, CAP, Wrapping> {
326 /// Add an element to the front of the deque.
327 ///
328 /// Return `None` if deque still has capacity, or `Some(existing)`
329 /// if the deque is full, where `existing` is the backmost element being kicked out.
330 ///
331 /// # Examples
332 ///
333 /// ```
334 /// // 1 -(+)-> [_, _, _] => [1, _, _] -> None
335 /// // 2 -(+)-> [1, _, _] => [2, 1, _] -> None
336 /// // 3 -(+)-> [2, 1, _] => [3, 2, 1] -> None
337 /// // 4 -(+)-> [3, 2, 1] => [4, 3, 2] -> Some(1)
338 ///
339 /// use arraydeque::{ArrayDeque, Wrapping};
340 ///
341 /// let mut buf: ArrayDeque<_, 3, Wrapping> = ArrayDeque::new();
342 ///
343 /// buf.push_front(1);
344 /// buf.push_front(2);
345 /// buf.push_front(3);
346 ///
347 /// let existing = buf.push_front(4);
348 ///
349 /// assert_eq!(existing, Some(1));
350 /// assert_eq!(buf.back(), Some(&2));
351 /// ```
352 pub fn push_front(&mut self, element: T) -> Option<T> {
353 let existing = if self.is_full() {
354 if self.capacity() == 0 {
355 return Some(element);
356 } else {
357 self.pop_back()
358 }
359 } else {
360 None
361 };
362
363 unsafe {
364 self.push_front_unchecked(element);
365 }
366
367 existing
368 }
369
370 /// Appends an element to the back of a buffer
371 ///
372 /// Return `None` if deque still has capacity, or `Some(existing)`
373 /// if the deque is full, where `existing` is the frontmost element being kicked out.
374 ///
375 /// # Examples
376 ///
377 /// ```
378 /// // [_, _, _] <-(+)- 1 => [_, _, 1] -> None
379 /// // [_, _, 1] <-(+)- 2 => [_, 1, 2] -> None
380 /// // [_, 1, 2] <-(+)- 3 => [1, 2, 3] -> None
381 /// // [1, 2, 3] <-(+)- 4 => [2, 3, 4] -> Some(1)
382 ///
383 /// use arraydeque::{ArrayDeque, Wrapping};
384 ///
385 /// let mut buf: ArrayDeque<_, 3, Wrapping> = ArrayDeque::new();
386 ///
387 /// buf.push_back(1);
388 /// buf.push_back(2);
389 /// buf.push_back(3);
390 ///
391 /// let existing = buf.push_back(4);
392 ///
393 /// assert_eq!(existing, Some(1));
394 /// assert_eq!(buf.back(), Some(&4));
395 /// ```
396 pub fn push_back(&mut self, element: T) -> Option<T> {
397 let existing = if self.is_full() {
398 if self.capacity() == 0 {
399 return Some(element);
400 } else {
401 self.pop_front()
402 }
403 } else {
404 None
405 };
406
407 unsafe {
408 self.push_back_unchecked(element);
409 }
410
411 existing
412 }
413
414 /// Extend deque from front with the contents of an iterator.
415 ///
416 /// Extracts all items from iterator and kicks out the backmost element if necessary.
417 ///
418 /// # Examples
419 ///
420 /// ```
421 /// // [9, 8, 7] -(+)-> [_, _, _, _, _, _, _] => [7, 8, 9, _, _, _, _]
422 /// // [6, 5, 4] -(+)-> [7, 8, 9, _, _, _, _] => [4, 5, 6, 7, 8, 9, _]
423 /// // [3, 2, 1] -(+)-> [4, 5, 6, 7, 8, 9, _] => [1, 2, 3, 4, 5, 6, 7]
424 ///
425 /// use arraydeque::{ArrayDeque, Wrapping};
426 ///
427 /// let mut buf: ArrayDeque<_, 7, Wrapping> = ArrayDeque::new();
428 ///
429 /// buf.extend_front([9, 8, 7].into_iter());
430 /// buf.extend_front([6, 5, 4].into_iter());
431 ///
432 /// assert_eq!(buf.len(), 6);
433 ///
434 /// // max capacity reached
435 /// buf.extend_front([3, 2, 1].into_iter());
436 ///
437 /// assert_eq!(buf.len(), 7);
438 /// assert_eq!(buf, [1, 2, 3, 4, 5, 6, 7].into());
439 /// ```
440 pub fn extend_front<I>(&mut self, iter: I)
441 where
442 I: IntoIterator<Item = T>,
443 {
444 for element in iter.into_iter() {
445 self.push_front(element);
446 }
447 }
448
449 /// Extend deque from back with the contents of an iterator.
450 ///
451 /// Extracts all items from iterator and kicks out the frontmost element if necessary.
452 ///
453 /// # Examples
454 ///
455 /// ```
456 /// // [_, _, _, _, _, _, _] <-(+)- [1, 2, 3] => [_, _, _, _, 1, 2, 3]
457 /// // [_, _, _, _, 1, 2, 3] <-(+)- [4, 5, 6] => [_, 1, 2, 3, 4, 5, 6]
458 /// // [_, 1, 2, 3, 4, 5, 6] <-(+)- [7, 8, 9] => [3, 4, 5, 6, 7, 8, 9]
459 ///
460 /// use arraydeque::{ArrayDeque, Wrapping};
461 ///
462 /// let mut buf: ArrayDeque<_, 7, Wrapping> = ArrayDeque::new();
463 ///
464 /// buf.extend_back([1, 2, 3].into_iter());
465 /// buf.extend_back([4, 5, 6].into_iter());
466 ///
467 /// assert_eq!(buf.len(), 6);
468 ///
469 /// // max capacity reached
470 /// buf.extend_back([7, 8, 9].into_iter());
471 ///
472 /// assert_eq!(buf.len(), 7);
473 /// assert_eq!(buf, [3, 4, 5, 6, 7, 8, 9].into());
474 /// ```
475 pub fn extend_back<I>(&mut self, iter: I)
476 where
477 I: IntoIterator<Item = T>,
478 {
479 for element in iter.into_iter() {
480 self.push_back(element);
481 }
482 }
483}
484
485#[allow(unused_must_use)]
486impl<T, const CAP: usize> Extend<T> for ArrayDeque<T, CAP, Wrapping> {
487 fn extend<I>(&mut self, iter: I)
488 where
489 I: IntoIterator<Item = T>,
490 {
491 let take = self.capacity() - self.len();
492 for elt in iter.into_iter().take(take) {
493 self.push_back(elt);
494 }
495 }
496}
497
498impl<T, const CAP: usize> FromIterator<T> for ArrayDeque<T, CAP, Wrapping> {
499 fn from_iter<I>(iter: I) -> Self
500 where
501 I: IntoIterator<Item = T>,
502 {
503 let mut array: ArrayDeque<_, CAP, Wrapping> = ArrayDeque::new();
504 array.extend_back(iter);
505 array
506 }
507}
508
509impl<T, const CAP: usize> Clone for ArrayDeque<T, CAP, Wrapping>
510where
511 T: Clone,
512{
513 fn clone(&self) -> Self {
514 self.iter().cloned().collect()
515 }
516}
517
518// primitive private methods
519impl<T, const CAP: usize, B: Behavior> ArrayDeque<T, CAP, B> {
520 #[inline]
521 fn wrap_add(index: usize, addend: usize) -> usize {
522 wrap_add(index, addend, CAP)
523 }
524
525 #[inline]
526 fn wrap_sub(index: usize, subtrahend: usize) -> usize {
527 wrap_sub(index, subtrahend, CAP)
528 }
529
530 #[inline]
531 fn ptr(&self) -> *const T {
532 self.xs.as_ptr().cast()
533 }
534
535 #[inline]
536 fn ptr_mut(&mut self) -> *mut T {
537 self.xs.as_mut_ptr().cast()
538 }
539
540 #[inline]
541 fn is_contiguous(&self) -> bool {
542 self.tail() + self.len() < CAP
543 }
544
545 #[inline]
546 fn head(&self) -> usize {
547 let tail = self.tail();
548 let len = self.len();
549 Self::wrap_add(tail, len)
550 }
551
552 #[inline]
553 fn tail(&self) -> usize {
554 self.tail
555 }
556
557 #[inline]
558 unsafe fn set_tail(&mut self, tail: usize) {
559 debug_assert!(tail <= self.capacity());
560 self.tail = tail;
561 }
562
563 #[inline]
564 unsafe fn set_len(&mut self, len: usize) {
565 debug_assert!(len <= self.capacity());
566 self.len = len;
567 }
568
569 #[inline]
570 unsafe fn set_tail_backward(&mut self) {
571 let new_tail = Self::wrap_sub(self.tail(), 1);
572 let new_len = self.len() + 1;
573 self.tail = new_tail;
574 self.len = new_len;
575 }
576
577 #[inline]
578 unsafe fn set_tail_forward(&mut self) {
579 debug_assert!(!self.is_empty());
580
581 let new_tail = Self::wrap_add(self.tail(), 1);
582 let new_len = self.len() - 1;
583 self.tail = new_tail;
584 self.len = new_len;
585 }
586
587 #[inline]
588 unsafe fn set_head_backward(&mut self) {
589 debug_assert!(!self.is_empty());
590
591 let new_len = self.len() - 1;
592 self.len = new_len;
593 }
594
595 #[inline]
596 unsafe fn set_head_forward(&mut self) {
597 debug_assert!(self.len() < CAP);
598
599 let new_len = self.len() + 1;
600 self.len = new_len;
601 }
602
603 #[inline]
604 unsafe fn push_front_unchecked(&mut self, element: T) {
605 debug_assert!(!self.is_full());
606
607 self.set_tail_backward();
608 let tail = self.tail();
609 self.buffer_write(tail, element);
610 }
611
612 #[inline]
613 unsafe fn push_back_unchecked(&mut self, element: T) {
614 debug_assert!(!self.is_full());
615
616 let head = self.head();
617 self.buffer_write(head, element);
618 self.set_head_forward();
619 }
620
621 #[allow(unused_unsafe)]
622 #[inline]
623 unsafe fn insert_unchecked(&mut self, index: usize, element: T) {
624 debug_assert!(!self.is_full());
625
626 // Move the least number of elements in the ring buffer and insert
627 // the given object
628 //
629 // At most len/2 - 1 elements will be moved. O(min(n, n-i))
630 //
631 // There are three main cases:
632 // Elements are contiguous
633 // - special case when tail is 0
634 // Elements are discontiguous and the insert is in the tail section
635 // Elements are discontiguous and the insert is in the head section
636 //
637 // For each of those there are two more cases:
638 // Insert is closer to tail
639 // Insert is closer to head
640 //
641 // Key: H - self.head
642 // T - self.tail
643 // o - Valid element
644 // I - Insertion element
645 // A - The element that should be after the insertion point
646 // M - Indicates element was moved
647
648 let idx = Self::wrap_add(self.tail(), index);
649
650 let distance_to_tail = index;
651 let distance_to_head = self.len() - index;
652
653 let contiguous = self.is_contiguous();
654
655 match (
656 contiguous,
657 distance_to_tail <= distance_to_head,
658 idx >= self.tail(),
659 ) {
660 (true, true, _) if index == 0 => {
661 // push_front
662 //
663 // T
664 // I H
665 // [A o o o o o o . . . . . . . . .]
666 //
667 // H T
668 // [A o o o o o o o . . . . . I]
669 //
670
671 self.set_tail_backward();
672 }
673 (true, true, _) => {
674 unsafe {
675 // contiguous, insert closer to tail:
676 //
677 // T I H
678 // [. . . o o A o o o o . . . . . .]
679 //
680 // T H
681 // [. . o o I A o o o o . . . . . .]
682 // M M
683 //
684 // contiguous, insert closer to tail and tail is 0:
685 //
686 //
687 // T I H
688 // [o o A o o o o . . . . . . . . .]
689 //
690 // H T
691 // [o I A o o o o o . . . . . . . o]
692 // M M
693
694 let tail = self.tail();
695 let new_tail = Self::wrap_sub(self.tail(), 1);
696
697 self.copy(new_tail, tail, 1);
698 // Already moved the tail, so we only copy `index - 1` elements.
699 self.copy(tail, tail + 1, index - 1);
700
701 self.set_tail_backward();
702 }
703 }
704 (true, false, _) => {
705 unsafe {
706 // contiguous, insert closer to head:
707 //
708 // T I H
709 // [. . . o o o o A o o . . . . . .]
710 //
711 // T H
712 // [. . . o o o o I A o o . . . . .]
713 // M M M
714
715 let head = self.head();
716 self.copy(idx + 1, idx, head - idx);
717
718 self.set_head_forward();
719 }
720 }
721 (false, true, true) => {
722 unsafe {
723 // discontiguous, insert closer to tail, tail section:
724 //
725 // H T I
726 // [o o o o o o . . . . . o o A o o]
727 //
728 // H T
729 // [o o o o o o . . . . o o I A o o]
730 // M M
731
732 let tail = self.tail();
733 self.copy(tail - 1, tail, index);
734
735 self.set_tail_backward();
736 }
737 }
738 (false, false, true) => {
739 unsafe {
740 // discontiguous, insert closer to head, tail section:
741 //
742 // H T I
743 // [o o . . . . . . . o o o o o A o]
744 //
745 // H T
746 // [o o o . . . . . . o o o o o I A]
747 // M M M M
748
749 // copy elements up to new head
750 let head = self.head();
751 self.copy(1, 0, head);
752
753 // copy last element into empty spot at bottom of buffer
754 self.copy(0, CAP - 1, 1);
755
756 // move elements from idx to end forward not including ^ element
757 self.copy(idx + 1, idx, CAP - 1 - idx);
758
759 self.set_head_forward();
760 }
761 }
762 (false, true, false) if idx == 0 => {
763 unsafe {
764 // discontiguous, insert is closer to tail, head section,
765 // and is at index zero in the internal buffer:
766 //
767 // I H T
768 // [A o o o o o o o o o . . . o o o]
769 //
770 // H T
771 // [A o o o o o o o o o . . o o o I]
772 // M M M
773
774 // copy elements up to new tail
775 let tail = self.tail();
776 self.copy(tail - 1, tail, CAP - tail);
777
778 // copy last element into empty spot at bottom of buffer
779 self.copy(CAP - 1, 0, 1);
780
781 self.set_tail_backward();
782 }
783 }
784 (false, true, false) => {
785 unsafe {
786 // discontiguous, insert closer to tail, head section:
787 //
788 // I H T
789 // [o o o A o o o o o o . . . o o o]
790 //
791 // H T
792 // [o o I A o o o o o o . . o o o o]
793 // M M M M M M
794
795 let tail = self.tail();
796 // copy elements up to new tail
797 self.copy(tail - 1, tail, CAP - tail);
798
799 // copy last element into empty spot at bottom of buffer
800 self.copy(CAP - 1, 0, 1);
801
802 // move elements from idx-1 to end forward not including ^ element
803 self.copy(0, 1, idx - 1);
804
805 self.set_tail_backward();
806 }
807 }
808 (false, false, false) => {
809 unsafe {
810 // discontiguous, insert closer to head, head section:
811 //
812 // I H T
813 // [o o o o A o o . . . . . . o o o]
814 //
815 // H T
816 // [o o o o I A o o . . . . . o o o]
817 // M M M
818
819 let head = self.head();
820 self.copy(idx + 1, idx, head - idx);
821
822 self.set_head_forward();
823 }
824 }
825 }
826
827 // tail might've been changed so we need to recalculate
828 let new_idx = Self::wrap_add(self.tail(), index);
829 unsafe {
830 self.buffer_write(new_idx, element);
831 }
832 }
833
834 /// Copies a contiguous block of memory len long from src to dst
835 #[inline]
836 unsafe fn copy(&mut self, dst: usize, src: usize, len: usize) {
837 debug_assert!(
838 dst + len <= CAP,
839 "cpy dst={} src={} len={} cap={}",
840 dst,
841 src,
842 len,
843 CAP
844 );
845 debug_assert!(
846 src + len <= CAP,
847 "cpy dst={} src={} len={} cap={}",
848 dst,
849 src,
850 len,
851 CAP
852 );
853 let xs = self.ptr_mut();
854 ptr::copy(xs.add(src), xs.add(dst), len);
855 }
856
857 /// Copies a potentially wrapping block of memory len long from src to dest.
858 /// (abs(dst - src) + len) must be no larger than cap() (There must be at
859 /// most one continuous overlapping region between src and dest).
860 unsafe fn wrap_copy(&mut self, dst: usize, src: usize, len: usize) {
861 #[allow(dead_code)]
862 fn diff(a: usize, b: usize) -> usize {
863 if a <= b {
864 b - a
865 } else {
866 a - b
867 }
868 }
869 debug_assert!(
870 cmp::min(diff(dst, src), CAP - diff(dst, src)) + len <= CAP,
871 "wrc dst={} src={} len={} cap={}",
872 dst,
873 src,
874 len,
875 CAP
876 );
877
878 if src == dst || len == 0 {
879 return;
880 }
881
882 let dst_after_src = Self::wrap_sub(dst, src) < len;
883
884 let src_pre_wrap_len = CAP - src;
885 let dst_pre_wrap_len = CAP - dst;
886 let src_wraps = src_pre_wrap_len < len;
887 let dst_wraps = dst_pre_wrap_len < len;
888
889 match (dst_after_src, src_wraps, dst_wraps) {
890 (_, false, false) => {
891 // src doesn't wrap, dst doesn't wrap
892 //
893 // S . . .
894 // 1 [_ _ A A B B C C _]
895 // 2 [_ _ A A A A B B _]
896 // D . . .
897 //
898 self.copy(dst, src, len);
899 }
900 (false, false, true) => {
901 // dst before src, src doesn't wrap, dst wraps
902 //
903 // S . . .
904 // 1 [A A B B _ _ _ C C]
905 // 2 [A A B B _ _ _ A A]
906 // 3 [B B B B _ _ _ A A]
907 // . . D .
908 //
909 self.copy(dst, src, dst_pre_wrap_len);
910 self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len);
911 }
912 (true, false, true) => {
913 // src before dst, src doesn't wrap, dst wraps
914 //
915 // S . . .
916 // 1 [C C _ _ _ A A B B]
917 // 2 [B B _ _ _ A A B B]
918 // 3 [B B _ _ _ A A A A]
919 // . . D .
920 //
921 self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len);
922 self.copy(dst, src, dst_pre_wrap_len);
923 }
924 (false, true, false) => {
925 // dst before src, src wraps, dst doesn't wrap
926 //
927 // . . S .
928 // 1 [C C _ _ _ A A B B]
929 // 2 [C C _ _ _ B B B B]
930 // 3 [C C _ _ _ B B C C]
931 // D . . .
932 //
933 self.copy(dst, src, src_pre_wrap_len);
934 self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len);
935 }
936 (true, true, false) => {
937 // src before dst, src wraps, dst doesn't wrap
938 //
939 // . . S .
940 // 1 [A A B B _ _ _ C C]
941 // 2 [A A A A _ _ _ C C]
942 // 3 [C C A A _ _ _ C C]
943 // D . . .
944 //
945 self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len);
946 self.copy(dst, src, src_pre_wrap_len);
947 }
948 (false, true, true) => {
949 // dst before src, src wraps, dst wraps
950 //
951 // . . . S .
952 // 1 [A B C D _ E F G H]
953 // 2 [A B C D _ E G H H]
954 // 3 [A B C D _ E G H A]
955 // 4 [B C C D _ E G H A]
956 // . . D . .
957 //
958 debug_assert!(dst_pre_wrap_len > src_pre_wrap_len);
959 let delta = dst_pre_wrap_len - src_pre_wrap_len;
960 self.copy(dst, src, src_pre_wrap_len);
961 self.copy(dst + src_pre_wrap_len, 0, delta);
962 self.copy(0, delta, len - dst_pre_wrap_len);
963 }
964 (true, true, true) => {
965 // src before dst, src wraps, dst wraps
966 //
967 // . . S . .
968 // 1 [A B C D _ E F G H]
969 // 2 [A A B D _ E F G H]
970 // 3 [H A B D _ E F G H]
971 // 4 [H A B D _ E F F G]
972 // . . . D .
973 //
974 debug_assert!(src_pre_wrap_len > dst_pre_wrap_len);
975 let delta = src_pre_wrap_len - dst_pre_wrap_len;
976 self.copy(delta, 0, len - src_pre_wrap_len);
977 self.copy(0, CAP - delta, delta);
978 self.copy(dst, src, dst_pre_wrap_len);
979 }
980 }
981 }
982
983 #[inline]
984 unsafe fn buffer_read(&mut self, offset: usize) -> T {
985 ptr::read(self.ptr().add(offset))
986 }
987
988 #[inline]
989 unsafe fn buffer_write(&mut self, offset: usize, element: T) {
990 ptr::write(self.ptr_mut().add(offset), element);
991 }
992}
993
994impl<T, const CAP: usize, B: Behavior> ArrayDeque<T, CAP, B> {
995 /// Creates an empty `ArrayDeque`.
996 ///
997 /// # Examples
998 ///
999 /// ```
1000 /// use arraydeque::ArrayDeque;
1001 ///
1002 /// let buf: ArrayDeque<usize, 2> = ArrayDeque::new();
1003 /// ```
1004 #[inline]
1005 pub const fn new() -> ArrayDeque<T, CAP, B> {
1006 ArrayDeque {
1007 xs: MaybeUninit::uninit(),
1008 tail: 0,
1009 len: 0,
1010 marker: marker::PhantomData,
1011 }
1012 }
1013
1014 /// Return the capacity of the `ArrayDeque`.
1015 ///
1016 /// # Examples
1017 ///
1018 /// ```
1019 /// use arraydeque::ArrayDeque;
1020 ///
1021 /// let buf: ArrayDeque<usize, 2> = ArrayDeque::new();
1022 ///
1023 /// assert_eq!(buf.capacity(), 2);
1024 /// ```
1025 #[inline]
1026 pub const fn capacity(&self) -> usize {
1027 CAP
1028 }
1029
1030 /// Returns the number of elements in the `ArrayDeque`.
1031 ///
1032 /// # Examples
1033 ///
1034 /// ```
1035 /// use arraydeque::ArrayDeque;
1036 ///
1037 /// let mut buf: ArrayDeque<_, 1> = ArrayDeque::new();
1038 ///
1039 /// assert_eq!(buf.len(), 0);
1040 ///
1041 /// buf.push_back(1);
1042 ///
1043 /// assert_eq!(buf.len(), 1);
1044 /// ```
1045 #[inline]
1046 pub fn len(&self) -> usize {
1047 self.len
1048 }
1049
1050 /// Returns true if the buffer contains no elements
1051 ///
1052 /// # Examples
1053 ///
1054 /// ```
1055 /// use arraydeque::ArrayDeque;
1056 ///
1057 /// let mut buf: ArrayDeque<_, 1> = ArrayDeque::new();
1058 ///
1059 /// assert!(buf.is_empty());
1060 ///
1061 /// buf.push_back(1);
1062 ///
1063 /// assert!(!buf.is_empty());
1064 /// ```
1065 #[inline]
1066 pub fn is_empty(&self) -> bool {
1067 self.len() == 0
1068 }
1069
1070 /// Entire capacity of the underlying storage
1071 pub fn as_uninit_slice(&self) -> &[MaybeUninit<T>] {
1072 unsafe { std::slice::from_raw_parts(self.xs.as_ptr().cast(), CAP) }
1073 }
1074
1075 /// Entire capacity of the underlying storage
1076 pub fn as_uninit_slice_mut(&mut self) -> &mut [MaybeUninit<T>] {
1077 unsafe { std::slice::from_raw_parts_mut(self.xs.as_mut_ptr().cast(), CAP) }
1078 }
1079
1080 /// Returns true if the buffer is full.
1081 ///
1082 /// # Examples
1083 ///
1084 /// ```
1085 /// use arraydeque::ArrayDeque;
1086 ///
1087 /// let mut buf: ArrayDeque<_, 1> = ArrayDeque::new();
1088 ///
1089 /// assert!(!buf.is_full());
1090 ///
1091 /// buf.push_back(1);
1092 ///
1093 /// assert!(buf.is_full());
1094 /// ```
1095 #[inline]
1096 pub fn is_full(&self) -> bool {
1097 self.len() == self.capacity()
1098 }
1099
1100 /// Returns `true` if the `ArrayDeque` contains an element equal to the
1101 /// given value.
1102 ///
1103 /// # Examples
1104 ///
1105 /// ```
1106 /// use arraydeque::ArrayDeque;
1107 ///
1108 /// let mut buf: ArrayDeque<_, 2> = ArrayDeque::new();
1109 ///
1110 /// buf.push_back(1);
1111 /// buf.push_back(2);
1112 ///
1113 /// assert_eq!(buf.contains(&1), true);
1114 /// assert_eq!(buf.contains(&3), false);
1115 /// ```
1116 pub fn contains(&self, x: &T) -> bool
1117 where
1118 T: PartialEq<T>,
1119 {
1120 let (a, b) = self.as_slices();
1121 a.contains(x) || b.contains(x)
1122 }
1123
1124 /// Provides a reference to the front element, or `None` if the sequence is
1125 /// empty.
1126 ///
1127 /// # Examples
1128 ///
1129 /// ```
1130 /// use arraydeque::ArrayDeque;
1131 ///
1132 /// let mut buf: ArrayDeque<_, 2> = ArrayDeque::new();
1133 /// assert_eq!(buf.front(), None);
1134 ///
1135 /// buf.push_back(1);
1136 /// buf.push_back(2);
1137 ///
1138 /// assert_eq!(buf.front(), Some(&1));
1139 /// ```
1140 pub fn front(&self) -> Option<&T> {
1141 if !self.is_empty() {
1142 Some(&self[0])
1143 } else {
1144 None
1145 }
1146 }
1147
1148 /// Provides a mutable reference to the front element, or `None` if the
1149 /// sequence is empty.
1150 ///
1151 /// # Examples
1152 ///
1153 /// ```
1154 /// use arraydeque::ArrayDeque;
1155 ///
1156 /// let mut buf: ArrayDeque<_, 2> = ArrayDeque::new();
1157 /// assert_eq!(buf.front_mut(), None);
1158 ///
1159 /// buf.push_back(1);
1160 /// buf.push_back(2);
1161 ///
1162 /// assert_eq!(buf.front_mut(), Some(&mut 1));
1163 /// ```
1164 pub fn front_mut(&mut self) -> Option<&mut T> {
1165 if !self.is_empty() {
1166 Some(&mut self[0])
1167 } else {
1168 None
1169 }
1170 }
1171
1172 /// Provides a reference to the back element, or `None` if the sequence is
1173 /// empty.
1174 ///
1175 /// # Examples
1176 ///
1177 /// ```
1178 /// use arraydeque::ArrayDeque;
1179 ///
1180 /// let mut buf: ArrayDeque<_, 2> = ArrayDeque::new();
1181 ///
1182 /// buf.push_back(1);
1183 /// buf.push_back(2);
1184 ///
1185 /// assert_eq!(buf.back(), Some(&2));
1186 /// ```
1187 pub fn back(&self) -> Option<&T> {
1188 if !self.is_empty() {
1189 Some(&self[self.len() - 1])
1190 } else {
1191 None
1192 }
1193 }
1194
1195 /// Provides a mutable reference to the back element, or `None` if the
1196 /// sequence is empty.
1197 ///
1198 /// # Examples
1199 ///
1200 /// ```
1201 /// use arraydeque::ArrayDeque;
1202 ///
1203 /// let mut buf: ArrayDeque<_, 2> = ArrayDeque::new();
1204 ///
1205 /// buf.push_back(1);
1206 /// buf.push_back(2);
1207 ///
1208 /// assert_eq!(buf.back_mut(), Some(&mut 2));
1209 /// ```
1210 pub fn back_mut(&mut self) -> Option<&mut T> {
1211 let len = self.len();
1212 if !self.is_empty() {
1213 Some(&mut self[len - 1])
1214 } else {
1215 None
1216 }
1217 }
1218
1219 /// Retrieves an element in the `ArrayDeque` by index.
1220 ///
1221 /// Element at index 0 is the front of the queue.
1222 ///
1223 /// # Examples
1224 ///
1225 /// ```
1226 /// use arraydeque::ArrayDeque;
1227 ///
1228 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
1229 ///
1230 /// buf.push_back(0);
1231 /// buf.push_back(1);
1232 /// buf.push_back(2);
1233 ///
1234 /// assert_eq!(buf.get(1), Some(&1));
1235 /// ```
1236 #[inline]
1237 pub fn get(&self, index: usize) -> Option<&T> {
1238 if index < self.len() {
1239 let idx = Self::wrap_add(self.tail(), index);
1240 unsafe { Some(&*self.ptr().add(idx)) }
1241 } else {
1242 None
1243 }
1244 }
1245
1246 /// Retrieves an element in the `ArrayDeque` mutably by index.
1247 ///
1248 /// Element at index 0 is the front of the queue.
1249 ///
1250 /// # Examples
1251 ///
1252 /// ```
1253 /// use arraydeque::ArrayDeque;
1254 ///
1255 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
1256 ///
1257 /// buf.push_back(0);
1258 /// buf.push_back(1);
1259 /// buf.push_back(2);
1260 ///
1261 /// assert_eq!(buf.get_mut(1), Some(&mut 1));
1262 /// ```
1263 #[inline]
1264 pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
1265 if index < self.len() {
1266 let idx = Self::wrap_add(self.tail(), index);
1267 unsafe { Some(&mut *self.ptr_mut().add(idx)) }
1268 } else {
1269 None
1270 }
1271 }
1272
1273 /// Returns a front-to-back iterator.
1274 ///
1275 /// # Examples
1276 ///
1277 /// ```
1278 /// use arraydeque::ArrayDeque;
1279 ///
1280 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
1281 ///
1282 /// buf.push_back(0);
1283 /// buf.push_back(1);
1284 /// buf.push_back(2);
1285 ///
1286 /// let expected = [0, 1, 2];
1287 ///
1288 /// assert!(buf.iter().eq(expected.iter()));
1289 /// ```
1290 #[inline]
1291 pub fn iter(&self) -> Iter<T> {
1292 Iter {
1293 tail: self.tail(),
1294 len: self.len(),
1295 ring: self.as_uninit_slice(),
1296 }
1297 }
1298
1299 /// Returns a front-to-back iterator that returns mutable references.
1300 ///
1301 /// # Examples
1302 ///
1303 /// ```
1304 /// use arraydeque::ArrayDeque;
1305 ///
1306 /// let mut buf: ArrayDeque<usize, 3> = ArrayDeque::new();
1307 ///
1308 /// buf.push_back(0);
1309 /// buf.push_back(1);
1310 /// buf.push_back(2);
1311 ///
1312 /// let mut expected = [0, 1, 2];
1313 ///
1314 /// assert!(buf.iter_mut().eq(expected.iter_mut()));
1315 /// ```
1316 #[inline]
1317 pub fn iter_mut(&mut self) -> IterMut<T> {
1318 IterMut {
1319 tail: self.tail(),
1320 len: self.len(),
1321 ring: self.as_uninit_slice_mut(),
1322 }
1323 }
1324
1325 /// Make the buffer contiguous
1326 ///
1327 /// The linearization may be required when interacting with external
1328 /// interfaces requiring contiguous slices.
1329 ///
1330 /// # Examples
1331 ///
1332 /// ```
1333 /// use arraydeque::ArrayDeque;
1334 ///
1335 /// let mut buf: ArrayDeque<isize, 10> = ArrayDeque::new();
1336 /// buf.extend_back([1, 2, 3]);
1337 /// buf.extend_front([-1, -2, -3]);
1338 ///
1339 /// buf.linearize();
1340 ///
1341 /// assert_eq!(buf.as_slices().1.len(), 0);
1342 /// ```
1343 ///
1344 /// # Complexity
1345 ///
1346 /// Takes `O(len())` time and no extra space.
1347 pub fn linearize(&mut self) {
1348 if self.is_contiguous() {
1349 return;
1350 }
1351
1352 let tail = self.tail();
1353 let len = self.len();
1354 let mut new_tail = tail;
1355 let mut dst: usize = 0;
1356
1357 while dst < len {
1358 let mut src = new_tail;
1359
1360 while src < CAP && dst < len {
1361 if dst == new_tail {
1362 new_tail = src;
1363 }
1364
1365 let xs = self.ptr_mut();
1366 unsafe {
1367 ptr::swap(xs.add(dst), xs.add(src));
1368 }
1369
1370 dst += 1;
1371 src += 1;
1372 }
1373 }
1374
1375 unsafe {
1376 self.set_tail(0);
1377 }
1378 }
1379
1380 /// Removes the first element and returns it, or `None` if the sequence is
1381 /// empty.
1382 ///
1383 /// # Examples
1384 ///
1385 /// ```
1386 /// use arraydeque::ArrayDeque;
1387 ///
1388 /// let mut buf: ArrayDeque<_, 2> = ArrayDeque::new();
1389 ///
1390 /// buf.push_back(1);
1391 /// buf.push_back(2);
1392 ///
1393 /// assert_eq!(buf.pop_front(), Some(1));
1394 /// assert_eq!(buf.pop_front(), Some(2));
1395 /// assert_eq!(buf.pop_front(), None);
1396 /// ```
1397 pub fn pop_front(&mut self) -> Option<T> {
1398 if self.is_empty() {
1399 return None;
1400 }
1401 unsafe {
1402 let tail = self.tail();
1403 self.set_tail_forward();
1404 Some(self.buffer_read(tail))
1405 }
1406 }
1407
1408 /// Removes the last element from a buffer and returns it, or `None` if
1409 /// it is empty.
1410 ///
1411 /// # Examples
1412 ///
1413 /// ```
1414 /// use arraydeque::ArrayDeque;
1415 ///
1416 /// let mut buf: ArrayDeque<_, 2> = ArrayDeque::new();
1417 /// assert_eq!(buf.pop_back(), None);
1418 ///
1419 /// buf.push_back(1);
1420 /// buf.push_back(2);
1421 ///
1422 /// assert_eq!(buf.pop_back(), Some(2));
1423 /// assert_eq!(buf.pop_back(), Some(1));
1424 /// ```
1425 pub fn pop_back(&mut self) -> Option<T> {
1426 if self.is_empty() {
1427 return None;
1428 }
1429 unsafe {
1430 self.set_head_backward();
1431 let head = self.head();
1432 Some(self.buffer_read(head))
1433 }
1434 }
1435
1436 /// Clears the buffer, removing all values.
1437 ///
1438 /// # Examples
1439 ///
1440 /// ```
1441 /// use arraydeque::ArrayDeque;
1442 ///
1443 /// let mut buf: ArrayDeque<_, 1> = ArrayDeque::new();
1444 ///
1445 /// buf.push_back(1);
1446 /// buf.clear();
1447 ///
1448 /// assert!(buf.is_empty());
1449 /// ```
1450 #[inline]
1451 pub fn clear(&mut self) {
1452 self.drain(..);
1453 }
1454
1455 /// Create a draining iterator that removes the specified range in the
1456 /// `ArrayDeque` and yields the removed items.
1457 ///
1458 /// Note 1: The element range is removed even if the iterator is not
1459 /// consumed until the end.
1460 ///
1461 /// Note 2: It is unspecified how many elements are removed from the deque,
1462 /// if the `Drain` value is not dropped, but the borrow it holds expires
1463 /// (eg. due to mem::forget).
1464 ///
1465 /// # Panics
1466 ///
1467 /// Panics if the starting point is greater than the end point or if
1468 /// the end point is greater than the length of the deque.
1469 ///
1470 /// # Examples
1471 ///
1472 /// ```
1473 /// use arraydeque::ArrayDeque;
1474 ///
1475 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
1476 ///
1477 /// buf.push_back(0);
1478 /// buf.push_back(1);
1479 /// buf.push_back(2);
1480 ///
1481 /// {
1482 /// let drain = buf.drain(2..);
1483 /// assert!([2].into_iter().eq(drain));
1484 /// }
1485 ///
1486 /// {
1487 /// let iter = buf.iter();
1488 /// assert!([0, 1].iter().eq(iter));
1489 /// }
1490 ///
1491 /// // A full range clears all contents
1492 /// buf.drain(..);
1493 /// assert!(buf.is_empty());
1494 /// ```
1495 #[track_caller]
1496 #[inline]
1497 pub fn drain<R>(&mut self, range: R) -> Drain<T, CAP, B>
1498 where
1499 R: RangeArgument<usize>,
1500 {
1501 let len = self.len();
1502 let start = range.start().unwrap_or(0);
1503 let end = range.end().unwrap_or(len);
1504 assert!(start <= end, "drain lower bound was too large");
1505 assert!(end <= len, "drain upper bound was too large");
1506
1507 let drain_tail = Self::wrap_add(self.tail(), start);
1508 let drain_head = Self::wrap_add(self.tail(), end);
1509 let drain_len = end - start;
1510
1511 unsafe { self.set_len(start) }
1512
1513 Drain {
1514 deque: self as *mut _,
1515 after_tail: drain_head,
1516 after_len: len - end,
1517 iter: Iter {
1518 tail: drain_tail,
1519 len: drain_len,
1520 ring: self.as_uninit_slice_mut(),
1521 },
1522 }
1523 }
1524
1525 /// Swaps elements at indices `i` and `j`.
1526 ///
1527 /// `i` and `j` may be equal.
1528 ///
1529 /// Fails if there is no element with either index.
1530 ///
1531 /// Element at index 0 is the front of the queue.
1532 ///
1533 /// # Examples
1534 ///
1535 /// ```
1536 /// use arraydeque::ArrayDeque;
1537 ///
1538 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
1539 ///
1540 /// buf.push_back(0);
1541 /// buf.push_back(1);
1542 /// buf.push_back(2);
1543 ///
1544 /// buf.swap(0, 2);
1545 ///
1546 /// assert_eq!(buf, [2, 1, 0].into());
1547 /// ```
1548 #[track_caller]
1549 #[inline]
1550 pub fn swap(&mut self, i: usize, j: usize) {
1551 assert!(i < self.len());
1552 assert!(j < self.len());
1553 let ri = Self::wrap_add(self.tail(), i);
1554 let rj = Self::wrap_add(self.tail(), j);
1555 let xs = self.ptr_mut();
1556 unsafe { ptr::swap(xs.add(ri), xs.add(rj)) }
1557 }
1558
1559 /// Removes an element from anywhere in the `ArrayDeque` and returns it, replacing it with the
1560 /// last element.
1561 ///
1562 /// This does not preserve ordering, but is O(1).
1563 ///
1564 /// Returns `None` if `index` is out of bounds.
1565 ///
1566 /// Element at index 0 is the front of the queue.
1567 ///
1568 /// # Examples
1569 ///
1570 /// ```
1571 /// use arraydeque::ArrayDeque;
1572 ///
1573 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
1574 /// assert_eq!(buf.swap_remove_back(0), None);
1575 ///
1576 /// buf.push_back(0);
1577 /// buf.push_back(1);
1578 /// buf.push_back(2);
1579 ///
1580 /// assert_eq!(buf.swap_remove_back(0), Some(0));
1581 /// assert_eq!(buf, [2, 1].into());
1582 /// ```
1583 pub fn swap_remove_back(&mut self, index: usize) -> Option<T> {
1584 let length = self.len();
1585 if length > 0 && index < length - 1 {
1586 self.swap(index, length - 1);
1587 } else if index >= length {
1588 return None;
1589 }
1590 self.pop_back()
1591 }
1592
1593 /// Removes an element from anywhere in the `ArrayDeque` and returns it,
1594 /// replacing it with the first element.
1595 ///
1596 /// This does not preserve ordering, but is O(1).
1597 ///
1598 /// Returns `None` if `index` is out of bounds.
1599 ///
1600 /// Element at index 0 is the front of the queue.
1601 ///
1602 /// # Examples
1603 ///
1604 /// ```
1605 /// use arraydeque::ArrayDeque;
1606 ///
1607 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
1608 /// assert_eq!(buf.swap_remove_back(0), None);
1609 ///
1610 /// buf.push_back(0);
1611 /// buf.push_back(1);
1612 /// buf.push_back(2);
1613 ///
1614 /// assert_eq!(buf.swap_remove_front(2), Some(2));
1615 /// assert_eq!(buf, [1, 0].into());
1616 /// ```
1617 pub fn swap_remove_front(&mut self, index: usize) -> Option<T> {
1618 let length = self.len();
1619 if length > 0 && index < length && index != 0 {
1620 self.swap(index, 0);
1621 } else if index >= length {
1622 return None;
1623 }
1624 self.pop_front()
1625 }
1626
1627 /// Removes and returns the element at `index` from the `ArrayDeque`.
1628 /// Whichever end is closer to the removal point will be moved to make
1629 /// room, and all the affected elements will be moved to new positions.
1630 /// Returns `None` if `index` is out of bounds.
1631 ///
1632 /// Element at index 0 is the front of the queue.
1633 ///
1634 /// # Examples
1635 ///
1636 /// ```
1637 /// use arraydeque::ArrayDeque;
1638 ///
1639 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
1640 ///
1641 /// buf.push_back(0);
1642 /// buf.push_back(1);
1643 /// buf.push_back(2);
1644 ///
1645 /// assert_eq!(buf.remove(1), Some(1));
1646 /// assert_eq!(buf, [0, 2].into());
1647 /// ```
1648 pub fn remove(&mut self, index: usize) -> Option<T> {
1649 if self.is_empty() || self.len() <= index {
1650 return None;
1651 }
1652
1653 // There are three main cases:
1654 // Elements are contiguous
1655 // Elements are discontiguous and the removal is in the tail section
1656 // Elements are discontiguous and the removal is in the head section
1657 // - special case when elements are technically contiguous,
1658 // but self.head = 0
1659 //
1660 // For each of those there are two more cases:
1661 // Insert is closer to tail
1662 // Insert is closer to head
1663 //
1664 // Key: H - self.head
1665 // T - self.tail
1666 // o - Valid element
1667 // x - Element marked for removal
1668 // R - Indicates element that is being removed
1669 // M - Indicates element was moved
1670
1671 let idx = Self::wrap_add(self.tail(), index);
1672
1673 let elem = unsafe { Some(self.buffer_read(idx)) };
1674
1675 let distance_to_tail = index;
1676 let distance_to_head = self.len() - index;
1677
1678 let contiguous = self.is_contiguous();
1679
1680 match (
1681 contiguous,
1682 distance_to_tail <= distance_to_head,
1683 idx >= self.tail(),
1684 ) {
1685 (true, true, _) => {
1686 unsafe {
1687 // contiguous, remove closer to tail:
1688 //
1689 // T R H
1690 // [. . . o o x o o o o . . . . . .]
1691 //
1692 // T H
1693 // [. . . . o o o o o o . . . . . .]
1694 // M M
1695
1696 let tail = self.tail();
1697 self.copy(tail + 1, tail, index);
1698 self.set_tail_forward();
1699 }
1700 }
1701 (true, false, _) => {
1702 unsafe {
1703 // contiguous, remove closer to head:
1704 //
1705 // T R H
1706 // [. . . o o o o x o o . . . . . .]
1707 //
1708 // T H
1709 // [. . . o o o o o o . . . . . . .]
1710 // M M
1711
1712 let head = self.head();
1713 self.copy(idx, idx + 1, head - idx - 1);
1714 self.set_head_backward();
1715 }
1716 }
1717 (false, true, true) => {
1718 unsafe {
1719 // discontiguous, remove closer to tail, tail section:
1720 //
1721 // H T R
1722 // [o o o o o o . . . . . o o x o o]
1723 //
1724 // H T
1725 // [o o o o o o . . . . . . o o o o]
1726 // M M
1727
1728 let tail = self.tail();
1729 self.copy(tail + 1, tail, index);
1730 self.set_tail_forward();
1731 }
1732 }
1733 (false, false, false) => {
1734 unsafe {
1735 // discontiguous, remove closer to head, head section:
1736 //
1737 // R H T
1738 // [o o o o x o o . . . . . . o o o]
1739 //
1740 // H T
1741 // [o o o o o o . . . . . . . o o o]
1742 // M M
1743
1744 let head = self.head();
1745 self.copy(idx, idx + 1, head - idx - 1);
1746 self.set_head_backward();
1747 }
1748 }
1749 (false, false, true) => {
1750 unsafe {
1751 // discontiguous, remove closer to head, tail section:
1752 //
1753 // H T R
1754 // [o o o . . . . . . o o o o o x o]
1755 //
1756 // H T
1757 // [o o . . . . . . . o o o o o o o]
1758 // M M M M
1759 //
1760 // or quasi-discontiguous, remove next to head, tail section:
1761 //
1762 // H T R
1763 // [. . . . . . . . . o o o o o x o]
1764 //
1765 // T H
1766 // [. . . . . . . . . o o o o o o .]
1767 // M
1768
1769 // draw in elements in the tail section
1770 self.copy(idx, idx + 1, CAP - idx - 1);
1771
1772 // Prevents underflow.
1773 if self.head() != 0 {
1774 // copy first element into empty spot
1775 self.copy(CAP - 1, 0, 1);
1776
1777 // move elements in the head section backwards
1778 let head = self.head();
1779 self.copy(0, 1, head - 1);
1780 }
1781
1782 self.set_head_backward();
1783 }
1784 }
1785 (false, true, false) => {
1786 unsafe {
1787 // discontiguous, remove closer to tail, head section:
1788 //
1789 // R H T
1790 // [o o x o o o o o o o . . . o o o]
1791 //
1792 // H T
1793 // [o o o o o o o o o o . . . . o o]
1794 // M M M M M
1795
1796 let tail = self.tail();
1797 // draw in elements up to idx
1798 self.copy(1, 0, idx);
1799
1800 // copy last element into empty spot
1801 self.copy(0, CAP - 1, 1);
1802
1803 // move elements from tail to end forward, excluding the last one
1804 self.copy(tail + 1, tail, CAP - tail - 1);
1805
1806 self.set_tail_forward();
1807 }
1808 }
1809 }
1810
1811 elem
1812 }
1813
1814 /// Splits the collection into two at the given index.
1815 ///
1816 /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
1817 /// and the returned `Self` contains elements `[at, len)`.
1818 ///
1819 /// Element at index 0 is the front of the queue.
1820 ///
1821 /// # Panics
1822 ///
1823 /// Panics if `at > len`
1824 ///
1825 /// # Examples
1826 ///
1827 /// ```
1828 /// use arraydeque::ArrayDeque;
1829 ///
1830 /// let mut buf: ArrayDeque<_, 3> = ArrayDeque::new();
1831 ///
1832 /// buf.push_back(0);
1833 /// buf.push_back(1);
1834 /// buf.push_back(2);
1835 ///
1836 /// // buf = [0], buf2 = [1, 2]
1837 /// let buf2 = buf.split_off(1);
1838 ///
1839 /// assert_eq!(buf.len(), 1);
1840 /// assert_eq!(buf2.len(), 2);
1841 /// ```
1842 #[track_caller]
1843 #[inline]
1844 pub fn split_off(&mut self, at: usize) -> Self {
1845 let len = self.len();
1846 assert!(at <= len, "`at` out of bounds");
1847
1848 let other_len = len - at;
1849 let mut other = Self::new();
1850
1851 unsafe {
1852 let (first_half, second_half) = self.as_slices();
1853
1854 let first_len = first_half.len();
1855 let second_len = second_half.len();
1856 if at < first_len {
1857 // `at` lies in the first half.
1858 let amount_in_first = first_len - at;
1859
1860 ptr::copy_nonoverlapping(
1861 first_half.as_ptr().add(at),
1862 other.ptr_mut(),
1863 amount_in_first,
1864 );
1865
1866 // just take all of the second half.
1867 ptr::copy_nonoverlapping(
1868 second_half.as_ptr(),
1869 other.ptr_mut().add(amount_in_first),
1870 second_len,
1871 );
1872 } else {
1873 // `at` lies in the second half, need to factor in the elements we skipped
1874 // in the first half.
1875 let offset = at - first_len;
1876 let amount_in_second = second_len - offset;
1877 ptr::copy_nonoverlapping(
1878 second_half.as_ptr().add(offset),
1879 other.ptr_mut(),
1880 amount_in_second,
1881 );
1882 }
1883 }
1884
1885 // Cleanup where the ends of the buffers are
1886 unsafe {
1887 self.set_len(at);
1888 other.set_len(other_len);
1889 }
1890
1891 other
1892 }
1893
1894 /// Retains only the elements specified by the predicate.
1895 ///
1896 /// In other words, remove all elements `e` such that `f(&e)` returns false.
1897 /// This method operates in place and preserves the order of the retained
1898 /// elements.
1899 ///
1900 /// # Examples
1901 ///
1902 /// ```
1903 /// use arraydeque::ArrayDeque;
1904 ///
1905 /// let mut buf: ArrayDeque<_, 4> = ArrayDeque::new();
1906 ///
1907 /// buf.extend_back(0..4);
1908 /// buf.retain(|&x| x % 2 == 0);
1909 ///
1910 /// assert_eq!(buf, [0, 2].into());
1911 /// ```
1912 pub fn retain<F>(&mut self, mut f: F)
1913 where
1914 F: FnMut(&T) -> bool,
1915 {
1916 let len = self.len();
1917 let mut del = 0;
1918 for i in 0..len {
1919 if !f(&self[i]) {
1920 del += 1;
1921 } else if del > 0 {
1922 self.swap(i - del, i);
1923 }
1924 }
1925 if del > 0 {
1926 for _ in (len - del)..self.len() {
1927 self.pop_back();
1928 }
1929 }
1930 }
1931
1932 /// Returns a pair of slices which contain, in order, the contents of the
1933 /// `ArrayDeque`.
1934 ///
1935 /// # Examples
1936 ///
1937 /// ```
1938 /// use arraydeque::ArrayDeque;
1939 ///
1940 /// let mut buf: ArrayDeque<_, 7> = ArrayDeque::new();
1941 ///
1942 /// buf.push_back(0);
1943 /// buf.push_back(1);
1944 ///
1945 /// assert_eq!(buf.as_slices(), (&[0, 1][..], &[][..]));
1946 ///
1947 /// buf.push_front(2);
1948 ///
1949 /// assert_eq!(buf.as_slices(), (&[2][..], &[0, 1][..]));
1950 /// ```
1951 #[inline]
1952 pub fn as_slices(&self) -> (&[T], &[T]) {
1953 let contiguous = self.is_contiguous();
1954 let head = self.head();
1955 let tail = self.tail();
1956 let buf = self.as_uninit_slice();
1957
1958 if contiguous {
1959 let (empty, buf) = buf.split_at(0);
1960 unsafe {
1961 (
1962 slice_assume_init_ref(&buf[tail..head]),
1963 slice_assume_init_ref(empty),
1964 )
1965 }
1966 } else {
1967 let (mid, right) = buf.split_at(tail);
1968 let (left, _) = mid.split_at(head);
1969
1970 unsafe { (slice_assume_init_ref(right), slice_assume_init_ref(left)) }
1971 }
1972 }
1973
1974 /// Returns a pair of slices which contain, in order, the contents of the
1975 /// `ArrayDeque`.
1976 ///
1977 /// # Examples
1978 ///
1979 /// ```
1980 /// use arraydeque::ArrayDeque;
1981 ///
1982 /// let mut buf: ArrayDeque<_, 7> = ArrayDeque::new();
1983 ///
1984 /// buf.push_back(0);
1985 /// buf.push_back(1);
1986 ///
1987 /// assert_eq!(buf.as_mut_slices(), (&mut [0, 1][..], &mut[][..]));
1988 ///
1989 /// buf.push_front(2);
1990 ///
1991 /// assert_eq!(buf.as_mut_slices(), (&mut[2][..], &mut[0, 1][..]));
1992 /// ```
1993 #[inline]
1994 pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
1995 let contiguous = self.is_contiguous();
1996 let head = self.head();
1997 let tail = self.tail();
1998 let buf = self.as_uninit_slice_mut();
1999
2000 if contiguous {
2001 let (empty, buf) = buf.split_at_mut(0);
2002 unsafe {
2003 (
2004 slice_assume_init_mut(&mut buf[tail..head]),
2005 slice_assume_init_mut(empty),
2006 )
2007 }
2008 } else {
2009 let (mid, right) = buf.split_at_mut(tail);
2010 let (left, _) = mid.split_at_mut(head);
2011
2012 unsafe { (slice_assume_init_mut(right), slice_assume_init_mut(left)) }
2013 }
2014 }
2015}
2016
2017/// Copy of currently-unstable `MaybeUninit::slice_assume_init_ref`.
2018unsafe fn slice_assume_init_ref<T>(slice: &[MaybeUninit<T>]) -> &[T] {
2019 // SAFETY: casting `slice` to a `*const [T]` is safe since the caller guarantees that
2020 // `slice` is initialized, and `MaybeUninit` is guaranteed to have the same layout as `T`.
2021 // The pointer obtained is valid since it refers to memory owned by `slice` which is a
2022 // reference and thus guaranteed to be valid for reads.
2023 &*(slice as *const [MaybeUninit<T>] as *const [T])
2024}
2025
2026/// Copy of currently-unstable `MaybeUninit::slice_assume_init_mut`.
2027unsafe fn slice_assume_init_mut<T>(slice: &mut [MaybeUninit<T>]) -> &mut [T] {
2028 // SAFETY: similar to safety notes for `slice_assume_init_ref`, but we have a
2029 // mutable reference which is also guaranteed to be valid for writes.
2030 &mut *(slice as *mut [MaybeUninit<T>] as *mut [T])
2031}
2032
2033impl<T, const CAP: usize> From<ArrayDeque<T, CAP, Wrapping>> for ArrayDeque<T, CAP, Saturating> {
2034 fn from(buf: ArrayDeque<T, CAP, Wrapping>) -> Self {
2035 buf.into_iter().collect()
2036 }
2037}
2038
2039impl<T, const CAP: usize> From<ArrayDeque<T, CAP, Saturating>> for ArrayDeque<T, CAP, Wrapping> {
2040 fn from(buf: ArrayDeque<T, CAP, Saturating>) -> Self {
2041 buf.into_iter().collect()
2042 }
2043}
2044
2045#[cfg(feature = "std")]
2046impl<T, const CAP: usize, B: Behavior> From<Vec<T>> for ArrayDeque<T, CAP, B>
2047where
2048 Self: FromIterator<T>,
2049{
2050 fn from(vec: Vec<T>) -> Self {
2051 vec.into_iter().collect()
2052 }
2053}
2054
2055impl<T, const CAP: usize, const N: usize, B: Behavior> From<[T; N]> for ArrayDeque<T, CAP, B>
2056where
2057 Self: FromIterator<T>,
2058{
2059 fn from(arr: [T; N]) -> Self {
2060 arr.into_iter().collect()
2061 }
2062}
2063
2064#[cfg(feature = "std")]
2065impl<T, const CAP: usize, B: Behavior> From<ArrayDeque<T, CAP, B>> for Vec<T>
2066where
2067 Self: FromIterator<T>,
2068{
2069 fn from(deque: ArrayDeque<T, CAP, B>) -> Self {
2070 deque.into_iter().collect()
2071 }
2072}
2073
2074impl<T, const CAP: usize, B: Behavior> Drop for ArrayDeque<T, CAP, B> {
2075 fn drop(&mut self) {
2076 self.clear();
2077 }
2078}
2079
2080impl<T, const CAP: usize, B: Behavior> Default for ArrayDeque<T, CAP, B> {
2081 #[inline]
2082 fn default() -> Self {
2083 ArrayDeque::new()
2084 }
2085}
2086
2087impl<T, const CAP: usize, B: Behavior> PartialEq for ArrayDeque<T, CAP, B>
2088where
2089 T: PartialEq,
2090{
2091 fn eq(&self, other: &Self) -> bool {
2092 if self.len() != other.len() {
2093 return false;
2094 }
2095 let (sa, sb) = self.as_slices();
2096 let (oa, ob) = other.as_slices();
2097 match sa.len().cmp(&oa.len()) {
2098 Ordering::Equal => sa == oa && sb == ob,
2099 Ordering::Less => {
2100 // Always divisible in three sections, for example:
2101 // self: [a b c|d e f]
2102 // other: [0 1 2 3|4 5]
2103 // front = 3, mid = 1,
2104 // [a b c] == [0 1 2] && [d] == [3] && [e f] == [4 5]
2105 let front = sa.len();
2106 let mid = oa.len() - front;
2107
2108 let (oa_front, oa_mid) = oa.split_at(front);
2109 let (sb_mid, sb_back) = sb.split_at(mid);
2110 debug_assert_eq!(sa.len(), oa_front.len());
2111 debug_assert_eq!(sb_mid.len(), oa_mid.len());
2112 debug_assert_eq!(sb_back.len(), ob.len());
2113 sa == oa_front && sb_mid == oa_mid && sb_back == ob
2114 }
2115 Ordering::Greater => {
2116 let front = oa.len();
2117 let mid = sa.len() - front;
2118
2119 let (sa_front, sa_mid) = sa.split_at(front);
2120 let (ob_mid, ob_back) = ob.split_at(mid);
2121 debug_assert_eq!(sa_front.len(), oa.len());
2122 debug_assert_eq!(sa_mid.len(), ob_mid.len());
2123 debug_assert_eq!(sb.len(), ob_back.len());
2124 sa_front == oa && sa_mid == ob_mid && sb == ob_back
2125 }
2126 }
2127 }
2128}
2129
2130impl<T, const CAP: usize, B: Behavior> Eq for ArrayDeque<T, CAP, B> where T: Eq {}
2131
2132impl<T, const CAP: usize, B: Behavior> PartialOrd for ArrayDeque<T, CAP, B>
2133where
2134 T: PartialOrd,
2135{
2136 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
2137 self.iter().partial_cmp(other.iter())
2138 }
2139}
2140
2141impl<T, const CAP: usize, B: Behavior> Ord for ArrayDeque<T, CAP, B>
2142where
2143 T: Ord,
2144{
2145 #[inline]
2146 fn cmp(&self, other: &Self) -> Ordering {
2147 self.iter().cmp(other.iter())
2148 }
2149}
2150
2151impl<T, const CAP: usize, B: Behavior> Hash for ArrayDeque<T, CAP, B>
2152where
2153 T: Hash,
2154{
2155 fn hash<H: Hasher>(&self, state: &mut H) {
2156 self.len().hash(state);
2157 let (a, b) = self.as_slices();
2158 Hash::hash_slice(a, state);
2159 Hash::hash_slice(b, state);
2160 }
2161}
2162
2163impl<T, const CAP: usize, B: Behavior> Index<usize> for ArrayDeque<T, CAP, B> {
2164 type Output = T;
2165
2166 #[inline]
2167 fn index(&self, index: usize) -> &T {
2168 let len = self.len();
2169 self.get(index)
2170 .or_else(|| {
2171 panic!(
2172 "index out of bounds: the len is {} but the index is {}",
2173 len, index
2174 )
2175 })
2176 .unwrap()
2177 }
2178}
2179
2180impl<T, const CAP: usize, B: Behavior> IndexMut<usize> for ArrayDeque<T, CAP, B> {
2181 #[inline]
2182 fn index_mut(&mut self, index: usize) -> &mut T {
2183 let len = self.len();
2184 self.get_mut(index)
2185 .or_else(|| {
2186 panic!(
2187 "index out of bounds: the len is {} but the index is {}",
2188 len, index
2189 )
2190 })
2191 .unwrap()
2192 }
2193}
2194
2195impl<T, const CAP: usize, B: Behavior> IntoIterator for ArrayDeque<T, CAP, B> {
2196 type Item = T;
2197 type IntoIter = IntoIter<T, CAP, B>;
2198
2199 fn into_iter(self) -> Self::IntoIter {
2200 IntoIter { inner: self }
2201 }
2202}
2203
2204impl<'a, T, const CAP: usize, B: Behavior> IntoIterator for &'a ArrayDeque<T, CAP, B> {
2205 type Item = &'a T;
2206 type IntoIter = Iter<'a, T>;
2207
2208 fn into_iter(self) -> Self::IntoIter {
2209 self.iter()
2210 }
2211}
2212
2213impl<'a, T, const CAP: usize, B: Behavior> IntoIterator for &'a mut ArrayDeque<T, CAP, B> {
2214 type Item = &'a mut T;
2215 type IntoIter = IterMut<'a, T>;
2216
2217 fn into_iter(self) -> Self::IntoIter {
2218 self.iter_mut()
2219 }
2220}
2221
2222impl<T, const CAP: usize, B: Behavior> fmt::Debug for ArrayDeque<T, CAP, B>
2223where
2224 T: fmt::Debug,
2225{
2226 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2227 f.debug_list().entries(self).finish()
2228 }
2229}
2230
2231#[inline]
2232fn wrap_add(index: usize, addend: usize, capacity: usize) -> usize {
2233 debug_assert!(addend <= capacity);
2234 (index + addend) % capacity
2235}
2236
2237#[inline]
2238fn wrap_sub(index: usize, subtrahend: usize, capacity: usize) -> usize {
2239 debug_assert!(subtrahend <= capacity);
2240 (index + capacity - subtrahend) % capacity
2241}
2242
2243/// `ArrayDeque` iterator
2244#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2245pub struct Iter<'a, T: 'a> {
2246 ring: &'a [MaybeUninit<T>],
2247 tail: usize,
2248 len: usize,
2249}
2250
2251impl<'a, T> Iterator for Iter<'a, T> {
2252 type Item = &'a T;
2253
2254 #[inline]
2255 fn next(&mut self) -> Option<&'a T> {
2256 if self.len == 0 {
2257 return None;
2258 }
2259 let tail = self.tail;
2260 self.tail = wrap_add(self.tail, 1, self.ring.len());
2261 self.len -= 1;
2262 unsafe { Some(self.ring.get_unchecked(tail).assume_init_ref()) }
2263 }
2264
2265 #[inline]
2266 fn size_hint(&self) -> (usize, Option<usize>) {
2267 (self.len, Some(self.len))
2268 }
2269}
2270
2271impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
2272 #[inline]
2273 fn next_back(&mut self) -> Option<&'a T> {
2274 if self.len == 0 {
2275 return None;
2276 }
2277 self.len -= 1;
2278 let head = wrap_add(self.tail, self.len, self.ring.len());
2279 unsafe { Some(self.ring.get_unchecked(head).assume_init_ref()) }
2280 }
2281}
2282
2283impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
2284
2285impl<'a, T> Clone for Iter<'a, T> {
2286 fn clone(&self) -> Self {
2287 Iter {
2288 ring: self.ring,
2289 tail: self.tail,
2290 len: self.len,
2291 }
2292 }
2293}
2294
2295/// `ArrayDeque` mutable iterator
2296#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2297pub struct IterMut<'a, T: 'a> {
2298 ring: &'a mut [MaybeUninit<T>],
2299 tail: usize,
2300 len: usize,
2301}
2302
2303impl<'a, T> Iterator for IterMut<'a, T> {
2304 type Item = &'a mut T;
2305
2306 #[inline]
2307 fn next(&mut self) -> Option<&'a mut T> {
2308 if self.len == 0 {
2309 return None;
2310 }
2311 let tail = self.tail;
2312 self.tail = wrap_add(self.tail, 1, self.ring.len());
2313 self.len -= 1;
2314 unsafe {
2315 let elem = self.ring.get_unchecked_mut(tail).assume_init_mut();
2316 Some(std::mem::transmute::<&mut T, &'a mut T>(elem))
2317 }
2318 }
2319
2320 #[inline]
2321 fn size_hint(&self) -> (usize, Option<usize>) {
2322 (self.len, Some(self.len))
2323 }
2324}
2325
2326impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
2327 #[inline]
2328 fn next_back(&mut self) -> Option<&'a mut T> {
2329 if self.len == 0 {
2330 return None;
2331 }
2332 self.len -= 1;
2333 let head = wrap_add(self.tail, self.len, self.ring.len());
2334 unsafe {
2335 let elem = self.ring.get_unchecked_mut(head).assume_init_mut();
2336 Some(std::mem::transmute::<&mut T, &'a mut T>(elem))
2337 }
2338 }
2339}
2340
2341impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
2342
2343/// By-value `ArrayDeque` iterator
2344#[must_use = "iterator adaptors are lazy and do nothing unless consumed"]
2345pub struct IntoIter<T, const CAP: usize, B: Behavior> {
2346 inner: ArrayDeque<T, CAP, B>,
2347}
2348
2349impl<T, const CAP: usize, B: Behavior> Iterator for IntoIter<T, CAP, B> {
2350 type Item = T;
2351
2352 #[inline]
2353 fn next(&mut self) -> Option<T> {
2354 self.inner.pop_front()
2355 }
2356
2357 #[inline]
2358 fn size_hint(&self) -> (usize, Option<usize>) {
2359 let len = self.inner.len();
2360 (len, Some(len))
2361 }
2362}
2363
2364impl<T, const CAP: usize, B: Behavior> DoubleEndedIterator for IntoIter<T, CAP, B> {
2365 #[inline]
2366 fn next_back(&mut self) -> Option<T> {
2367 self.inner.pop_back()
2368 }
2369}
2370
2371impl<T, const CAP: usize, B: Behavior> ExactSizeIterator for IntoIter<T, CAP, B> {}
2372
2373/// Draining `ArrayDeque` iterator
2374pub struct Drain<'a, T, const CAP: usize, B>
2375where
2376 B: Behavior,
2377{
2378 after_tail: usize,
2379 after_len: usize,
2380 iter: Iter<'a, T>,
2381 deque: *mut ArrayDeque<T, CAP, B>,
2382}
2383
2384impl<'a, T, const CAP: usize, B> Drop for Drain<'a, T, CAP, B>
2385where
2386 B: Behavior,
2387{
2388 fn drop(&mut self) {
2389 for _ in self.by_ref() {}
2390
2391 let source_deque = unsafe { &mut *self.deque };
2392
2393 let tail_len = source_deque.len();
2394 let head_len = self.after_len;
2395
2396 let orig_tail = source_deque.tail();
2397 let drain_tail = wrap_add(orig_tail, tail_len, CAP);
2398 let drain_head = self.after_tail;
2399 let orig_head = wrap_add(drain_head, head_len, CAP);
2400 let orig_len = wrap_sub(orig_head, orig_tail, CAP);
2401
2402 // Restore the original len value
2403 unsafe { source_deque.set_len(orig_len) }
2404 match (tail_len, head_len) {
2405 (0, 0) => unsafe {
2406 source_deque.set_tail(0);
2407 source_deque.set_len(0);
2408 },
2409 (0, _) => unsafe {
2410 source_deque.set_tail(drain_head);
2411 source_deque.set_len(head_len);
2412 },
2413 (_, 0) => unsafe { source_deque.set_len(tail_len) },
2414 _ => unsafe {
2415 if tail_len <= head_len {
2416 let new_tail = wrap_sub(drain_head, tail_len, CAP);
2417 source_deque.set_tail(new_tail);
2418 source_deque.set_len(tail_len + head_len);
2419 source_deque.wrap_copy(new_tail, orig_tail, tail_len);
2420 } else {
2421 source_deque.set_len(tail_len + head_len);
2422 source_deque.wrap_copy(drain_tail, drain_head, head_len);
2423 }
2424 },
2425 }
2426 }
2427}
2428
2429impl<'a, T, const CAP: usize, B: Behavior> Iterator for Drain<'a, T, CAP, B> {
2430 type Item = T;
2431
2432 #[inline]
2433 fn next(&mut self) -> Option<T> {
2434 self.iter.next().map(|elt| unsafe { ptr::read(elt) })
2435 }
2436
2437 #[inline]
2438 fn size_hint(&self) -> (usize, Option<usize>) {
2439 self.iter.size_hint()
2440 }
2441}
2442
2443impl<'a, T, const CAP: usize, B: Behavior> DoubleEndedIterator for Drain<'a, T, CAP, B> {
2444 #[inline]
2445 fn next_back(&mut self) -> Option<T> {
2446 self.iter.next_back().map(|elt| unsafe { ptr::read(elt) })
2447 }
2448}
2449
2450impl<'a, T, const CAP: usize, B: Behavior> ExactSizeIterator for Drain<'a, T, CAP, B> {}
2451
2452#[cfg(test)]
2453mod tests {
2454 #![allow(unused_must_use)]
2455 use super::*;
2456
2457 #[test]
2458 fn test_simple() {
2459 macro_rules! test {
2460 ($behavior:ident) => {{
2461 let mut tester: ArrayDeque<_, 7, $behavior> = ArrayDeque::new();
2462 assert_eq!(tester.capacity(), 7);
2463 assert_eq!(tester.len(), 0);
2464
2465 tester.push_back(1);
2466 tester.push_back(2);
2467 tester.push_back(3);
2468 tester.push_back(4);
2469 assert_eq!(tester.len(), 4);
2470 assert_eq!(tester.pop_front(), Some(1));
2471 assert_eq!(tester.pop_front(), Some(2));
2472 assert_eq!(tester.len(), 2);
2473 assert_eq!(tester.pop_front(), Some(3));
2474 assert_eq!(tester.pop_front(), Some(4));
2475 assert_eq!(tester.pop_front(), None);
2476 }};
2477 }
2478
2479 test!(Saturating);
2480 test!(Wrapping);
2481 }
2482
2483 #[test]
2484 fn test_simple_reversely() {
2485 macro_rules! test {
2486 ($behavior:ident) => {{
2487 let mut tester: ArrayDeque<_, 7, $behavior> = ArrayDeque::new();
2488 assert_eq!(tester.capacity(), 7);
2489 assert_eq!(tester.len(), 0);
2490
2491 tester.push_front(1);
2492 tester.push_front(2);
2493 tester.push_front(3);
2494 tester.push_front(4);
2495 assert_eq!(tester.len(), 4);
2496 assert_eq!(tester.pop_back(), Some(1));
2497 assert_eq!(tester.pop_back(), Some(2));
2498 assert_eq!(tester.len(), 2);
2499 assert_eq!(tester.pop_back(), Some(3));
2500 assert_eq!(tester.pop_back(), Some(4));
2501 assert_eq!(tester.pop_back(), None);
2502 }};
2503 }
2504
2505 test!(Saturating);
2506 test!(Wrapping);
2507 }
2508
2509 #[test]
2510 fn test_overflow_saturating() {
2511 let mut tester: ArrayDeque<_, 2, Saturating> = ArrayDeque::new();
2512 assert_eq!(tester.push_back(1), Ok(()));
2513 assert_eq!(tester.push_back(2), Ok(()));
2514 assert_eq!(tester.push_back(3), Err(CapacityError { element: 3 }));
2515
2516 let mut tester: ArrayDeque<_, 2, Saturating> = ArrayDeque::new();
2517 assert_eq!(tester.insert(0, 1), Ok(()));
2518 assert_eq!(tester.insert(1, 2), Ok(()));
2519 assert_eq!(tester.insert(2, 3), Err(CapacityError { element: 3 }));
2520 }
2521
2522 #[test]
2523 fn test_overflow_wrapping() {
2524 let mut tester: ArrayDeque<_, 2, Wrapping> = ArrayDeque::new();
2525 assert_eq!(tester.push_back(1), None);
2526 assert_eq!(tester.push_back(2), None);
2527 assert_eq!(tester.push_back(3), Some(1));
2528 }
2529
2530 #[test]
2531 fn test_pop_empty() {
2532 let mut tester: ArrayDeque<_, 2> = ArrayDeque::new();
2533 assert_eq!(tester.push_back(1), Ok(()));
2534 assert_eq!(tester.pop_front(), Some(1));
2535 assert_eq!(tester.is_empty(), true);
2536 assert_eq!(tester.len(), 0);
2537 assert_eq!(tester.pop_front(), None);
2538 }
2539
2540 #[test]
2541 fn test_index() {
2542 let mut tester: ArrayDeque<_, 3> = ArrayDeque::new();
2543 tester.push_back(1);
2544 tester.push_back(2);
2545 tester.push_back(3);
2546 assert_eq!(tester[0], 1);
2547 // pop_front 1 <- [2, 3]
2548 assert_eq!(tester.pop_front(), Some(1));
2549 assert_eq!(tester[0], 2);
2550 assert_eq!(tester.len(), 2);
2551 // push_front 0 -> [0, 2, 3]
2552 tester.push_front(0);
2553 assert_eq!(tester[0], 0);
2554 // [0, 2] -> 3 pop_back
2555 assert_eq!(tester.pop_back(), Some(3));
2556 assert_eq!(tester[1], 2);
2557 }
2558
2559 #[test]
2560 #[should_panic]
2561 fn test_index_overflow() {
2562 let mut tester: ArrayDeque<_, 3> = ArrayDeque::new();
2563 tester.push_back(1);
2564 tester.push_back(2);
2565 tester[2];
2566 }
2567
2568 #[test]
2569 fn test_iter() {
2570 let mut tester: ArrayDeque<_, 2> = ArrayDeque::new();
2571 tester.push_back(1);
2572 tester.push_back(2);
2573 {
2574 let mut iter = tester.iter();
2575 assert_eq!(iter.size_hint(), (2, Some(2)));
2576 assert_eq!(iter.next(), Some(&1));
2577 assert_eq!(iter.next(), Some(&2));
2578 assert_eq!(iter.next(), None);
2579 assert_eq!(iter.size_hint(), (0, Some(0)));
2580 }
2581 tester.pop_front();
2582 tester.push_back(3);
2583 {
2584 let mut iter = (&tester).into_iter();
2585 assert_eq!(iter.next(), Some(&2));
2586
2587 // test clone
2588 let mut iter2 = iter.clone();
2589 assert_eq!(iter.next(), Some(&3));
2590 assert_eq!(iter.next(), None);
2591 assert_eq!(iter2.next(), Some(&3));
2592 assert_eq!(iter2.next(), None);
2593 }
2594 }
2595
2596 #[test]
2597 fn test_iter_mut() {
2598 let mut tester: ArrayDeque<_, 2> = ArrayDeque::new();
2599 tester.push_back(1);
2600 tester.push_back(2);
2601 {
2602 let mut iter = tester.iter_mut();
2603 assert_eq!(iter.size_hint(), (2, Some(2)));
2604 assert_eq!(iter.next(), Some(&mut 1));
2605 assert_eq!(iter.next(), Some(&mut 2));
2606 assert_eq!(iter.next(), None);
2607 assert_eq!(iter.size_hint(), (0, Some(0)));
2608 }
2609 tester.pop_front();
2610 tester.push_back(3);
2611 {
2612 let mut iter = (&mut tester).into_iter();
2613 assert_eq!(iter.next(), Some(&mut 2));
2614 assert_eq!(iter.next(), Some(&mut 3));
2615 assert_eq!(iter.next(), None);
2616 }
2617 {
2618 // mutation
2619 let mut iter = tester.iter_mut();
2620 iter.next().map(|n| *n += 1);
2621 iter.next().map(|n| *n += 2);
2622 }
2623 assert_eq!(tester[0], 3);
2624 assert_eq!(tester[1], 5);
2625 }
2626
2627 #[test]
2628 fn test_into_iter() {
2629 #[derive(Eq, PartialEq, Debug)]
2630 struct NoCopy<T>(T);
2631
2632 {
2633 let mut tester: ArrayDeque<NoCopy<u8>, 3> = ArrayDeque::new();
2634 tester.push_back(NoCopy(1));
2635 tester.push_back(NoCopy(2));
2636 let mut iter = tester.into_iter();
2637 assert_eq!(iter.size_hint(), (2, Some(2)));
2638 assert_eq!(iter.next(), Some(NoCopy(1)));
2639 assert_eq!(iter.next(), Some(NoCopy(2)));
2640 assert_eq!(iter.next(), None);
2641 assert_eq!(iter.size_hint(), (0, Some(0)));
2642 }
2643 {
2644 let mut tester: ArrayDeque<NoCopy<u8>, 3> = ArrayDeque::new();
2645 tester.push_back(NoCopy(1));
2646 tester.push_back(NoCopy(2));
2647 tester.pop_front();
2648 tester.push_back(NoCopy(3));
2649 let mut iter = tester.into_iter();
2650 assert_eq!(iter.next(), Some(NoCopy(2)));
2651 assert_eq!(iter.next(), Some(NoCopy(3)));
2652 assert_eq!(iter.next(), None);
2653 }
2654 {
2655 let mut tester: ArrayDeque<NoCopy<u8>, 3> = ArrayDeque::new();
2656 tester.push_back(NoCopy(1));
2657 tester.push_back(NoCopy(2));
2658 tester.pop_front();
2659 tester.push_back(NoCopy(3));
2660 tester.pop_front();
2661 tester.push_back(NoCopy(4));
2662 let mut iter = tester.into_iter();
2663 assert_eq!(iter.next(), Some(NoCopy(3)));
2664 assert_eq!(iter.next(), Some(NoCopy(4)));
2665 assert_eq!(iter.next(), None);
2666 }
2667 }
2668
2669 #[test]
2670 #[cfg(feature = "std")]
2671 fn test_drain() {
2672 const CAP: usize = 8;
2673 let mut tester: ArrayDeque<_, CAP> = ArrayDeque::new();
2674
2675 for padding in 0..CAP {
2676 for drain_start in 0..CAP {
2677 for drain_end in drain_start..CAP {
2678 // deque starts from different tail position
2679 unsafe {
2680 tester.set_len(0);
2681 tester.set_tail(padding);
2682 }
2683
2684 tester.extend_back(0..CAP);
2685
2686 let mut expected = vec![0, 1, 2, 3, 4, 5, 6, 7];
2687 let drains: Vec<_> = tester.drain(drain_start..drain_end).collect();
2688 let expected_drains: Vec<_> = expected.drain(drain_start..drain_end).collect();
2689 assert_eq!(drains, expected_drains);
2690 assert_eq!(tester, expected.into());
2691 }
2692 }
2693 }
2694 }
2695
2696 #[test]
2697 fn test_drop() {
2698 use std::cell::Cell;
2699
2700 let flag = &Cell::new(0);
2701
2702 struct Bump<'a>(&'a Cell<i32>);
2703
2704 impl<'a> Drop for Bump<'a> {
2705 fn drop(&mut self) {
2706 let n = self.0.get();
2707 self.0.set(n + 1);
2708 }
2709 }
2710
2711 {
2712 let mut tester = ArrayDeque::<Bump, 128>::new();
2713 tester.push_back(Bump(flag));
2714 tester.push_back(Bump(flag));
2715 }
2716 assert_eq!(flag.get(), 2);
2717
2718 // test something with the nullable pointer optimization
2719 flag.set(0);
2720 {
2721 let mut tester = ArrayDeque::<_, 3>::new();
2722 tester.push_back(vec![Bump(flag)]);
2723 tester.push_back(vec![Bump(flag), Bump(flag)]);
2724 tester.push_back(vec![]);
2725 tester.push_back(vec![Bump(flag)]);
2726 assert_eq!(flag.get(), 1);
2727 drop(tester.pop_back());
2728 assert_eq!(flag.get(), 1);
2729 drop(tester.pop_back());
2730 assert_eq!(flag.get(), 3);
2731 }
2732 assert_eq!(flag.get(), 4);
2733 }
2734
2735 #[test]
2736 fn test_as_slice() {
2737 const CAP: usize = 10;
2738 let mut tester = ArrayDeque::<_, CAP>::new();
2739
2740 for len in 0..CAP + 1 {
2741 for padding in 0..CAP {
2742 // deque starts from different tail position
2743 unsafe {
2744 tester.set_len(0);
2745 tester.set_tail(padding);
2746 }
2747
2748 let mut expected = vec![];
2749 tester.extend_back(0..len);
2750 expected.extend(0..len);
2751
2752 let split_idx = CAP - padding;
2753 if split_idx < len {
2754 assert_eq!(tester.as_slices(), expected[..].split_at(split_idx));
2755 } else {
2756 assert_eq!(tester.as_slices(), (&expected[..], &[][..]));
2757 }
2758 }
2759 }
2760 }
2761
2762 #[test]
2763 fn test_partial_equal() {
2764 const CAP: usize = 10;
2765 let mut tester = ArrayDeque::<f64, CAP>::new();
2766
2767 for len in 0..CAP + 1 {
2768 for padding in 0..CAP {
2769 // deque starts from different tail position
2770 unsafe {
2771 tester.set_len(0);
2772 tester.set_tail(padding);
2773 }
2774
2775 let mut expected = ArrayDeque::<f64, CAP>::new();
2776 for x in 0..len {
2777 tester.push_back(x as f64);
2778 expected.push_back(x as f64);
2779 }
2780 assert_eq!(tester, expected);
2781
2782 // test negative
2783 if len > 2 {
2784 tester.pop_front();
2785 expected.pop_back();
2786 assert!(tester != expected);
2787 }
2788 }
2789 }
2790 }
2791
2792 #[test]
2793 fn test_fmt() {
2794 let mut tester = ArrayDeque::<_, 5>::new();
2795 tester.extend_back(0..4);
2796 assert_eq!(format!("{:?}", tester), "[0, 1, 2, 3]");
2797 }
2798
2799 #[test]
2800 fn test_swap_front_back_remove() {
2801 fn test(back: bool) {
2802 const CAP: usize = 16;
2803 let mut tester = ArrayDeque::<_, CAP>::new();
2804 let usable_cap = tester.capacity();
2805 let final_len = usable_cap / 2;
2806
2807 for len in 0..final_len {
2808 let expected = if back {
2809 (0..len).collect()
2810 } else {
2811 (0..len).rev().collect()
2812 };
2813 for padding in 0..usable_cap {
2814 unsafe {
2815 tester.set_tail(padding);
2816 tester.set_len(0);
2817 }
2818 if back {
2819 for i in 0..len * 2 {
2820 tester.push_front(i);
2821 }
2822 for i in 0..len {
2823 assert_eq!(tester.swap_remove_back(i), Some(len * 2 - 1 - i));
2824 }
2825 } else {
2826 for i in 0..len * 2 {
2827 tester.push_back(i);
2828 }
2829 for i in 0..len {
2830 let idx = tester.len() - 1 - i;
2831 assert_eq!(tester.swap_remove_front(idx), Some(len * 2 - 1 - i));
2832 }
2833 }
2834 assert!(tester.tail() < CAP);
2835 assert!(tester.head() < CAP);
2836 assert_eq!(tester, expected);
2837 }
2838 }
2839 }
2840 test(true);
2841 test(false);
2842 }
2843
2844 #[test]
2845 fn test_retain() {
2846 const CAP: usize = 10;
2847 let mut tester: ArrayDeque<_, CAP> = ArrayDeque::new();
2848 for padding in 0..CAP {
2849 unsafe {
2850 tester.set_tail(padding);
2851 tester.set_len(0);
2852 }
2853 tester.extend_back(0..CAP);
2854 tester.retain(|x| x % 2 == 0);
2855 assert_eq!(tester.iter().count(), CAP / 2);
2856 }
2857 }
2858
2859 #[test]
2860 fn test_split_off() {
2861 const CAP: usize = 16;
2862 let mut tester = ArrayDeque::<_, CAP>::new();
2863 for len in 0..CAP + 1 {
2864 // index to split at
2865 for at in 0..len + 1 {
2866 for padding in 0..CAP {
2867 let expected_self = (0..).take(at).collect();
2868 let expected_other = (at..).take(len - at).collect();
2869 unsafe {
2870 tester.set_len(0);
2871 tester.set_tail(padding);
2872 }
2873 for i in 0..len {
2874 tester.push_back(i);
2875 }
2876 let result = tester.split_off(at);
2877 assert!(tester.tail() < CAP);
2878 assert!(tester.head() < CAP);
2879 assert!(result.tail() < CAP);
2880 assert!(result.head() < CAP);
2881 assert_eq!(tester, expected_self);
2882 assert_eq!(result, expected_other);
2883 }
2884 }
2885 }
2886 }
2887
2888 #[test]
2889 fn test_remove() {
2890 const CAP: usize = 16;
2891 let mut tester = ArrayDeque::<_, CAP>::new();
2892
2893 // len is the length *after* removal
2894 for len in 0..CAP {
2895 // 0, 1, 2, .., len - 1
2896 let expected = (0..).take(len).collect();
2897 for padding in 0..CAP {
2898 for to_remove in 0..len + 1 {
2899 unsafe {
2900 tester.set_tail(padding);
2901 tester.set_len(0);
2902 }
2903 for i in 0..len {
2904 if i == to_remove {
2905 tester.push_back(1234);
2906 }
2907 tester.push_back(i);
2908 }
2909 if to_remove == len {
2910 tester.push_back(1234);
2911 }
2912 tester.remove(to_remove);
2913 assert!(tester.tail() < CAP);
2914 assert!(tester.head() < CAP);
2915 assert_eq!(tester, expected);
2916 }
2917 }
2918 }
2919 }
2920
2921 #[test]
2922 fn test_clone() {
2923 let tester: ArrayDeque<_, 16> = (0..16).into_iter().collect();
2924 let cloned = tester.clone();
2925 assert_eq!(tester, cloned)
2926 }
2927
2928 #[test]
2929 fn test_option_encoding() {
2930 let tester: ArrayDeque<Box<()>, 100> = ArrayDeque::new();
2931 assert!(Some(tester).is_some());
2932 }
2933
2934 #[test]
2935 fn test_insert_unchecked() {
2936 const CAP: usize = 16;
2937 let mut tester = ArrayDeque::<_, CAP>::new();
2938
2939 // len is the length *after* insertion
2940 for len in 1..CAP {
2941 // 0, 1, 2, .., len - 1
2942 let expected = (0..).take(len).collect();
2943 for padding in 0..CAP {
2944 for to_insert in 0..len {
2945 unsafe {
2946 tester.set_tail(padding);
2947 tester.set_len(0);
2948 }
2949 for i in 0..len {
2950 if i != to_insert {
2951 tester.push_back(i);
2952 }
2953 }
2954 unsafe { tester.insert_unchecked(to_insert, to_insert) };
2955 assert!(tester.tail() < CAP);
2956 assert!(tester.head() < CAP);
2957 assert_eq!(tester, expected);
2958 }
2959 }
2960 }
2961 }
2962
2963 #[test]
2964 fn test_linearize() {
2965 let mut tester: ArrayDeque<isize, 10, Saturating> = ArrayDeque::new();
2966 tester.extend_back([1, 2, 3]);
2967 tester.extend_front([-1, -2]);
2968 assert_eq!(tester, [-2, -1, 1, 2, 3].into());
2969 tester.linearize();
2970 assert_eq!(tester, [-2, -1, 1, 2, 3].into());
2971 assert_eq!(tester.as_slices().1.len(), 0);
2972
2973 let mut tester: ArrayDeque<isize, 10, Saturating> = ArrayDeque::new();
2974 tester.extend_back([1, 2]);
2975 tester.extend_front([-1, -2, -3]);
2976 assert_eq!(tester, [-3, -2, -1, 1, 2].into());
2977 tester.linearize();
2978 assert_eq!(tester, [-3, -2, -1, 1, 2].into());
2979 assert_eq!(tester.as_slices().1.len(), 0);
2980
2981 let mut tester: ArrayDeque<isize, 10, Saturating> = ArrayDeque::new();
2982 tester.extend_back([1, 2, 3]);
2983 tester.extend_front([-1, -2, -3]);
2984 assert_eq!(tester, [-3, -2, -1, 1, 2, 3].into());
2985 tester.linearize();
2986 assert_eq!(tester, [-3, -2, -1, 1, 2, 3].into());
2987 assert_eq!(tester.as_slices().1.len(), 0);
2988
2989 let mut tester: ArrayDeque<isize, 5, Saturating> = ArrayDeque::new();
2990 tester.extend_back([1, 2, 3]);
2991 tester.extend_front([-1, -2]);
2992 assert_eq!(tester, [-2, -1, 1, 2, 3].into());
2993 tester.linearize();
2994 assert_eq!(tester, [-2, -1, 1, 2, 3].into());
2995 assert_eq!(tester.as_slices().1.len(), 0);
2996
2997 let mut tester: ArrayDeque<isize, 5, Saturating> = ArrayDeque::new();
2998 tester.extend_back([1, 2]);
2999 tester.extend_front([-1, -2, -3]);
3000 assert_eq!(tester, [-3, -2, -1, 1, 2].into());
3001 tester.linearize();
3002 assert_eq!(tester, [-3, -2, -1, 1, 2].into());
3003 assert_eq!(tester.as_slices().1.len(), 0);
3004
3005 let mut tester: ArrayDeque<isize, 6, Saturating> = ArrayDeque::new();
3006 tester.extend_back([1, 2, 3]);
3007 tester.extend_front([-1, -2, -3]);
3008 assert_eq!(tester, [-3, -2, -1, 1, 2, 3].into());
3009 tester.linearize();
3010 assert_eq!(tester, [-3, -2, -1, 1, 2, 3].into());
3011 assert_eq!(tester.as_slices().1.len(), 0);
3012
3013 let mut tester: ArrayDeque<isize, 10, Saturating> = ArrayDeque::new();
3014 tester.extend_back([1, 2, 3, 4, 5]);
3015 tester.extend_front([-1]);
3016 assert_eq!(tester, [-1, 1, 2, 3, 4, 5].into());
3017 tester.linearize();
3018 assert_eq!(tester, [-1, 1, 2, 3, 4, 5].into());
3019 assert_eq!(tester.as_slices().1.len(), 0);
3020
3021 let mut tester: ArrayDeque<isize, 10, Saturating> = ArrayDeque::new();
3022 tester.extend_back([1]);
3023 tester.extend_front([-1, -2, -3, -4, -5]);
3024 assert_eq!(tester, [-5, -4, -3, -2, -1, 1].into());
3025 tester.linearize();
3026 assert_eq!(tester, [-5, -4, -3, -2, -1, 1].into());
3027 assert_eq!(tester.as_slices().1.len(), 0);
3028 }
3029
3030 #[test]
3031 fn test_from_iterator_saturating() {
3032 assert_eq!(
3033 ArrayDeque::<_, 3, Saturating>::from_iter([1, 2, 3]),
3034 [1, 2, 3].into()
3035 );
3036 assert_eq!(
3037 ArrayDeque::<_, 3, Saturating>::from_iter([1, 2, 3, 4, 5]),
3038 [1, 2, 3].into()
3039 );
3040 }
3041
3042 #[test]
3043 fn test_from_iterator_wrapping() {
3044 assert_eq!(
3045 ArrayDeque::<_, 3, Wrapping>::from_iter([1, 2, 3]),
3046 [1, 2, 3].into()
3047 );
3048 assert_eq!(
3049 ArrayDeque::<_, 3, Wrapping>::from_iter([1, 2, 3, 4, 5]),
3050 [3, 4, 5].into()
3051 );
3052 }
3053
3054 #[test]
3055 fn test_extend_front_saturating() {
3056 let mut tester: ArrayDeque<usize, 3, Saturating> = ArrayDeque::new();
3057 tester.extend_front([1, 2, 3]);
3058 assert_eq!(tester, [3, 2, 1].into());
3059 tester.extend_front([4, 5]);
3060 assert_eq!(tester, [3, 2, 1].into());
3061 }
3062
3063 #[test]
3064 fn test_extend_back_saturating() {
3065 let mut tester: ArrayDeque<usize, 3, Saturating> = ArrayDeque::new();
3066 tester.extend_back([1, 2, 3]);
3067 assert_eq!(tester, [1, 2, 3].into());
3068 tester.extend_back([4, 5]);
3069 assert_eq!(tester, [1, 2, 3].into());
3070 }
3071
3072 #[test]
3073 fn test_extend_front_wrapping() {
3074 let mut tester: ArrayDeque<usize, 3, Wrapping> = ArrayDeque::new();
3075 tester.extend_front([1, 2, 3]);
3076 assert_eq!(tester, [3, 2, 1].into());
3077 tester.extend_front([4, 5]);
3078 assert_eq!(tester, [5, 4, 3].into());
3079 }
3080
3081 #[test]
3082 fn test_extend_back_wrapping() {
3083 let mut tester: ArrayDeque<usize, 3, Wrapping> = ArrayDeque::new();
3084 tester.extend_back([1, 2, 3]);
3085 assert_eq!(tester, [1, 2, 3].into());
3086 tester.extend_back([4, 5]);
3087 assert_eq!(tester, [3, 4, 5].into());
3088 }
3089}