mod.rs source code [crates/alloc/src/collections/vec_deque/mod.rs]

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