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