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