src/libcollections/ring_buf.rs

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