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 impl<'a, T> ExactSizeIterator<&'a T> for Items<'a, T> {}
 699
 700 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
 701     #[inline]
 702     fn indexable(&self) -> uint {
 703         let (len, _) = self.size_hint();
 704         len
 705     }
 706
 707     #[inline]
 708     fn idx(&mut self, j: uint) -> Option<&'a T> {
 709         if j >= self.indexable() {
 710             None
 711         } else {
 712             let idx = wrap_index(self.tail + j, self.ring.len());
 713             unsafe { Some(self.ring.unsafe_get(idx)) }
 714         }
 715     }
 716 }
 717
 718 // FIXME This was implemented differently from Items because of a problem
 719 //       with returning the mutable reference. I couldn't find a way to
 720 //       make the lifetime checker happy so, but there should be a way.
 721 /// `RingBuf` mutable iterator.
 722 pub struct MutItems<'a, T:'a> {
 723     ptr: *mut T,
 724     tail: uint,
 725     head: uint,
 726     cap: uint,
 727     marker: marker::ContravariantLifetime<'a>,
 728     marker2: marker::NoCopy
 729 }
 730
 731 impl<'a, T> Iterator<&'a mut T> for MutItems<'a, T> {
 732     #[inline]
 733     fn next(&mut self) -> Option<&'a mut T> {
 734         if self.tail == self.head {
 735             return None;
 736         }
 737         let tail = self.tail;
 738         self.tail = wrap_index(self.tail + 1, self.cap);
 739         if mem::size_of::<T>() != 0 {
 740             unsafe { Some(&mut *self.ptr.offset(tail as int)) }
 741         } else {
 742             // use a non-zero pointer
 743             Some(unsafe { mem::transmute(1u) })
 744         }
 745     }
 746
 747     #[inline]
 748     fn size_hint(&self) -> (uint, Option<uint>) {
 749         let len = count(self.tail, self.head, self.cap);
 750         (len, Some(len))
 751     }
 752 }
 753
 754 impl<'a, T> DoubleEndedIterator<&'a mut T> for MutItems<'a, T> {
 755     #[inline]
 756     fn next_back(&mut self) -> Option<&'a mut T> {
 757         if self.tail == self.head {
 758             return None;
 759         }
 760         self.head = wrap_index(self.head - 1, self.cap);
 761         unsafe { Some(&mut *self.ptr.offset(self.head as int)) }
 762     }
 763 }
 764
 765 impl<'a, T> ExactSizeIterator<&'a mut T> for MutItems<'a, T> {}
 766
 767 impl<A: PartialEq> PartialEq for RingBuf<A> {
 768     fn eq(&self, other: &RingBuf<A>) -> bool {
 769         self.len() == other.len() &&
 770             self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
 771     }
 772     fn ne(&self, other: &RingBuf<A>) -> bool {
 773         !self.eq(other)
 774     }
 775 }
 776
 777 impl<A: Eq> Eq for RingBuf<A> {}
 778
 779 impl<A: PartialOrd> PartialOrd for RingBuf<A> {
 780     fn partial_cmp(&self, other: &RingBuf<A>) -> Option<Ordering> {
 781         iter::order::partial_cmp(self.iter(), other.iter())
 782     }
 783 }
 784
 785 impl<A: Ord> Ord for RingBuf<A> {
 786     #[inline]
 787     fn cmp(&self, other: &RingBuf<A>) -> Ordering {
 788         iter::order::cmp(self.iter(), other.iter())
 789     }
 790 }
 791
 792 impl<S: Writer, A: Hash<S>> Hash<S> for RingBuf<A> {
 793     fn hash(&self, state: &mut S) {
 794         self.len().hash(state);
 795         for elt in self.iter() {
 796             elt.hash(state);
 797         }
 798     }
 799 }
 800
 801 impl<A> Index<uint, A> for RingBuf<A> {
 802     #[inline]
 803     fn index<'a>(&'a self, i: &uint) -> &'a A {
 804         self.get(*i).expect("Out of bounds access")
 805     }
 806 }
 807
 808 impl<A> IndexMut<uint, A> for RingBuf<A> {
 809     #[inline]
 810     fn index_mut<'a>(&'a mut self, i: &uint) -> &'a mut A {
 811         self.get_mut(*i).expect("Out of bounds access")
 812     }
 813 }
 814
 815 impl<A> FromIterator<A> for RingBuf<A> {
 816     fn from_iter<T: Iterator<A>>(iterator: T) -> RingBuf<A> {
 817         let (lower, _) = iterator.size_hint();
 818         let mut deq = RingBuf::with_capacity(lower);
 819         deq.extend(iterator);
 820         deq
 821     }
 822 }
 823
 824 impl<A> Extend<A> for RingBuf<A> {
 825     fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
 826         for elt in iterator {
 827             self.push_back(elt);
 828         }
 829     }
 830 }
 831
 832 impl<T: fmt::Show> fmt::Show for RingBuf<T> {
 833     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 834         try!(write!(f, "["));
 835
 836         for (i, e) in self.iter().enumerate() {
 837             if i != 0 { try!(write!(f, ", ")); }
 838             try!(write!(f, "{}", *e));
 839         }
 840
 841         write!(f, "]")
 842     }
 843 }
 844
 845 #[cfg(test)]
 846 mod tests {
 847     use self::Taggy::*;
 848     use self::Taggypar::*;
 849     use std::fmt::Show;
 850     use std::prelude::*;
 851     use std::hash;
 852     use test::Bencher;
 853     use test;
 854
 855     use super::RingBuf;
 856     use vec::Vec;
 857
 858     #[test]
 859     #[allow(deprecated)]
 860     fn test_simple() {
 861         let mut d = RingBuf::new();
 862         assert_eq!(d.len(), 0u);
 863         d.push_front(17i);
 864         d.push_front(42i);
 865         d.push_back(137);
 866         assert_eq!(d.len(), 3u);
 867         d.push_back(137);
 868         assert_eq!(d.len(), 4u);
 869         debug!("{}", d.front());
 870         assert_eq!(*d.front().unwrap(), 42);
 871         debug!("{}", d.back());
 872         assert_eq!(*d.back().unwrap(), 137);
 873         let mut i = d.pop_front();
 874         debug!("{}", i);
 875         assert_eq!(i, Some(42));
 876         i = d.pop_back();
 877         debug!("{}", i);
 878         assert_eq!(i, Some(137));
 879         i = d.pop_back();
 880         debug!("{}", i);
 881         assert_eq!(i, Some(137));
 882         i = d.pop_back();
 883         debug!("{}", i);
 884         assert_eq!(i, Some(17));
 885         assert_eq!(d.len(), 0u);
 886         d.push_back(3);
 887         assert_eq!(d.len(), 1u);
 888         d.push_front(2);
 889         assert_eq!(d.len(), 2u);
 890         d.push_back(4);
 891         assert_eq!(d.len(), 3u);
 892         d.push_front(1);
 893         assert_eq!(d.len(), 4u);
 894         debug!("{}", d[0]);
 895         debug!("{}", d[1]);
 896         debug!("{}", d[2]);
 897         debug!("{}", d[3]);
 898         assert_eq!(d[0], 1);
 899         assert_eq!(d[1], 2);
 900         assert_eq!(d[2], 3);
 901         assert_eq!(d[3], 4);
 902     }
 903
 904     #[cfg(test)]
 905     fn test_parameterized<T:Clone + PartialEq + Show>(a: T, b: T, c: T, d: T) {
 906         let mut deq = RingBuf::new();
 907         assert_eq!(deq.len(), 0);
 908         deq.push_front(a.clone());
 909         deq.push_front(b.clone());
 910         deq.push_back(c.clone());
 911         assert_eq!(deq.len(), 3);
 912         deq.push_back(d.clone());
 913         assert_eq!(deq.len(), 4);
 914         assert_eq!((*deq.front().unwrap()).clone(), b.clone());
 915         assert_eq!((*deq.back().unwrap()).clone(), d.clone());
 916         assert_eq!(deq.pop_front().unwrap(), b.clone());
 917         assert_eq!(deq.pop_back().unwrap(), d.clone());
 918         assert_eq!(deq.pop_back().unwrap(), c.clone());
 919         assert_eq!(deq.pop_back().unwrap(), a.clone());
 920         assert_eq!(deq.len(), 0);
 921         deq.push_back(c.clone());
 922         assert_eq!(deq.len(), 1);
 923         deq.push_front(b.clone());
 924         assert_eq!(deq.len(), 2);
 925         deq.push_back(d.clone());
 926         assert_eq!(deq.len(), 3);
 927         deq.push_front(a.clone());
 928         assert_eq!(deq.len(), 4);
 929         assert_eq!(deq[0].clone(), a.clone());
 930         assert_eq!(deq[1].clone(), b.clone());
 931         assert_eq!(deq[2].clone(), c.clone());
 932         assert_eq!(deq[3].clone(), d.clone());
 933     }
 934
 935     #[test]
 936     fn test_push_front_grow() {
 937         let mut deq = RingBuf::new();
 938         for i in range(0u, 66) {
 939             deq.push_front(i);
 940         }
 941         assert_eq!(deq.len(), 66);
 942
 943         for i in range(0u, 66) {
 944             assert_eq!(deq[i], 65 - i);
 945         }
 946
 947         let mut deq = RingBuf::new();
 948         for i in range(0u, 66) {
 949             deq.push_back(i);
 950         }
 951
 952         for i in range(0u, 66) {
 953             assert_eq!(deq[i], i);
 954         }
 955     }
 956
 957     #[test]
 958     fn test_index() {
 959         let mut deq = RingBuf::new();
 960         for i in range(1u, 4) {
 961             deq.push_front(i);
 962         }
 963         assert_eq!(deq[1], 2);
 964     }
 965
 966     #[test]
 967     #[should_fail]
 968     fn test_index_out_of_bounds() {
 969         let mut deq = RingBuf::new();
 970         for i in range(1u, 4) {
 971             deq.push_front(i);
 972         }
 973         deq[3];
 974     }
 975
 976     #[bench]
 977     fn bench_new(b: &mut test::Bencher) {
 978         b.iter(|| {
 979             let ring: RingBuf<u64> = RingBuf::new();
 980             test::black_box(ring);
 981         })
 982     }
 983
 984     #[bench]
 985     fn bench_push_back_100(b: &mut test::Bencher) {
 986         let mut deq = RingBuf::with_capacity(101);
 987         b.iter(|| {
 988             for i in range(0i, 100) {
 989                 deq.push_back(i);
 990             }
 991             deq.head = 0;
 992             deq.tail = 0;
 993         })
 994     }
 995
 996     #[bench]
 997     fn bench_push_front_100(b: &mut test::Bencher) {
 998         let mut deq = RingBuf::with_capacity(101);
 999         b.iter(|| {
1000             for i in range(0i, 100) {
1001                 deq.push_front(i);
1002             }
1003             deq.head = 0;
1004             deq.tail = 0;
1005         })
1006     }
1007
1008     #[bench]
1009     fn bench_pop_back_100(b: &mut test::Bencher) {
1010         let mut deq: RingBuf<int> = RingBuf::with_capacity(101);
1011
1012         b.iter(|| {
1013             deq.head = 100;
1014             deq.tail = 0;
1015             while !deq.is_empty() {
1016                 test::black_box(deq.pop_back());
1017             }
1018         })
1019     }
1020
1021     #[bench]
1022     fn bench_pop_front_100(b: &mut test::Bencher) {
1023         let mut deq: RingBuf<int> = RingBuf::with_capacity(101);
1024
1025         b.iter(|| {
1026             deq.head = 100;
1027             deq.tail = 0;
1028             while !deq.is_empty() {
1029                 test::black_box(deq.pop_front());
1030             }
1031         })
1032     }
1033
1034     #[bench]
1035     fn bench_grow_1025(b: &mut test::Bencher) {
1036         b.iter(|| {
1037             let mut deq = RingBuf::new();
1038             for i in range(0i, 1025) {
1039                 deq.push_front(i);
1040             }
1041             test::black_box(deq);
1042         })
1043     }
1044
1045     #[bench]
1046     fn bench_iter_1000(b: &mut test::Bencher) {
1047         let ring: RingBuf<int> = range(0i, 1000).collect();
1048
1049         b.iter(|| {
1050             let mut sum = 0;
1051             for &i in ring.iter() {
1052                 sum += i;
1053             }
1054             test::black_box(sum);
1055         })
1056     }
1057
1058     #[bench]
1059     fn bench_mut_iter_1000(b: &mut test::Bencher) {
1060         let mut ring: RingBuf<int> = range(0i, 1000).collect();
1061
1062         b.iter(|| {
1063             let mut sum = 0;
1064             for i in ring.iter_mut() {
1065                 sum += *i;
1066             }
1067             test::black_box(sum);
1068         })
1069     }
1070
1071
1072     #[deriving(Clone, PartialEq, Show)]
1073     enum Taggy {
1074         One(int),
1075         Two(int, int),
1076         Three(int, int, int),
1077     }
1078
1079     #[deriving(Clone, PartialEq, Show)]
1080     enum Taggypar<T> {
1081         Onepar(int),
1082         Twopar(int, int),
1083         Threepar(int, int, int),
1084     }
1085
1086     #[deriving(Clone, PartialEq, Show)]
1087     struct RecCy {
1088         x: int,
1089         y: int,
1090         t: Taggy
1091     }
1092
1093     #[test]
1094     fn test_param_int() {
1095         test_parameterized::<int>(5, 72, 64, 175);
1096     }
1097
1098     #[test]
1099     fn test_param_taggy() {
1100         test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
1101     }
1102
1103     #[test]
1104     fn test_param_taggypar() {
1105         test_parameterized::<Taggypar<int>>(Onepar::<int>(1),
1106                                             Twopar::<int>(1, 2),
1107                                             Threepar::<int>(1, 2, 3),
1108                                             Twopar::<int>(17, 42));
1109     }
1110
1111     #[test]
1112     fn test_param_reccy() {
1113         let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
1114         let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
1115         let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
1116         let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
1117         test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
1118     }
1119
1120     #[test]
1121     fn test_with_capacity() {
1122         let mut d = RingBuf::with_capacity(0);
1123         d.push_back(1i);
1124         assert_eq!(d.len(), 1);
1125         let mut d = RingBuf::with_capacity(50);
1126         d.push_back(1i);
1127         assert_eq!(d.len(), 1);
1128     }
1129
1130     #[test]
1131     fn test_with_capacity_non_power_two() {
1132         let mut d3 = RingBuf::with_capacity(3);
1133         d3.push_back(1i);
1134
1135         // X = None, | = lo
1136         // [|1, X, X]
1137         assert_eq!(d3.pop_front(), Some(1));
1138         // [X, |X, X]
1139         assert_eq!(d3.front(), None);
1140
1141         // [X, |3, X]
1142         d3.push_back(3);
1143         // [X, |3, 6]
1144         d3.push_back(6);
1145         // [X, X, |6]
1146         assert_eq!(d3.pop_front(), Some(3));
1147
1148         // Pushing the lo past half way point to trigger
1149         // the 'B' scenario for growth
1150         // [9, X, |6]
1151         d3.push_back(9);
1152         // [9, 12, |6]
1153         d3.push_back(12);
1154
1155         d3.push_back(15);
1156         // There used to be a bug here about how the
1157         // RingBuf made growth assumptions about the
1158         // underlying Vec which didn't hold and lead
1159         // to corruption.
1160         // (Vec grows to next power of two)
1161         //good- [9, 12, 15, X, X, X, X, |6]
1162         //bug-  [15, 12, X, X, X, |6, X, X]
1163         assert_eq!(d3.pop_front(), Some(6));
1164
1165         // Which leads us to the following state which
1166         // would be a failure case.
1167         //bug-  [15, 12, X, X, X, X, |X, X]
1168         assert_eq!(d3.front(), Some(&9));
1169     }
1170
1171     #[test]
1172     fn test_reserve_exact() {
1173         let mut d = RingBuf::new();
1174         d.push_back(0u64);
1175         d.reserve_exact(50);
1176         assert!(d.capacity() >= 51);
1177         let mut d = RingBuf::new();
1178         d.push_back(0u32);
1179         d.reserve_exact(50);
1180         assert!(d.capacity() >= 51);
1181     }
1182
1183     #[test]
1184     fn test_reserve() {
1185         let mut d = RingBuf::new();
1186         d.push_back(0u64);
1187         d.reserve(50);
1188         assert!(d.capacity() >= 51);
1189         let mut d = RingBuf::new();
1190         d.push_back(0u32);
1191         d.reserve(50);
1192         assert!(d.capacity() >= 51);
1193     }
1194
1195     #[test]
1196     fn test_swap() {
1197         let mut d: RingBuf<int> = range(0i, 5).collect();
1198         d.pop_front();
1199         d.swap(0, 3);
1200         assert_eq!(d.iter().map(|&x|x).collect::<Vec<int>>(), vec!(4, 2, 3, 1));
1201     }
1202
1203     #[test]
1204     fn test_iter() {
1205         let mut d = RingBuf::new();
1206         assert_eq!(d.iter().next(), None);
1207         assert_eq!(d.iter().size_hint(), (0, Some(0)));
1208
1209         for i in range(0i, 5) {
1210             d.push_back(i);
1211         }
1212         {
1213             let b: &[_] = &[&0,&1,&2,&3,&4];
1214             assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), b);
1215         }
1216
1217         for i in range(6i, 9) {
1218             d.push_front(i);
1219         }
1220         {
1221             let b: &[_] = &[&8,&7,&6,&0,&1,&2,&3,&4];
1222             assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), b);
1223         }
1224
1225         let mut it = d.iter();
1226         let mut len = d.len();
1227         loop {
1228             match it.next() {
1229                 None => break,
1230                 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
1231             }
1232         }
1233     }
1234
1235     #[test]
1236     fn test_rev_iter() {
1237         let mut d = RingBuf::new();
1238         assert_eq!(d.iter().rev().next(), None);
1239
1240         for i in range(0i, 5) {
1241             d.push_back(i);
1242         }
1243         {
1244             let b: &[_] = &[&4,&3,&2,&1,&0];
1245             assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), b);
1246         }
1247
1248         for i in range(6i, 9) {
1249             d.push_front(i);
1250         }
1251         let b: &[_] = &[&4,&3,&2,&1,&0,&6,&7,&8];
1252         assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), b);
1253     }
1254
1255     #[test]
1256     fn test_mut_rev_iter_wrap() {
1257         let mut d = RingBuf::with_capacity(3);
1258         assert!(d.iter_mut().rev().next().is_none());
1259
1260         d.push_back(1i);
1261         d.push_back(2);
1262         d.push_back(3);
1263         assert_eq!(d.pop_front(), Some(1));
1264         d.push_back(4);
1265
1266         assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<int>>(),
1267                    vec!(4, 3, 2));
1268     }
1269
1270     #[test]
1271     fn test_mut_iter() {
1272         let mut d = RingBuf::new();
1273         assert!(d.iter_mut().next().is_none());
1274
1275         for i in range(0u, 3) {
1276             d.push_front(i);
1277         }
1278
1279         for (i, elt) in d.iter_mut().enumerate() {
1280             assert_eq!(*elt, 2 - i);
1281             *elt = i;
1282         }
1283
1284         {
1285             let mut it = d.iter_mut();
1286             assert_eq!(*it.next().unwrap(), 0);
1287             assert_eq!(*it.next().unwrap(), 1);
1288             assert_eq!(*it.next().unwrap(), 2);
1289             assert!(it.next().is_none());
1290         }
1291     }
1292
1293     #[test]
1294     fn test_mut_rev_iter() {
1295         let mut d = RingBuf::new();
1296         assert!(d.iter_mut().rev().next().is_none());
1297
1298         for i in range(0u, 3) {
1299             d.push_front(i);
1300         }
1301
1302         for (i, elt) in d.iter_mut().rev().enumerate() {
1303             assert_eq!(*elt, i);
1304             *elt = i;
1305         }
1306
1307         {
1308             let mut it = d.iter_mut().rev();
1309             assert_eq!(*it.next().unwrap(), 0);
1310             assert_eq!(*it.next().unwrap(), 1);
1311             assert_eq!(*it.next().unwrap(), 2);
1312             assert!(it.next().is_none());
1313         }
1314     }
1315
1316     #[test]
1317     fn test_from_iter() {
1318         use std::iter;
1319         let v = vec!(1i,2,3,4,5,6,7);
1320         let deq: RingBuf<int> = v.iter().map(|&x| x).collect();
1321         let u: Vec<int> = deq.iter().map(|&x| x).collect();
1322         assert_eq!(u, v);
1323
1324         let seq = iter::count(0u, 2).take(256);
1325         let deq: RingBuf<uint> = seq.collect();
1326         for (i, &x) in deq.iter().enumerate() {
1327             assert_eq!(2*i, x);
1328         }
1329         assert_eq!(deq.len(), 256);
1330     }
1331
1332     #[test]
1333     fn test_clone() {
1334         let mut d = RingBuf::new();
1335         d.push_front(17i);
1336         d.push_front(42);
1337         d.push_back(137);
1338         d.push_back(137);
1339         assert_eq!(d.len(), 4u);
1340         let mut e = d.clone();
1341         assert_eq!(e.len(), 4u);
1342         while !d.is_empty() {
1343             assert_eq!(d.pop_back(), e.pop_back());
1344         }
1345         assert_eq!(d.len(), 0u);
1346         assert_eq!(e.len(), 0u);
1347     }
1348
1349     #[test]
1350     fn test_eq() {
1351         let mut d = RingBuf::new();
1352         assert!(d == RingBuf::with_capacity(0));
1353         d.push_front(137i);
1354         d.push_front(17);
1355         d.push_front(42);
1356         d.push_back(137);
1357         let mut e = RingBuf::with_capacity(0);
1358         e.push_back(42);
1359         e.push_back(17);
1360         e.push_back(137);
1361         e.push_back(137);
1362         assert!(&e == &d);
1363         e.pop_back();
1364         e.push_back(0);
1365         assert!(e != d);
1366         e.clear();
1367         assert!(e == RingBuf::new());
1368     }
1369
1370     #[test]
1371     fn test_hash() {
1372       let mut x = RingBuf::new();
1373       let mut y = RingBuf::new();
1374
1375       x.push_back(1i);
1376       x.push_back(2);
1377       x.push_back(3);
1378
1379       y.push_back(0i);
1380       y.push_back(1i);
1381       y.pop_front();
1382       y.push_back(2);
1383       y.push_back(3);
1384
1385       assert!(hash::hash(&x) == hash::hash(&y));
1386     }
1387
1388     #[test]
1389     fn test_ord() {
1390         let x = RingBuf::new();
1391         let mut y = RingBuf::new();
1392         y.push_back(1i);
1393         y.push_back(2);
1394         y.push_back(3);
1395         assert!(x < y);
1396         assert!(y > x);
1397         assert!(x <= x);
1398         assert!(x >= x);
1399     }
1400
1401     #[test]
1402     fn test_show() {
1403         let ringbuf: RingBuf<int> = range(0i, 10).collect();
1404         assert!(format!("{}", ringbuf).as_slice() == "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
1405
1406         let ringbuf: RingBuf<&str> = vec!["just", "one", "test", "more"].iter()
1407                                                                         .map(|&s| s)
1408                                                                         .collect();
1409         assert!(format!("{}", ringbuf).as_slice() == "[just, one, test, more]");
1410     }
1411
1412     #[test]
1413     fn test_drop() {
1414         static mut drops: uint = 0;
1415         struct Elem;
1416         impl Drop for Elem {
1417             fn drop(&mut self) {
1418                 unsafe { drops += 1; }
1419             }
1420         }
1421
1422         let mut ring = RingBuf::new();
1423         ring.push_back(Elem);
1424         ring.push_front(Elem);
1425         ring.push_back(Elem);
1426         ring.push_front(Elem);
1427         drop(ring);
1428
1429         assert_eq!(unsafe {drops}, 4);
1430     }
1431
1432     #[test]
1433     fn test_drop_with_pop() {
1434         static mut drops: uint = 0;
1435         struct Elem;
1436         impl Drop for Elem {
1437             fn drop(&mut self) {
1438                 unsafe { drops += 1; }
1439             }
1440         }
1441
1442         let mut ring = RingBuf::new();
1443         ring.push_back(Elem);
1444         ring.push_front(Elem);
1445         ring.push_back(Elem);
1446         ring.push_front(Elem);
1447
1448         drop(ring.pop_back());
1449         drop(ring.pop_front());
1450         assert_eq!(unsafe {drops}, 2);
1451
1452         drop(ring);
1453         assert_eq!(unsafe {drops}, 4);
1454     }
1455
1456     #[test]
1457     fn test_drop_clear() {
1458         static mut drops: uint = 0;
1459         struct Elem;
1460         impl Drop for Elem {
1461             fn drop(&mut self) {
1462                 unsafe { drops += 1; }
1463             }
1464         }
1465
1466         let mut ring = RingBuf::new();
1467         ring.push_back(Elem);
1468         ring.push_front(Elem);
1469         ring.push_back(Elem);
1470         ring.push_front(Elem);
1471         ring.clear();
1472         assert_eq!(unsafe {drops}, 4);
1473
1474         drop(ring);
1475         assert_eq!(unsafe {drops}, 4);
1476     }
1477
1478     #[test]
1479     fn test_reserve_grow() {
1480         // test growth path A
1481         // [T o o H] -> [T o o H . . . . ]
1482         let mut ring = RingBuf::with_capacity(4);
1483         for i in range(0i, 3) {
1484             ring.push_back(i);
1485         }
1486         ring.reserve(7);
1487         for i in range(0i, 3) {
1488             assert_eq!(ring.pop_front(), Some(i));
1489         }
1490
1491         // test growth path B
1492         // [H T o o] -> [. T o o H . . . ]
1493         let mut ring = RingBuf::with_capacity(4);
1494         for i in range(0i, 1) {
1495             ring.push_back(i);
1496             assert_eq!(ring.pop_front(), Some(i));
1497         }
1498         for i in range(0i, 3) {
1499             ring.push_back(i);
1500         }
1501         ring.reserve(7);
1502         for i in range(0i, 3) {
1503             assert_eq!(ring.pop_front(), Some(i));
1504         }
1505
1506         // test growth path C
1507         // [o o H T] -> [o o H . . . . T ]
1508         let mut ring = RingBuf::with_capacity(4);
1509         for i in range(0i, 3) {
1510             ring.push_back(i);
1511             assert_eq!(ring.pop_front(), Some(i));
1512         }
1513         for i in range(0i, 3) {
1514             ring.push_back(i);
1515         }
1516         ring.reserve(7);
1517         for i in range(0i, 3) {
1518             assert_eq!(ring.pop_front(), Some(i));
1519         }
1520     }
1521
1522     #[test]
1523     fn test_get() {
1524         let mut ring = RingBuf::new();
1525         ring.push_back(0i);
1526         assert_eq!(ring.get(0), Some(&0));
1527         assert_eq!(ring.get(1), None);
1528
1529         ring.push_back(1);
1530         assert_eq!(ring.get(0), Some(&0));
1531         assert_eq!(ring.get(1), Some(&1));
1532         assert_eq!(ring.get(2), None);
1533
1534         ring.push_back(2);
1535         assert_eq!(ring.get(0), Some(&0));
1536         assert_eq!(ring.get(1), Some(&1));
1537         assert_eq!(ring.get(2), Some(&2));
1538         assert_eq!(ring.get(3), None);
1539
1540         assert_eq!(ring.pop_front(), Some(0));
1541         assert_eq!(ring.get(0), Some(&1));
1542         assert_eq!(ring.get(1), Some(&2));
1543         assert_eq!(ring.get(2), None);
1544
1545         assert_eq!(ring.pop_front(), Some(1));
1546         assert_eq!(ring.get(0), Some(&2));
1547         assert_eq!(ring.get(1), None);
1548
1549         assert_eq!(ring.pop_front(), Some(2));
1550         assert_eq!(ring.get(0), None);
1551         assert_eq!(ring.get(1), None);
1552     }
1553
1554     #[test]
1555     fn test_get_mut() {
1556         let mut ring = RingBuf::new();
1557         for i in range(0i, 3) {
1558             ring.push_back(i);
1559         }
1560
1561         match ring.get_mut(1) {
1562             Some(x) => *x = -1,
1563             None => ()
1564         };
1565
1566         assert_eq!(ring.get_mut(0), Some(&mut 0));
1567         assert_eq!(ring.get_mut(1), Some(&mut -1));
1568         assert_eq!(ring.get_mut(2), Some(&mut 2));
1569         assert_eq!(ring.get_mut(3), None);
1570
1571         assert_eq!(ring.pop_front(), Some(0));
1572         assert_eq!(ring.get_mut(0), Some(&mut -1));
1573         assert_eq!(ring.get_mut(1), Some(&mut 2));
1574         assert_eq!(ring.get_mut(2), None);
1575     }
1576 }