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