library/alloc/src/collections/vec_deque.rs

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