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