src/libcollections/ring_buf.rs

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