src/libcollections/ring_buf.rs

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