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 // NOTE(stage0): remove impl after a snapshot
1376 #[cfg(stage0)]
1377 #[stable]
1378 impl<A> Index<uint, A> for RingBuf<A> {
1379     #[inline]
1380     fn index<'a>(&'a self, i: &uint) -> &'a A {
1381         self.get(*i).expect("Out of bounds access")
1382     }
1383 }
1384
1385 #[cfg(not(stage0))]  // NOTE(stage0): remove cfg after a snapshot
1386 #[stable]
1387 impl<A> Index<uint> for RingBuf<A> {
1388     type Output = A;
1389
1390     #[inline]
1391     fn index<'a>(&'a self, i: &uint) -> &'a A {
1392         self.get(*i).expect("Out of bounds access")
1393     }
1394 }
1395
1396 // NOTE(stage0): remove impl after a snapshot
1397 #[cfg(stage0)]
1398 #[stable]
1399 impl<A> IndexMut<uint, A> for RingBuf<A> {
1400     #[inline]
1401     fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut A {
1402         self.get_mut(*i).expect("Out of bounds access")
1403     }
1404 }
1405
1406 #[cfg(not(stage0))]  // NOTE(stage0): remove cfg after a snapshot
1407 #[stable]
1408 impl<A> IndexMut<uint> for RingBuf<A> {
1409     type Output = A;
1410
1411     #[inline]
1412     fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut A {
1413         self.get_mut(*i).expect("Out of bounds access")
1414     }
1415 }
1416
1417 #[stable]
1418 impl<A> FromIterator<A> for RingBuf<A> {
1419     fn from_iter<T: Iterator<Item=A>>(iterator: T) -> RingBuf<A> {
1420         let (lower, _) = iterator.size_hint();
1421         let mut deq = RingBuf::with_capacity(lower);
1422         deq.extend(iterator);
1423         deq
1424     }
1425 }
1426
1427 #[stable]
1428 impl<A> Extend<A> for RingBuf<A> {
1429     fn extend<T: Iterator<Item=A>>(&mut self, mut iterator: T) {
1430         for elt in iterator {
1431             self.push_back(elt);
1432         }
1433     }
1434 }
1435
1436 #[stable]
1437 impl<T: fmt::Show> fmt::Show for RingBuf<T> {
1438     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1439         try!(write!(f, "["));
1440
1441         for (i, e) in self.iter().enumerate() {
1442             if i != 0 { try!(write!(f, ", ")); }
1443             try!(write!(f, "{}", *e));
1444         }
1445
1446         write!(f, "]")
1447     }
1448 }
1449
1450 #[cfg(test)]
1451 mod tests {
1452     use self::Taggy::*;
1453     use self::Taggypar::*;
1454     use prelude::*;
1455     use core::cmp;
1456     use core::iter;
1457     use std::fmt::Show;
1458     use std::hash;
1459     use test::Bencher;
1460     use test;
1461
1462     use super::RingBuf;
1463
1464     #[test]
1465     #[allow(deprecated)]
1466     fn test_simple() {
1467         let mut d = RingBuf::new();
1468         assert_eq!(d.len(), 0u);
1469         d.push_front(17i);
1470         d.push_front(42i);
1471         d.push_back(137);
1472         assert_eq!(d.len(), 3u);
1473         d.push_back(137);
1474         assert_eq!(d.len(), 4u);
1475         debug!("{}", d.front());
1476         assert_eq!(*d.front().unwrap(), 42);
1477         debug!("{}", d.back());
1478         assert_eq!(*d.back().unwrap(), 137);
1479         let mut i = d.pop_front();
1480         debug!("{}", i);
1481         assert_eq!(i, Some(42));
1482         i = d.pop_back();
1483         debug!("{}", i);
1484         assert_eq!(i, Some(137));
1485         i = d.pop_back();
1486         debug!("{}", i);
1487         assert_eq!(i, Some(137));
1488         i = d.pop_back();
1489         debug!("{}", i);
1490         assert_eq!(i, Some(17));
1491         assert_eq!(d.len(), 0u);
1492         d.push_back(3);
1493         assert_eq!(d.len(), 1u);
1494         d.push_front(2);
1495         assert_eq!(d.len(), 2u);
1496         d.push_back(4);
1497         assert_eq!(d.len(), 3u);
1498         d.push_front(1);
1499         assert_eq!(d.len(), 4u);
1500         debug!("{}", d[0]);
1501         debug!("{}", d[1]);
1502         debug!("{}", d[2]);
1503         debug!("{}", d[3]);
1504         assert_eq!(d[0], 1);
1505         assert_eq!(d[1], 2);
1506         assert_eq!(d[2], 3);
1507         assert_eq!(d[3], 4);
1508     }
1509
1510     #[cfg(test)]
1511     fn test_parameterized<T:Clone + PartialEq + Show>(a: T, b: T, c: T, d: T) {
1512         let mut deq = RingBuf::new();
1513         assert_eq!(deq.len(), 0);
1514         deq.push_front(a.clone());
1515         deq.push_front(b.clone());
1516         deq.push_back(c.clone());
1517         assert_eq!(deq.len(), 3);
1518         deq.push_back(d.clone());
1519         assert_eq!(deq.len(), 4);
1520         assert_eq!((*deq.front().unwrap()).clone(), b.clone());
1521         assert_eq!((*deq.back().unwrap()).clone(), d.clone());
1522         assert_eq!(deq.pop_front().unwrap(), b.clone());
1523         assert_eq!(deq.pop_back().unwrap(), d.clone());
1524         assert_eq!(deq.pop_back().unwrap(), c.clone());
1525         assert_eq!(deq.pop_back().unwrap(), a.clone());
1526         assert_eq!(deq.len(), 0);
1527         deq.push_back(c.clone());
1528         assert_eq!(deq.len(), 1);
1529         deq.push_front(b.clone());
1530         assert_eq!(deq.len(), 2);
1531         deq.push_back(d.clone());
1532         assert_eq!(deq.len(), 3);
1533         deq.push_front(a.clone());
1534         assert_eq!(deq.len(), 4);
1535         assert_eq!(deq[0].clone(), a.clone());
1536         assert_eq!(deq[1].clone(), b.clone());
1537         assert_eq!(deq[2].clone(), c.clone());
1538         assert_eq!(deq[3].clone(), d.clone());
1539     }
1540
1541     #[test]
1542     fn test_push_front_grow() {
1543         let mut deq = RingBuf::new();
1544         for i in range(0u, 66) {
1545             deq.push_front(i);
1546         }
1547         assert_eq!(deq.len(), 66);
1548
1549         for i in range(0u, 66) {
1550             assert_eq!(deq[i], 65 - i);
1551         }
1552
1553         let mut deq = RingBuf::new();
1554         for i in range(0u, 66) {
1555             deq.push_back(i);
1556         }
1557
1558         for i in range(0u, 66) {
1559             assert_eq!(deq[i], i);
1560         }
1561     }
1562
1563     #[test]
1564     fn test_index() {
1565         let mut deq = RingBuf::new();
1566         for i in range(1u, 4) {
1567             deq.push_front(i);
1568         }
1569         assert_eq!(deq[1], 2);
1570     }
1571
1572     #[test]
1573     #[should_fail]
1574     fn test_index_out_of_bounds() {
1575         let mut deq = RingBuf::new();
1576         for i in range(1u, 4) {
1577             deq.push_front(i);
1578         }
1579         deq[3];
1580     }
1581
1582     #[bench]
1583     fn bench_new(b: &mut test::Bencher) {
1584         b.iter(|| {
1585             let ring: RingBuf<u64> = RingBuf::new();
1586             test::black_box(ring);
1587         })
1588     }
1589
1590     #[bench]
1591     fn bench_push_back_100(b: &mut test::Bencher) {
1592         let mut deq = RingBuf::with_capacity(101);
1593         b.iter(|| {
1594             for i in range(0i, 100) {
1595                 deq.push_back(i);
1596             }
1597             deq.head = 0;
1598             deq.tail = 0;
1599         })
1600     }
1601
1602     #[bench]
1603     fn bench_push_front_100(b: &mut test::Bencher) {
1604         let mut deq = RingBuf::with_capacity(101);
1605         b.iter(|| {
1606             for i in range(0i, 100) {
1607                 deq.push_front(i);
1608             }
1609             deq.head = 0;
1610             deq.tail = 0;
1611         })
1612     }
1613
1614     #[bench]
1615     fn bench_pop_back_100(b: &mut test::Bencher) {
1616         let mut deq: RingBuf<int> = RingBuf::with_capacity(101);
1617
1618         b.iter(|| {
1619             deq.head = 100;
1620             deq.tail = 0;
1621             while !deq.is_empty() {
1622                 test::black_box(deq.pop_back());
1623             }
1624         })
1625     }
1626
1627     #[bench]
1628     fn bench_pop_front_100(b: &mut test::Bencher) {
1629         let mut deq: RingBuf<int> = RingBuf::with_capacity(101);
1630
1631         b.iter(|| {
1632             deq.head = 100;
1633             deq.tail = 0;
1634             while !deq.is_empty() {
1635                 test::black_box(deq.pop_front());
1636             }
1637         })
1638     }
1639
1640     #[bench]
1641     fn bench_grow_1025(b: &mut test::Bencher) {
1642         b.iter(|| {
1643             let mut deq = RingBuf::new();
1644             for i in range(0i, 1025) {
1645                 deq.push_front(i);
1646             }
1647             test::black_box(deq);
1648         })
1649     }
1650
1651     #[bench]
1652     fn bench_iter_1000(b: &mut test::Bencher) {
1653         let ring: RingBuf<int> = range(0i, 1000).collect();
1654
1655         b.iter(|| {
1656             let mut sum = 0;
1657             for &i in ring.iter() {
1658                 sum += i;
1659             }
1660             test::black_box(sum);
1661         })
1662     }
1663
1664     #[bench]
1665     fn bench_mut_iter_1000(b: &mut test::Bencher) {
1666         let mut ring: RingBuf<int> = range(0i, 1000).collect();
1667
1668         b.iter(|| {
1669             let mut sum = 0;
1670             for i in ring.iter_mut() {
1671                 sum += *i;
1672             }
1673             test::black_box(sum);
1674         })
1675     }
1676
1677     #[deriving(Clone, PartialEq, Show)]
1678     enum Taggy {
1679         One(int),
1680         Two(int, int),
1681         Three(int, int, int),
1682     }
1683
1684     #[deriving(Clone, PartialEq, Show)]
1685     enum Taggypar<T> {
1686         Onepar(int),
1687         Twopar(int, int),
1688         Threepar(int, int, int),
1689     }
1690
1691     #[deriving(Clone, PartialEq, Show)]
1692     struct RecCy {
1693         x: int,
1694         y: int,
1695         t: Taggy
1696     }
1697
1698     #[test]
1699     fn test_param_int() {
1700         test_parameterized::<int>(5, 72, 64, 175);
1701     }
1702
1703     #[test]
1704     fn test_param_taggy() {
1705         test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
1706     }
1707
1708     #[test]
1709     fn test_param_taggypar() {
1710         test_parameterized::<Taggypar<int>>(Onepar::<int>(1),
1711                                             Twopar::<int>(1, 2),
1712                                             Threepar::<int>(1, 2, 3),
1713                                             Twopar::<int>(17, 42));
1714     }
1715
1716     #[test]
1717     fn test_param_reccy() {
1718         let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
1719         let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
1720         let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
1721         let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
1722         test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
1723     }
1724
1725     #[test]
1726     fn test_with_capacity() {
1727         let mut d = RingBuf::with_capacity(0);
1728         d.push_back(1i);
1729         assert_eq!(d.len(), 1);
1730         let mut d = RingBuf::with_capacity(50);
1731         d.push_back(1i);
1732         assert_eq!(d.len(), 1);
1733     }
1734
1735     #[test]
1736     fn test_with_capacity_non_power_two() {
1737         let mut d3 = RingBuf::with_capacity(3);
1738         d3.push_back(1i);
1739
1740         // X = None, | = lo
1741         // [|1, X, X]
1742         assert_eq!(d3.pop_front(), Some(1));
1743         // [X, |X, X]
1744         assert_eq!(d3.front(), None);
1745
1746         // [X, |3, X]
1747         d3.push_back(3);
1748         // [X, |3, 6]
1749         d3.push_back(6);
1750         // [X, X, |6]
1751         assert_eq!(d3.pop_front(), Some(3));
1752
1753         // Pushing the lo past half way point to trigger
1754         // the 'B' scenario for growth
1755         // [9, X, |6]
1756         d3.push_back(9);
1757         // [9, 12, |6]
1758         d3.push_back(12);
1759
1760         d3.push_back(15);
1761         // There used to be a bug here about how the
1762         // RingBuf made growth assumptions about the
1763         // underlying Vec which didn't hold and lead
1764         // to corruption.
1765         // (Vec grows to next power of two)
1766         //good- [9, 12, 15, X, X, X, X, |6]
1767         //bug-  [15, 12, X, X, X, |6, X, X]
1768         assert_eq!(d3.pop_front(), Some(6));
1769
1770         // Which leads us to the following state which
1771         // would be a failure case.
1772         //bug-  [15, 12, X, X, X, X, |X, X]
1773         assert_eq!(d3.front(), Some(&9));
1774     }
1775
1776     #[test]
1777     fn test_reserve_exact() {
1778         let mut d = RingBuf::new();
1779         d.push_back(0u64);
1780         d.reserve_exact(50);
1781         assert!(d.capacity() >= 51);
1782         let mut d = RingBuf::new();
1783         d.push_back(0u32);
1784         d.reserve_exact(50);
1785         assert!(d.capacity() >= 51);
1786     }
1787
1788     #[test]
1789     fn test_reserve() {
1790         let mut d = RingBuf::new();
1791         d.push_back(0u64);
1792         d.reserve(50);
1793         assert!(d.capacity() >= 51);
1794         let mut d = RingBuf::new();
1795         d.push_back(0u32);
1796         d.reserve(50);
1797         assert!(d.capacity() >= 51);
1798     }
1799
1800     #[test]
1801     fn test_swap() {
1802         let mut d: RingBuf<int> = range(0i, 5).collect();
1803         d.pop_front();
1804         d.swap(0, 3);
1805         assert_eq!(d.iter().map(|&x|x).collect::<Vec<int>>(), vec!(4, 2, 3, 1));
1806     }
1807
1808     #[test]
1809     fn test_iter() {
1810         let mut d = RingBuf::new();
1811         assert_eq!(d.iter().next(), None);
1812         assert_eq!(d.iter().size_hint(), (0, Some(0)));
1813
1814         for i in range(0i, 5) {
1815             d.push_back(i);
1816         }
1817         {
1818             let b: &[_] = &[&0,&1,&2,&3,&4];
1819             assert_eq!(d.iter().collect::<Vec<&int>>(), b);
1820         }
1821
1822         for i in range(6i, 9) {
1823             d.push_front(i);
1824         }
1825         {
1826             let b: &[_] = &[&8,&7,&6,&0,&1,&2,&3,&4];
1827             assert_eq!(d.iter().collect::<Vec<&int>>(), b);
1828         }
1829
1830         let mut it = d.iter();
1831         let mut len = d.len();
1832         loop {
1833             match it.next() {
1834                 None => break,
1835                 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
1836             }
1837         }
1838     }
1839
1840     #[test]
1841     fn test_rev_iter() {
1842         let mut d = RingBuf::new();
1843         assert_eq!(d.iter().rev().next(), None);
1844
1845         for i in range(0i, 5) {
1846             d.push_back(i);
1847         }
1848         {
1849             let b: &[_] = &[&4,&3,&2,&1,&0];
1850             assert_eq!(d.iter().rev().collect::<Vec<&int>>(), b);
1851         }
1852
1853         for i in range(6i, 9) {
1854             d.push_front(i);
1855         }
1856         let b: &[_] = &[&4,&3,&2,&1,&0,&6,&7,&8];
1857         assert_eq!(d.iter().rev().collect::<Vec<&int>>(), b);
1858     }
1859
1860     #[test]
1861     fn test_mut_rev_iter_wrap() {
1862         let mut d = RingBuf::with_capacity(3);
1863         assert!(d.iter_mut().rev().next().is_none());
1864
1865         d.push_back(1i);
1866         d.push_back(2);
1867         d.push_back(3);
1868         assert_eq!(d.pop_front(), Some(1));
1869         d.push_back(4);
1870
1871         assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<int>>(),
1872                    vec!(4, 3, 2));
1873     }
1874
1875     #[test]
1876     fn test_mut_iter() {
1877         let mut d = RingBuf::new();
1878         assert!(d.iter_mut().next().is_none());
1879
1880         for i in range(0u, 3) {
1881             d.push_front(i);
1882         }
1883
1884         for (i, elt) in d.iter_mut().enumerate() {
1885             assert_eq!(*elt, 2 - i);
1886             *elt = i;
1887         }
1888
1889         {
1890             let mut it = d.iter_mut();
1891             assert_eq!(*it.next().unwrap(), 0);
1892             assert_eq!(*it.next().unwrap(), 1);
1893             assert_eq!(*it.next().unwrap(), 2);
1894             assert!(it.next().is_none());
1895         }
1896     }
1897
1898     #[test]
1899     fn test_mut_rev_iter() {
1900         let mut d = RingBuf::new();
1901         assert!(d.iter_mut().rev().next().is_none());
1902
1903         for i in range(0u, 3) {
1904             d.push_front(i);
1905         }
1906
1907         for (i, elt) in d.iter_mut().rev().enumerate() {
1908             assert_eq!(*elt, i);
1909             *elt = i;
1910         }
1911
1912         {
1913             let mut it = d.iter_mut().rev();
1914             assert_eq!(*it.next().unwrap(), 0);
1915             assert_eq!(*it.next().unwrap(), 1);
1916             assert_eq!(*it.next().unwrap(), 2);
1917             assert!(it.next().is_none());
1918         }
1919     }
1920
1921     #[test]
1922     fn test_into_iter() {
1923
1924         // Empty iter
1925         {
1926             let d: RingBuf<int> = RingBuf::new();
1927             let mut iter = d.into_iter();
1928
1929             assert_eq!(iter.size_hint(), (0, Some(0)));
1930             assert_eq!(iter.next(), None);
1931             assert_eq!(iter.size_hint(), (0, Some(0)));
1932         }
1933
1934         // simple iter
1935         {
1936             let mut d = RingBuf::new();
1937             for i in range(0i, 5) {
1938                 d.push_back(i);
1939             }
1940
1941             let b = vec![0,1,2,3,4];
1942             assert_eq!(d.into_iter().collect::<Vec<int>>(), b);
1943         }
1944
1945         // wrapped iter
1946         {
1947             let mut d = RingBuf::new();
1948             for i in range(0i, 5) {
1949                 d.push_back(i);
1950             }
1951             for i in range(6, 9) {
1952                 d.push_front(i);
1953             }
1954
1955             let b = vec![8,7,6,0,1,2,3,4];
1956             assert_eq!(d.into_iter().collect::<Vec<int>>(), b);
1957         }
1958
1959         // partially used
1960         {
1961             let mut d = RingBuf::new();
1962             for i in range(0i, 5) {
1963                 d.push_back(i);
1964             }
1965             for i in range(6, 9) {
1966                 d.push_front(i);
1967             }
1968
1969             let mut it = d.into_iter();
1970             assert_eq!(it.size_hint(), (8, Some(8)));
1971             assert_eq!(it.next(), Some(8));
1972             assert_eq!(it.size_hint(), (7, Some(7)));
1973             assert_eq!(it.next_back(), Some(4));
1974             assert_eq!(it.size_hint(), (6, Some(6)));
1975             assert_eq!(it.next(), Some(7));
1976             assert_eq!(it.size_hint(), (5, Some(5)));
1977         }
1978     }
1979
1980     #[test]
1981     fn test_drain() {
1982
1983         // Empty iter
1984         {
1985             let mut d: RingBuf<int> = RingBuf::new();
1986
1987             {
1988                 let mut iter = d.drain();
1989
1990                 assert_eq!(iter.size_hint(), (0, Some(0)));
1991                 assert_eq!(iter.next(), None);
1992                 assert_eq!(iter.size_hint(), (0, Some(0)));
1993             }
1994
1995             assert!(d.is_empty());
1996         }
1997
1998         // simple iter
1999         {
2000             let mut d = RingBuf::new();
2001             for i in range(0i, 5) {
2002                 d.push_back(i);
2003             }
2004
2005             assert_eq!(d.drain().collect::<Vec<int>>(), [0, 1, 2, 3, 4]);
2006             assert!(d.is_empty());
2007         }
2008
2009         // wrapped iter
2010         {
2011             let mut d = RingBuf::new();
2012             for i in range(0i, 5) {
2013                 d.push_back(i);
2014             }
2015             for i in range(6, 9) {
2016                 d.push_front(i);
2017             }
2018
2019             assert_eq!(d.drain().collect::<Vec<int>>(), [8,7,6,0,1,2,3,4]);
2020             assert!(d.is_empty());
2021         }
2022
2023         // partially used
2024         {
2025             let mut d = RingBuf::new();
2026             for i in range(0i, 5) {
2027                 d.push_back(i);
2028             }
2029             for i in range(6, 9) {
2030                 d.push_front(i);
2031             }
2032
2033             {
2034                 let mut it = d.drain();
2035                 assert_eq!(it.size_hint(), (8, Some(8)));
2036                 assert_eq!(it.next(), Some(8));
2037                 assert_eq!(it.size_hint(), (7, Some(7)));
2038                 assert_eq!(it.next_back(), Some(4));
2039                 assert_eq!(it.size_hint(), (6, Some(6)));
2040                 assert_eq!(it.next(), Some(7));
2041                 assert_eq!(it.size_hint(), (5, Some(5)));
2042             }
2043             assert!(d.is_empty());
2044         }
2045     }
2046
2047     #[test]
2048     fn test_from_iter() {
2049         use core::iter;
2050         let v = vec!(1i,2,3,4,5,6,7);
2051         let deq: RingBuf<int> = v.iter().map(|&x| x).collect();
2052         let u: Vec<int> = deq.iter().map(|&x| x).collect();
2053         assert_eq!(u, v);
2054
2055         let seq = iter::count(0u, 2).take(256);
2056         let deq: RingBuf<uint> = seq.collect();
2057         for (i, &x) in deq.iter().enumerate() {
2058             assert_eq!(2*i, x);
2059         }
2060         assert_eq!(deq.len(), 256);
2061     }
2062
2063     #[test]
2064     fn test_clone() {
2065         let mut d = RingBuf::new();
2066         d.push_front(17i);
2067         d.push_front(42);
2068         d.push_back(137);
2069         d.push_back(137);
2070         assert_eq!(d.len(), 4u);
2071         let mut e = d.clone();
2072         assert_eq!(e.len(), 4u);
2073         while !d.is_empty() {
2074             assert_eq!(d.pop_back(), e.pop_back());
2075         }
2076         assert_eq!(d.len(), 0u);
2077         assert_eq!(e.len(), 0u);
2078     }
2079
2080     #[test]
2081     fn test_eq() {
2082         let mut d = RingBuf::new();
2083         assert!(d == RingBuf::with_capacity(0));
2084         d.push_front(137i);
2085         d.push_front(17);
2086         d.push_front(42);
2087         d.push_back(137);
2088         let mut e = RingBuf::with_capacity(0);
2089         e.push_back(42);
2090         e.push_back(17);
2091         e.push_back(137);
2092         e.push_back(137);
2093         assert!(&e == &d);
2094         e.pop_back();
2095         e.push_back(0);
2096         assert!(e != d);
2097         e.clear();
2098         assert!(e == RingBuf::new());
2099     }
2100
2101     #[test]
2102     fn test_hash() {
2103       let mut x = RingBuf::new();
2104       let mut y = RingBuf::new();
2105
2106       x.push_back(1i);
2107       x.push_back(2);
2108       x.push_back(3);
2109
2110       y.push_back(0i);
2111       y.push_back(1i);
2112       y.pop_front();
2113       y.push_back(2);
2114       y.push_back(3);
2115
2116       assert!(hash::hash(&x) == hash::hash(&y));
2117     }
2118
2119     #[test]
2120     fn test_ord() {
2121         let x = RingBuf::new();
2122         let mut y = RingBuf::new();
2123         y.push_back(1i);
2124         y.push_back(2);
2125         y.push_back(3);
2126         assert!(x < y);
2127         assert!(y > x);
2128         assert!(x <= x);
2129         assert!(x >= x);
2130     }
2131
2132     #[test]
2133     fn test_show() {
2134         let ringbuf: RingBuf<int> = range(0i, 10).collect();
2135         assert!(format!("{}", ringbuf) == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
2136
2137         let ringbuf: RingBuf<&str> = vec!["just", "one", "test", "more"].iter()
2138                                                                         .map(|&s| s)
2139                                                                         .collect();
2140         assert!(format!("{}", ringbuf) == "[just, one, test, more]");
2141     }
2142
2143     #[test]
2144     fn test_drop() {
2145         static mut drops: uint = 0;
2146         struct Elem;
2147         impl Drop for Elem {
2148             fn drop(&mut self) {
2149                 unsafe { drops += 1; }
2150             }
2151         }
2152
2153         let mut ring = RingBuf::new();
2154         ring.push_back(Elem);
2155         ring.push_front(Elem);
2156         ring.push_back(Elem);
2157         ring.push_front(Elem);
2158         drop(ring);
2159
2160         assert_eq!(unsafe {drops}, 4);
2161     }
2162
2163     #[test]
2164     fn test_drop_with_pop() {
2165         static mut drops: uint = 0;
2166         struct Elem;
2167         impl Drop for Elem {
2168             fn drop(&mut self) {
2169                 unsafe { drops += 1; }
2170             }
2171         }
2172
2173         let mut ring = RingBuf::new();
2174         ring.push_back(Elem);
2175         ring.push_front(Elem);
2176         ring.push_back(Elem);
2177         ring.push_front(Elem);
2178
2179         drop(ring.pop_back());
2180         drop(ring.pop_front());
2181         assert_eq!(unsafe {drops}, 2);
2182
2183         drop(ring);
2184         assert_eq!(unsafe {drops}, 4);
2185     }
2186
2187     #[test]
2188     fn test_drop_clear() {
2189         static mut drops: uint = 0;
2190         struct Elem;
2191         impl Drop for Elem {
2192             fn drop(&mut self) {
2193                 unsafe { drops += 1; }
2194             }
2195         }
2196
2197         let mut ring = RingBuf::new();
2198         ring.push_back(Elem);
2199         ring.push_front(Elem);
2200         ring.push_back(Elem);
2201         ring.push_front(Elem);
2202         ring.clear();
2203         assert_eq!(unsafe {drops}, 4);
2204
2205         drop(ring);
2206         assert_eq!(unsafe {drops}, 4);
2207     }
2208
2209     #[test]
2210     fn test_reserve_grow() {
2211         // test growth path A
2212         // [T o o H] -> [T o o H . . . . ]
2213         let mut ring = RingBuf::with_capacity(4);
2214         for i in range(0i, 3) {
2215             ring.push_back(i);
2216         }
2217         ring.reserve(7);
2218         for i in range(0i, 3) {
2219             assert_eq!(ring.pop_front(), Some(i));
2220         }
2221
2222         // test growth path B
2223         // [H T o o] -> [. T o o H . . . ]
2224         let mut ring = RingBuf::with_capacity(4);
2225         for i in range(0i, 1) {
2226             ring.push_back(i);
2227             assert_eq!(ring.pop_front(), Some(i));
2228         }
2229         for i in range(0i, 3) {
2230             ring.push_back(i);
2231         }
2232         ring.reserve(7);
2233         for i in range(0i, 3) {
2234             assert_eq!(ring.pop_front(), Some(i));
2235         }
2236
2237         // test growth path C
2238         // [o o H T] -> [o o H . . . . T ]
2239         let mut ring = RingBuf::with_capacity(4);
2240         for i in range(0i, 3) {
2241             ring.push_back(i);
2242             assert_eq!(ring.pop_front(), Some(i));
2243         }
2244         for i in range(0i, 3) {
2245             ring.push_back(i);
2246         }
2247         ring.reserve(7);
2248         for i in range(0i, 3) {
2249             assert_eq!(ring.pop_front(), Some(i));
2250         }
2251     }
2252
2253     #[test]
2254     fn test_get() {
2255         let mut ring = RingBuf::new();
2256         ring.push_back(0i);
2257         assert_eq!(ring.get(0), Some(&0));
2258         assert_eq!(ring.get(1), None);
2259
2260         ring.push_back(1);
2261         assert_eq!(ring.get(0), Some(&0));
2262         assert_eq!(ring.get(1), Some(&1));
2263         assert_eq!(ring.get(2), None);
2264
2265         ring.push_back(2);
2266         assert_eq!(ring.get(0), Some(&0));
2267         assert_eq!(ring.get(1), Some(&1));
2268         assert_eq!(ring.get(2), Some(&2));
2269         assert_eq!(ring.get(3), None);
2270
2271         assert_eq!(ring.pop_front(), Some(0));
2272         assert_eq!(ring.get(0), Some(&1));
2273         assert_eq!(ring.get(1), Some(&2));
2274         assert_eq!(ring.get(2), None);
2275
2276         assert_eq!(ring.pop_front(), Some(1));
2277         assert_eq!(ring.get(0), Some(&2));
2278         assert_eq!(ring.get(1), None);
2279
2280         assert_eq!(ring.pop_front(), Some(2));
2281         assert_eq!(ring.get(0), None);
2282         assert_eq!(ring.get(1), None);
2283     }
2284
2285     #[test]
2286     fn test_get_mut() {
2287         let mut ring = RingBuf::new();
2288         for i in range(0i, 3) {
2289             ring.push_back(i);
2290         }
2291
2292         match ring.get_mut(1) {
2293             Some(x) => *x = -1,
2294             None => ()
2295         };
2296
2297         assert_eq!(ring.get_mut(0), Some(&mut 0));
2298         assert_eq!(ring.get_mut(1), Some(&mut -1));
2299         assert_eq!(ring.get_mut(2), Some(&mut 2));
2300         assert_eq!(ring.get_mut(3), None);
2301
2302         assert_eq!(ring.pop_front(), Some(0));
2303         assert_eq!(ring.get_mut(0), Some(&mut -1));
2304         assert_eq!(ring.get_mut(1), Some(&mut 2));
2305         assert_eq!(ring.get_mut(2), None);
2306     }
2307
2308     #[test]
2309     fn test_insert() {
2310         // This test checks that every single combination of tail position, length, and
2311         // insertion position is tested. Capacity 15 should be large enough to cover every case.
2312
2313         let mut tester = RingBuf::with_capacity(15);
2314         // can't guarantee we got 15, so have to get what we got.
2315         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2316         // this test isn't covering what it wants to
2317         let cap = tester.capacity();
2318
2319
2320         // len is the length *after* insertion
2321         for len in range(1, cap) {
2322             // 0, 1, 2, .., len - 1
2323             let expected = iter::count(0, 1).take(len).collect();
2324             for tail_pos in range(0, cap) {
2325                 for to_insert in range(0, len) {
2326                     tester.tail = tail_pos;
2327                     tester.head = tail_pos;
2328                     for i in range(0, len) {
2329                         if i != to_insert {
2330                             tester.push_back(i);
2331                         }
2332                     }
2333                     tester.insert(to_insert, to_insert);
2334                     assert!(tester.tail < tester.cap);
2335                     assert!(tester.head < tester.cap);
2336                     assert_eq!(tester, expected);
2337                 }
2338             }
2339         }
2340     }
2341
2342     #[test]
2343     fn test_remove() {
2344         // This test checks that every single combination of tail position, length, and
2345         // removal position is tested. Capacity 15 should be large enough to cover every case.
2346
2347         let mut tester = RingBuf::with_capacity(15);
2348         // can't guarantee we got 15, so have to get what we got.
2349         // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2350         // this test isn't covering what it wants to
2351         let cap = tester.capacity();
2352
2353         // len is the length *after* removal
2354         for len in range(0, cap - 1) {
2355             // 0, 1, 2, .., len - 1
2356             let expected = iter::count(0, 1).take(len).collect();
2357             for tail_pos in range(0, cap) {
2358                 for to_remove in range(0, len + 1) {
2359                     tester.tail = tail_pos;
2360                     tester.head = tail_pos;
2361                     for i in range(0, len) {
2362                         if i == to_remove {
2363                             tester.push_back(1234);
2364                         }
2365                         tester.push_back(i);
2366                     }
2367                     if to_remove == len {
2368                         tester.push_back(1234);
2369                     }
2370                     tester.remove(to_remove);
2371                     assert!(tester.tail < tester.cap);
2372                     assert!(tester.head < tester.cap);
2373                     assert_eq!(tester, expected);
2374                 }
2375             }
2376         }
2377     }
2378
2379     #[test]
2380     fn test_front() {
2381         let mut ring = RingBuf::new();
2382         ring.push_back(10i);
2383         ring.push_back(20i);
2384         assert_eq!(ring.front(), Some(&10));
2385         ring.pop_front();
2386         assert_eq!(ring.front(), Some(&20));
2387         ring.pop_front();
2388         assert_eq!(ring.front(), None);
2389     }
2390
2391     #[test]
2392     fn test_as_slices() {
2393         let mut ring: RingBuf<int> = RingBuf::with_capacity(127);
2394         let cap = ring.capacity() as int;
2395         let first = cap/2;
2396         let last  = cap - first;
2397         for i in range(0, first) {
2398             ring.push_back(i);
2399
2400             let (left, right) = ring.as_slices();
2401             let expected: Vec<_> = range(0, i+1).collect();
2402             assert_eq!(left, expected);
2403             assert_eq!(right, []);
2404         }
2405
2406         for j in range(-last, 0) {
2407             ring.push_front(j);
2408             let (left, right) = ring.as_slices();
2409             let expected_left: Vec<_> = range(-last, j+1).rev().collect();
2410             let expected_right: Vec<_> = range(0, first).collect();
2411             assert_eq!(left, expected_left);
2412             assert_eq!(right, expected_right);
2413         }
2414
2415         assert_eq!(ring.len() as int, cap);
2416         assert_eq!(ring.capacity() as int, cap);
2417     }
2418
2419     #[test]
2420     fn test_as_mut_slices() {
2421         let mut ring: RingBuf<int> = RingBuf::with_capacity(127);
2422         let cap = ring.capacity() as int;
2423         let first = cap/2;
2424         let last  = cap - first;
2425         for i in range(0, first) {
2426             ring.push_back(i);
2427
2428             let (left, right) = ring.as_mut_slices();
2429             let expected: Vec<_> = range(0, i+1).collect();
2430             assert_eq!(left, expected);
2431             assert_eq!(right, []);
2432         }
2433
2434         for j in range(-last, 0) {
2435             ring.push_front(j);
2436             let (left, right) = ring.as_mut_slices();
2437             let expected_left: Vec<_> = range(-last, j+1).rev().collect();
2438             let expected_right: Vec<_> = range(0, first).collect();
2439             assert_eq!(left, expected_left);
2440             assert_eq!(right, expected_right);
2441         }
2442
2443         assert_eq!(ring.len() as int, cap);
2444         assert_eq!(ring.capacity() as int, cap);
2445     }
2446 }