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: uint = 7u; // 2^3 - 1
  36 static MINIMUM_CAPACITY: uint = 1u; // 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: uint,
  48     head: uint,
  49     cap: uint,
  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().map(|t| t.clone()).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: uint) -> T {
 103         ptr::read(self.ptr.offset(off as int))
 104     }
 105
 106     /// Writes an element into the buffer, moving it.
 107     #[inline]
 108     unsafe fn buffer_write(&mut self, off: uint, t: T) {
 109         ptr::write(self.ptr.offset(off as int), 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: uint) -> uint { 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: uint, src: uint, len: uint) {
 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 int),
 129             self.ptr.offset(src as int),
 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: uint, src: uint, len: uint) {
 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 int),
 142             self.ptr.offset(src as int),
 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: uint) -> 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: uint) -> Option<&T> {
 196         if i < self.len() {
 197             let idx = self.wrap_index(self.tail + i);
 198             unsafe { Some(&*self.ptr.offset(idx as int)) }
 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: uint) -> 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 int)) }
 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: uint, j: uint) {
 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 int), self.ptr.offset(rj as int))
 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) -> uint { 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 `uint`.
 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: uint) {
 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 `uint`.
 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: uint) {
 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(0u..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: uint) {
 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<'a>(&'a mut self) -> IterMut<'a, T> {
 533         IterMut {
 534             tail: self.tail,
 535             head: self.head,
 536             cap: self.cap,
 537             ptr: self.ptr,
 538             marker: marker::ContravariantLifetime::<'a>,
 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<'a>(&'a self) -> (&'a [T], &'a [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<'a>(&'a mut self) -> (&'a mut [T], &'a 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) -> uint { 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: uint) -> 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: uint) -> 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: uint, 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: uint) -> 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: uint, 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: uint, size: uint) -> uint {
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: uint, head: uint, size: uint) -> uint {
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: uint,
1345     head: uint
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) -> (uint, Option<uint>) {
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) -> uint {
1399         let (len, _) = self.size_hint();
1400         len
1401     }
1402
1403     #[inline]
1404     fn idx(&mut self, j: uint) -> 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: uint,
1422     head: uint,
1423     cap: uint,
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 int))
1441         }
1442     }
1443
1444     #[inline]
1445     fn size_hint(&self) -> (uint, Option<uint>) {
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 int))
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) -> (uint, Option<uint>) {
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) -> (uint, Option<uint>) {
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<uint> for RingBuf<A> {
1584     type Output = A;
1585
1586     #[inline]
1587     fn index<'a>(&'a self, i: &uint) -> &'a 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<uint> for RingBuf<A> {
1594     type Output = A;
1595
1596     #[inline]
1597     fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut A {
1598         self.get_mut(*i).expect("Out of bounds access")
1599     }
1600 }
1601
1602 #[stable(feature = "rust1", since = "1.0.0")]
1603 impl<A> FromIterator<A> for RingBuf<A> {
1604     fn from_iter<T: Iterator<Item=A>>(iterator: T) -> RingBuf<A> {
1605         let (lower, _) = iterator.size_hint();
1606         let mut deq = RingBuf::with_capacity(lower);
1607         deq.extend(iterator);
1608         deq
1609     }
1610 }
1611
1612 impl<T> IntoIterator for RingBuf<T> {
1613     type Iter = IntoIter<T>;
1614
1615     fn into_iter(self) -> IntoIter<T> {
1616         self.into_iter()
1617     }
1618 }
1619
1620 impl<'a, T> IntoIterator for &'a RingBuf<T> {
1621     type Iter = Iter<'a, T>;
1622
1623     fn into_iter(self) -> Iter<'a, T> {
1624         self.iter()
1625     }
1626 }
1627
1628 impl<'a, T> IntoIterator for &'a mut RingBuf<T> {
1629     type Iter = IterMut<'a, T>;
1630
1631     fn into_iter(mut self) -> IterMut<'a, T> {
1632         self.iter_mut()
1633     }
1634 }
1635
1636 #[stable(feature = "rust1", since = "1.0.0")]
1637 impl<A> Extend<A> for RingBuf<A> {
1638     fn extend<T: Iterator<Item=A>>(&mut self, mut iterator: T) {
1639         for elt in iterator {
1640             self.push_back(elt);
1641         }
1642     }
1643 }
1644
1645 #[stable(feature = "rust1", since = "1.0.0")]
1646 impl<T: fmt::Debug> fmt::Debug for RingBuf<T> {
1647     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1648         try!(write!(f, "RingBuf ["));
1649
1650         for (i, e) in self.iter().enumerate() {
1651             if i != 0 { try!(write!(f, ", ")); }
1652             try!(write!(f, "{:?}", *e));
1653         }
1654
1655         write!(f, "]")
1656     }
1657 }
1658
1659 #[cfg(test)]
1660 mod tests {
1661     use self::Taggy::*;
1662     use self::Taggypar::*;
1663     use prelude::*;
1664     use core::iter;
1665     use std::fmt::Debug;
1666     use std::hash::{self, SipHasher};
1667     use test::Bencher;
1668     use test;
1669
1670     use super::RingBuf;
1671
1672     #[test]
1673     #[allow(deprecated)]
1674     fn test_simple() {
1675         let mut d = RingBuf::new();
1676         assert_eq!(d.len(), 0u);
1677         d.push_front(17);
1678         d.push_front(42);
1679         d.push_back(137);
1680         assert_eq!(d.len(), 3u);
1681         d.push_back(137);
1682         assert_eq!(d.len(), 4u);
1683         assert_eq!(*d.front().unwrap(), 42);
1684         assert_eq!(*d.back().unwrap(), 137);
1685         let mut i = d.pop_front();
1686         assert_eq!(i, Some(42));
1687         i = d.pop_back();
1688         assert_eq!(i, Some(137));
1689         i = d.pop_back();
1690         assert_eq!(i, Some(137));
1691         i = d.pop_back();
1692         assert_eq!(i, Some(17));
1693         assert_eq!(d.len(), 0u);
1694         d.push_back(3);
1695         assert_eq!(d.len(), 1u);
1696         d.push_front(2);
1697         assert_eq!(d.len(), 2u);
1698         d.push_back(4);
1699         assert_eq!(d.len(), 3u);
1700         d.push_front(1);
1701         assert_eq!(d.len(), 4u);
1702         debug!("{}", d[0]);
1703         debug!("{}", d[1]);
1704         debug!("{}", d[2]);
1705         debug!("{}", d[3]);
1706         assert_eq!(d[0], 1);
1707         assert_eq!(d[1], 2);
1708         assert_eq!(d[2], 3);
1709         assert_eq!(d[3], 4);
1710     }
1711
1712     #[cfg(test)]
1713     fn test_parameterized<T:Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) {
1714         let mut deq = RingBuf::new();
1715         assert_eq!(deq.len(), 0);
1716         deq.push_front(a.clone());
1717         deq.push_front(b.clone());
1718         deq.push_back(c.clone());
1719         assert_eq!(deq.len(), 3);
1720         deq.push_back(d.clone());
1721         assert_eq!(deq.len(), 4);
1722         assert_eq!((*deq.front().unwrap()).clone(), b.clone());
1723         assert_eq!((*deq.back().unwrap()).clone(), d.clone());
1724         assert_eq!(deq.pop_front().unwrap(), b.clone());
1725         assert_eq!(deq.pop_back().unwrap(), d.clone());
1726         assert_eq!(deq.pop_back().unwrap(), c.clone());
1727         assert_eq!(deq.pop_back().unwrap(), a.clone());
1728         assert_eq!(deq.len(), 0);
1729         deq.push_back(c.clone());
1730         assert_eq!(deq.len(), 1);
1731         deq.push_front(b.clone());
1732         assert_eq!(deq.len(), 2);
1733         deq.push_back(d.clone());
1734         assert_eq!(deq.len(), 3);
1735         deq.push_front(a.clone());
1736         assert_eq!(deq.len(), 4);
1737         assert_eq!(deq[0].clone(), a.clone());
1738         assert_eq!(deq[1].clone(), b.clone());
1739         assert_eq!(deq[2].clone(), c.clone());
1740         assert_eq!(deq[3].clone(), d.clone());
1741     }
1742
1743     #[test]
1744     fn test_push_front_grow() {
1745         let mut deq = RingBuf::new();
1746         for i in 0u..66 {
1747             deq.push_front(i);
1748         }
1749         assert_eq!(deq.len(), 66);
1750
1751         for i in 0u..66 {
1752             assert_eq!(deq[i], 65 - i);
1753         }
1754
1755         let mut deq = RingBuf::new();
1756         for i in 0u..66 {
1757             deq.push_back(i);
1758         }
1759
1760         for i in 0u..66 {
1761             assert_eq!(deq[i], i);
1762         }
1763     }
1764
1765     #[test]
1766     fn test_index() {
1767         let mut deq = RingBuf::new();
1768         for i in 1u..4 {
1769             deq.push_front(i);
1770         }
1771         assert_eq!(deq[1], 2);
1772     }
1773
1774     #[test]
1775     #[should_fail]
1776     fn test_index_out_of_bounds() {
1777         let mut deq = RingBuf::new();
1778         for i in 1u..4 {
1779             deq.push_front(i);
1780         }
1781         deq[3];
1782     }
1783
1784     #[bench]
1785     fn bench_new(b: &mut test::Bencher) {
1786         b.iter(|| {
1787             let ring: RingBuf<u64> = RingBuf::new();
1788             test::black_box(ring);
1789         })
1790     }
1791
1792     #[bench]
1793     fn bench_push_back_100(b: &mut test::Bencher) {
1794         let mut deq = RingBuf::with_capacity(101);
1795         b.iter(|| {
1796             for i in 0..100 {
1797                 deq.push_back(i);
1798             }
1799             deq.head = 0;
1800             deq.tail = 0;
1801         })
1802     }
1803
1804     #[bench]
1805     fn bench_push_front_100(b: &mut test::Bencher) {
1806         let mut deq = RingBuf::with_capacity(101);
1807         b.iter(|| {
1808             for i in 0..100 {
1809                 deq.push_front(i);
1810             }
1811             deq.head = 0;
1812             deq.tail = 0;
1813         })
1814     }
1815
1816     #[bench]
1817     fn bench_pop_back_100(b: &mut test::Bencher) {
1818         let mut deq: RingBuf<i32> = RingBuf::with_capacity(101);
1819
1820         b.iter(|| {
1821             deq.head = 100;
1822             deq.tail = 0;
1823             while !deq.is_empty() {
1824                 test::black_box(deq.pop_back());
1825             }
1826         })
1827     }
1828
1829     #[bench]
1830     fn bench_pop_front_100(b: &mut test::Bencher) {
1831         let mut deq: RingBuf<i32> = RingBuf::with_capacity(101);
1832
1833         b.iter(|| {
1834             deq.head = 100;
1835             deq.tail = 0;
1836             while !deq.is_empty() {
1837                 test::black_box(deq.pop_front());
1838             }
1839         })
1840     }
1841
1842     #[bench]
1843     fn bench_grow_1025(b: &mut test::Bencher) {
1844         b.iter(|| {
1845             let mut deq = RingBuf::new();
1846             for i in 0..1025 {
1847                 deq.push_front(i);
1848             }
1849             test::black_box(deq);
1850         })
1851     }
1852
1853     #[bench]
1854     fn bench_iter_1000(b: &mut test::Bencher) {
1855         let ring: RingBuf<i32> = (0..1000).collect();
1856
1857         b.iter(|| {
1858             let mut sum = 0;
1859             for &i in &ring {
1860                 sum += i;
1861             }
1862             test::black_box(sum);
1863         })
1864     }
1865
1866     #[bench]
1867     fn bench_mut_iter_1000(b: &mut test::Bencher) {
1868         let mut ring: RingBuf<i32> = (0..1000).collect();
1869
1870         b.iter(|| {
1871             let mut sum = 0;
1872             for i in &mut ring {
1873                 sum += *i;
1874             }
1875             test::black_box(sum);
1876         })
1877     }
1878
1879     #[derive(Clone, PartialEq, Debug)]
1880     enum Taggy {
1881         One(i32),
1882         Two(i32, i32),
1883         Three(i32, i32, i32),
1884     }
1885
1886     #[derive(Clone, PartialEq, Debug)]
1887     enum Taggypar<T> {
1888         Onepar(i32),
1889         Twopar(i32, i32),
1890         Threepar(i32, i32, i32),
1891     }
1892
1893     #[derive(Clone, PartialEq, Debug)]
1894     struct RecCy {
1895         x: i32,
1896         y: i32,
1897         t: Taggy
1898     }
1899
1900     #[test]
1901     fn test_param_int() {
1902         test_parameterized::<i32>(5, 72, 64, 175);
1903     }
1904
1905     #[test]
1906     fn test_param_taggy() {
1907         test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
1908     }
1909
1910     #[test]
1911     fn test_param_taggypar() {
1912         test_parameterized::<Taggypar<i32>>(Onepar::<i32>(1),
1913                                             Twopar::<i32>(1, 2),
1914                                             Threepar::<i32>(1, 2, 3),
1915                                             Twopar::<i32>(17, 42));
1916     }
1917
1918     #[test]
1919     fn test_param_reccy() {
1920         let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
1921         let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
1922         let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
1923         let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
1924         test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
1925     }
1926
1927     #[test]
1928     fn test_with_capacity() {
1929         let mut d = RingBuf::with_capacity(0);
1930         d.push_back(1);
1931         assert_eq!(d.len(), 1);
1932         let mut d = RingBuf::with_capacity(50);
1933         d.push_back(1);
1934         assert_eq!(d.len(), 1);
1935     }
1936
1937     #[test]
1938     fn test_with_capacity_non_power_two() {
1939         let mut d3 = RingBuf::with_capacity(3);
1940         d3.push_back(1);
1941
1942         // X = None, | = lo
1943         // [|1, X, X]
1944         assert_eq!(d3.pop_front(), Some(1));
1945         // [X, |X, X]
1946         assert_eq!(d3.front(), None);
1947
1948         // [X, |3, X]
1949         d3.push_back(3);
1950         // [X, |3, 6]
1951         d3.push_back(6);
1952         // [X, X, |6]
1953         assert_eq!(d3.pop_front(), Some(3));
1954
1955         // Pushing the lo past half way point to trigger
1956         // the 'B' scenario for growth
1957         // [9, X, |6]
1958         d3.push_back(9);
1959         // [9, 12, |6]
1960         d3.push_back(12);
1961
1962         d3.push_back(15);
1963         // There used to be a bug here about how the
1964         // RingBuf made growth assumptions about the
1965         // underlying Vec which didn't hold and lead
1966         // to corruption.
1967         // (Vec grows to next power of two)
1968         //good- [9, 12, 15, X, X, X, X, |6]
1969         //bug-  [15, 12, X, X, X, |6, X, X]
1970         assert_eq!(d3.pop_front(), Some(6));
1971
1972         // Which leads us to the following state which
1973         // would be a failure case.
1974         //bug-  [15, 12, X, X, X, X, |X, X]
1975         assert_eq!(d3.front(), Some(&9));
1976     }
1977
1978     #[test]
1979     fn test_reserve_exact() {
1980         let mut d = RingBuf::new();
1981         d.push_back(0u64);
1982         d.reserve_exact(50);
1983         assert!(d.capacity() >= 51);
1984         let mut d = RingBuf::new();
1985         d.push_back(0u32);
1986         d.reserve_exact(50);
1987         assert!(d.capacity() >= 51);
1988     }
1989
1990     #[test]
1991     fn test_reserve() {
1992         let mut d = RingBuf::new();
1993         d.push_back(0u64);
1994         d.reserve(50);
1995         assert!(d.capacity() >= 51);
1996         let mut d = RingBuf::new();
1997         d.push_back(0u32);
1998         d.reserve(50);
1999         assert!(d.capacity() >= 51);
2000     }
2001
2002     #[test]
2003     fn test_swap() {
2004         let mut d: RingBuf<i32> = (0..5).collect();
2005         d.pop_front();
2006         d.swap(0, 3);
2007         assert_eq!(d.iter().map(|&x|x).collect::<Vec<i32>>(), vec!(4, 2, 3, 1));
2008     }
2009
2010     #[test]
2011     fn test_iter() {
2012         let mut d = RingBuf::new();
2013         assert_eq!(d.iter().next(), None);
2014         assert_eq!(d.iter().size_hint(), (0, Some(0)));
2015
2016         for i in 0..5 {
2017             d.push_back(i);
2018         }
2019         {
2020             let b: &[_] = &[&0,&1,&2,&3,&4];
2021             assert_eq!(d.iter().collect::<Vec<&i32>>(), b);
2022         }
2023
2024         for i in 6..9 {
2025             d.push_front(i);
2026         }
2027         {
2028             let b: &[_] = &[&8,&7,&6,&0,&1,&2,&3,&4];
2029             assert_eq!(d.iter().collect::<Vec<&i32>>(), b);
2030         }
2031
2032         let mut it = d.iter();
2033         let mut len = d.len();
2034         loop {
2035             match it.next() {
2036                 None => break,
2037                 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
2038             }
2039         }
2040     }
2041
2042     #[test]
2043     fn test_rev_iter() {
2044         let mut d = RingBuf::new();
2045         assert_eq!(d.iter().rev().next(), None);
2046
2047         for i in 0..5 {
2048             d.push_back(i);
2049         }
2050         {
2051             let b: &[_] = &[&4,&3,&2,&1,&0];
2052             assert_eq!(d.iter().rev().collect::<Vec<&i32>>(), b);
2053         }
2054
2055         for i in 6..9 {
2056             d.push_front(i);
2057         }
2058         let b: &[_] = &[&4,&3,&2,&1,&0,&6,&7,&8];
2059         assert_eq!(d.iter().rev().collect::<Vec<&i32>>(), b);
2060     }
2061
2062     #[test]
2063     fn test_mut_rev_iter_wrap() {
2064         let mut d = RingBuf::with_capacity(3);
2065         assert!(d.iter_mut().rev().next().is_none());
2066
2067         d.push_back(1);
2068         d.push_back(2);
2069         d.push_back(3);
2070         assert_eq!(d.pop_front(), Some(1));
2071         d.push_back(4);
2072
2073         assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<i32>>(),
2074                    vec!(4, 3, 2));
2075     }
2076
2077     #[test]
2078     fn test_mut_iter() {
2079         let mut d = RingBuf::new();
2080         assert!(d.iter_mut().next().is_none());
2081
2082         for i in 0u..3 {
2083             d.push_front(i);
2084         }
2085
2086         for (i, elt) in d.iter_mut().enumerate() {
2087             assert_eq!(*elt, 2 - i);
2088             *elt = i;
2089         }
2090
2091         {
2092             let mut it = d.iter_mut();
2093             assert_eq!(*it.next().unwrap(), 0);
2094             assert_eq!(*it.next().unwrap(), 1);
2095             assert_eq!(*it.next().unwrap(), 2);
2096             assert!(it.next().is_none());
2097         }
2098     }
2099
2100     #[test]
2101     fn test_mut_rev_iter() {
2102         let mut d = RingBuf::new();
2103         assert!(d.iter_mut().rev().next().is_none());
2104
2105         for i in 0u..3 {
2106             d.push_front(i);
2107         }
2108
2109         for (i, elt) in d.iter_mut().rev().enumerate() {
2110             assert_eq!(*elt, i);
2111             *elt = i;
2112         }
2113
2114         {
2115             let mut it = d.iter_mut().rev();
2116             assert_eq!(*it.next().unwrap(), 0);
2117             assert_eq!(*it.next().unwrap(), 1);
2118             assert_eq!(*it.next().unwrap(), 2);
2119             assert!(it.next().is_none());
2120         }
2121     }
2122
2123     #[test]
2124     fn test_into_iter() {
2125
2126         // Empty iter
2127         {
2128             let d: RingBuf<i32> = RingBuf::new();
2129             let mut iter = d.into_iter();
2130
2131             assert_eq!(iter.size_hint(), (0, Some(0)));
2132             assert_eq!(iter.next(), None);
2133             assert_eq!(iter.size_hint(), (0, Some(0)));
2134         }
2135
2136         // simple iter
2137         {
2138             let mut d = RingBuf::new();
2139             for i in 0..5 {
2140                 d.push_back(i);
2141             }
2142
2143             let b = vec![0,1,2,3,4];
2144             assert_eq!(d.into_iter().collect::<Vec<i32>>(), b);
2145         }
2146
2147         // wrapped iter
2148         {
2149             let mut d = RingBuf::new();
2150             for i in 0..5 {
2151                 d.push_back(i);
2152             }
2153             for i in 6..9 {
2154                 d.push_front(i);
2155             }
2156
2157             let b = vec![8,7,6,0,1,2,3,4];
2158             assert_eq!(d.into_iter().collect::<Vec<i32>>(), b);
2159         }
2160
2161         // partially used
2162         {
2163             let mut d = RingBuf::new();
2164             for i in 0..5 {
2165                 d.push_back(i);
2166             }
2167             for i in 6..9 {
2168                 d.push_front(i);
2169             }
2170
2171             let mut it = d.into_iter();
2172             assert_eq!(it.size_hint(), (8, Some(8)));
2173             assert_eq!(it.next(), Some(8));
2174             assert_eq!(it.size_hint(), (7, Some(7)));
2175             assert_eq!(it.next_back(), Some(4));
2176             assert_eq!(it.size_hint(), (6, Some(6)));
2177             assert_eq!(it.next(), Some(7));
2178             assert_eq!(it.size_hint(), (5, Some(5)));
2179         }
2180     }
2181
2182     #[test]
2183     fn test_drain() {
2184
2185         // Empty iter
2186         {
2187             let mut d: RingBuf<i32> = RingBuf::new();
2188
2189             {
2190                 let mut iter = d.drain();
2191
2192                 assert_eq!(iter.size_hint(), (0, Some(0)));
2193                 assert_eq!(iter.next(), None);
2194                 assert_eq!(iter.size_hint(), (0, Some(0)));
2195             }
2196
2197             assert!(d.is_empty());
2198         }
2199
2200         // simple iter
2201         {
2202             let mut d = RingBuf::new();
2203             for i in 0..5 {
2204                 d.push_back(i);
2205             }
2206
2207             assert_eq!(d.drain().collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
2208             assert!(d.is_empty());
2209         }
2210
2211         // wrapped iter
2212         {
2213             let mut d = RingBuf::new();
2214             for i in 0..5 {
2215                 d.push_back(i);
2216             }
2217             for i in 6..9 {
2218                 d.push_front(i);
2219             }
2220
2221             assert_eq!(d.drain().collect::<Vec<_>>(), [8,7,6,0,1,2,3,4]);
2222             assert!(d.is_empty());
2223         }
2224
2225         // partially used
2226         {
2227             let mut d: RingBuf<i32> = RingBuf::new();
2228             for i in 0..5 {
2229                 d.push_back(i);
2230             }
2231             for i in 6..9 {
2232                 d.push_front(i);
2233             }
2234
2235             {
2236                 let mut it = d.drain();
2237                 assert_eq!(it.size_hint(), (8, Some(8)));
2238                 assert_eq!(it.next(), Some(8));
2239                 assert_eq!(it.size_hint(), (7, Some(7)));
2240                 assert_eq!(it.next_back(), Some(4));
2241                 assert_eq!(it.size_hint(), (6, Some(6)));
2242                 assert_eq!(it.next(), Some(7));
2243                 assert_eq!(it.size_hint(), (5, Some(5)));
2244             }
2245             assert!(d.is_empty());
2246         }
2247     }
2248
2249     #[test]
2250     fn test_from_iter() {
2251         use core::iter;
2252         let v = vec!(1,2,3,4,5,6,7);
2253         let deq: RingBuf<i32> = v.iter().map(|&x| x).collect();
2254         let u: Vec<i32> = deq.iter().map(|&x| x).collect();
2255         assert_eq!(u, v);
2256
2257         let seq = iter::count(0u, 2).take(256);
2258         let deq: RingBuf<uint> = seq.collect();
2259         for (i, &x) in deq.iter().enumerate() {
2260             assert_eq!(2*i, x);
2261         }
2262         assert_eq!(deq.len(), 256);
2263     }
2264
2265     #[test]
2266     fn test_clone() {
2267         let mut d = RingBuf::new();
2268         d.push_front(17);
2269         d.push_front(42);
2270         d.push_back(137);
2271         d.push_back(137);
2272         assert_eq!(d.len(), 4u);
2273         let mut e = d.clone();
2274         assert_eq!(e.len(), 4u);
2275         while !d.is_empty() {
2276             assert_eq!(d.pop_back(), e.pop_back());
2277         }
2278         assert_eq!(d.len(), 0u);
2279         assert_eq!(e.len(), 0u);
2280     }
2281
2282     #[test]
2283     fn test_eq() {
2284         let mut d = RingBuf::new();
2285         assert!(d == RingBuf::with_capacity(0));
2286         d.push_front(137);
2287         d.push_front(17);
2288         d.push_front(42);
2289         d.push_back(137);
2290         let mut e = RingBuf::with_capacity(0);
2291         e.push_back(42);
2292         e.push_back(17);
2293         e.push_back(137);
2294         e.push_back(137);
2295         assert!(&e == &d);
2296         e.pop_back();
2297         e.push_back(0);
2298         assert!(e != d);
2299         e.clear();
2300         assert!(e == RingBuf::new());
2301     }
2302
2303     #[test]
2304     fn test_hash() {
2305       let mut x = RingBuf::new();
2306       let mut y = RingBuf::new();
2307
2308       x.push_back(1);
2309       x.push_back(2);
2310       x.push_back(3);
2311
2312       y.push_back(0);
2313       y.push_back(1);
2314       y.pop_front();
2315       y.push_back(2);
2316       y.push_back(3);
2317
2318       assert!(hash::hash::<_, SipHasher>(&x) == hash::hash::<_, SipHasher>(&y));
2319     }
2320
2321     #[test]
2322     fn test_ord() {
2323         let x = RingBuf::new();
2324         let mut y = RingBuf::new();
2325         y.push_back(1);
2326         y.push_back(2);
2327         y.push_back(3);
2328         assert!(x < y);
2329         assert!(y > x);
2330         assert!(x <= x);
2331         assert!(x >= x);
2332     }
2333
2334     #[test]
2335     fn test_show() {
2336         let ringbuf: RingBuf<i32> = (0..10).collect();
2337         assert_eq!(format!("{:?}", ringbuf), "RingBuf [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
2338
2339         let ringbuf: RingBuf<&str> = vec!["just", "one", "test", "more"].iter()
2340                                                                         .map(|&s| s)
2341                                                                         .collect();
2342         assert_eq!(format!("{:?}", ringbuf), "RingBuf [\"just\", \"one\", \"test\", \"more\"]");
2343     }
2344
2345     #[test]
2346     fn test_drop() {
2347         static mut drops: uint = 0;
2348         struct Elem;
2349         impl Drop for Elem {
2350             fn drop(&mut self) {
2351                 unsafe { drops += 1; }
2352             }
2353         }
2354
2355         let mut ring = RingBuf::new();
2356         ring.push_back(Elem);
2357         ring.push_front(Elem);
2358         ring.push_back(Elem);
2359         ring.push_front(Elem);
2360         drop(ring);
2361
2362         assert_eq!(unsafe {drops}, 4);
2363     }
2364
2365     #[test]
2366     fn test_drop_with_pop() {
2367         static mut drops: uint = 0;
2368         struct Elem;
2369         impl Drop for Elem {
2370             fn drop(&mut self) {
2371                 unsafe { drops += 1; }
2372             }
2373         }
2374
2375         let mut ring = RingBuf::new();
2376         ring.push_back(Elem);
2377         ring.push_front(Elem);
2378         ring.push_back(Elem);
2379         ring.push_front(Elem);
2380
2381         drop(ring.pop_back());
2382         drop(ring.pop_front());
2383         assert_eq!(unsafe {drops}, 2);
2384
2385         drop(ring);
2386         assert_eq!(unsafe {drops}, 4);
2387     }
2388
2389     #[test]
2390     fn test_drop_clear() {
2391         static mut drops: uint = 0;
2392         struct Elem;
2393         impl Drop for Elem {
2394             fn drop(&mut self) {
2395                 unsafe { drops += 1; }
2396             }
2397         }
2398
2399         let mut ring = RingBuf::new();
2400         ring.push_back(Elem);
2401         ring.push_front(Elem);
2402         ring.push_back(Elem);
2403         ring.push_front(Elem);
2404         ring.clear();
2405         assert_eq!(unsafe {drops}, 4);
2406
2407         drop(ring);
2408         assert_eq!(unsafe {drops}, 4);
2409     }
2410
2411     #[test]
2412     fn test_reserve_grow() {
2413         // test growth path A
2414         // [T o o H] -> [T o o H . . . . ]
2415         let mut ring = RingBuf::with_capacity(4);
2416         for i in 0..3 {
2417             ring.push_back(i);
2418         }
2419         ring.reserve(7);
2420         for i in 0..3 {
2421             assert_eq!(ring.pop_front(), Some(i));
2422         }
2423
2424         // test growth path B
2425         // [H T o o] -> [. T o o H . . . ]
2426         let mut ring = RingBuf::with_capacity(4);
2427         for i in 0..1 {
2428             ring.push_back(i);
2429             assert_eq!(ring.pop_front(), Some(i));
2430         }
2431         for i in 0..3 {
2432             ring.push_back(i);
2433         }
2434         ring.reserve(7);
2435         for i in 0..3 {
2436             assert_eq!(ring.pop_front(), Some(i));
2437         }
2438
2439         // test growth path C
2440         // [o o H T] -> [o o H . . . . T ]
2441         let mut ring = RingBuf::with_capacity(4);
2442         for i in 0..3 {
2443             ring.push_back(i);
2444             assert_eq!(ring.pop_front(), Some(i));
2445         }
2446         for i in 0..3 {
2447             ring.push_back(i);
2448         }
2449         ring.reserve(7);
2450         for i in 0..3 {
2451             assert_eq!(ring.pop_front(), Some(i));
2452         }
2453     }
2454
2455     #[test]
2456     fn test_get() {
2457         let mut ring = RingBuf::new();
2458         ring.push_back(0);
2459         assert_eq!(ring.get(0), Some(&0));
2460         assert_eq!(ring.get(1), None);
2461
2462         ring.push_back(1);
2463         assert_eq!(ring.get(0), Some(&0));
2464         assert_eq!(ring.get(1), Some(&1));
2465         assert_eq!(ring.get(2), None);
2466
2467         ring.push_back(2);
2468         assert_eq!(ring.get(0), Some(&0));
2469         assert_eq!(ring.get(1), Some(&1));
2470         assert_eq!(ring.get(2), Some(&2));
2471         assert_eq!(ring.get(3), None);
2472
2473         assert_eq!(ring.pop_front(), Some(0));
2474         assert_eq!(ring.get(0), Some(&1));
2475         assert_eq!(ring.get(1), Some(&2));
2476         assert_eq!(ring.get(2), None);
2477
2478         assert_eq!(ring.pop_front(), Some(1));
2479         assert_eq!(ring.get(0), Some(&2));
2480         assert_eq!(ring.get(1), None);
2481
2482         assert_eq!(ring.pop_front(), Some(2));
2483         assert_eq!(ring.get(0), None);
2484         assert_eq!(ring.get(1), None);
2485     }
2486
2487     #[test]
2488     fn test_get_mut() {
2489         let mut ring = RingBuf::new();
2490         for i in 0..3 {
2491             ring.push_back(i);
2492         }
2493
2494         match ring.get_mut(1) {
2495             Some(x) => *x = -1,
2496             None => ()
2497         };
2498
2499         assert_eq!(ring.get_mut(0), Some(&mut 0));
2500         assert_eq!(ring.get_mut(1), Some(&mut -1));
2501         assert_eq!(ring.get_mut(2), Some(&mut 2));
2502         assert_eq!(ring.get_mut(3), None);
2503
2504         assert_eq!(ring.pop_front(), Some(0));
2505         assert_eq!(ring.get_mut(0), Some(&mut -1));
2506         assert_eq!(ring.get_mut(1), Some(&mut 2));
2507         assert_eq!(ring.get_mut(2), None);
2508     }
2509
2510     #[test]
2511     fn test_swap_front_back_remove() {
2512         fn test(back: bool) {
2513             // This test checks that every single combination of tail position and length is tested.
2514             // Capacity 15 should be large enough to cover every case.
2515             let mut tester = RingBuf::with_capacity(15);
2516             let usable_cap = tester.capacity();
2517             let final_len = usable_cap / 2;
2518
2519             for len in 0..final_len {
2520                 let expected = if back {
2521                     (0..len).collect()
2522                 } else {
2523                     (0..len).rev().collect()
2524                 };
2525                 for tail_pos in 0..usable_cap {
2526                     tester.tail = tail_pos;
2527                     tester.head = tail_pos;
2528                     if back {
2529                         for i in 0..len * 2 {
2530                             tester.push_front(i);
2531                         }
2532                         for i in 0..len {
2533                             assert_eq!(tester.swap_back_remove(i), Some(len * 2 - 1 - i));
2534                         }
2535                     } else {
2536                         for i in 0..len * 2 {
2537                             tester.push_back(i);
2538                         }
2539                         for i in 0..len {
2540                             let idx = tester.len() - 1 - i;
2541                             assert_eq!(tester.swap_front_remove(idx), Some(len * 2 - 1 - i));
2542                         }
2543                     }
2544                     assert!(tester.tail < tester.cap);
2545                     assert!(tester.head < tester.cap);
2546                     assert_eq!(tester, expected);
2547                 }
2548             }
2549         }
2550         test(true);
2551         test(false);
2552     }
2553
2554     #[test]
2555     fn test_insert() {
2556         // This test checks that every single combination of tail position, length, and
2557         // insertion position is tested. Capacity 15 should be large enough to cover every case.
2558
2559         let mut tester = RingBuf::with_capacity(15);
2560         // can't guarantee we got 15, so have to get what we got.
2561         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2562         // this test isn't covering what it wants to
2563         let cap = tester.capacity();
2564
2565
2566         // len is the length *after* insertion
2567         for len in 1..cap {
2568             // 0, 1, 2, .., len - 1
2569             let expected = iter::count(0, 1).take(len).collect();
2570             for tail_pos in 0..cap {
2571                 for to_insert in 0..len {
2572                     tester.tail = tail_pos;
2573                     tester.head = tail_pos;
2574                     for i in 0..len {
2575                         if i != to_insert {
2576                             tester.push_back(i);
2577                         }
2578                     }
2579                     tester.insert(to_insert, to_insert);
2580                     assert!(tester.tail < tester.cap);
2581                     assert!(tester.head < tester.cap);
2582                     assert_eq!(tester, expected);
2583                 }
2584             }
2585         }
2586     }
2587
2588     #[test]
2589     fn test_remove() {
2590         // This test checks that every single combination of tail position, length, and
2591         // removal position is tested. Capacity 15 should be large enough to cover every case.
2592
2593         let mut tester = RingBuf::with_capacity(15);
2594         // can't guarantee we got 15, so have to get what we got.
2595         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2596         // this test isn't covering what it wants to
2597         let cap = tester.capacity();
2598
2599         // len is the length *after* removal
2600         for len in 0..cap - 1 {
2601             // 0, 1, 2, .., len - 1
2602             let expected = iter::count(0, 1).take(len).collect();
2603             for tail_pos in 0..cap {
2604                 for to_remove in 0..len + 1 {
2605                     tester.tail = tail_pos;
2606                     tester.head = tail_pos;
2607                     for i in 0..len {
2608                         if i == to_remove {
2609                             tester.push_back(1234);
2610                         }
2611                         tester.push_back(i);
2612                     }
2613                     if to_remove == len {
2614                         tester.push_back(1234);
2615                     }
2616                     tester.remove(to_remove);
2617                     assert!(tester.tail < tester.cap);
2618                     assert!(tester.head < tester.cap);
2619                     assert_eq!(tester, expected);
2620                 }
2621             }
2622         }
2623     }
2624
2625     #[test]
2626     fn test_shrink_to_fit() {
2627         // This test checks that every single combination of head and tail position,
2628         // is tested. Capacity 15 should be large enough to cover every case.
2629
2630         let mut tester = RingBuf::with_capacity(15);
2631         // can't guarantee we got 15, so have to get what we got.
2632         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2633         // this test isn't covering what it wants to
2634         let cap = tester.capacity();
2635         tester.reserve(63);
2636         let max_cap = tester.capacity();
2637
2638         for len in 0..cap + 1 {
2639             // 0, 1, 2, .., len - 1
2640             let expected = iter::count(0, 1).take(len).collect();
2641             for tail_pos in 0..max_cap + 1 {
2642                 tester.tail = tail_pos;
2643                 tester.head = tail_pos;
2644                 tester.reserve(63);
2645                 for i in 0..len {
2646                     tester.push_back(i);
2647                 }
2648                 tester.shrink_to_fit();
2649                 assert!(tester.capacity() <= cap);
2650                 assert!(tester.tail < tester.cap);
2651                 assert!(tester.head < tester.cap);
2652                 assert_eq!(tester, expected);
2653             }
2654         }
2655     }
2656
2657     #[test]
2658     fn test_front() {
2659         let mut ring = RingBuf::new();
2660         ring.push_back(10);
2661         ring.push_back(20);
2662         assert_eq!(ring.front(), Some(&10));
2663         ring.pop_front();
2664         assert_eq!(ring.front(), Some(&20));
2665         ring.pop_front();
2666         assert_eq!(ring.front(), None);
2667     }
2668
2669     #[test]
2670     fn test_as_slices() {
2671         let mut ring: RingBuf<i32> = RingBuf::with_capacity(127);
2672         let cap = ring.capacity() as i32;
2673         let first = cap/2;
2674         let last  = cap - first;
2675         for i in 0..first {
2676             ring.push_back(i);
2677
2678             let (left, right) = ring.as_slices();
2679             let expected: Vec<_> = (0..i+1).collect();
2680             assert_eq!(left, expected);
2681             assert_eq!(right, []);
2682         }
2683
2684         for j in -last..0 {
2685             ring.push_front(j);
2686             let (left, right) = ring.as_slices();
2687             let expected_left: Vec<_> = (-last..j+1).rev().collect();
2688             let expected_right: Vec<_> = (0..first).collect();
2689             assert_eq!(left, expected_left);
2690             assert_eq!(right, expected_right);
2691         }
2692
2693         assert_eq!(ring.len() as i32, cap);
2694         assert_eq!(ring.capacity() as i32, cap);
2695     }
2696
2697     #[test]
2698     fn test_as_mut_slices() {
2699         let mut ring: RingBuf<i32> = RingBuf::with_capacity(127);
2700         let cap = ring.capacity() as i32;
2701         let first = cap/2;
2702         let last  = cap - first;
2703         for i in 0..first {
2704             ring.push_back(i);
2705
2706             let (left, right) = ring.as_mut_slices();
2707             let expected: Vec<_> = (0..i+1).collect();
2708             assert_eq!(left, expected);
2709             assert_eq!(right, []);
2710         }
2711
2712         for j in -last..0 {
2713             ring.push_front(j);
2714             let (left, right) = ring.as_mut_slices();
2715             let expected_left: Vec<_> = (-last..j+1).rev().collect();
2716             let expected_right: Vec<_> = (0..first).collect();
2717             assert_eq!(left, expected_left);
2718             assert_eq!(right, expected_right);
2719         }
2720
2721         assert_eq!(ring.len() as i32, cap);
2722         assert_eq!(ring.capacity() as i32, cap);
2723     }
2724 }