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