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