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