src/libcollections/ring_buf.rs

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