src/libcollections/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 //! VecDeque is a double-ended queue, which is implemented with the help of a
  12 //! growing ring buffer.
  13 //!
  14 //! This queue has `O(1)` amortized inserts and removals from both ends of the
  15 //! container. It also has `O(1)` indexing like a vector. The contained elements
  16 //! are not required to be copyable, and the queue will be sendable if the
  17 //! contained type is sendable.
  18
  19 #![stable(feature = "rust1", since = "1.0.0")]
  20
  21 use core::cmp::Ordering;
  22 use core::fmt;
  23 use core::iter::{repeat, FromIterator};
  24 use core::mem;
  25 use core::ops::{Index, IndexMut};
  26 use core::ptr;
  27 use core::slice;
  28
  29 use core::hash::{Hash, Hasher};
  30 use core::cmp;
  31
  32 use alloc::raw_vec::RawVec;
  33
  34 use super::range::RangeArgument;
  35
  36 const INITIAL_CAPACITY: usize = 7; // 2^3 - 1
  37 const MINIMUM_CAPACITY: usize = 1; // 2 - 1
  38 #[cfg(target_pointer_width = "32")]
  39 const MAXIMUM_ZST_CAPACITY: usize = 1 << (32 - 1); // Largest possible power of two
  40 #[cfg(target_pointer_width = "64")]
  41 const MAXIMUM_ZST_CAPACITY: usize = 1 << (64 - 1); // Largest possible power of two
  42
  43 /// `VecDeque` is a growable ring buffer, which can be used as a double-ended
  44 /// queue efficiently.
  45 ///
  46 /// The "default" usage of this type as a queue is to use `push_back` to add to
  47 /// the queue, and `pop_front` to remove from the queue. `extend` and `append`
  48 /// push onto the back in this manner, and iterating over `VecDeque` goes front
  49 /// to back.
  50 #[stable(feature = "rust1", since = "1.0.0")]
  51 pub struct VecDeque<T> {
  52     // tail and head are pointers into the buffer. Tail always points
  53     // to the first element that could be read, Head always points
  54     // to where data should be written.
  55     // If tail == head the buffer is empty. The length of the ringbuffer
  56     // is defined as the distance between the two.
  57     tail: usize,
  58     head: usize,
  59     buf: RawVec<T>,
  60 }
  61
  62 #[stable(feature = "rust1", since = "1.0.0")]
  63 impl<T: Clone> Clone for VecDeque<T> {
  64     fn clone(&self) -> VecDeque<T> {
  65         self.iter().cloned().collect()
  66     }
  67 }
  68
  69 #[stable(feature = "rust1", since = "1.0.0")]
  70 impl<T> Drop for VecDeque<T> {
  71     #[unsafe_destructor_blind_to_params]
  72     fn drop(&mut self) {
  73         self.clear();
  74         // RawVec handles deallocation
  75     }
  76 }
  77
  78 #[stable(feature = "rust1", since = "1.0.0")]
  79 impl<T> Default for VecDeque<T> {
  80     #[inline]
  81     fn default() -> VecDeque<T> {
  82         VecDeque::new()
  83     }
  84 }
  85
  86 impl<T> VecDeque<T> {
  87     /// Marginally more convenient
  88     #[inline]
  89     fn ptr(&self) -> *mut T {
  90         self.buf.ptr()
  91     }
  92
  93     /// Marginally more convenient
  94     #[inline]
  95     fn cap(&self) -> usize {
  96         if mem::size_of::<T>() == 0 {
  97             // For zero sized types, we are always at maximum capacity
  98             MAXIMUM_ZST_CAPACITY
  99         } else {
 100             self.buf.cap()
 101         }
 102     }
 103
 104     /// Turn ptr into a slice
 105     #[inline]
 106     unsafe fn buffer_as_slice(&self) -> &[T] {
 107         slice::from_raw_parts(self.ptr(), self.cap())
 108     }
 109
 110     /// Turn ptr into a mut slice
 111     #[inline]
 112     unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T] {
 113         slice::from_raw_parts_mut(self.ptr(), self.cap())
 114     }
 115
 116     /// Moves an element out of the buffer
 117     #[inline]
 118     unsafe fn buffer_read(&mut self, off: usize) -> T {
 119         ptr::read(self.ptr().offset(off as isize))
 120     }
 121
 122     /// Writes an element into the buffer, moving it.
 123     #[inline]
 124     unsafe fn buffer_write(&mut self, off: usize, value: T) {
 125         ptr::write(self.ptr().offset(off as isize), value);
 126     }
 127
 128     /// Returns true if and only if the buffer is at capacity
 129     #[inline]
 130     fn is_full(&self) -> bool {
 131         self.cap() - self.len() == 1
 132     }
 133
 134     /// Returns the index in the underlying buffer for a given logical element
 135     /// index.
 136     #[inline]
 137     fn wrap_index(&self, idx: usize) -> usize {
 138         wrap_index(idx, self.cap())
 139     }
 140
 141     /// Returns the index in the underlying buffer for a given logical element
 142     /// index + addend.
 143     #[inline]
 144     fn wrap_add(&self, idx: usize, addend: usize) -> usize {
 145         wrap_index(idx.wrapping_add(addend), self.cap())
 146     }
 147
 148     /// Returns the index in the underlying buffer for a given logical element
 149     /// index - subtrahend.
 150     #[inline]
 151     fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize {
 152         wrap_index(idx.wrapping_sub(subtrahend), self.cap())
 153     }
 154
 155     /// Copies a contiguous block of memory len long from src to dst
 156     #[inline]
 157     unsafe fn copy(&self, dst: usize, src: usize, len: usize) {
 158         debug_assert!(dst + len <= self.cap(),
 159                       "cpy dst={} src={} len={} cap={}",
 160                       dst,
 161                       src,
 162                       len,
 163                       self.cap());
 164         debug_assert!(src + len <= self.cap(),
 165                       "cpy dst={} src={} len={} cap={}",
 166                       dst,
 167                       src,
 168                       len,
 169                       self.cap());
 170         ptr::copy(self.ptr().offset(src as isize),
 171                   self.ptr().offset(dst as isize),
 172                   len);
 173     }
 174
 175     /// Copies a contiguous block of memory len long from src to dst
 176     #[inline]
 177     unsafe fn copy_nonoverlapping(&self, dst: usize, src: usize, len: usize) {
 178         debug_assert!(dst + len <= self.cap(),
 179                       "cno dst={} src={} len={} cap={}",
 180                       dst,
 181                       src,
 182                       len,
 183                       self.cap());
 184         debug_assert!(src + len <= self.cap(),
 185                       "cno dst={} src={} len={} cap={}",
 186                       dst,
 187                       src,
 188                       len,
 189                       self.cap());
 190         ptr::copy_nonoverlapping(self.ptr().offset(src as isize),
 191                                  self.ptr().offset(dst as isize),
 192                                  len);
 193     }
 194
 195     /// Copies a potentially wrapping block of memory len long from src to dest.
 196     /// (abs(dst - src) + len) must be no larger than cap() (There must be at
 197     /// most one continuous overlapping region between src and dest).
 198     unsafe fn wrap_copy(&self, dst: usize, src: usize, len: usize) {
 199         #[allow(dead_code)]
 200         fn diff(a: usize, b: usize) -> usize {
 201             if a <= b {
 202                 b - a
 203             } else {
 204                 a - b
 205             }
 206         }
 207         debug_assert!(cmp::min(diff(dst, src), self.cap() - diff(dst, src)) + len <= self.cap(),
 208                       "wrc dst={} src={} len={} cap={}",
 209                       dst,
 210                       src,
 211                       len,
 212                       self.cap());
 213
 214         if src == dst || len == 0 {
 215             return;
 216         }
 217
 218         let dst_after_src = self.wrap_sub(dst, src) < len;
 219
 220         let src_pre_wrap_len = self.cap() - src;
 221         let dst_pre_wrap_len = self.cap() - dst;
 222         let src_wraps = src_pre_wrap_len < len;
 223         let dst_wraps = dst_pre_wrap_len < len;
 224
 225         match (dst_after_src, src_wraps, dst_wraps) {
 226             (_, false, false) => {
 227                 // src doesn't wrap, dst doesn't wrap
 228                 //
 229                 //        S . . .
 230                 // 1 [_ _ A A B B C C _]
 231                 // 2 [_ _ A A A A B B _]
 232                 //            D . . .
 233                 //
 234                 self.copy(dst, src, len);
 235             }
 236             (false, false, true) => {
 237                 // dst before src, src doesn't wrap, dst wraps
 238                 //
 239                 //    S . . .
 240                 // 1 [A A B B _ _ _ C C]
 241                 // 2 [A A B B _ _ _ A A]
 242                 // 3 [B B B B _ _ _ A A]
 243                 //    . .           D .
 244                 //
 245                 self.copy(dst, src, dst_pre_wrap_len);
 246                 self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len);
 247             }
 248             (true, false, true) => {
 249                 // src before dst, src doesn't wrap, dst wraps
 250                 //
 251                 //              S . . .
 252                 // 1 [C C _ _ _ A A B B]
 253                 // 2 [B B _ _ _ A A B B]
 254                 // 3 [B B _ _ _ A A A A]
 255                 //    . .           D .
 256                 //
 257                 self.copy(0, src + dst_pre_wrap_len, len - dst_pre_wrap_len);
 258                 self.copy(dst, src, dst_pre_wrap_len);
 259             }
 260             (false, true, false) => {
 261                 // dst before src, src wraps, dst doesn't wrap
 262                 //
 263                 //    . .           S .
 264                 // 1 [C C _ _ _ A A B B]
 265                 // 2 [C C _ _ _ B B B B]
 266                 // 3 [C C _ _ _ B B C C]
 267                 //              D . . .
 268                 //
 269                 self.copy(dst, src, src_pre_wrap_len);
 270                 self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len);
 271             }
 272             (true, true, false) => {
 273                 // src before dst, src wraps, dst doesn't wrap
 274                 //
 275                 //    . .           S .
 276                 // 1 [A A B B _ _ _ C C]
 277                 // 2 [A A A A _ _ _ C C]
 278                 // 3 [C C A A _ _ _ C C]
 279                 //    D . . .
 280                 //
 281                 self.copy(dst + src_pre_wrap_len, 0, len - src_pre_wrap_len);
 282                 self.copy(dst, src, src_pre_wrap_len);
 283             }
 284             (false, true, true) => {
 285                 // dst before src, src wraps, dst wraps
 286                 //
 287                 //    . . .         S .
 288                 // 1 [A B C D _ E F G H]
 289                 // 2 [A B C D _ E G H H]
 290                 // 3 [A B C D _ E G H A]
 291                 // 4 [B C C D _ E G H A]
 292                 //    . .         D . .
 293                 //
 294                 debug_assert!(dst_pre_wrap_len > src_pre_wrap_len);
 295                 let delta = dst_pre_wrap_len - src_pre_wrap_len;
 296                 self.copy(dst, src, src_pre_wrap_len);
 297                 self.copy(dst + src_pre_wrap_len, 0, delta);
 298                 self.copy(0, delta, len - dst_pre_wrap_len);
 299             }
 300             (true, true, true) => {
 301                 // src before dst, src wraps, dst wraps
 302                 //
 303                 //    . .         S . .
 304                 // 1 [A B C D _ E F G H]
 305                 // 2 [A A B D _ E F G H]
 306                 // 3 [H A B D _ E F G H]
 307                 // 4 [H A B D _ E F F G]
 308                 //    . . .         D .
 309                 //
 310                 debug_assert!(src_pre_wrap_len > dst_pre_wrap_len);
 311                 let delta = src_pre_wrap_len - dst_pre_wrap_len;
 312                 self.copy(delta, 0, len - src_pre_wrap_len);
 313                 self.copy(0, self.cap() - delta, delta);
 314                 self.copy(dst, src, dst_pre_wrap_len);
 315             }
 316         }
 317     }
 318
 319     /// Frobs the head and tail sections around to handle the fact that we
 320     /// just reallocated. Unsafe because it trusts old_cap.
 321     #[inline]
 322     unsafe fn handle_cap_increase(&mut self, old_cap: usize) {
 323         let new_cap = self.cap();
 324
 325         // Move the shortest contiguous section of the ring buffer
 326         //    T             H
 327         //   [o o o o o o o . ]
 328         //    T             H
 329         // A [o o o o o o o . . . . . . . . . ]
 330         //        H T
 331         //   [o o . o o o o o ]
 332         //          T             H
 333         // B [. . . o o o o o o o . . . . . . ]
 334         //              H T
 335         //   [o o o o o . o o ]
 336         //              H                 T
 337         // C [o o o o o . . . . . . . . . o o ]
 338
 339         if self.tail <= self.head {
 340             // A
 341             // Nop
 342         } else if self.head < old_cap - self.tail {
 343             // B
 344             self.copy_nonoverlapping(old_cap, 0, self.head);
 345             self.head += old_cap;
 346             debug_assert!(self.head > self.tail);
 347         } else {
 348             // C
 349             let new_tail = new_cap - (old_cap - self.tail);
 350             self.copy_nonoverlapping(new_tail, self.tail, old_cap - self.tail);
 351             self.tail = new_tail;
 352             debug_assert!(self.head < self.tail);
 353         }
 354         debug_assert!(self.head < self.cap());
 355         debug_assert!(self.tail < self.cap());
 356         debug_assert!(self.cap().count_ones() == 1);
 357     }
 358 }
 359
 360 impl<T> VecDeque<T> {
 361     /// Creates an empty `VecDeque`.
 362     #[stable(feature = "rust1", since = "1.0.0")]
 363     pub fn new() -> VecDeque<T> {
 364         VecDeque::with_capacity(INITIAL_CAPACITY)
 365     }
 366
 367     /// Creates an empty `VecDeque` with space for at least `n` elements.
 368     #[stable(feature = "rust1", since = "1.0.0")]
 369     pub fn with_capacity(n: usize) -> VecDeque<T> {
 370         // +1 since the ringbuffer always leaves one space empty
 371         let cap = cmp::max(n + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
 372         assert!(cap > n, "capacity overflow");
 373
 374         VecDeque {
 375             tail: 0,
 376             head: 0,
 377             buf: RawVec::with_capacity(cap),
 378         }
 379     }
 380
 381     /// Retrieves an element in the `VecDeque` by index.
 382     ///
 383     /// # Examples
 384     ///
 385     /// ```
 386     /// use std::collections::VecDeque;
 387     ///
 388     /// let mut buf = VecDeque::new();
 389     /// buf.push_back(3);
 390     /// buf.push_back(4);
 391     /// buf.push_back(5);
 392     /// assert_eq!(buf.get(1), Some(&4));
 393     /// ```
 394     #[stable(feature = "rust1", since = "1.0.0")]
 395     pub fn get(&self, index: usize) -> Option<&T> {
 396         if index < self.len() {
 397             let idx = self.wrap_add(self.tail, index);
 398             unsafe { Some(&*self.ptr().offset(idx as isize)) }
 399         } else {
 400             None
 401         }
 402     }
 403
 404     /// Retrieves an element in the `VecDeque` mutably by index.
 405     ///
 406     /// # Examples
 407     ///
 408     /// ```
 409     /// use std::collections::VecDeque;
 410     ///
 411     /// let mut buf = VecDeque::new();
 412     /// buf.push_back(3);
 413     /// buf.push_back(4);
 414     /// buf.push_back(5);
 415     /// if let Some(elem) = buf.get_mut(1) {
 416     ///     *elem = 7;
 417     /// }
 418     ///
 419     /// assert_eq!(buf[1], 7);
 420     /// ```
 421     #[stable(feature = "rust1", since = "1.0.0")]
 422     pub fn get_mut(&mut self, index: usize) -> Option<&mut T> {
 423         if index < self.len() {
 424             let idx = self.wrap_add(self.tail, index);
 425             unsafe { Some(&mut *self.ptr().offset(idx as isize)) }
 426         } else {
 427             None
 428         }
 429     }
 430
 431     /// Swaps elements at indices `i` and `j`.
 432     ///
 433     /// `i` and `j` may be equal.
 434     ///
 435     /// Fails if there is no element with either index.
 436     ///
 437     /// # Examples
 438     ///
 439     /// ```
 440     /// use std::collections::VecDeque;
 441     ///
 442     /// let mut buf = VecDeque::new();
 443     /// buf.push_back(3);
 444     /// buf.push_back(4);
 445     /// buf.push_back(5);
 446     /// buf.swap(0, 2);
 447     /// assert_eq!(buf[0], 5);
 448     /// assert_eq!(buf[2], 3);
 449     /// ```
 450     #[stable(feature = "rust1", since = "1.0.0")]
 451     pub fn swap(&mut self, i: usize, j: usize) {
 452         assert!(i < self.len());
 453         assert!(j < self.len());
 454         let ri = self.wrap_add(self.tail, i);
 455         let rj = self.wrap_add(self.tail, j);
 456         unsafe {
 457             ptr::swap(self.ptr().offset(ri as isize),
 458                       self.ptr().offset(rj as isize))
 459         }
 460     }
 461
 462     /// Returns the number of elements the `VecDeque` can hold without
 463     /// reallocating.
 464     ///
 465     /// # Examples
 466     ///
 467     /// ```
 468     /// use std::collections::VecDeque;
 469     ///
 470     /// let buf: VecDeque<i32> = VecDeque::with_capacity(10);
 471     /// assert!(buf.capacity() >= 10);
 472     /// ```
 473     #[inline]
 474     #[stable(feature = "rust1", since = "1.0.0")]
 475     pub fn capacity(&self) -> usize {
 476         self.cap() - 1
 477     }
 478
 479     /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
 480     /// given `VecDeque`. Does nothing if the capacity is already sufficient.
 481     ///
 482     /// Note that the allocator may give the collection more space than it requests. Therefore
 483     /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
 484     /// insertions are expected.
 485     ///
 486     /// # Panics
 487     ///
 488     /// Panics if the new capacity overflows `usize`.
 489     ///
 490     /// # Examples
 491     ///
 492     /// ```
 493     /// use std::collections::VecDeque;
 494     ///
 495     /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
 496     /// buf.reserve_exact(10);
 497     /// assert!(buf.capacity() >= 11);
 498     /// ```
 499     #[stable(feature = "rust1", since = "1.0.0")]
 500     pub fn reserve_exact(&mut self, additional: usize) {
 501         self.reserve(additional);
 502     }
 503
 504     /// Reserves capacity for at least `additional` more elements to be inserted in the given
 505     /// `VecDeque`. The collection may reserve more space to avoid frequent reallocations.
 506     ///
 507     /// # Panics
 508     ///
 509     /// Panics if the new capacity overflows `usize`.
 510     ///
 511     /// # Examples
 512     ///
 513     /// ```
 514     /// use std::collections::VecDeque;
 515     ///
 516     /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
 517     /// buf.reserve(10);
 518     /// assert!(buf.capacity() >= 11);
 519     /// ```
 520     #[stable(feature = "rust1", since = "1.0.0")]
 521     pub fn reserve(&mut self, additional: usize) {
 522         let old_cap = self.cap();
 523         let used_cap = self.len() + 1;
 524         let new_cap = used_cap.checked_add(additional)
 525                               .and_then(|needed_cap| needed_cap.checked_next_power_of_two())
 526                               .expect("capacity overflow");
 527
 528         if new_cap > self.capacity() {
 529             self.buf.reserve_exact(used_cap, new_cap - used_cap);
 530             unsafe {
 531                 self.handle_cap_increase(old_cap);
 532             }
 533         }
 534     }
 535
 536     /// Shrinks the capacity of the `VecDeque` as much as possible.
 537     ///
 538     /// It will drop down as close as possible to the length but the allocator may still inform the
 539     /// `VecDeque` that there is space for a few more elements.
 540     ///
 541     /// # Examples
 542     ///
 543     /// ```
 544     /// use std::collections::VecDeque;
 545     ///
 546     /// let mut buf = VecDeque::with_capacity(15);
 547     /// buf.extend(0..4);
 548     /// assert_eq!(buf.capacity(), 15);
 549     /// buf.shrink_to_fit();
 550     /// assert!(buf.capacity() >= 4);
 551     /// ```
 552     #[stable(feature = "deque_extras_15", since = "1.5.0")]
 553     pub fn shrink_to_fit(&mut self) {
 554         // +1 since the ringbuffer always leaves one space empty
 555         // len + 1 can't overflow for an existing, well-formed ringbuffer.
 556         let target_cap = cmp::max(self.len() + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
 557         if target_cap < self.cap() {
 558             // There are three cases of interest:
 559             //   All elements are out of desired bounds
 560             //   Elements are contiguous, and head is out of desired bounds
 561             //   Elements are discontiguous, and tail is out of desired bounds
 562             //
 563             // At all other times, element positions are unaffected.
 564             //
 565             // Indicates that elements at the head should be moved.
 566             let head_outside = self.head == 0 || self.head >= target_cap;
 567             // Move elements from out of desired bounds (positions after target_cap)
 568             if self.tail >= target_cap && head_outside {
 569                 //                    T             H
 570                 //   [. . . . . . . . o o o o o o o . ]
 571                 //    T             H
 572                 //   [o o o o o o o . ]
 573                 unsafe {
 574                     self.copy_nonoverlapping(0, self.tail, self.len());
 575                 }
 576                 self.head = self.len();
 577                 self.tail = 0;
 578             } else if self.tail != 0 && self.tail < target_cap && head_outside {
 579                 //          T             H
 580                 //   [. . . o o o o o o o . . . . . . ]
 581                 //        H T
 582                 //   [o o . o o o o o ]
 583                 let len = self.wrap_sub(self.head, target_cap);
 584                 unsafe {
 585                     self.copy_nonoverlapping(0, target_cap, len);
 586                 }
 587                 self.head = len;
 588                 debug_assert!(self.head < self.tail);
 589             } else if self.tail >= target_cap {
 590                 //              H                 T
 591                 //   [o o o o o . . . . . . . . . o o ]
 592                 //              H T
 593                 //   [o o o o o . o o ]
 594                 debug_assert!(self.wrap_sub(self.head, 1) < target_cap);
 595                 let len = self.cap() - self.tail;
 596                 let new_tail = target_cap - len;
 597                 unsafe {
 598                     self.copy_nonoverlapping(new_tail, self.tail, len);
 599                 }
 600                 self.tail = new_tail;
 601                 debug_assert!(self.head < self.tail);
 602             }
 603
 604             self.buf.shrink_to_fit(target_cap);
 605
 606             debug_assert!(self.head < self.cap());
 607             debug_assert!(self.tail < self.cap());
 608             debug_assert!(self.cap().count_ones() == 1);
 609         }
 610     }
 611
 612     /// Shortens a `VecDeque`, dropping excess elements from the back.
 613     ///
 614     /// If `len` is greater than the `VecDeque`'s current length, this has no
 615     /// effect.
 616     ///
 617     /// # Examples
 618     ///
 619     /// ```
 620     /// #![feature(deque_extras)]
 621     ///
 622     /// use std::collections::VecDeque;
 623     ///
 624     /// let mut buf = VecDeque::new();
 625     /// buf.push_back(5);
 626     /// buf.push_back(10);
 627     /// buf.push_back(15);
 628     /// buf.truncate(1);
 629     /// assert_eq!(buf.len(), 1);
 630     /// assert_eq!(Some(&5), buf.get(0));
 631     /// ```
 632     #[unstable(feature = "deque_extras",
 633                reason = "matches collection reform specification; waiting on panic semantics",
 634                issue = "27788")]
 635     pub fn truncate(&mut self, len: usize) {
 636         for _ in len..self.len() {
 637             self.pop_back();
 638         }
 639     }
 640
 641     /// Returns a front-to-back iterator.
 642     ///
 643     /// # Examples
 644     ///
 645     /// ```
 646     /// use std::collections::VecDeque;
 647     ///
 648     /// let mut buf = VecDeque::new();
 649     /// buf.push_back(5);
 650     /// buf.push_back(3);
 651     /// buf.push_back(4);
 652     /// let b: &[_] = &[&5, &3, &4];
 653     /// let c: Vec<&i32> = buf.iter().collect();
 654     /// assert_eq!(&c[..], b);
 655     /// ```
 656     #[stable(feature = "rust1", since = "1.0.0")]
 657     pub fn iter(&self) -> Iter<T> {
 658         Iter {
 659             tail: self.tail,
 660             head: self.head,
 661             ring: unsafe { self.buffer_as_slice() },
 662         }
 663     }
 664
 665     /// Returns a front-to-back iterator that returns mutable references.
 666     ///
 667     /// # Examples
 668     ///
 669     /// ```
 670     /// use std::collections::VecDeque;
 671     ///
 672     /// let mut buf = VecDeque::new();
 673     /// buf.push_back(5);
 674     /// buf.push_back(3);
 675     /// buf.push_back(4);
 676     /// for num in buf.iter_mut() {
 677     ///     *num = *num - 2;
 678     /// }
 679     /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
 680     /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b);
 681     /// ```
 682     #[stable(feature = "rust1", since = "1.0.0")]
 683     pub fn iter_mut(&mut self) -> IterMut<T> {
 684         IterMut {
 685             tail: self.tail,
 686             head: self.head,
 687             ring: unsafe { self.buffer_as_mut_slice() },
 688         }
 689     }
 690
 691     /// Returns a pair of slices which contain, in order, the contents of the
 692     /// `VecDeque`.
 693     #[inline]
 694     #[stable(feature = "deque_extras_15", since = "1.5.0")]
 695     pub fn as_slices(&self) -> (&[T], &[T]) {
 696         unsafe {
 697             let contiguous = self.is_contiguous();
 698             let buf = self.buffer_as_slice();
 699             if contiguous {
 700                 let (empty, buf) = buf.split_at(0);
 701                 (&buf[self.tail..self.head], empty)
 702             } else {
 703                 let (mid, right) = buf.split_at(self.tail);
 704                 let (left, _) = mid.split_at(self.head);
 705                 (right, left)
 706             }
 707         }
 708     }
 709
 710     /// Returns a pair of slices which contain, in order, the contents of the
 711     /// `VecDeque`.
 712     #[inline]
 713     #[stable(feature = "deque_extras_15", since = "1.5.0")]
 714     pub fn as_mut_slices(&mut self) -> (&mut [T], &mut [T]) {
 715         unsafe {
 716             let contiguous = self.is_contiguous();
 717             let head = self.head;
 718             let tail = self.tail;
 719             let buf = self.buffer_as_mut_slice();
 720
 721             if contiguous {
 722                 let (empty, buf) = buf.split_at_mut(0);
 723                 (&mut buf[tail..head], empty)
 724             } else {
 725                 let (mid, right) = buf.split_at_mut(tail);
 726                 let (left, _) = mid.split_at_mut(head);
 727
 728                 (right, left)
 729             }
 730         }
 731     }
 732
 733     /// Returns the number of elements in the `VecDeque`.
 734     ///
 735     /// # Examples
 736     ///
 737     /// ```
 738     /// use std::collections::VecDeque;
 739     ///
 740     /// let mut v = VecDeque::new();
 741     /// assert_eq!(v.len(), 0);
 742     /// v.push_back(1);
 743     /// assert_eq!(v.len(), 1);
 744     /// ```
 745     #[stable(feature = "rust1", since = "1.0.0")]
 746     pub fn len(&self) -> usize {
 747         count(self.tail, self.head, self.cap())
 748     }
 749
 750     /// Returns true if the buffer contains no elements
 751     ///
 752     /// # Examples
 753     ///
 754     /// ```
 755     /// use std::collections::VecDeque;
 756     ///
 757     /// let mut v = VecDeque::new();
 758     /// assert!(v.is_empty());
 759     /// v.push_front(1);
 760     /// assert!(!v.is_empty());
 761     /// ```
 762     #[stable(feature = "rust1", since = "1.0.0")]
 763     pub fn is_empty(&self) -> bool {
 764         self.len() == 0
 765     }
 766
 767     /// Create a draining iterator that removes the specified range in the
 768     /// `VecDeque` and yields the removed items.
 769     ///
 770     /// Note 1: The element range is removed even if the iterator is not
 771     /// consumed until the end.
 772     ///
 773     /// Note 2: It is unspecified how many elements are removed from the deque,
 774     /// if the `Drain` value is not dropped, but the borrow it holds expires
 775     /// (eg. due to mem::forget).
 776     ///
 777     /// # Panics
 778     ///
 779     /// Panics if the starting point is greater than the end point or if
 780     /// the end point is greater than the length of the vector.
 781     ///
 782     /// # Examples
 783     ///
 784     /// ```
 785     /// use std::collections::VecDeque;
 786
 787     /// let mut v: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
 788     /// assert_eq!(vec![3].into_iter().collect::<VecDeque<_>>(), v.drain(2..).collect());
 789     /// assert_eq!(vec![1, 2].into_iter().collect::<VecDeque<_>>(), v);
 790     ///
 791     /// // A full range clears all contents
 792     /// v.drain(..);
 793     /// assert!(v.is_empty());
 794     /// ```
 795     #[inline]
 796     #[stable(feature = "drain", since = "1.6.0")]
 797     pub fn drain<R>(&mut self, range: R) -> Drain<T>
 798         where R: RangeArgument<usize>
 799     {
 800         // Memory safety
 801         //
 802         // When the Drain is first created, the source deque is shortened to
 803         // make sure no uninitialized or moved-from elements are accessible at
 804         // all if the Drain's destructor never gets to run.
 805         //
 806         // Drain will ptr::read out the values to remove.
 807         // When finished, the remaining data will be copied back to cover the hole,
 808         // and the head/tail values will be restored correctly.
 809         //
 810         let len = self.len();
 811         let start = *range.start().unwrap_or(&0);
 812         let end = *range.end().unwrap_or(&len);
 813         assert!(start <= end, "drain lower bound was too large");
 814         assert!(end <= len, "drain upper bound was too large");
 815
 816         // The deque's elements are parted into three segments:
 817         // * self.tail  -> drain_tail
 818         // * drain_tail -> drain_head
 819         // * drain_head -> self.head
 820         //
 821         // T = self.tail; H = self.head; t = drain_tail; h = drain_head
 822         //
 823         // We store drain_tail as self.head, and drain_head and self.head as
 824         // after_tail and after_head respectively on the Drain. This also
 825         // truncates the effective array such that if the Drain is leaked, we
 826         // have forgotten about the potentially moved values after the start of
 827         // the drain.
 828         //
 829         //        T   t   h   H
 830         // [. . . o o x x o o . . .]
 831         //
 832         let drain_tail = self.wrap_add(self.tail, start);
 833         let drain_head = self.wrap_add(self.tail, end);
 834         let head = self.head;
 835
 836         // "forget" about the values after the start of the drain until after
 837         // the drain is complete and the Drain destructor is run.
 838         self.head = drain_tail;
 839
 840         Drain {
 841             deque: self as *mut _,
 842             after_tail: drain_head,
 843             after_head: head,
 844             iter: Iter {
 845                 tail: drain_tail,
 846                 head: drain_head,
 847                 ring: unsafe { self.buffer_as_mut_slice() },
 848             },
 849         }
 850     }
 851
 852     /// Clears the buffer, removing all values.
 853     ///
 854     /// # Examples
 855     ///
 856     /// ```
 857     /// use std::collections::VecDeque;
 858     ///
 859     /// let mut v = VecDeque::new();
 860     /// v.push_back(1);
 861     /// v.clear();
 862     /// assert!(v.is_empty());
 863     /// ```
 864     #[stable(feature = "rust1", since = "1.0.0")]
 865     #[inline]
 866     pub fn clear(&mut self) {
 867         self.drain(..);
 868     }
 869
 870     /// Provides a reference to the front element, or `None` if the sequence is
 871     /// empty.
 872     ///
 873     /// # Examples
 874     ///
 875     /// ```
 876     /// use std::collections::VecDeque;
 877     ///
 878     /// let mut d = VecDeque::new();
 879     /// assert_eq!(d.front(), None);
 880     ///
 881     /// d.push_back(1);
 882     /// d.push_back(2);
 883     /// assert_eq!(d.front(), Some(&1));
 884     /// ```
 885     #[stable(feature = "rust1", since = "1.0.0")]
 886     pub fn front(&self) -> Option<&T> {
 887         if !self.is_empty() {
 888             Some(&self[0])
 889         } else {
 890             None
 891         }
 892     }
 893
 894     /// Provides a mutable reference to the front element, or `None` if the
 895     /// sequence is empty.
 896     ///
 897     /// # Examples
 898     ///
 899     /// ```
 900     /// use std::collections::VecDeque;
 901     ///
 902     /// let mut d = VecDeque::new();
 903     /// assert_eq!(d.front_mut(), None);
 904     ///
 905     /// d.push_back(1);
 906     /// d.push_back(2);
 907     /// match d.front_mut() {
 908     ///     Some(x) => *x = 9,
 909     ///     None => (),
 910     /// }
 911     /// assert_eq!(d.front(), Some(&9));
 912     /// ```
 913     #[stable(feature = "rust1", since = "1.0.0")]
 914     pub fn front_mut(&mut self) -> Option<&mut T> {
 915         if !self.is_empty() {
 916             Some(&mut self[0])
 917         } else {
 918             None
 919         }
 920     }
 921
 922     /// Provides a reference to the back element, or `None` if the sequence is
 923     /// empty.
 924     ///
 925     /// # Examples
 926     ///
 927     /// ```
 928     /// use std::collections::VecDeque;
 929     ///
 930     /// let mut d = VecDeque::new();
 931     /// assert_eq!(d.back(), None);
 932     ///
 933     /// d.push_back(1);
 934     /// d.push_back(2);
 935     /// assert_eq!(d.back(), Some(&2));
 936     /// ```
 937     #[stable(feature = "rust1", since = "1.0.0")]
 938     pub fn back(&self) -> Option<&T> {
 939         if !self.is_empty() {
 940             Some(&self[self.len() - 1])
 941         } else {
 942             None
 943         }
 944     }
 945
 946     /// Provides a mutable reference to the back element, or `None` if the
 947     /// sequence is empty.
 948     ///
 949     /// # Examples
 950     ///
 951     /// ```
 952     /// use std::collections::VecDeque;
 953     ///
 954     /// let mut d = VecDeque::new();
 955     /// assert_eq!(d.back(), None);
 956     ///
 957     /// d.push_back(1);
 958     /// d.push_back(2);
 959     /// match d.back_mut() {
 960     ///     Some(x) => *x = 9,
 961     ///     None => (),
 962     /// }
 963     /// assert_eq!(d.back(), Some(&9));
 964     /// ```
 965     #[stable(feature = "rust1", since = "1.0.0")]
 966     pub fn back_mut(&mut self) -> Option<&mut T> {
 967         let len = self.len();
 968         if !self.is_empty() {
 969             Some(&mut self[len - 1])
 970         } else {
 971             None
 972         }
 973     }
 974
 975     /// Removes the first element and returns it, or `None` if the sequence is
 976     /// empty.
 977     ///
 978     /// # Examples
 979     ///
 980     /// ```
 981     /// use std::collections::VecDeque;
 982     ///
 983     /// let mut d = VecDeque::new();
 984     /// d.push_back(1);
 985     /// d.push_back(2);
 986     ///
 987     /// assert_eq!(d.pop_front(), Some(1));
 988     /// assert_eq!(d.pop_front(), Some(2));
 989     /// assert_eq!(d.pop_front(), None);
 990     /// ```
 991     #[stable(feature = "rust1", since = "1.0.0")]
 992     pub fn pop_front(&mut self) -> Option<T> {
 993         if self.is_empty() {
 994             None
 995         } else {
 996             let tail = self.tail;
 997             self.tail = self.wrap_add(self.tail, 1);
 998             unsafe { Some(self.buffer_read(tail)) }
 999         }
1000     }
1001
1002     /// Inserts an element first in the sequence.
1003     ///
1004     /// # Examples
1005     ///
1006     /// ```
1007     /// use std::collections::VecDeque;
1008     ///
1009     /// let mut d = VecDeque::new();
1010     /// d.push_front(1);
1011     /// d.push_front(2);
1012     /// assert_eq!(d.front(), Some(&2));
1013     /// ```
1014     #[stable(feature = "rust1", since = "1.0.0")]
1015     pub fn push_front(&mut self, value: T) {
1016         if self.is_full() {
1017             let old_cap = self.cap();
1018             self.buf.double();
1019             unsafe {
1020                 self.handle_cap_increase(old_cap);
1021             }
1022             debug_assert!(!self.is_full());
1023         }
1024
1025         self.tail = self.wrap_sub(self.tail, 1);
1026         let tail = self.tail;
1027         unsafe {
1028             self.buffer_write(tail, value);
1029         }
1030     }
1031
1032     /// Appends an element to the back of a buffer
1033     ///
1034     /// # Examples
1035     ///
1036     /// ```
1037     /// use std::collections::VecDeque;
1038     ///
1039     /// let mut buf = VecDeque::new();
1040     /// buf.push_back(1);
1041     /// buf.push_back(3);
1042     /// assert_eq!(3, *buf.back().unwrap());
1043     /// ```
1044     #[stable(feature = "rust1", since = "1.0.0")]
1045     pub fn push_back(&mut self, value: T) {
1046         if self.is_full() {
1047             let old_cap = self.cap();
1048             self.buf.double();
1049             unsafe {
1050                 self.handle_cap_increase(old_cap);
1051             }
1052             debug_assert!(!self.is_full());
1053         }
1054
1055         let head = self.head;
1056         self.head = self.wrap_add(self.head, 1);
1057         unsafe { self.buffer_write(head, value) }
1058     }
1059
1060     /// Removes the last element from a buffer and returns it, or `None` if
1061     /// it is empty.
1062     ///
1063     /// # Examples
1064     ///
1065     /// ```
1066     /// use std::collections::VecDeque;
1067     ///
1068     /// let mut buf = VecDeque::new();
1069     /// assert_eq!(buf.pop_back(), None);
1070     /// buf.push_back(1);
1071     /// buf.push_back(3);
1072     /// assert_eq!(buf.pop_back(), Some(3));
1073     /// ```
1074     #[stable(feature = "rust1", since = "1.0.0")]
1075     pub fn pop_back(&mut self) -> Option<T> {
1076         if self.is_empty() {
1077             None
1078         } else {
1079             self.head = self.wrap_sub(self.head, 1);
1080             let head = self.head;
1081             unsafe { Some(self.buffer_read(head)) }
1082         }
1083     }
1084
1085     #[inline]
1086     fn is_contiguous(&self) -> bool {
1087         self.tail <= self.head
1088     }
1089
1090     /// Removes an element from anywhere in the `VecDeque` and returns it, replacing it with the
1091     /// last element.
1092     ///
1093     /// This does not preserve ordering, but is O(1).
1094     ///
1095     /// Returns `None` if `index` is out of bounds.
1096     ///
1097     /// # Examples
1098     ///
1099     /// ```
1100     /// use std::collections::VecDeque;
1101     ///
1102     /// let mut buf = VecDeque::new();
1103     /// assert_eq!(buf.swap_remove_back(0), None);
1104     /// buf.push_back(1);
1105     /// buf.push_back(2);
1106     /// buf.push_back(3);
1107     ///
1108     /// assert_eq!(buf.swap_remove_back(0), Some(1));
1109     /// assert_eq!(buf.len(), 2);
1110     /// assert_eq!(buf[0], 3);
1111     /// assert_eq!(buf[1], 2);
1112     /// ```
1113     #[stable(feature = "deque_extras_15", since = "1.5.0")]
1114     pub fn swap_remove_back(&mut self, index: usize) -> Option<T> {
1115         let length = self.len();
1116         if length > 0 && index < length - 1 {
1117             self.swap(index, length - 1);
1118         } else if index >= length {
1119             return None;
1120         }
1121         self.pop_back()
1122     }
1123
1124     /// Removes an element from anywhere in the `VecDeque` and returns it,
1125     /// replacing it with the first element.
1126     ///
1127     /// This does not preserve ordering, but is O(1).
1128     ///
1129     /// Returns `None` if `index` is out of bounds.
1130     ///
1131     /// # Examples
1132     ///
1133     /// ```
1134     /// use std::collections::VecDeque;
1135     ///
1136     /// let mut buf = VecDeque::new();
1137     /// assert_eq!(buf.swap_remove_front(0), None);
1138     /// buf.push_back(1);
1139     /// buf.push_back(2);
1140     /// buf.push_back(3);
1141     ///
1142     /// assert_eq!(buf.swap_remove_front(2), Some(3));
1143     /// assert_eq!(buf.len(), 2);
1144     /// assert_eq!(buf[0], 2);
1145     /// assert_eq!(buf[1], 1);
1146     /// ```
1147     #[stable(feature = "deque_extras_15", since = "1.5.0")]
1148     pub fn swap_remove_front(&mut self, index: usize) -> Option<T> {
1149         let length = self.len();
1150         if length > 0 && index < length && index != 0 {
1151             self.swap(index, 0);
1152         } else if index >= length {
1153             return None;
1154         }
1155         self.pop_front()
1156     }
1157
1158     /// Inserts an element at `index` within the `VecDeque`. Whichever
1159     /// end is closer to the insertion point will be moved to make room,
1160     /// and all the affected elements will be moved to new positions.
1161     ///
1162     /// # Panics
1163     ///
1164     /// Panics if `index` is greater than `VecDeque`'s length
1165     ///
1166     /// # Examples
1167     /// ```
1168     /// use std::collections::VecDeque;
1169     ///
1170     /// let mut buf = VecDeque::new();
1171     /// buf.push_back(10);
1172     /// buf.push_back(12);
1173     /// buf.insert(1, 11);
1174     /// assert_eq!(Some(&11), buf.get(1));
1175     /// ```
1176     #[stable(feature = "deque_extras_15", since = "1.5.0")]
1177     pub fn insert(&mut self, index: usize, value: T) {
1178         assert!(index <= self.len(), "index out of bounds");
1179         if self.is_full() {
1180             let old_cap = self.cap();
1181             self.buf.double();
1182             unsafe {
1183                 self.handle_cap_increase(old_cap);
1184             }
1185             debug_assert!(!self.is_full());
1186         }
1187
1188         // Move the least number of elements in the ring buffer and insert
1189         // the given object
1190         //
1191         // At most len/2 - 1 elements will be moved. O(min(n, n-i))
1192         //
1193         // There are three main cases:
1194         //  Elements are contiguous
1195         //      - special case when tail is 0
1196         //  Elements are discontiguous and the insert is in the tail section
1197         //  Elements are discontiguous and the insert is in the head section
1198         //
1199         // For each of those there are two more cases:
1200         //  Insert is closer to tail
1201         //  Insert is closer to head
1202         //
1203         // Key: H - self.head
1204         //      T - self.tail
1205         //      o - Valid element
1206         //      I - Insertion element
1207         //      A - The element that should be after the insertion point
1208         //      M - Indicates element was moved
1209
1210         let idx = self.wrap_add(self.tail, index);
1211
1212         let distance_to_tail = index;
1213         let distance_to_head = self.len() - index;
1214
1215         let contiguous = self.is_contiguous();
1216
1217         match (contiguous,
1218                distance_to_tail <= distance_to_head,
1219                idx >= self.tail) {
1220             (true, true, _) if index == 0 => {
1221                 // push_front
1222                 //
1223                 //       T
1224                 //       I             H
1225                 //      [A o o o o o o . . . . . . . . .]
1226                 //
1227                 //                       H         T
1228                 //      [A o o o o o o o . . . . . I]
1229                 //
1230
1231                 self.tail = self.wrap_sub(self.tail, 1);
1232             }
1233             (true, true, _) => {
1234                 unsafe {
1235                     // contiguous, insert closer to tail:
1236                     //
1237                     //             T   I         H
1238                     //      [. . . o o A o o o o . . . . . .]
1239                     //
1240                     //           T               H
1241                     //      [. . o o I A o o o o . . . . . .]
1242                     //           M M
1243                     //
1244                     // contiguous, insert closer to tail and tail is 0:
1245                     //
1246                     //
1247                     //       T   I         H
1248                     //      [o o A o o o o . . . . . . . . .]
1249                     //
1250                     //                       H             T
1251                     //      [o I A o o o o o . . . . . . . o]
1252                     //       M                             M
1253
1254                     let new_tail = self.wrap_sub(self.tail, 1);
1255
1256                     self.copy(new_tail, self.tail, 1);
1257                     // Already moved the tail, so we only copy `index - 1` elements.
1258                     self.copy(self.tail, self.tail + 1, index - 1);
1259
1260                     self.tail = new_tail;
1261                 }
1262             }
1263             (true, false, _) => {
1264                 unsafe {
1265                     //  contiguous, insert closer to head:
1266                     //
1267                     //             T       I     H
1268                     //      [. . . o o o o A o o . . . . . .]
1269                     //
1270                     //             T               H
1271                     //      [. . . o o o o I A o o . . . . .]
1272                     //                       M M M
1273
1274                     self.copy(idx + 1, idx, self.head - idx);
1275                     self.head = self.wrap_add(self.head, 1);
1276                 }
1277             }
1278             (false, true, true) => {
1279                 unsafe {
1280                     // discontiguous, insert closer to tail, tail section:
1281                     //
1282                     //                   H         T   I
1283                     //      [o o o o o o . . . . . o o A o o]
1284                     //
1285                     //                   H       T
1286                     //      [o o o o o o . . . . o o I A o o]
1287                     //                           M M
1288
1289                     self.copy(self.tail - 1, self.tail, index);
1290                     self.tail -= 1;
1291                 }
1292             }
1293             (false, false, true) => {
1294                 unsafe {
1295                     // discontiguous, insert closer to head, tail section:
1296                     //
1297                     //           H             T         I
1298                     //      [o o . . . . . . . o o o o o A o]
1299                     //
1300                     //             H           T
1301                     //      [o o o . . . . . . o o o o o I A]
1302                     //       M M M                         M
1303
1304                     // copy elements up to new head
1305                     self.copy(1, 0, self.head);
1306
1307                     // copy last element into empty spot at bottom of buffer
1308                     self.copy(0, self.cap() - 1, 1);
1309
1310                     // move elements from idx to end forward not including ^ element
1311                     self.copy(idx + 1, idx, self.cap() - 1 - idx);
1312
1313                     self.head += 1;
1314                 }
1315             }
1316             (false, true, false) if idx == 0 => {
1317                 unsafe {
1318                     // discontiguous, insert is closer to tail, head section,
1319                     // and is at index zero in the internal buffer:
1320                     //
1321                     //       I                   H     T
1322                     //      [A o o o o o o o o o . . . o o o]
1323                     //
1324                     //                           H   T
1325                     //      [A o o o o o o o o o . . o o o I]
1326                     //                               M M M
1327
1328                     // copy elements up to new tail
1329                     self.copy(self.tail - 1, self.tail, self.cap() - self.tail);
1330
1331                     // copy last element into empty spot at bottom of buffer
1332                     self.copy(self.cap() - 1, 0, 1);
1333
1334                     self.tail -= 1;
1335                 }
1336             }
1337             (false, true, false) => {
1338                 unsafe {
1339                     // discontiguous, insert closer to tail, head section:
1340                     //
1341                     //             I             H     T
1342                     //      [o o o A o o o o o o . . . o o o]
1343                     //
1344                     //                           H   T
1345                     //      [o o I A o o o o o o . . o o o o]
1346                     //       M M                     M M M M
1347
1348                     // copy elements up to new tail
1349                     self.copy(self.tail - 1, self.tail, self.cap() - self.tail);
1350
1351                     // copy last element into empty spot at bottom of buffer
1352                     self.copy(self.cap() - 1, 0, 1);
1353
1354                     // move elements from idx-1 to end forward not including ^ element
1355                     self.copy(0, 1, idx - 1);
1356
1357                     self.tail -= 1;
1358                 }
1359             }
1360             (false, false, false) => {
1361                 unsafe {
1362                     // discontiguous, insert closer to head, head section:
1363                     //
1364                     //               I     H           T
1365                     //      [o o o o A o o . . . . . . o o o]
1366                     //
1367                     //                     H           T
1368                     //      [o o o o I A o o . . . . . o o o]
1369                     //                 M M M
1370
1371                     self.copy(idx + 1, idx, self.head - idx);
1372                     self.head += 1;
1373                 }
1374             }
1375         }
1376
1377         // tail might've been changed so we need to recalculate
1378         let new_idx = self.wrap_add(self.tail, index);
1379         unsafe {
1380             self.buffer_write(new_idx, value);
1381         }
1382     }
1383
1384     /// Removes and returns the element at `index` from the `VecDeque`.
1385     /// Whichever end is closer to the removal point will be moved to make
1386     /// room, and all the affected elements will be moved to new positions.
1387     /// Returns `None` if `index` is out of bounds.
1388     ///
1389     /// # Examples
1390     /// ```
1391     /// use std::collections::VecDeque;
1392     ///
1393     /// let mut buf = VecDeque::new();
1394     /// buf.push_back(1);
1395     /// buf.push_back(2);
1396     /// buf.push_back(3);
1397     ///
1398     /// assert_eq!(buf.remove(1), Some(2));
1399     /// assert_eq!(buf.get(1), Some(&3));
1400     /// ```
1401     #[stable(feature = "rust1", since = "1.0.0")]
1402     pub fn remove(&mut self, index: usize) -> Option<T> {
1403         if self.is_empty() || self.len() <= index {
1404             return None;
1405         }
1406
1407         // There are three main cases:
1408         //  Elements are contiguous
1409         //  Elements are discontiguous and the removal is in the tail section
1410         //  Elements are discontiguous and the removal is in the head section
1411         //      - special case when elements are technically contiguous,
1412         //        but self.head = 0
1413         //
1414         // For each of those there are two more cases:
1415         //  Insert is closer to tail
1416         //  Insert is closer to head
1417         //
1418         // Key: H - self.head
1419         //      T - self.tail
1420         //      o - Valid element
1421         //      x - Element marked for removal
1422         //      R - Indicates element that is being removed
1423         //      M - Indicates element was moved
1424
1425         let idx = self.wrap_add(self.tail, index);
1426
1427         let elem = unsafe { Some(self.buffer_read(idx)) };
1428
1429         let distance_to_tail = index;
1430         let distance_to_head = self.len() - index;
1431
1432         let contiguous = self.is_contiguous();
1433
1434         match (contiguous,
1435                distance_to_tail <= distance_to_head,
1436                idx >= self.tail) {
1437             (true, true, _) => {
1438                 unsafe {
1439                     // contiguous, remove closer to tail:
1440                     //
1441                     //             T   R         H
1442                     //      [. . . o o x o o o o . . . . . .]
1443                     //
1444                     //               T           H
1445                     //      [. . . . o o o o o o . . . . . .]
1446                     //               M M
1447
1448                     self.copy(self.tail + 1, self.tail, index);
1449                     self.tail += 1;
1450                 }
1451             }
1452             (true, false, _) => {
1453                 unsafe {
1454                     // contiguous, remove closer to head:
1455                     //
1456                     //             T       R     H
1457                     //      [. . . o o o o x o o . . . . . .]
1458                     //
1459                     //             T           H
1460                     //      [. . . o o o o o o . . . . . . .]
1461                     //                     M M
1462
1463                     self.copy(idx, idx + 1, self.head - idx - 1);
1464                     self.head -= 1;
1465                 }
1466             }
1467             (false, true, true) => {
1468                 unsafe {
1469                     // discontiguous, remove closer to tail, tail section:
1470                     //
1471                     //                   H         T   R
1472                     //      [o o o o o o . . . . . o o x o o]
1473                     //
1474                     //                   H           T
1475                     //      [o o o o o o . . . . . . o o o o]
1476                     //                               M M
1477
1478                     self.copy(self.tail + 1, self.tail, index);
1479                     self.tail = self.wrap_add(self.tail, 1);
1480                 }
1481             }
1482             (false, false, false) => {
1483                 unsafe {
1484                     // discontiguous, remove closer to head, head section:
1485                     //
1486                     //               R     H           T
1487                     //      [o o o o x o o . . . . . . o o o]
1488                     //
1489                     //                   H             T
1490                     //      [o o o o o o . . . . . . . o o o]
1491                     //               M M
1492
1493                     self.copy(idx, idx + 1, self.head - idx - 1);
1494                     self.head -= 1;
1495                 }
1496             }
1497             (false, false, true) => {
1498                 unsafe {
1499                     // discontiguous, remove closer to head, tail section:
1500                     //
1501                     //             H           T         R
1502                     //      [o o o . . . . . . o o o o o x o]
1503                     //
1504                     //           H             T
1505                     //      [o o . . . . . . . o o o o o o o]
1506                     //       M M                         M M
1507                     //
1508                     // or quasi-discontiguous, remove next to head, tail section:
1509                     //
1510                     //       H                 T         R
1511                     //      [. . . . . . . . . o o o o o x o]
1512                     //
1513                     //                         T           H
1514                     //      [. . . . . . . . . o o o o o o .]
1515                     //                                   M
1516
1517                     // draw in elements in the tail section
1518                     self.copy(idx, idx + 1, self.cap() - idx - 1);
1519
1520                     // Prevents underflow.
1521                     if self.head != 0 {
1522                         // copy first element into empty spot
1523                         self.copy(self.cap() - 1, 0, 1);
1524
1525                         // move elements in the head section backwards
1526                         self.copy(0, 1, self.head - 1);
1527                     }
1528
1529                     self.head = self.wrap_sub(self.head, 1);
1530                 }
1531             }
1532             (false, true, false) => {
1533                 unsafe {
1534                     // discontiguous, remove closer to tail, head section:
1535                     //
1536                     //           R               H     T
1537                     //      [o o x o o o o o o o . . . o o o]
1538                     //
1539                     //                           H       T
1540                     //      [o o o o o o o o o o . . . . o o]
1541                     //       M M M                       M M
1542
1543                     // draw in elements up to idx
1544                     self.copy(1, 0, idx);
1545
1546                     // copy last element into empty spot
1547                     self.copy(0, self.cap() - 1, 1);
1548
1549                     // move elements from tail to end forward, excluding the last one
1550                     self.copy(self.tail + 1, self.tail, self.cap() - self.tail - 1);
1551
1552                     self.tail = self.wrap_add(self.tail, 1);
1553                 }
1554             }
1555         }
1556
1557         return elem;
1558     }
1559
1560     /// Splits the collection into two at the given index.
1561     ///
1562     /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
1563     /// and the returned `Self` contains elements `[at, len)`.
1564     ///
1565     /// Note that the capacity of `self` does not change.
1566     ///
1567     /// # Panics
1568     ///
1569     /// Panics if `at > len`
1570     ///
1571     /// # Examples
1572     ///
1573     /// ```
1574     /// use std::collections::VecDeque;
1575     ///
1576     /// let mut buf: VecDeque<_> = vec![1,2,3].into_iter().collect();
1577     /// let buf2 = buf.split_off(1);
1578     /// // buf = [1], buf2 = [2, 3]
1579     /// assert_eq!(buf.len(), 1);
1580     /// assert_eq!(buf2.len(), 2);
1581     /// ```
1582     #[inline]
1583     #[stable(feature = "split_off", since = "1.4.0")]
1584     pub fn split_off(&mut self, at: usize) -> Self {
1585         let len = self.len();
1586         assert!(at <= len, "`at` out of bounds");
1587
1588         let other_len = len - at;
1589         let mut other = VecDeque::with_capacity(other_len);
1590
1591         unsafe {
1592             let (first_half, second_half) = self.as_slices();
1593
1594             let first_len = first_half.len();
1595             let second_len = second_half.len();
1596             if at < first_len {
1597                 // `at` lies in the first half.
1598                 let amount_in_first = first_len - at;
1599
1600                 ptr::copy_nonoverlapping(first_half.as_ptr().offset(at as isize),
1601                                          other.ptr(),
1602                                          amount_in_first);
1603
1604                 // just take all of the second half.
1605                 ptr::copy_nonoverlapping(second_half.as_ptr(),
1606                                          other.ptr().offset(amount_in_first as isize),
1607                                          second_len);
1608             } else {
1609                 // `at` lies in the second half, need to factor in the elements we skipped
1610                 // in the first half.
1611                 let offset = at - first_len;
1612                 let amount_in_second = second_len - offset;
1613                 ptr::copy_nonoverlapping(second_half.as_ptr().offset(offset as isize),
1614                                          other.ptr(),
1615                                          amount_in_second);
1616             }
1617         }
1618
1619         // Cleanup where the ends of the buffers are
1620         self.head = self.wrap_sub(self.head, other_len);
1621         other.head = other.wrap_index(other_len);
1622
1623         other
1624     }
1625
1626     /// Moves all the elements of `other` into `Self`, leaving `other` empty.
1627     ///
1628     /// # Panics
1629     ///
1630     /// Panics if the new number of elements in self overflows a `usize`.
1631     ///
1632     /// # Examples
1633     ///
1634     /// ```
1635     /// use std::collections::VecDeque;
1636     ///
1637     /// let mut buf: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
1638     /// let mut buf2: VecDeque<_> = vec![4, 5, 6].into_iter().collect();
1639     /// buf.append(&mut buf2);
1640     /// assert_eq!(buf.len(), 6);
1641     /// assert_eq!(buf2.len(), 0);
1642     /// ```
1643     #[inline]
1644     #[stable(feature = "append", since = "1.4.0")]
1645     pub fn append(&mut self, other: &mut Self) {
1646         // naive impl
1647         self.extend(other.drain(..));
1648     }
1649
1650     /// Retains only the elements specified by the predicate.
1651     ///
1652     /// In other words, remove all elements `e` such that `f(&e)` returns false.
1653     /// This method operates in place and preserves the order of the retained
1654     /// elements.
1655     ///
1656     /// # Examples
1657     ///
1658     /// ```
1659     /// use std::collections::VecDeque;
1660     ///
1661     /// let mut buf = VecDeque::new();
1662     /// buf.extend(1..5);
1663     /// buf.retain(|&x| x%2 == 0);
1664     ///
1665     /// let v: Vec<_> = buf.into_iter().collect();
1666     /// assert_eq!(&v[..], &[2, 4]);
1667     /// ```
1668     #[stable(feature = "vec_deque_retain", since = "1.4.0")]
1669     pub fn retain<F>(&mut self, mut f: F)
1670         where F: FnMut(&T) -> bool
1671     {
1672         let len = self.len();
1673         let mut del = 0;
1674         for i in 0..len {
1675             if !f(&self[i]) {
1676                 del += 1;
1677             } else if del > 0 {
1678                 self.swap(i - del, i);
1679             }
1680         }
1681         if del > 0 {
1682             self.truncate(len - del);
1683         }
1684     }
1685 }
1686
1687 impl<T: Clone> VecDeque<T> {
1688     /// Modifies the `VecDeque` in-place so that `len()` is equal to new_len,
1689     /// either by removing excess elements or by appending copies of a value to the back.
1690     ///
1691     /// # Examples
1692     ///
1693     /// ```
1694     /// #![feature(deque_extras)]
1695     ///
1696     /// use std::collections::VecDeque;
1697     ///
1698     /// let mut buf = VecDeque::new();
1699     /// buf.push_back(5);
1700     /// buf.push_back(10);
1701     /// buf.push_back(15);
1702     /// buf.resize(2, 0);
1703     /// buf.resize(6, 20);
1704     /// for (a, b) in [5, 10, 20, 20, 20, 20].iter().zip(&buf) {
1705     ///     assert_eq!(a, b);
1706     /// }
1707     /// ```
1708     #[unstable(feature = "deque_extras",
1709                reason = "matches collection reform specification; waiting on panic semantics",
1710                issue = "27788")]
1711     pub fn resize(&mut self, new_len: usize, value: T) {
1712         let len = self.len();
1713
1714         if new_len > len {
1715             self.extend(repeat(value).take(new_len - len))
1716         } else {
1717             self.truncate(new_len);
1718         }
1719     }
1720 }
1721
1722 /// Returns the index in the underlying buffer for a given logical element index.
1723 #[inline]
1724 fn wrap_index(index: usize, size: usize) -> usize {
1725     // size is always a power of 2
1726     debug_assert!(size.is_power_of_two());
1727     index & (size - 1)
1728 }
1729
1730 /// Calculate the number of elements left to be read in the buffer
1731 #[inline]
1732 fn count(tail: usize, head: usize, size: usize) -> usize {
1733     // size is always a power of 2
1734     (head.wrapping_sub(tail)) & (size - 1)
1735 }
1736
1737 /// `VecDeque` iterator.
1738 #[stable(feature = "rust1", since = "1.0.0")]
1739 pub struct Iter<'a, T: 'a> {
1740     ring: &'a [T],
1741     tail: usize,
1742     head: usize,
1743 }
1744
1745 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1746 #[stable(feature = "rust1", since = "1.0.0")]
1747 impl<'a, T> Clone for Iter<'a, T> {
1748     fn clone(&self) -> Iter<'a, T> {
1749         Iter {
1750             ring: self.ring,
1751             tail: self.tail,
1752             head: self.head,
1753         }
1754     }
1755 }
1756
1757 #[stable(feature = "rust1", since = "1.0.0")]
1758 impl<'a, T> Iterator for Iter<'a, T> {
1759     type Item = &'a T;
1760
1761     #[inline]
1762     fn next(&mut self) -> Option<&'a T> {
1763         if self.tail == self.head {
1764             return None;
1765         }
1766         let tail = self.tail;
1767         self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len());
1768         unsafe { Some(self.ring.get_unchecked(tail)) }
1769     }
1770
1771     #[inline]
1772     fn size_hint(&self) -> (usize, Option<usize>) {
1773         let len = count(self.tail, self.head, self.ring.len());
1774         (len, Some(len))
1775     }
1776 }
1777
1778 #[stable(feature = "rust1", since = "1.0.0")]
1779 impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
1780     #[inline]
1781     fn next_back(&mut self) -> Option<&'a T> {
1782         if self.tail == self.head {
1783             return None;
1784         }
1785         self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len());
1786         unsafe { Some(self.ring.get_unchecked(self.head)) }
1787     }
1788 }
1789
1790 #[stable(feature = "rust1", since = "1.0.0")]
1791 impl<'a, T> ExactSizeIterator for Iter<'a, T> {}
1792
1793 /// `VecDeque` mutable iterator.
1794 #[stable(feature = "rust1", since = "1.0.0")]
1795 pub struct IterMut<'a, T: 'a> {
1796     ring: &'a mut [T],
1797     tail: usize,
1798     head: usize,
1799 }
1800
1801 #[stable(feature = "rust1", since = "1.0.0")]
1802 impl<'a, T> Iterator for IterMut<'a, T> {
1803     type Item = &'a mut T;
1804
1805     #[inline]
1806     fn next(&mut self) -> Option<&'a mut T> {
1807         if self.tail == self.head {
1808             return None;
1809         }
1810         let tail = self.tail;
1811         self.tail = wrap_index(self.tail.wrapping_add(1), self.ring.len());
1812
1813         unsafe {
1814             let elem = self.ring.get_unchecked_mut(tail);
1815             Some(&mut *(elem as *mut _))
1816         }
1817     }
1818
1819     #[inline]
1820     fn size_hint(&self) -> (usize, Option<usize>) {
1821         let len = count(self.tail, self.head, self.ring.len());
1822         (len, Some(len))
1823     }
1824 }
1825
1826 #[stable(feature = "rust1", since = "1.0.0")]
1827 impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
1828     #[inline]
1829     fn next_back(&mut self) -> Option<&'a mut T> {
1830         if self.tail == self.head {
1831             return None;
1832         }
1833         self.head = wrap_index(self.head.wrapping_sub(1), self.ring.len());
1834
1835         unsafe {
1836             let elem = self.ring.get_unchecked_mut(self.head);
1837             Some(&mut *(elem as *mut _))
1838         }
1839     }
1840 }
1841
1842 #[stable(feature = "rust1", since = "1.0.0")]
1843 impl<'a, T> ExactSizeIterator for IterMut<'a, T> {}
1844
1845 /// A by-value VecDeque iterator
1846 #[derive(Clone)]
1847 #[stable(feature = "rust1", since = "1.0.0")]
1848 pub struct IntoIter<T> {
1849     inner: VecDeque<T>,
1850 }
1851
1852 #[stable(feature = "rust1", since = "1.0.0")]
1853 impl<T> Iterator for IntoIter<T> {
1854     type Item = T;
1855
1856     #[inline]
1857     fn next(&mut self) -> Option<T> {
1858         self.inner.pop_front()
1859     }
1860
1861     #[inline]
1862     fn size_hint(&self) -> (usize, Option<usize>) {
1863         let len = self.inner.len();
1864         (len, Some(len))
1865     }
1866 }
1867
1868 #[stable(feature = "rust1", since = "1.0.0")]
1869 impl<T> DoubleEndedIterator for IntoIter<T> {
1870     #[inline]
1871     fn next_back(&mut self) -> Option<T> {
1872         self.inner.pop_back()
1873     }
1874 }
1875
1876 #[stable(feature = "rust1", since = "1.0.0")]
1877 impl<T> ExactSizeIterator for IntoIter<T> {}
1878
1879 /// A draining VecDeque iterator
1880 #[stable(feature = "drain", since = "1.6.0")]
1881 pub struct Drain<'a, T: 'a> {
1882     after_tail: usize,
1883     after_head: usize,
1884     iter: Iter<'a, T>,
1885     deque: *mut VecDeque<T>,
1886 }
1887
1888 #[stable(feature = "drain", since = "1.6.0")]
1889 unsafe impl<'a, T: Sync> Sync for Drain<'a, T> {}
1890 #[stable(feature = "drain", since = "1.6.0")]
1891 unsafe impl<'a, T: Send> Send for Drain<'a, T> {}
1892
1893 #[stable(feature = "rust1", since = "1.0.0")]
1894 impl<'a, T: 'a> Drop for Drain<'a, T> {
1895     fn drop(&mut self) {
1896         for _ in self.by_ref() {}
1897
1898         let source_deque = unsafe { &mut *self.deque };
1899
1900         // T = source_deque_tail; H = source_deque_head; t = drain_tail; h = drain_head
1901         //
1902         //        T   t   h   H
1903         // [. . . o o x x o o . . .]
1904         //
1905         let orig_tail = source_deque.tail;
1906         let drain_tail = source_deque.head;
1907         let drain_head = self.after_tail;
1908         let orig_head = self.after_head;
1909
1910         let tail_len = count(orig_tail, drain_tail, source_deque.cap());
1911         let head_len = count(drain_head, orig_head, source_deque.cap());
1912
1913         // Restore the original head value
1914         source_deque.head = orig_head;
1915
1916         match (tail_len, head_len) {
1917             (0, 0) => {
1918                 source_deque.head = 0;
1919                 source_deque.tail = 0;
1920             }
1921             (0, _) => {
1922                 source_deque.tail = drain_head;
1923             }
1924             (_, 0) => {
1925                 source_deque.head = drain_tail;
1926             }
1927             _ => {
1928                 unsafe {
1929                     if tail_len <= head_len {
1930                         source_deque.tail = source_deque.wrap_sub(drain_head, tail_len);
1931                         source_deque.wrap_copy(source_deque.tail, orig_tail, tail_len);
1932                     } else {
1933                         source_deque.head = source_deque.wrap_add(drain_tail, head_len);
1934                         source_deque.wrap_copy(drain_tail, drain_head, head_len);
1935                     }
1936                 }
1937             }
1938         }
1939     }
1940 }
1941
1942 #[stable(feature = "rust1", since = "1.0.0")]
1943 impl<'a, T: 'a> Iterator for Drain<'a, T> {
1944     type Item = T;
1945
1946     #[inline]
1947     fn next(&mut self) -> Option<T> {
1948         self.iter.next().map(|elt| unsafe { ptr::read(elt) })
1949     }
1950
1951     #[inline]
1952     fn size_hint(&self) -> (usize, Option<usize>) {
1953         self.iter.size_hint()
1954     }
1955 }
1956
1957 #[stable(feature = "rust1", since = "1.0.0")]
1958 impl<'a, T: 'a> DoubleEndedIterator for Drain<'a, T> {
1959     #[inline]
1960     fn next_back(&mut self) -> Option<T> {
1961         self.iter.next_back().map(|elt| unsafe { ptr::read(elt) })
1962     }
1963 }
1964
1965 #[stable(feature = "rust1", since = "1.0.0")]
1966 impl<'a, T: 'a> ExactSizeIterator for Drain<'a, T> {}
1967
1968 #[stable(feature = "rust1", since = "1.0.0")]
1969 impl<A: PartialEq> PartialEq for VecDeque<A> {
1970     fn eq(&self, other: &VecDeque<A>) -> bool {
1971         self.len() == other.len() && self.iter().zip(other).all(|(a, b)| a.eq(b))
1972     }
1973 }
1974
1975 #[stable(feature = "rust1", since = "1.0.0")]
1976 impl<A: Eq> Eq for VecDeque<A> {}
1977
1978 #[stable(feature = "rust1", since = "1.0.0")]
1979 impl<A: PartialOrd> PartialOrd for VecDeque<A> {
1980     fn partial_cmp(&self, other: &VecDeque<A>) -> Option<Ordering> {
1981         self.iter().partial_cmp(other.iter())
1982     }
1983 }
1984
1985 #[stable(feature = "rust1", since = "1.0.0")]
1986 impl<A: Ord> Ord for VecDeque<A> {
1987     #[inline]
1988     fn cmp(&self, other: &VecDeque<A>) -> Ordering {
1989         self.iter().cmp(other.iter())
1990     }
1991 }
1992
1993 #[stable(feature = "rust1", since = "1.0.0")]
1994 impl<A: Hash> Hash for VecDeque<A> {
1995     fn hash<H: Hasher>(&self, state: &mut H) {
1996         self.len().hash(state);
1997         let (a, b) = self.as_slices();
1998         Hash::hash_slice(a, state);
1999         Hash::hash_slice(b, state);
2000     }
2001 }
2002
2003 #[stable(feature = "rust1", since = "1.0.0")]
2004 impl<A> Index<usize> for VecDeque<A> {
2005     type Output = A;
2006
2007     #[inline]
2008     fn index(&self, index: usize) -> &A {
2009         self.get(index).expect("Out of bounds access")
2010     }
2011 }
2012
2013 #[stable(feature = "rust1", since = "1.0.0")]
2014 impl<A> IndexMut<usize> for VecDeque<A> {
2015     #[inline]
2016     fn index_mut(&mut self, index: usize) -> &mut A {
2017         self.get_mut(index).expect("Out of bounds access")
2018     }
2019 }
2020
2021 #[stable(feature = "rust1", since = "1.0.0")]
2022 impl<A> FromIterator<A> for VecDeque<A> {
2023     fn from_iter<T: IntoIterator<Item = A>>(iterable: T) -> VecDeque<A> {
2024         let iterator = iterable.into_iter();
2025         let (lower, _) = iterator.size_hint();
2026         let mut deq = VecDeque::with_capacity(lower);
2027         deq.extend(iterator);
2028         deq
2029     }
2030 }
2031
2032 #[stable(feature = "rust1", since = "1.0.0")]
2033 impl<T> IntoIterator for VecDeque<T> {
2034     type Item = T;
2035     type IntoIter = IntoIter<T>;
2036
2037     /// Consumes the list into a front-to-back iterator yielding elements by
2038     /// value.
2039     fn into_iter(self) -> IntoIter<T> {
2040         IntoIter { inner: self }
2041     }
2042 }
2043
2044 #[stable(feature = "rust1", since = "1.0.0")]
2045 impl<'a, T> IntoIterator for &'a VecDeque<T> {
2046     type Item = &'a T;
2047     type IntoIter = Iter<'a, T>;
2048
2049     fn into_iter(self) -> Iter<'a, T> {
2050         self.iter()
2051     }
2052 }
2053
2054 #[stable(feature = "rust1", since = "1.0.0")]
2055 impl<'a, T> IntoIterator for &'a mut VecDeque<T> {
2056     type Item = &'a mut T;
2057     type IntoIter = IterMut<'a, T>;
2058
2059     fn into_iter(mut self) -> IterMut<'a, T> {
2060         self.iter_mut()
2061     }
2062 }
2063
2064 #[stable(feature = "rust1", since = "1.0.0")]
2065 impl<A> Extend<A> for VecDeque<A> {
2066     fn extend<T: IntoIterator<Item = A>>(&mut self, iter: T) {
2067         for elt in iter {
2068             self.push_back(elt);
2069         }
2070     }
2071 }
2072
2073 #[stable(feature = "extend_ref", since = "1.2.0")]
2074 impl<'a, T: 'a + Copy> Extend<&'a T> for VecDeque<T> {
2075     fn extend<I: IntoIterator<Item = &'a T>>(&mut self, iter: I) {
2076         self.extend(iter.into_iter().cloned());
2077     }
2078 }
2079
2080 #[stable(feature = "rust1", since = "1.0.0")]
2081 impl<T: fmt::Debug> fmt::Debug for VecDeque<T> {
2082     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
2083         f.debug_list().entries(self).finish()
2084     }
2085 }
2086
2087 #[cfg(test)]
2088 mod tests {
2089     use core::iter::Iterator;
2090     use core::option::Option::Some;
2091
2092     use test;
2093
2094     use super::VecDeque;
2095
2096     #[bench]
2097     fn bench_push_back_100(b: &mut test::Bencher) {
2098         let mut deq = VecDeque::with_capacity(101);
2099         b.iter(|| {
2100             for i in 0..100 {
2101                 deq.push_back(i);
2102             }
2103             deq.head = 0;
2104             deq.tail = 0;
2105         })
2106     }
2107
2108     #[bench]
2109     fn bench_push_front_100(b: &mut test::Bencher) {
2110         let mut deq = VecDeque::with_capacity(101);
2111         b.iter(|| {
2112             for i in 0..100 {
2113                 deq.push_front(i);
2114             }
2115             deq.head = 0;
2116             deq.tail = 0;
2117         })
2118     }
2119
2120     #[bench]
2121     fn bench_pop_back_100(b: &mut test::Bencher) {
2122         let mut deq = VecDeque::<i32>::with_capacity(101);
2123
2124         b.iter(|| {
2125             deq.head = 100;
2126             deq.tail = 0;
2127             while !deq.is_empty() {
2128                 test::black_box(deq.pop_back());
2129             }
2130         })
2131     }
2132
2133     #[bench]
2134     fn bench_pop_front_100(b: &mut test::Bencher) {
2135         let mut deq = VecDeque::<i32>::with_capacity(101);
2136
2137         b.iter(|| {
2138             deq.head = 100;
2139             deq.tail = 0;
2140             while !deq.is_empty() {
2141                 test::black_box(deq.pop_front());
2142             }
2143         })
2144     }
2145
2146     #[test]
2147     fn test_swap_front_back_remove() {
2148         fn test(back: bool) {
2149             // This test checks that every single combination of tail position and length is tested.
2150             // Capacity 15 should be large enough to cover every case.
2151             let mut tester = VecDeque::with_capacity(15);
2152             let usable_cap = tester.capacity();
2153             let final_len = usable_cap / 2;
2154
2155             for len in 0..final_len {
2156                 let expected = if back {
2157                     (0..len).collect()
2158                 } else {
2159                     (0..len).rev().collect()
2160                 };
2161                 for tail_pos in 0..usable_cap {
2162                     tester.tail = tail_pos;
2163                     tester.head = tail_pos;
2164                     if back {
2165                         for i in 0..len * 2 {
2166                             tester.push_front(i);
2167                         }
2168                         for i in 0..len {
2169                             assert_eq!(tester.swap_remove_back(i), Some(len * 2 - 1 - i));
2170                         }
2171                     } else {
2172                         for i in 0..len * 2 {
2173                             tester.push_back(i);
2174                         }
2175                         for i in 0..len {
2176                             let idx = tester.len() - 1 - i;
2177                             assert_eq!(tester.swap_remove_front(idx), Some(len * 2 - 1 - i));
2178                         }
2179                     }
2180                     assert!(tester.tail < tester.cap());
2181                     assert!(tester.head < tester.cap());
2182                     assert_eq!(tester, expected);
2183                 }
2184             }
2185         }
2186         test(true);
2187         test(false);
2188     }
2189
2190     #[test]
2191     fn test_insert() {
2192         // This test checks that every single combination of tail position, length, and
2193         // insertion position is tested. Capacity 15 should be large enough to cover every case.
2194
2195         let mut tester = VecDeque::with_capacity(15);
2196         // can't guarantee we got 15, so have to get what we got.
2197         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2198         // this test isn't covering what it wants to
2199         let cap = tester.capacity();
2200
2201
2202         // len is the length *after* insertion
2203         for len in 1..cap {
2204             // 0, 1, 2, .., len - 1
2205             let expected = (0..).take(len).collect();
2206             for tail_pos in 0..cap {
2207                 for to_insert in 0..len {
2208                     tester.tail = tail_pos;
2209                     tester.head = tail_pos;
2210                     for i in 0..len {
2211                         if i != to_insert {
2212                             tester.push_back(i);
2213                         }
2214                     }
2215                     tester.insert(to_insert, to_insert);
2216                     assert!(tester.tail < tester.cap());
2217                     assert!(tester.head < tester.cap());
2218                     assert_eq!(tester, expected);
2219                 }
2220             }
2221         }
2222     }
2223
2224     #[test]
2225     fn test_remove() {
2226         // This test checks that every single combination of tail position, length, and
2227         // removal position is tested. Capacity 15 should be large enough to cover every case.
2228
2229         let mut tester = VecDeque::with_capacity(15);
2230         // can't guarantee we got 15, so have to get what we got.
2231         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2232         // this test isn't covering what it wants to
2233         let cap = tester.capacity();
2234
2235         // len is the length *after* removal
2236         for len in 0..cap - 1 {
2237             // 0, 1, 2, .., len - 1
2238             let expected = (0..).take(len).collect();
2239             for tail_pos in 0..cap {
2240                 for to_remove in 0..len + 1 {
2241                     tester.tail = tail_pos;
2242                     tester.head = tail_pos;
2243                     for i in 0..len {
2244                         if i == to_remove {
2245                             tester.push_back(1234);
2246                         }
2247                         tester.push_back(i);
2248                     }
2249                     if to_remove == len {
2250                         tester.push_back(1234);
2251                     }
2252                     tester.remove(to_remove);
2253                     assert!(tester.tail < tester.cap());
2254                     assert!(tester.head < tester.cap());
2255                     assert_eq!(tester, expected);
2256                 }
2257             }
2258         }
2259     }
2260
2261     #[test]
2262     fn test_drain() {
2263         let mut tester: VecDeque<usize> = VecDeque::with_capacity(7);
2264
2265         let cap = tester.capacity();
2266         for len in 0..cap + 1 {
2267             for tail in 0..cap + 1 {
2268                 for drain_start in 0..len + 1 {
2269                     for drain_end in drain_start..len + 1 {
2270                         tester.tail = tail;
2271                         tester.head = tail;
2272                         for i in 0..len {
2273                             tester.push_back(i);
2274                         }
2275
2276                         // Check that we drain the correct values
2277                         let drained: VecDeque<_> = tester.drain(drain_start..drain_end).collect();
2278                         let drained_expected: VecDeque<_> = (drain_start..drain_end).collect();
2279                         assert_eq!(drained, drained_expected);
2280
2281                         // We shouldn't have changed the capacity or made the
2282                         // head or tail out of bounds
2283                         assert_eq!(tester.capacity(), cap);
2284                         assert!(tester.tail < tester.cap());
2285                         assert!(tester.head < tester.cap());
2286
2287                         // We should see the correct values in the VecDeque
2288                         let expected: VecDeque<_> = (0..drain_start)
2289                                                         .chain(drain_end..len)
2290                                                         .collect();
2291                         assert_eq!(expected, tester);
2292                     }
2293                 }
2294             }
2295         }
2296     }
2297
2298     #[test]
2299     fn test_shrink_to_fit() {
2300         // This test checks that every single combination of head and tail position,
2301         // is tested. Capacity 15 should be large enough to cover every case.
2302
2303         let mut tester = VecDeque::with_capacity(15);
2304         // can't guarantee we got 15, so have to get what we got.
2305         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2306         // this test isn't covering what it wants to
2307         let cap = tester.capacity();
2308         tester.reserve(63);
2309         let max_cap = tester.capacity();
2310
2311         for len in 0..cap + 1 {
2312             // 0, 1, 2, .., len - 1
2313             let expected = (0..).take(len).collect();
2314             for tail_pos in 0..max_cap + 1 {
2315                 tester.tail = tail_pos;
2316                 tester.head = tail_pos;
2317                 tester.reserve(63);
2318                 for i in 0..len {
2319                     tester.push_back(i);
2320                 }
2321                 tester.shrink_to_fit();
2322                 assert!(tester.capacity() <= cap);
2323                 assert!(tester.tail < tester.cap());
2324                 assert!(tester.head < tester.cap());
2325                 assert_eq!(tester, expected);
2326             }
2327         }
2328     }
2329
2330     #[test]
2331     fn test_split_off() {
2332         // This test checks that every single combination of tail position, length, and
2333         // split position is tested. Capacity 15 should be large enough to cover every case.
2334
2335         let mut tester = VecDeque::with_capacity(15);
2336         // can't guarantee we got 15, so have to get what we got.
2337         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2338         // this test isn't covering what it wants to
2339         let cap = tester.capacity();
2340
2341         // len is the length *before* splitting
2342         for len in 0..cap {
2343             // index to split at
2344             for at in 0..len + 1 {
2345                 // 0, 1, 2, .., at - 1 (may be empty)
2346                 let expected_self = (0..).take(at).collect();
2347                 // at, at + 1, .., len - 1 (may be empty)
2348                 let expected_other = (at..).take(len - at).collect();
2349
2350                 for tail_pos in 0..cap {
2351                     tester.tail = tail_pos;
2352                     tester.head = tail_pos;
2353                     for i in 0..len {
2354                         tester.push_back(i);
2355                     }
2356                     let result = tester.split_off(at);
2357                     assert!(tester.tail < tester.cap());
2358                     assert!(tester.head < tester.cap());
2359                     assert!(result.tail < result.cap());
2360                     assert!(result.head < result.cap());
2361                     assert_eq!(tester, expected_self);
2362                     assert_eq!(result, expected_other);
2363                 }
2364             }
2365         }
2366     }
2367 }