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