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 //! Its interface `Deque` is defined in `collections`.
  15
  16 use core::prelude::*;
  17
  18 use core::default::Default;
  19 use core::fmt;
  20 use core::iter;
  21 use core::raw::Slice as RawSlice;
  22 use core::ptr;
  23 use core::kinds::marker;
  24 use core::mem;
  25 use core::num::{Int, UnsignedInt};
  26
  27 use std::hash::{Writer, Hash};
  28 use std::cmp;
  29
  30 use alloc::heap;
  31
  32 static INITIAL_CAPACITY: uint = 8u; // 2^3
  33 static MINIMUM_CAPACITY: uint = 2u;
  34
  35 // FIXME(conventions): implement shrink_to_fit. Awkward with the current design, but it should
  36 // be scrapped anyway. Defer to rewrite?
  37 // FIXME(conventions): implement into_iter
  38
  39
  40 /// `RingBuf` is a circular buffer that implements `Deque`.
  41 pub struct RingBuf<T> {
  42     // tail and head are pointers into the buffer. Tail always points
  43     // to the first element that could be read, Head always points
  44     // to where data should be written.
  45     // If tail == head the buffer is empty. The length of the ringbuf
  46     // is defined as the distance between the two.
  47
  48     tail: uint,
  49     head: uint,
  50     cap: uint,
  51     ptr: *mut T
  52 }
  53
  54 impl<T: Clone> Clone for RingBuf<T> {
  55     fn clone(&self) -> RingBuf<T> {
  56         self.iter().map(|t| t.clone()).collect()
  57     }
  58 }
  59
  60 #[unsafe_destructor]
  61 impl<T> Drop for RingBuf<T> {
  62     fn drop(&mut self) {
  63         self.clear();
  64         unsafe {
  65             if mem::size_of::<T>() != 0 {
  66                 heap::deallocate(self.ptr as *mut u8,
  67                                  self.cap * mem::size_of::<T>(),
  68                                  mem::min_align_of::<T>())
  69             }
  70         }
  71     }
  72 }
  73
  74 impl<T> Default for RingBuf<T> {
  75     #[inline]
  76     fn default() -> RingBuf<T> { RingBuf::new() }
  77 }
  78
  79 impl<T> RingBuf<T> {
  80     /// Turn ptr into a slice
  81     #[inline]
  82     unsafe fn buffer_as_slice(&self) -> &[T] {
  83         mem::transmute(RawSlice { data: self.ptr as *const T, len: self.cap })
  84     }
  85
  86     /// Moves an element out of the buffer
  87     #[inline]
  88     unsafe fn buffer_read(&mut self, off: uint) -> T {
  89         ptr::read(self.ptr.offset(off as int) as *const T)
  90     }
  91
  92     /// Writes an element into the buffer, moving it.
  93     #[inline]
  94     unsafe fn buffer_write(&mut self, off: uint, t: T) {
  95         ptr::write(self.ptr.offset(off as int), t);
  96     }
  97
  98     /// Returns true iff the buffer is at capacity
  99     #[inline]
 100     fn is_full(&self) -> bool { self.cap - self.len() == 1 }
 101
 102     /// Returns the index in the underlying buffer for a given logical element index.
 103     #[inline]
 104     fn wrap_index(&self, idx: uint) -> uint { wrap_index(idx, self.cap) }
 105 }
 106
 107 impl<T> RingBuf<T> {
 108     /// Creates an empty `RingBuf`.
 109     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 110     pub fn new() -> RingBuf<T> {
 111         RingBuf::with_capacity(INITIAL_CAPACITY)
 112     }
 113
 114     /// Creates an empty `RingBuf` with space for at least `n` elements.
 115     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 116     pub fn with_capacity(n: uint) -> RingBuf<T> {
 117         // +1 since the ringbuffer always leaves one space empty
 118         let cap = cmp::max(n + 1, MINIMUM_CAPACITY).next_power_of_two();
 119         let size = cap.checked_mul(mem::size_of::<T>())
 120                       .expect("capacity overflow");
 121
 122         let ptr = if mem::size_of::<T>() != 0 {
 123             unsafe {
 124                 let ptr = heap::allocate(size, mem::min_align_of::<T>())  as *mut T;;
 125                 if ptr.is_null() { ::alloc::oom() }
 126                 ptr
 127             }
 128         } else {
 129             heap::EMPTY as *mut T
 130         };
 131
 132         RingBuf {
 133             tail: 0,
 134             head: 0,
 135             cap: cap,
 136             ptr: ptr
 137         }
 138     }
 139
 140     /// Retrieves an element in the `RingBuf` by index.
 141     ///
 142     /// # Example
 143     ///
 144     /// ```rust
 145     /// use std::collections::RingBuf;
 146     ///
 147     /// let mut buf = RingBuf::new();
 148     /// buf.push_back(3i);
 149     /// buf.push_back(4);
 150     /// buf.push_back(5);
 151     /// assert_eq!(buf.get(1).unwrap(), &4);
 152     /// ```
 153     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 154     pub fn get(&self, i: uint) -> Option<&T> {
 155         if i < self.len() {
 156             let idx = self.wrap_index(self.tail + i);
 157             unsafe { Some(&*self.ptr.offset(idx as int)) }
 158         } else {
 159             None
 160         }
 161     }
 162
 163     /// Retrieves an element in the `RingBuf` mutably by index.
 164     ///
 165     /// # Example
 166     ///
 167     /// ```rust
 168     /// use std::collections::RingBuf;
 169     ///
 170     /// let mut buf = RingBuf::new();
 171     /// buf.push_back(3i);
 172     /// buf.push_back(4);
 173     /// buf.push_back(5);
 174     /// match buf.get_mut(1) {
 175     ///     None => {}
 176     ///     Some(elem) => {
 177     ///         *elem = 7;
 178     ///     }
 179     /// }
 180     ///
 181     /// assert_eq!(buf[1], 7);
 182     /// ```
 183     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 184     pub fn get_mut(&mut self, i: uint) -> Option<&mut T> {
 185         if i < self.len() {
 186             let idx = self.wrap_index(self.tail + i);
 187             unsafe { Some(&mut *self.ptr.offset(idx as int)) }
 188         } else {
 189             None
 190         }
 191     }
 192
 193     /// Swaps elements at indices `i` and `j`.
 194     ///
 195     /// `i` and `j` may be equal.
 196     ///
 197     /// Fails if there is no element with either index.
 198     ///
 199     /// # Example
 200     ///
 201     /// ```rust
 202     /// use std::collections::RingBuf;
 203     ///
 204     /// let mut buf = RingBuf::new();
 205     /// buf.push_back(3i);
 206     /// buf.push_back(4);
 207     /// buf.push_back(5);
 208     /// buf.swap(0, 2);
 209     /// assert_eq!(buf[0], 5);
 210     /// assert_eq!(buf[2], 3);
 211     /// ```
 212     pub fn swap(&mut self, i: uint, j: uint) {
 213         assert!(i < self.len());
 214         assert!(j < self.len());
 215         let ri = self.wrap_index(self.tail + i);
 216         let rj = self.wrap_index(self.tail + j);
 217         unsafe {
 218             ptr::swap(self.ptr.offset(ri as int), self.ptr.offset(rj as int))
 219         }
 220     }
 221
 222     /// Returns the number of elements the `RingBuf` can hold without
 223     /// reallocating.
 224     ///
 225     /// # Example
 226     ///
 227     /// ```
 228     /// use std::collections::RingBuf;
 229     ///
 230     /// let buf: RingBuf<int> = RingBuf::with_capacity(10);
 231     /// assert!(buf.capacity() >= 10);
 232     /// ```
 233     #[inline]
 234     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 235     pub fn capacity(&self) -> uint { self.cap - 1 }
 236
 237     /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
 238     /// given `RingBuf`. Does nothing if the capacity is already sufficient.
 239     ///
 240     /// Note that the allocator may give the collection more space than it requests. Therefore
 241     /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
 242     /// insertions are expected.
 243     ///
 244     /// # Panics
 245     ///
 246     /// Panics if the new capacity overflows `uint`.
 247     ///
 248     /// # Example
 249     ///
 250     /// ```
 251     /// use std::collections::RingBuf;
 252     ///
 253     /// let mut buf: RingBuf<int> = vec![1].into_iter().collect();
 254     /// buf.reserve_exact(10);
 255     /// assert!(buf.capacity() >= 11);
 256     /// ```
 257     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 258     pub fn reserve_exact(&mut self, additional: uint) {
 259         self.reserve(additional);
 260     }
 261
 262     /// Reserves capacity for at least `additional` more elements to be inserted in the given
 263     /// `Ringbuf`. The collection may reserve more space to avoid frequent reallocations.
 264     ///
 265     /// # Panics
 266     ///
 267     /// Panics if the new capacity overflows `uint`.
 268     ///
 269     /// # Example
 270     ///
 271     /// ```
 272     /// use std::collections::RingBuf;
 273     ///
 274     /// let mut buf: RingBuf<int> = vec![1].into_iter().collect();
 275     /// buf.reserve(10);
 276     /// assert!(buf.capacity() >= 11);
 277     /// ```
 278     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 279     pub fn reserve(&mut self, additional: uint) {
 280         let new_len = self.len() + additional;
 281         assert!(new_len + 1 > self.len(), "capacity overflow");
 282         if new_len > self.capacity() {
 283             let count = (new_len + 1).next_power_of_two();
 284             assert!(count >= new_len + 1);
 285
 286             if mem::size_of::<T>() != 0 {
 287                 let old = self.cap * mem::size_of::<T>();
 288                 let new = count.checked_mul(mem::size_of::<T>())
 289                                .expect("capacity overflow");
 290                 unsafe {
 291                     self.ptr = heap::reallocate(self.ptr as *mut u8,
 292                                                 old,
 293                                                 new,
 294                                                 mem::min_align_of::<T>()) as *mut T;
 295                     if self.ptr.is_null() { ::alloc::oom() }
 296                 }
 297             }
 298
 299             // Move the shortest contiguous section of the ring buffer
 300             //    T             H
 301             //   [o o o o o o o . ]
 302             //    T             H
 303             // A [o o o o o o o . . . . . . . . . ]
 304             //        H T
 305             //   [o o . o o o o o ]
 306             //          T             H
 307             // B [. . . o o o o o o o . . . . . . ]
 308             //              H T
 309             //   [o o o o o . o o ]
 310             //              H                 T
 311             // C [o o o o o . . . . . . . . . o o ]
 312
 313             let oldcap = self.cap;
 314             self.cap = count;
 315
 316             if self.tail <= self.head { // A
 317                 // Nop
 318             } else if self.head < oldcap - self.tail { // B
 319                 unsafe {
 320                     ptr::copy_nonoverlapping_memory(
 321                         self.ptr.offset(oldcap as int),
 322                         self.ptr as *const T,
 323                         self.head
 324                     );
 325                 }
 326                 self.head += oldcap;
 327                 debug_assert!(self.head > self.tail);
 328             } else { // C
 329                 unsafe {
 330                     ptr::copy_nonoverlapping_memory(
 331                         self.ptr.offset((count - (oldcap - self.tail)) as int),
 332                         self.ptr.offset(self.tail as int) as *const T,
 333                         oldcap - self.tail
 334                     );
 335                 }
 336                 self.tail = count - (oldcap - self.tail);
 337                 debug_assert!(self.head < self.tail);
 338             }
 339             debug_assert!(self.head < self.cap);
 340             debug_assert!(self.tail < self.cap);
 341             debug_assert!(self.cap.count_ones() == 1);
 342         }
 343     }
 344
 345     /// Returns a front-to-back iterator.
 346     ///
 347     /// # Example
 348     ///
 349     /// ```rust
 350     /// use std::collections::RingBuf;
 351     ///
 352     /// let mut buf = RingBuf::new();
 353     /// buf.push_back(5i);
 354     /// buf.push_back(3);
 355     /// buf.push_back(4);
 356     /// let b: &[_] = &[&5, &3, &4];
 357     /// assert_eq!(buf.iter().collect::<Vec<&int>>().as_slice(), b);
 358     /// ```
 359     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 360     pub fn iter(&self) -> Items<T> {
 361         Items {
 362             tail: self.tail,
 363             head: self.head,
 364             ring: unsafe { self.buffer_as_slice() }
 365         }
 366     }
 367
 368     /// Returns a front-to-back iterator which returns mutable references.
 369     ///
 370     /// # Example
 371     ///
 372     /// ```rust
 373     /// use std::collections::RingBuf;
 374     ///
 375     /// let mut buf = RingBuf::new();
 376     /// buf.push_back(5i);
 377     /// buf.push_back(3);
 378     /// buf.push_back(4);
 379     /// for num in buf.iter_mut() {
 380     ///     *num = *num - 2;
 381     /// }
 382     /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
 383     /// assert_eq!(buf.iter_mut().collect::<Vec<&mut int>>()[], b);
 384     /// ```
 385     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 386     pub fn iter_mut<'a>(&'a mut self) -> MutItems<'a, T> {
 387         MutItems {
 388             tail: self.tail,
 389             head: self.head,
 390             cap: self.cap,
 391             ptr: self.ptr,
 392             marker: marker::ContravariantLifetime::<'a>,
 393             marker2: marker::NoCopy
 394         }
 395     }
 396
 397     /// Returns the number of elements in the `RingBuf`.
 398     ///
 399     /// # Example
 400     ///
 401     /// ```
 402     /// use std::collections::RingBuf;
 403     ///
 404     /// let mut v = RingBuf::new();
 405     /// assert_eq!(v.len(), 0);
 406     /// v.push_back(1i);
 407     /// assert_eq!(v.len(), 1);
 408     /// ```
 409     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 410     pub fn len(&self) -> uint { count(self.tail, self.head, self.cap) }
 411
 412     /// Returns true if the buffer contains no elements
 413     ///
 414     /// # Example
 415     ///
 416     /// ```
 417     /// use std::collections::RingBuf;
 418     ///
 419     /// let mut v = RingBuf::new();
 420     /// assert!(v.is_empty());
 421     /// v.push_front(1i);
 422     /// assert!(!v.is_empty());
 423     /// ```
 424     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 425     pub fn is_empty(&self) -> bool { self.len() == 0 }
 426
 427     /// Clears the buffer, removing all values.
 428     ///
 429     /// # Example
 430     ///
 431     /// ```
 432     /// use std::collections::RingBuf;
 433     ///
 434     /// let mut v = RingBuf::new();
 435     /// v.push_back(1i);
 436     /// v.clear();
 437     /// assert!(v.is_empty());
 438     /// ```
 439     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 440     pub fn clear(&mut self) {
 441         while self.pop_front().is_some() {}
 442         self.head = 0;
 443         self.tail = 0;
 444     }
 445
 446     /// Provides a reference to the front element, or `None` if the sequence is
 447     /// empty.
 448     ///
 449     /// # Example
 450     ///
 451     /// ```
 452     /// use std::collections::RingBuf;
 453     ///
 454     /// let mut d = RingBuf::new();
 455     /// assert_eq!(d.front(), None);
 456     ///
 457     /// d.push_back(1i);
 458     /// d.push_back(2i);
 459     /// assert_eq!(d.front(), Some(&1i));
 460     /// ```
 461     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 462     pub fn front(&self) -> Option<&T> {
 463         if !self.is_empty() { Some(&self[0]) } else { None }
 464     }
 465
 466     /// Provides a mutable reference to the front element, or `None` if the
 467     /// sequence is empty.
 468     ///
 469     /// # Example
 470     ///
 471     /// ```
 472     /// use std::collections::RingBuf;
 473     ///
 474     /// let mut d = RingBuf::new();
 475     /// assert_eq!(d.front_mut(), None);
 476     ///
 477     /// d.push_back(1i);
 478     /// d.push_back(2i);
 479     /// match d.front_mut() {
 480     ///     Some(x) => *x = 9i,
 481     ///     None => (),
 482     /// }
 483     /// assert_eq!(d.front(), Some(&9i));
 484     /// ```
 485     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 486     pub fn front_mut(&mut self) -> Option<&mut T> {
 487         if !self.is_empty() { Some(&mut self[0]) } else { None }
 488     }
 489
 490     /// Provides a reference to the back element, or `None` if the sequence is
 491     /// empty.
 492     ///
 493     /// # Example
 494     ///
 495     /// ```
 496     /// use std::collections::RingBuf;
 497     ///
 498     /// let mut d = RingBuf::new();
 499     /// assert_eq!(d.back(), None);
 500     ///
 501     /// d.push_back(1i);
 502     /// d.push_back(2i);
 503     /// assert_eq!(d.back(), Some(&2i));
 504     /// ```
 505     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 506     pub fn back(&self) -> Option<&T> {
 507         if !self.is_empty() { Some(&self[self.len() - 1]) } else { None }
 508     }
 509
 510     /// Provides a mutable reference to the back element, or `None` if the
 511     /// sequence is empty.
 512     ///
 513     /// # Example
 514     ///
 515     /// ```
 516     /// use std::collections::RingBuf;
 517     ///
 518     /// let mut d = RingBuf::new();
 519     /// assert_eq!(d.back(), None);
 520     ///
 521     /// d.push_back(1i);
 522     /// d.push_back(2i);
 523     /// match d.back_mut() {
 524     ///     Some(x) => *x = 9i,
 525     ///     None => (),
 526     /// }
 527     /// assert_eq!(d.back(), Some(&9i));
 528     /// ```
 529     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 530     pub fn back_mut(&mut self) -> Option<&mut T> {
 531         let len = self.len();
 532         if !self.is_empty() { Some(&mut self[len - 1]) } else { None }
 533     }
 534
 535     /// Removes the first element and returns it, or `None` if the sequence is
 536     /// empty.
 537     ///
 538     /// # Example
 539     ///
 540     /// ```
 541     /// use std::collections::RingBuf;
 542     ///
 543     /// let mut d = RingBuf::new();
 544     /// d.push_back(1i);
 545     /// d.push_back(2i);
 546     ///
 547     /// assert_eq!(d.pop_front(), Some(1i));
 548     /// assert_eq!(d.pop_front(), Some(2i));
 549     /// assert_eq!(d.pop_front(), None);
 550     /// ```
 551     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 552     pub fn pop_front(&mut self) -> Option<T> {
 553         if self.is_empty() {
 554             None
 555         } else {
 556             let tail = self.tail;
 557             self.tail = self.wrap_index(self.tail + 1);
 558             unsafe { Some(self.buffer_read(tail)) }
 559         }
 560     }
 561
 562     /// Inserts an element first in the sequence.
 563     ///
 564     /// # Example
 565     ///
 566     /// ```
 567     /// use std::collections::RingBuf;
 568     ///
 569     /// let mut d = RingBuf::new();
 570     /// d.push_front(1i);
 571     /// d.push_front(2i);
 572     /// assert_eq!(d.front(), Some(&2i));
 573     /// ```
 574     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 575     pub fn push_front(&mut self, t: T) {
 576         if self.is_full() {
 577             self.reserve(1);
 578             debug_assert!(!self.is_full());
 579         }
 580
 581         self.tail = self.wrap_index(self.tail - 1);
 582         let tail = self.tail;
 583         unsafe { self.buffer_write(tail, t); }
 584     }
 585
 586     /// Deprecated: Renamed to `push_back`.
 587     #[deprecated = "Renamed to `push_back`"]
 588     pub fn push(&mut self, t: T) {
 589         self.push_back(t)
 590     }
 591
 592     /// Appends an element to the back of a buffer
 593     ///
 594     /// # Example
 595     ///
 596     /// ```rust
 597     /// use std::collections::RingBuf;
 598     ///
 599     /// let mut buf = RingBuf::new();
 600     /// buf.push_back(1i);
 601     /// buf.push_back(3);
 602     /// assert_eq!(3, *buf.back().unwrap());
 603     /// ```
 604     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 605     pub fn push_back(&mut self, t: T) {
 606         if self.is_full() {
 607             self.reserve(1);
 608             debug_assert!(!self.is_full());
 609         }
 610
 611         let head = self.head;
 612         self.head = self.wrap_index(self.head + 1);
 613         unsafe { self.buffer_write(head, t) }
 614     }
 615
 616     /// Deprecated: Renamed to `pop_back`.
 617     #[deprecated = "Renamed to `pop_back`"]
 618     pub fn pop(&mut self) -> Option<T> {
 619         self.pop_back()
 620     }
 621
 622     /// Removes the last element from a buffer and returns it, or `None` if
 623     /// it is empty.
 624     ///
 625     /// # Example
 626     ///
 627     /// ```rust
 628     /// use std::collections::RingBuf;
 629     ///
 630     /// let mut buf = RingBuf::new();
 631     /// assert_eq!(buf.pop_back(), None);
 632     /// buf.push_back(1i);
 633     /// buf.push_back(3);
 634     /// assert_eq!(buf.pop_back(), Some(3));
 635     /// ```
 636     #[unstable = "matches collection reform specification, waiting for dust to settle"]
 637     pub fn pop_back(&mut self) -> Option<T> {
 638         if self.is_empty() {
 639             None
 640         } else {
 641             self.head = self.wrap_index(self.head - 1);
 642             let head = self.head;
 643             unsafe { Some(self.buffer_read(head)) }
 644         }
 645     }
 646 }
 647
 648 /// Returns the index in the underlying buffer for a given logical element index.
 649 #[inline]
 650 fn wrap_index(index: uint, size: uint) -> uint {
 651     // size is always a power of 2
 652     index & (size - 1)
 653 }
 654
 655 /// Calculate the number of elements left to be read in the buffer
 656 #[inline]
 657 fn count(tail: uint, head: uint, size: uint) -> uint {
 658     // size is always a power of 2
 659     (head - tail) & (size - 1)
 660 }
 661
 662 /// `RingBuf` iterator.
 663 pub struct Items<'a, T:'a> {
 664     ring: &'a [T],
 665     tail: uint,
 666     head: uint
 667 }
 668
 669 impl<'a, T> Iterator<&'a T> for Items<'a, T> {
 670     #[inline]
 671     fn next(&mut self) -> Option<&'a T> {
 672         if self.tail == self.head {
 673             return None;
 674         }
 675         let tail = self.tail;
 676         self.tail = wrap_index(self.tail + 1, self.ring.len());
 677         unsafe { Some(self.ring.unsafe_get(tail)) }
 678     }
 679
 680     #[inline]
 681     fn size_hint(&self) -> (uint, Option<uint>) {
 682         let len = count(self.tail, self.head, self.ring.len());
 683         (len, Some(len))
 684     }
 685 }
 686
 687 impl<'a, T> DoubleEndedIterator<&'a T> for Items<'a, T> {
 688     #[inline]
 689     fn next_back(&mut self) -> Option<&'a T> {
 690         if self.tail == self.head {
 691             return None;
 692         }
 693         self.head = wrap_index(self.head - 1, self.ring.len());
 694         unsafe { Some(self.ring.unsafe_get(self.head)) }
 695     }
 696 }
 697
 698
 699 impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
 700
 701 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
 702     #[inline]
 703     fn indexable(&self) -> uint {
 704         let (len, _) = self.size_hint();
 705         len
 706     }
 707
 708     #[inline]
 709     fn idx(&mut self, j: uint) -> Option<&'a T> {
 710         if j >= self.indexable() {
 711             None
 712         } else {
 713             let idx = wrap_index(self.tail + j, self.ring.len());
 714             unsafe { Some(self.ring.unsafe_get(idx)) }
 715         }
 716     }
 717 }
 718
 719 // FIXME This was implemented differently from Items because of a problem
 720 //       with returning the mutable reference. I couldn't find a way to
 721 //       make the lifetime checker happy so, but there should be a way.
 722 /// `RingBuf` mutable iterator.
 723 pub struct MutItems<'a, T:'a> {
 724     ptr: *mut T,
 725     tail: uint,
 726     head: uint,
 727     cap: uint,
 728     marker: marker::ContravariantLifetime<'a>,
 729     marker2: marker::NoCopy
 730 }
 731
 732 impl<'a, T> Iterator<&'a mut T> for MutItems<'a, T> {
 733     #[inline]
 734     fn next(&mut self) -> Option<&'a mut T> {
 735         if self.tail == self.head {
 736             return None;
 737         }
 738         let tail = self.tail;
 739         self.tail = wrap_index(self.tail + 1, self.cap);
 740         if mem::size_of::<T>() != 0 {
 741             unsafe { Some(&mut *self.ptr.offset(tail as int)) }
 742         } else {
 743             // use a non-zero pointer
 744             Some(unsafe { mem::transmute(1u) })
 745         }
 746     }
 747
 748     #[inline]
 749     fn size_hint(&self) -> (uint, Option<uint>) {
 750         let len = count(self.tail, self.head, self.cap);
 751         (len, Some(len))
 752     }
 753 }
 754
 755 impl<'a, T> DoubleEndedIterator<&'a mut T> for MutItems<'a, T> {
 756     #[inline]
 757     fn next_back(&mut self) -> Option<&'a mut T> {
 758         if self.tail == self.head {
 759             return None;
 760         }
 761         self.head = wrap_index(self.head - 1, self.cap);
 762         unsafe { Some(&mut *self.ptr.offset(self.head as int)) }
 763     }
 764 }
 765
 766 impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
 767
 768 impl<A: PartialEq> PartialEq for RingBuf<A> {
 769     fn eq(&self, other: &RingBuf<A>) -> bool {
 770         self.len() == other.len() &&
 771             self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
 772     }
 773     fn ne(&self, other: &RingBuf<A>) -> bool {
 774         !self.eq(other)
 775     }
 776 }
 777
 778 impl<A: Eq> Eq for RingBuf<A> {}
 779
 780 impl<A: PartialOrd> PartialOrd for RingBuf<A> {
 781     fn partial_cmp(&self, other: &RingBuf<A>) -> Option<Ordering> {
 782         iter::order::partial_cmp(self.iter(), other.iter())
 783     }
 784 }
 785
 786 impl<A: Ord> Ord for RingBuf<A> {
 787     #[inline]
 788     fn cmp(&self, other: &RingBuf<A>) -> Ordering {
 789         iter::order::cmp(self.iter(), other.iter())
 790     }
 791 }
 792
 793 impl<S: Writer, A: Hash<S>> Hash<S> for RingBuf<A> {
 794     fn hash(&self, state: &mut S) {
 795         self.len().hash(state);
 796         for elt in self.iter() {
 797             elt.hash(state);
 798         }
 799     }
 800 }
 801
 802 impl<A> Index<uint, A> for RingBuf<A> {
 803     #[inline]
 804     fn index<'a>(&'a self, i: &uint) -> &'a A {
 805         self.get(*i).expect("Out of bounds access")
 806     }
 807 }
 808
 809 impl<A> IndexMut<uint, A> for RingBuf<A> {
 810     #[inline]
 811     fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut A {
 812         self.get_mut(*i).expect("Out of bounds access")
 813     }
 814 }
 815
 816 impl<A> FromIterator<A> for RingBuf<A> {
 817     fn from_iter<T: Iterator<A>>(iterator: T) -> RingBuf<A> {
 818         let (lower, _) = iterator.size_hint();
 819         let mut deq = RingBuf::with_capacity(lower);
 820         deq.extend(iterator);
 821         deq
 822     }
 823 }
 824
 825 impl<A> Extend<A> for RingBuf<A> {
 826     fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
 827         for elt in iterator {
 828             self.push_back(elt);
 829         }
 830     }
 831 }
 832
 833 impl<T: fmt::Show> fmt::Show for RingBuf<T> {
 834     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 835         try!(write!(f, "["));
 836
 837         for (i, e) in self.iter().enumerate() {
 838             if i != 0 { try!(write!(f, ", ")); }
 839             try!(write!(f, "{}", *e));
 840         }
 841
 842         write!(f, "]")
 843     }
 844 }
 845
 846 #[cfg(test)]
 847 mod tests {
 848     use std::fmt::Show;
 849     use std::prelude::*;
 850     use std::hash;
 851     use test::Bencher;
 852     use test;
 853
 854     use super::RingBuf;
 855     use vec::Vec;
 856
 857     #[test]
 858     #[allow(deprecated)]
 859     fn test_simple() {
 860         let mut d = RingBuf::new();
 861         assert_eq!(d.len(), 0u);
 862         d.push_front(17i);
 863         d.push_front(42i);
 864         d.push_back(137);
 865         assert_eq!(d.len(), 3u);
 866         d.push_back(137);
 867         assert_eq!(d.len(), 4u);
 868         debug!("{}", d.front());
 869         assert_eq!(*d.front().unwrap(), 42);
 870         debug!("{}", d.back());
 871         assert_eq!(*d.back().unwrap(), 137);
 872         let mut i = d.pop_front();
 873         debug!("{}", i);
 874         assert_eq!(i, Some(42));
 875         i = d.pop_back();
 876         debug!("{}", i);
 877         assert_eq!(i, Some(137));
 878         i = d.pop_back();
 879         debug!("{}", i);
 880         assert_eq!(i, Some(137));
 881         i = d.pop_back();
 882         debug!("{}", i);
 883         assert_eq!(i, Some(17));
 884         assert_eq!(d.len(), 0u);
 885         d.push_back(3);
 886         assert_eq!(d.len(), 1u);
 887         d.push_front(2);
 888         assert_eq!(d.len(), 2u);
 889         d.push_back(4);
 890         assert_eq!(d.len(), 3u);
 891         d.push_front(1);
 892         assert_eq!(d.len(), 4u);
 893         debug!("{}", d[0]);
 894         debug!("{}", d[1]);
 895         debug!("{}", d[2]);
 896         debug!("{}", d[3]);
 897         assert_eq!(d[0], 1);
 898         assert_eq!(d[1], 2);
 899         assert_eq!(d[2], 3);
 900         assert_eq!(d[3], 4);
 901     }
 902
 903     #[cfg(test)]
 904     fn test_parameterized<T:Clone + PartialEq + Show>(a: T, b: T, c: T, d: T) {
 905         let mut deq = RingBuf::new();
 906         assert_eq!(deq.len(), 0);
 907         deq.push_front(a.clone());
 908         deq.push_front(b.clone());
 909         deq.push_back(c.clone());
 910         assert_eq!(deq.len(), 3);
 911         deq.push_back(d.clone());
 912         assert_eq!(deq.len(), 4);
 913         assert_eq!((*deq.front().unwrap()).clone(), b.clone());
 914         assert_eq!((*deq.back().unwrap()).clone(), d.clone());
 915         assert_eq!(deq.pop_front().unwrap(), b.clone());
 916         assert_eq!(deq.pop_back().unwrap(), d.clone());
 917         assert_eq!(deq.pop_back().unwrap(), c.clone());
 918         assert_eq!(deq.pop_back().unwrap(), a.clone());
 919         assert_eq!(deq.len(), 0);
 920         deq.push_back(c.clone());
 921         assert_eq!(deq.len(), 1);
 922         deq.push_front(b.clone());
 923         assert_eq!(deq.len(), 2);
 924         deq.push_back(d.clone());
 925         assert_eq!(deq.len(), 3);
 926         deq.push_front(a.clone());
 927         assert_eq!(deq.len(), 4);
 928         assert_eq!(deq[0].clone(), a.clone());
 929         assert_eq!(deq[1].clone(), b.clone());
 930         assert_eq!(deq[2].clone(), c.clone());
 931         assert_eq!(deq[3].clone(), d.clone());
 932     }
 933
 934     #[test]
 935     fn test_push_front_grow() {
 936         let mut deq = RingBuf::new();
 937         for i in range(0u, 66) {
 938             deq.push_front(i);
 939         }
 940         assert_eq!(deq.len(), 66);
 941
 942         for i in range(0u, 66) {
 943             assert_eq!(deq[i], 65 - i);
 944         }
 945
 946         let mut deq = RingBuf::new();
 947         for i in range(0u, 66) {
 948             deq.push_back(i);
 949         }
 950
 951         for i in range(0u, 66) {
 952             assert_eq!(deq[i], i);
 953         }
 954     }
 955
 956     #[test]
 957     fn test_index() {
 958         let mut deq = RingBuf::new();
 959         for i in range(1u, 4) {
 960             deq.push_front(i);
 961         }
 962         assert_eq!(deq[1], 2);
 963     }
 964
 965     #[test]
 966     #[should_fail]
 967     fn test_index_out_of_bounds() {
 968         let mut deq = RingBuf::new();
 969         for i in range(1u, 4) {
 970             deq.push_front(i);
 971         }
 972         deq[3];
 973     }
 974
 975     #[bench]
 976     fn bench_new(b: &mut test::Bencher) {
 977         b.iter(|| {
 978             let ring: RingBuf<u64> = RingBuf::new();
 979             test::black_box(ring);
 980         })
 981     }
 982
 983     #[bench]
 984     fn bench_push_back_100(b: &mut test::Bencher) {
 985         let mut deq = RingBuf::with_capacity(101);
 986         b.iter(|| {
 987             for i in range(0i, 100) {
 988                 deq.push_back(i);
 989             }
 990             deq.head = 0;
 991             deq.tail = 0;
 992         })
 993     }
 994
 995     #[bench]
 996     fn bench_push_front_100(b: &mut test::Bencher) {
 997         let mut deq = RingBuf::with_capacity(101);
 998         b.iter(|| {
 999             for i in range(0i, 100) {
1000                 deq.push_front(i);
1001             }
1002             deq.head = 0;
1003             deq.tail = 0;
1004         })
1005     }
1006
1007     #[bench]
1008     fn bench_pop_back_100(b: &mut test::Bencher) {
1009         let mut deq: RingBuf<int> = RingBuf::with_capacity(101);
1010
1011         b.iter(|| {
1012             deq.head = 100;
1013             deq.tail = 0;
1014             while !deq.is_empty() {
1015                 test::black_box(deq.pop_back());
1016             }
1017         })
1018     }
1019
1020     #[bench]
1021     fn bench_pop_front_100(b: &mut test::Bencher) {
1022         let mut deq: RingBuf<int> = RingBuf::with_capacity(101);
1023
1024         b.iter(|| {
1025             deq.head = 100;
1026             deq.tail = 0;
1027             while !deq.is_empty() {
1028                 test::black_box(deq.pop_front());
1029             }
1030         })
1031     }
1032
1033     #[bench]
1034     fn bench_grow_1025(b: &mut test::Bencher) {
1035         b.iter(|| {
1036             let mut deq = RingBuf::new();
1037             for i in range(0i, 1025) {
1038                 deq.push_front(i);
1039             }
1040             test::black_box(deq);
1041         })
1042     }
1043
1044     #[bench]
1045     fn bench_iter_1000(b: &mut test::Bencher) {
1046         let ring: RingBuf<int> = range(0i, 1000).collect();
1047
1048         b.iter(|| {
1049             let mut sum = 0;
1050             for &i in ring.iter() {
1051                 sum += i;
1052             }
1053             test::black_box(sum);
1054         })
1055     }
1056
1057     #[bench]
1058     fn bench_mut_iter_1000(b: &mut test::Bencher) {
1059         let mut ring: RingBuf<int> = range(0i, 1000).collect();
1060
1061         b.iter(|| {
1062             let mut sum = 0;
1063             for i in ring.iter_mut() {
1064                 sum += *i;
1065             }
1066             test::black_box(sum);
1067         })
1068     }
1069
1070
1071     #[deriving(Clone, PartialEq, Show)]
1072     enum Taggy {
1073         One(int),
1074         Two(int, int),
1075         Three(int, int, int),
1076     }
1077
1078     #[deriving(Clone, PartialEq, Show)]
1079     enum Taggypar<T> {
1080         Onepar(int),
1081         Twopar(int, int),
1082         Threepar(int, int, int),
1083     }
1084
1085     #[deriving(Clone, PartialEq, Show)]
1086     struct RecCy {
1087         x: int,
1088         y: int,
1089         t: Taggy
1090     }
1091
1092     #[test]
1093     fn test_param_int() {
1094         test_parameterized::<int>(5, 72, 64, 175);
1095     }
1096
1097     #[test]
1098     fn test_param_taggy() {
1099         test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
1100     }
1101
1102     #[test]
1103     fn test_param_taggypar() {
1104         test_parameterized::<Taggypar<int>>(Onepar::<int>(1),
1105                                             Twopar::<int>(1, 2),
1106                                             Threepar::<int>(1, 2, 3),
1107                                             Twopar::<int>(17, 42));
1108     }
1109
1110     #[test]
1111     fn test_param_reccy() {
1112         let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
1113         let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
1114         let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
1115         let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
1116         test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
1117     }
1118
1119     #[test]
1120     fn test_with_capacity() {
1121         let mut d = RingBuf::with_capacity(0);
1122         d.push_back(1i);
1123         assert_eq!(d.len(), 1);
1124         let mut d = RingBuf::with_capacity(50);
1125         d.push_back(1i);
1126         assert_eq!(d.len(), 1);
1127     }
1128
1129     #[test]
1130     fn test_with_capacity_non_power_two() {
1131         let mut d3 = RingBuf::with_capacity(3);
1132         d3.push_back(1i);
1133
1134         // X = None, | = lo
1135         // [|1, X, X]
1136         assert_eq!(d3.pop_front(), Some(1));
1137         // [X, |X, X]
1138         assert_eq!(d3.front(), None);
1139
1140         // [X, |3, X]
1141         d3.push_back(3);
1142         // [X, |3, 6]
1143         d3.push_back(6);
1144         // [X, X, |6]
1145         assert_eq!(d3.pop_front(), Some(3));
1146
1147         // Pushing the lo past half way point to trigger
1148         // the 'B' scenario for growth
1149         // [9, X, |6]
1150         d3.push_back(9);
1151         // [9, 12, |6]
1152         d3.push_back(12);
1153
1154         d3.push_back(15);
1155         // There used to be a bug here about how the
1156         // RingBuf made growth assumptions about the
1157         // underlying Vec which didn't hold and lead
1158         // to corruption.
1159         // (Vec grows to next power of two)
1160         //good- [9, 12, 15, X, X, X, X, |6]
1161         //bug-  [15, 12, X, X, X, |6, X, X]
1162         assert_eq!(d3.pop_front(), Some(6));
1163
1164         // Which leads us to the following state which
1165         // would be a failure case.
1166         //bug-  [15, 12, X, X, X, X, |X, X]
1167         assert_eq!(d3.front(), Some(&9));
1168     }
1169
1170     #[test]
1171     fn test_reserve_exact() {
1172         let mut d = RingBuf::new();
1173         d.push_back(0u64);
1174         d.reserve_exact(50);
1175         assert!(d.capacity() >= 51);
1176         let mut d = RingBuf::new();
1177         d.push_back(0u32);
1178         d.reserve_exact(50);
1179         assert!(d.capacity() >= 51);
1180     }
1181
1182     #[test]
1183     fn test_reserve() {
1184         let mut d = RingBuf::new();
1185         d.push_back(0u64);
1186         d.reserve(50);
1187         assert!(d.capacity() >= 51);
1188         let mut d = RingBuf::new();
1189         d.push_back(0u32);
1190         d.reserve(50);
1191         assert!(d.capacity() >= 51);
1192     }
1193
1194     #[test]
1195     fn test_swap() {
1196         let mut d: RingBuf<int> = range(0i, 5).collect();
1197         d.pop_front();
1198         d.swap(0, 3);
1199         assert_eq!(d.iter().map(|&x|x).collect::<Vec<int>>(), vec!(4, 2, 3, 1));
1200     }
1201
1202     #[test]
1203     fn test_iter() {
1204         let mut d = RingBuf::new();
1205         assert_eq!(d.iter().next(), None);
1206         assert_eq!(d.iter().size_hint(), (0, Some(0)));
1207
1208         for i in range(0i, 5) {
1209             d.push_back(i);
1210         }
1211         {
1212             let b: &[_] = &[&0,&1,&2,&3,&4];
1213             assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), b);
1214         }
1215
1216         for i in range(6i, 9) {
1217             d.push_front(i);
1218         }
1219         {
1220             let b: &[_] = &[&8,&7,&6,&0,&1,&2,&3,&4];
1221             assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), b);
1222         }
1223
1224         let mut it = d.iter();
1225         let mut len = d.len();
1226         loop {
1227             match it.next() {
1228                 None => break,
1229                 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
1230             }
1231         }
1232     }
1233
1234     #[test]
1235     fn test_rev_iter() {
1236         let mut d = RingBuf::new();
1237         assert_eq!(d.iter().rev().next(), None);
1238
1239         for i in range(0i, 5) {
1240             d.push_back(i);
1241         }
1242         {
1243             let b: &[_] = &[&4,&3,&2,&1,&0];
1244             assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), b);
1245         }
1246
1247         for i in range(6i, 9) {
1248             d.push_front(i);
1249         }
1250         let b: &[_] = &[&4,&3,&2,&1,&0,&6,&7,&8];
1251         assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), b);
1252     }
1253
1254     #[test]
1255     fn test_mut_rev_iter_wrap() {
1256         let mut d = RingBuf::with_capacity(3);
1257         assert!(d.iter_mut().rev().next().is_none());
1258
1259         d.push_back(1i);
1260         d.push_back(2);
1261         d.push_back(3);
1262         assert_eq!(d.pop_front(), Some(1));
1263         d.push_back(4);
1264
1265         assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<int>>(),
1266                    vec!(4, 3, 2));
1267     }
1268
1269     #[test]
1270     fn test_mut_iter() {
1271         let mut d = RingBuf::new();
1272         assert!(d.iter_mut().next().is_none());
1273
1274         for i in range(0u, 3) {
1275             d.push_front(i);
1276         }
1277
1278         for (i, elt) in d.iter_mut().enumerate() {
1279             assert_eq!(*elt, 2 - i);
1280             *elt = i;
1281         }
1282
1283         {
1284             let mut it = d.iter_mut();
1285             assert_eq!(*it.next().unwrap(), 0);
1286             assert_eq!(*it.next().unwrap(), 1);
1287             assert_eq!(*it.next().unwrap(), 2);
1288             assert!(it.next().is_none());
1289         }
1290     }
1291
1292     #[test]
1293     fn test_mut_rev_iter() {
1294         let mut d = RingBuf::new();
1295         assert!(d.iter_mut().rev().next().is_none());
1296
1297         for i in range(0u, 3) {
1298             d.push_front(i);
1299         }
1300
1301         for (i, elt) in d.iter_mut().rev().enumerate() {
1302             assert_eq!(*elt, i);
1303             *elt = i;
1304         }
1305
1306         {
1307             let mut it = d.iter_mut().rev();
1308             assert_eq!(*it.next().unwrap(), 0);
1309             assert_eq!(*it.next().unwrap(), 1);
1310             assert_eq!(*it.next().unwrap(), 2);
1311             assert!(it.next().is_none());
1312         }
1313     }
1314
1315     #[test]
1316     fn test_from_iter() {
1317         use std::iter;
1318         let v = vec!(1i,2,3,4,5,6,7);
1319         let deq: RingBuf<int> = v.iter().map(|&x| x).collect();
1320         let u: Vec<int> = deq.iter().map(|&x| x).collect();
1321         assert_eq!(u, v);
1322
1323         let mut seq = iter::count(0u, 2).take(256);
1324         let deq: RingBuf<uint> = seq.collect();
1325         for (i, &x) in deq.iter().enumerate() {
1326             assert_eq!(2*i, x);
1327         }
1328         assert_eq!(deq.len(), 256);
1329     }
1330
1331     #[test]
1332     fn test_clone() {
1333         let mut d = RingBuf::new();
1334         d.push_front(17i);
1335         d.push_front(42);
1336         d.push_back(137);
1337         d.push_back(137);
1338         assert_eq!(d.len(), 4u);
1339         let mut e = d.clone();
1340         assert_eq!(e.len(), 4u);
1341         while !d.is_empty() {
1342             assert_eq!(d.pop_back(), e.pop_back());
1343         }
1344         assert_eq!(d.len(), 0u);
1345         assert_eq!(e.len(), 0u);
1346     }
1347
1348     #[test]
1349     fn test_eq() {
1350         let mut d = RingBuf::new();
1351         assert!(d == RingBuf::with_capacity(0));
1352         d.push_front(137i);
1353         d.push_front(17);
1354         d.push_front(42);
1355         d.push_back(137);
1356         let mut e = RingBuf::with_capacity(0);
1357         e.push_back(42);
1358         e.push_back(17);
1359         e.push_back(137);
1360         e.push_back(137);
1361         assert!(&e == &d);
1362         e.pop_back();
1363         e.push_back(0);
1364         assert!(e != d);
1365         e.clear();
1366         assert!(e == RingBuf::new());
1367     }
1368
1369     #[test]
1370     fn test_hash() {
1371       let mut x = RingBuf::new();
1372       let mut y = RingBuf::new();
1373
1374       x.push_back(1i);
1375       x.push_back(2);
1376       x.push_back(3);
1377
1378       y.push_back(0i);
1379       y.push_back(1i);
1380       y.pop_front();
1381       y.push_back(2);
1382       y.push_back(3);
1383
1384       assert!(hash::hash(&x) == hash::hash(&y));
1385     }
1386
1387     #[test]
1388     fn test_ord() {
1389         let x = RingBuf::new();
1390         let mut y = RingBuf::new();
1391         y.push_back(1i);
1392         y.push_back(2);
1393         y.push_back(3);
1394         assert!(x < y);
1395         assert!(y > x);
1396         assert!(x <= x);
1397         assert!(x >= x);
1398     }
1399
1400     #[test]
1401     fn test_show() {
1402         let ringbuf: RingBuf<int> = range(0i, 10).collect();
1403         assert!(format!("{}", ringbuf).as_slice() == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
1404
1405         let ringbuf: RingBuf<&str> = vec!["just", "one", "test", "more"].iter()
1406                                                                         .map(|&s| s)
1407                                                                         .collect();
1408         assert!(format!("{}", ringbuf).as_slice() == "[just, one, test, more]");
1409     }
1410
1411     #[test]
1412     fn test_drop() {
1413         static mut drops: uint = 0;
1414         struct Elem;
1415         impl Drop for Elem {
1416             fn drop(&mut self) {
1417                 unsafe { drops += 1; }
1418             }
1419         }
1420
1421         let mut ring = RingBuf::new();
1422         ring.push_back(Elem);
1423         ring.push_front(Elem);
1424         ring.push_back(Elem);
1425         ring.push_front(Elem);
1426         drop(ring);
1427
1428         assert_eq!(unsafe {drops}, 4);
1429     }
1430
1431     #[test]
1432     fn test_drop_with_pop() {
1433         static mut drops: uint = 0;
1434         struct Elem;
1435         impl Drop for Elem {
1436             fn drop(&mut self) {
1437                 unsafe { drops += 1; }
1438             }
1439         }
1440
1441         let mut ring = RingBuf::new();
1442         ring.push_back(Elem);
1443         ring.push_front(Elem);
1444         ring.push_back(Elem);
1445         ring.push_front(Elem);
1446
1447         drop(ring.pop_back());
1448         drop(ring.pop_front());
1449         assert_eq!(unsafe {drops}, 2);
1450
1451         drop(ring);
1452         assert_eq!(unsafe {drops}, 4);
1453     }
1454
1455     #[test]
1456     fn test_drop_clear() {
1457         static mut drops: uint = 0;
1458         struct Elem;
1459         impl Drop for Elem {
1460             fn drop(&mut self) {
1461                 unsafe { drops += 1; }
1462             }
1463         }
1464
1465         let mut ring = RingBuf::new();
1466         ring.push_back(Elem);
1467         ring.push_front(Elem);
1468         ring.push_back(Elem);
1469         ring.push_front(Elem);
1470         ring.clear();
1471         assert_eq!(unsafe {drops}, 4);
1472
1473         drop(ring);
1474         assert_eq!(unsafe {drops}, 4);
1475     }
1476
1477     #[test]
1478     fn test_reserve_grow() {
1479         // test growth path A
1480         // [T o o H] -> [T o o H . . . . ]
1481         let mut ring = RingBuf::with_capacity(4);
1482         for i in range(0i, 3) {
1483             ring.push_back(i);
1484         }
1485         ring.reserve(7);
1486         for i in range(0i, 3) {
1487             assert_eq!(ring.pop_front(), Some(i));
1488         }
1489
1490         // test growth path B
1491         // [H T o o] -> [. T o o H . . . ]
1492         let mut ring = RingBuf::with_capacity(4);
1493         for i in range(0i, 1) {
1494             ring.push_back(i);
1495             assert_eq!(ring.pop_front(), Some(i));
1496         }
1497         for i in range(0i, 3) {
1498             ring.push_back(i);
1499         }
1500         ring.reserve(7);
1501         for i in range(0i, 3) {
1502             assert_eq!(ring.pop_front(), Some(i));
1503         }
1504
1505         // test growth path C
1506         // [o o H T] -> [o o H . . . . T ]
1507         let mut ring = RingBuf::with_capacity(4);
1508         for i in range(0i, 3) {
1509             ring.push_back(i);
1510             assert_eq!(ring.pop_front(), Some(i));
1511         }
1512         for i in range(0i, 3) {
1513             ring.push_back(i);
1514         }
1515         ring.reserve(7);
1516         for i in range(0i, 3) {
1517             assert_eq!(ring.pop_front(), Some(i));
1518         }
1519     }
1520
1521     #[test]
1522     fn test_get() {
1523         let mut ring = RingBuf::new();
1524         ring.push_back(0i);
1525         assert_eq!(ring.get(0), Some(&0));
1526         assert_eq!(ring.get(1), None);
1527
1528         ring.push_back(1);
1529         assert_eq!(ring.get(0), Some(&0));
1530         assert_eq!(ring.get(1), Some(&1));
1531         assert_eq!(ring.get(2), None);
1532
1533         ring.push_back(2);
1534         assert_eq!(ring.get(0), Some(&0));
1535         assert_eq!(ring.get(1), Some(&1));
1536         assert_eq!(ring.get(2), Some(&2));
1537         assert_eq!(ring.get(3), None);
1538
1539         assert_eq!(ring.pop_front(), Some(0));
1540         assert_eq!(ring.get(0), Some(&1));
1541         assert_eq!(ring.get(1), Some(&2));
1542         assert_eq!(ring.get(2), None);
1543
1544         assert_eq!(ring.pop_front(), Some(1));
1545         assert_eq!(ring.get(0), Some(&2));
1546         assert_eq!(ring.get(1), None);
1547
1548         assert_eq!(ring.pop_front(), Some(2));
1549         assert_eq!(ring.get(0), None);
1550         assert_eq!(ring.get(1), None);
1551     }
1552
1553     #[test]
1554     fn test_get_mut() {
1555         let mut ring = RingBuf::new();
1556         for i in range(0i, 3) {
1557             ring.push_back(i);
1558         }
1559
1560         match ring.get_mut(1) {
1561             Some(x) => *x = -1,
1562             None => ()
1563         };
1564
1565         assert_eq!(ring.get_mut(0), Some(&mut 0));
1566         assert_eq!(ring.get_mut(1), Some(&mut -1));
1567         assert_eq!(ring.get_mut(2), Some(&mut 2));
1568         assert_eq!(ring.get_mut(3), None);
1569
1570         assert_eq!(ring.pop_front(), Some(0));
1571         assert_eq!(ring.get_mut(0), Some(&mut -1));
1572         assert_eq!(ring.get_mut(1), Some(&mut 2));
1573         assert_eq!(ring.get_mut(2), None);
1574     }
1575 }