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