Skip to main content

hybrid_arraydeque/
lib.rs

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