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