src/liballoc/collections/vec_deque.rs

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