src/libcollections/vec_deque.rs

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