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