src/liballoc/collections/vec_deque.rs

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