src/libcollections/ringbuf.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 //! A double-ended queue implemented as a circular buffer
  12 //!
  13 //! RingBuf implements the trait Deque. It should be imported with `use
  14 //! collections::deque::Deque`.
  15
  16 use std::cmp;
  17 use std::iter::RandomAccessIterator;
  18
  19 use deque::Deque;
  20
  21 static INITIAL_CAPACITY: uint = 8u; // 2^3
  22 static MINIMUM_CAPACITY: uint = 2u;
  23
  24 /// RingBuf is a circular buffer that implements Deque.
  25 #[deriving(Clone)]
  26 pub struct RingBuf<T> {
  27     nelts: uint,
  28     lo: uint,
  29     elts: Vec<Option<T>>
  30 }
  31
  32 impl<T> Container for RingBuf<T> {
  33     /// Return the number of elements in the RingBuf
  34     fn len(&self) -> uint { self.nelts }
  35 }
  36
  37 impl<T> Mutable for RingBuf<T> {
  38     /// Clear the RingBuf, removing all values.
  39     fn clear(&mut self) {
  40         for x in self.elts.mut_iter() { *x = None }
  41         self.nelts = 0;
  42         self.lo = 0;
  43     }
  44 }
  45
  46 impl<T> Deque<T> for RingBuf<T> {
  47     /// Return a reference to the first element in the RingBuf
  48     fn front<'a>(&'a self) -> Option<&'a T> {
  49         if self.nelts > 0 { Some(self.get(0)) } else { None }
  50     }
  51
  52     /// Return a mutable reference to the first element in the RingBuf
  53     fn front_mut<'a>(&'a mut self) -> Option<&'a mut T> {
  54         if self.nelts > 0 { Some(self.get_mut(0)) } else { None }
  55     }
  56
  57     /// Return a reference to the last element in the RingBuf
  58     fn back<'a>(&'a self) -> Option<&'a T> {
  59         if self.nelts > 0 { Some(self.get(self.nelts - 1)) } else { None }
  60     }
  61
  62     /// Return a mutable reference to the last element in the RingBuf
  63     fn back_mut<'a>(&'a mut self) -> Option<&'a mut T> {
  64         if self.nelts > 0 { Some(self.get_mut(self.nelts - 1)) } else { None }
  65     }
  66
  67     /// Remove and return the first element in the RingBuf, or None if it is empty
  68     fn pop_front(&mut self) -> Option<T> {
  69         let result = self.elts.get_mut(self.lo).take();
  70         if result.is_some() {
  71             self.lo = (self.lo + 1u) % self.elts.len();
  72             self.nelts -= 1u;
  73         }
  74         result
  75     }
  76
  77     /// Remove and return the last element in the RingBuf, or None if it is empty
  78     fn pop_back(&mut self) -> Option<T> {
  79         if self.nelts > 0 {
  80             self.nelts -= 1;
  81             let hi = self.raw_index(self.nelts);
  82             self.elts.get_mut(hi).take()
  83         } else {
  84             None
  85         }
  86     }
  87
  88     /// Prepend an element to the RingBuf
  89     fn push_front(&mut self, t: T) {
  90         if self.nelts == self.elts.len() {
  91             grow(self.nelts, &mut self.lo, &mut self.elts);
  92         }
  93         if self.lo == 0u {
  94             self.lo = self.elts.len() - 1u;
  95         } else { self.lo -= 1u; }
  96         *self.elts.get_mut(self.lo) = Some(t);
  97         self.nelts += 1u;
  98     }
  99
 100     /// Append an element to the RingBuf
 101     fn push_back(&mut self, t: T) {
 102         if self.nelts == self.elts.len() {
 103             grow(self.nelts, &mut self.lo, &mut self.elts);
 104         }
 105         let hi = self.raw_index(self.nelts);
 106         *self.elts.get_mut(hi) = Some(t);
 107         self.nelts += 1u;
 108     }
 109 }
 110
 111 impl<T> RingBuf<T> {
 112     /// Create an empty RingBuf
 113     pub fn new() -> RingBuf<T> {
 114         RingBuf::with_capacity(INITIAL_CAPACITY)
 115     }
 116
 117     /// Create an empty RingBuf with space for at least `n` elements.
 118     pub fn with_capacity(n: uint) -> RingBuf<T> {
 119         RingBuf{nelts: 0, lo: 0,
 120               elts: Vec::from_fn(cmp::max(MINIMUM_CAPACITY, n), |_| None)}
 121     }
 122
 123     /// Retrieve an element in the RingBuf by index
 124     ///
 125     /// Fails if there is no element with the given index
 126     pub fn get<'a>(&'a self, i: uint) -> &'a T {
 127         let idx = self.raw_index(i);
 128         match *self.elts.get(idx) {
 129             None => fail!(),
 130             Some(ref v) => v
 131         }
 132     }
 133
 134     /// Retrieve an element in the RingBuf by index
 135     ///
 136     /// Fails if there is no element with the given index
 137     pub fn get_mut<'a>(&'a mut self, i: uint) -> &'a mut T {
 138         let idx = self.raw_index(i);
 139         match *self.elts.get_mut(idx) {
 140             None => fail!(),
 141             Some(ref mut v) => v
 142         }
 143     }
 144
 145     /// Swap elements at indices `i` and `j`
 146     ///
 147     /// `i` and `j` may be equal.
 148     ///
 149     /// Fails if there is no element with the given index
 150     pub fn swap(&mut self, i: uint, j: uint) {
 151         assert!(i < self.len());
 152         assert!(j < self.len());
 153         let ri = self.raw_index(i);
 154         let rj = self.raw_index(j);
 155         self.elts.as_mut_slice().swap(ri, rj);
 156     }
 157
 158     /// Return index in underlying vec for a given logical element index
 159     fn raw_index(&self, idx: uint) -> uint {
 160         raw_index(self.lo, self.elts.len(), idx)
 161     }
 162
 163     /// Reserve capacity for exactly `n` elements in the given RingBuf,
 164     /// doing nothing if `self`'s capacity is already equal to or greater
 165     /// than the requested capacity
 166     ///
 167     /// # Arguments
 168     ///
 169     /// * n - The number of elements to reserve space for
 170     pub fn reserve_exact(&mut self, n: uint) {
 171         self.elts.reserve_exact(n);
 172     }
 173
 174     /// Reserve capacity for at least `n` elements in the given RingBuf,
 175     /// over-allocating in case the caller needs to reserve additional
 176     /// space.
 177     ///
 178     /// Do nothing if `self`'s capacity is already equal to or greater
 179     /// than the requested capacity.
 180     ///
 181     /// # Arguments
 182     ///
 183     /// * n - The number of elements to reserve space for
 184     pub fn reserve(&mut self, n: uint) {
 185         self.elts.reserve(n);
 186     }
 187
 188     /// Front-to-back iterator.
 189     pub fn iter<'a>(&'a self) -> Items<'a, T> {
 190         Items{index: 0, rindex: self.nelts, lo: self.lo, elts: self.elts.as_slice()}
 191     }
 192
 193     /// Front-to-back iterator which returns mutable values.
 194     pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
 195         let start_index = raw_index(self.lo, self.elts.len(), 0);
 196         let end_index = raw_index(self.lo, self.elts.len(), self.nelts);
 197
 198         // Divide up the array
 199         if end_index <= start_index {
 200             // Items to iterate goes from:
 201             //    start_index to self.elts.len()
 202             // and then
 203             //    0 to end_index
 204             let (temp, remaining1) = self.elts.mut_split_at(start_index);
 205             let (remaining2, _) = temp.mut_split_at(end_index);
 206             MutItems { remaining1: remaining1,
 207                                  remaining2: remaining2,
 208                                  nelts: self.nelts }
 209         } else {
 210             // Items to iterate goes from start_index to end_index:
 211             let (empty, elts) = self.elts.mut_split_at(0);
 212             let remaining1 = elts.mut_slice(start_index, end_index);
 213             MutItems { remaining1: remaining1,
 214                                  remaining2: empty,
 215                                  nelts: self.nelts }
 216         }
 217     }
 218 }
 219
 220 /// RingBuf iterator
 221 pub struct Items<'a, T> {
 222     lo: uint,
 223     index: uint,
 224     rindex: uint,
 225     elts: &'a [Option<T>],
 226 }
 227
 228 impl<'a, T> Iterator<&'a T> for Items<'a, T> {
 229     #[inline]
 230     fn next(&mut self) -> Option<&'a T> {
 231         if self.index == self.rindex {
 232             return None;
 233         }
 234         let raw_index = raw_index(self.lo, self.elts.len(), self.index);
 235         self.index += 1;
 236         Some(self.elts[raw_index].get_ref())
 237     }
 238
 239     #[inline]
 240     fn size_hint(&self) -> (uint, Option<uint>) {
 241         let len = self.rindex - self.index;
 242         (len, Some(len))
 243     }
 244 }
 245
 246 impl<'a, T> DoubleEndedIterator<&'a T> for Items<'a, T> {
 247     #[inline]
 248     fn next_back(&mut self) -> Option<&'a T> {
 249         if self.index == self.rindex {
 250             return None;
 251         }
 252         self.rindex -= 1;
 253         let raw_index = raw_index(self.lo, self.elts.len(), self.rindex);
 254         Some(self.elts[raw_index].get_ref())
 255     }
 256 }
 257
 258 impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
 259
 260 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
 261     #[inline]
 262     fn indexable(&self) -> uint { self.rindex - self.index }
 263
 264     #[inline]
 265     fn idx(&mut self, j: uint) -> Option<&'a T> {
 266         if j >= self.indexable() {
 267             None
 268         } else {
 269             let raw_index = raw_index(self.lo, self.elts.len(), self.index + j);
 270             Some(self.elts[raw_index].get_ref())
 271         }
 272     }
 273 }
 274
 275 /// RingBuf mutable iterator
 276 pub struct MutItems<'a, T> {
 277     remaining1: &'a mut [Option<T>],
 278     remaining2: &'a mut [Option<T>],
 279     nelts: uint,
 280 }
 281
 282 impl<'a, T> Iterator<&'a mut T> for MutItems<'a, T> {
 283     #[inline]
 284     fn next(&mut self) -> Option<&'a mut T> {
 285         if self.nelts == 0 {
 286             return None;
 287         }
 288         let r = if self.remaining1.len() > 0 {
 289             &mut self.remaining1
 290         } else {
 291             assert!(self.remaining2.len() > 0);
 292             &mut self.remaining2
 293         };
 294         self.nelts -= 1;
 295         Some(r.mut_shift_ref().unwrap().get_mut_ref())
 296     }
 297
 298     #[inline]
 299     fn size_hint(&self) -> (uint, Option<uint>) {
 300         (self.nelts, Some(self.nelts))
 301     }
 302 }
 303
 304 impl<'a, T> DoubleEndedIterator<&'a mut T> for MutItems<'a, T> {
 305     #[inline]
 306     fn next_back(&mut self) -> Option<&'a mut T> {
 307         if self.nelts == 0 {
 308             return None;
 309         }
 310         let r = if self.remaining2.len() > 0 {
 311             &mut self.remaining2
 312         } else {
 313             assert!(self.remaining1.len() > 0);
 314             &mut self.remaining1
 315         };
 316         self.nelts -= 1;
 317         Some(r.mut_pop_ref().unwrap().get_mut_ref())
 318     }
 319 }
 320
 321 impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
 322
 323 /// Grow is only called on full elts, so nelts is also len(elts), unlike
 324 /// elsewhere.
 325 fn grow<T>(nelts: uint, loptr: &mut uint, elts: &mut Vec<Option<T>>) {
 326     assert_eq!(nelts, elts.len());
 327     let lo = *loptr;
 328     let newlen = nelts * 2;
 329     elts.reserve(newlen);
 330
 331     /* fill with None */
 332     for _ in range(elts.len(), elts.capacity()) {
 333         elts.push(None);
 334     }
 335
 336     /*
 337       Move the shortest half into the newly reserved area.
 338       lo ---->|
 339       nelts ----------->|
 340         [o o o|o o o o o]
 341       A [. . .|o o o o o o o o|. . . . .]
 342       B [o o o|. . . . . . . .|o o o o o]
 343      */
 344
 345     assert!(newlen - nelts/2 >= nelts);
 346     if lo <= (nelts - lo) { // A
 347         for i in range(0u, lo) {
 348             elts.as_mut_slice().swap(i, nelts + i);
 349         }
 350     } else {                // B
 351         for i in range(lo, nelts) {
 352             elts.as_mut_slice().swap(i, newlen - nelts + i);
 353         }
 354         *loptr += newlen - nelts;
 355     }
 356 }
 357
 358 /// Return index in underlying vec for a given logical element index
 359 fn raw_index(lo: uint, len: uint, index: uint) -> uint {
 360     if lo >= len - index {
 361         lo + index - len
 362     } else {
 363         lo + index
 364     }
 365 }
 366
 367 impl<A: PartialEq> PartialEq for RingBuf<A> {
 368     fn eq(&self, other: &RingBuf<A>) -> bool {
 369         self.nelts == other.nelts &&
 370             self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
 371     }
 372     fn ne(&self, other: &RingBuf<A>) -> bool {
 373         !self.eq(other)
 374     }
 375 }
 376
 377 impl<A> FromIterator<A> for RingBuf<A> {
 378     fn from_iter<T: Iterator<A>>(iterator: T) -> RingBuf<A> {
 379         let (lower, _) = iterator.size_hint();
 380         let mut deq = RingBuf::with_capacity(lower);
 381         deq.extend(iterator);
 382         deq
 383     }
 384 }
 385
 386 impl<A> Extendable<A> for RingBuf<A> {
 387     fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
 388         for elt in iterator {
 389             self.push_back(elt);
 390         }
 391     }
 392 }
 393
 394 #[cfg(test)]
 395 mod tests {
 396     extern crate test;
 397     use self::test::Bencher;
 398     use deque::Deque;
 399     use std::clone::Clone;
 400     use std::cmp::PartialEq;
 401     use std::fmt::Show;
 402     use super::RingBuf;
 403
 404     #[test]
 405     fn test_simple() {
 406         let mut d = RingBuf::new();
 407         assert_eq!(d.len(), 0u);
 408         d.push_front(17);
 409         d.push_front(42);
 410         d.push_back(137);
 411         assert_eq!(d.len(), 3u);
 412         d.push_back(137);
 413         assert_eq!(d.len(), 4u);
 414         debug!("{:?}", d.front());
 415         assert_eq!(*d.front().unwrap(), 42);
 416         debug!("{:?}", d.back());
 417         assert_eq!(*d.back().unwrap(), 137);
 418         let mut i = d.pop_front();
 419         debug!("{:?}", i);
 420         assert_eq!(i, Some(42));
 421         i = d.pop_back();
 422         debug!("{:?}", i);
 423         assert_eq!(i, Some(137));
 424         i = d.pop_back();
 425         debug!("{:?}", i);
 426         assert_eq!(i, Some(137));
 427         i = d.pop_back();
 428         debug!("{:?}", i);
 429         assert_eq!(i, Some(17));
 430         assert_eq!(d.len(), 0u);
 431         d.push_back(3);
 432         assert_eq!(d.len(), 1u);
 433         d.push_front(2);
 434         assert_eq!(d.len(), 2u);
 435         d.push_back(4);
 436         assert_eq!(d.len(), 3u);
 437         d.push_front(1);
 438         assert_eq!(d.len(), 4u);
 439         debug!("{:?}", d.get(0));
 440         debug!("{:?}", d.get(1));
 441         debug!("{:?}", d.get(2));
 442         debug!("{:?}", d.get(3));
 443         assert_eq!(*d.get(0), 1);
 444         assert_eq!(*d.get(1), 2);
 445         assert_eq!(*d.get(2), 3);
 446         assert_eq!(*d.get(3), 4);
 447     }
 448
 449     #[test]
 450     fn test_boxes() {
 451         let a: @int = @5;
 452         let b: @int = @72;
 453         let c: @int = @64;
 454         let d: @int = @175;
 455
 456         let mut deq = RingBuf::new();
 457         assert_eq!(deq.len(), 0);
 458         deq.push_front(a);
 459         deq.push_front(b);
 460         deq.push_back(c);
 461         assert_eq!(deq.len(), 3);
 462         deq.push_back(d);
 463         assert_eq!(deq.len(), 4);
 464         assert_eq!(deq.front(), Some(&b));
 465         assert_eq!(deq.back(), Some(&d));
 466         assert_eq!(deq.pop_front(), Some(b));
 467         assert_eq!(deq.pop_back(), Some(d));
 468         assert_eq!(deq.pop_back(), Some(c));
 469         assert_eq!(deq.pop_back(), Some(a));
 470         assert_eq!(deq.len(), 0);
 471         deq.push_back(c);
 472         assert_eq!(deq.len(), 1);
 473         deq.push_front(b);
 474         assert_eq!(deq.len(), 2);
 475         deq.push_back(d);
 476         assert_eq!(deq.len(), 3);
 477         deq.push_front(a);
 478         assert_eq!(deq.len(), 4);
 479         assert_eq!(*deq.get(0), a);
 480         assert_eq!(*deq.get(1), b);
 481         assert_eq!(*deq.get(2), c);
 482         assert_eq!(*deq.get(3), d);
 483     }
 484
 485     #[cfg(test)]
 486     fn test_parameterized<T:Clone + PartialEq + Show>(a: T, b: T, c: T, d: T) {
 487         let mut deq = RingBuf::new();
 488         assert_eq!(deq.len(), 0);
 489         deq.push_front(a.clone());
 490         deq.push_front(b.clone());
 491         deq.push_back(c.clone());
 492         assert_eq!(deq.len(), 3);
 493         deq.push_back(d.clone());
 494         assert_eq!(deq.len(), 4);
 495         assert_eq!((*deq.front().unwrap()).clone(), b.clone());
 496         assert_eq!((*deq.back().unwrap()).clone(), d.clone());
 497         assert_eq!(deq.pop_front().unwrap(), b.clone());
 498         assert_eq!(deq.pop_back().unwrap(), d.clone());
 499         assert_eq!(deq.pop_back().unwrap(), c.clone());
 500         assert_eq!(deq.pop_back().unwrap(), a.clone());
 501         assert_eq!(deq.len(), 0);
 502         deq.push_back(c.clone());
 503         assert_eq!(deq.len(), 1);
 504         deq.push_front(b.clone());
 505         assert_eq!(deq.len(), 2);
 506         deq.push_back(d.clone());
 507         assert_eq!(deq.len(), 3);
 508         deq.push_front(a.clone());
 509         assert_eq!(deq.len(), 4);
 510         assert_eq!((*deq.get(0)).clone(), a.clone());
 511         assert_eq!((*deq.get(1)).clone(), b.clone());
 512         assert_eq!((*deq.get(2)).clone(), c.clone());
 513         assert_eq!((*deq.get(3)).clone(), d.clone());
 514     }
 515
 516     #[test]
 517     fn test_push_front_grow() {
 518         let mut deq = RingBuf::new();
 519         for i in range(0u, 66) {
 520             deq.push_front(i);
 521         }
 522         assert_eq!(deq.len(), 66);
 523
 524         for i in range(0u, 66) {
 525             assert_eq!(*deq.get(i), 65 - i);
 526         }
 527
 528         let mut deq = RingBuf::new();
 529         for i in range(0u, 66) {
 530             deq.push_back(i);
 531         }
 532
 533         for i in range(0u, 66) {
 534             assert_eq!(*deq.get(i), i);
 535         }
 536     }
 537
 538     #[bench]
 539     fn bench_new(b: &mut test::Bencher) {
 540         b.iter(|| {
 541             let _: RingBuf<u64> = RingBuf::new();
 542         })
 543     }
 544
 545     #[bench]
 546     fn bench_push_back(b: &mut test::Bencher) {
 547         let mut deq = RingBuf::new();
 548         b.iter(|| {
 549             deq.push_back(0);
 550         })
 551     }
 552
 553     #[bench]
 554     fn bench_push_front(b: &mut test::Bencher) {
 555         let mut deq = RingBuf::new();
 556         b.iter(|| {
 557             deq.push_front(0);
 558         })
 559     }
 560
 561     #[bench]
 562     fn bench_grow(b: &mut test::Bencher) {
 563         let mut deq = RingBuf::new();
 564         b.iter(|| {
 565             for _ in range(0, 65) {
 566                 deq.push_front(1);
 567             }
 568         })
 569     }
 570
 571     #[deriving(Clone, PartialEq, Show)]
 572     enum Taggy {
 573         One(int),
 574         Two(int, int),
 575         Three(int, int, int),
 576     }
 577
 578     #[deriving(Clone, PartialEq, Show)]
 579     enum Taggypar<T> {
 580         Onepar(int),
 581         Twopar(int, int),
 582         Threepar(int, int, int),
 583     }
 584
 585     #[deriving(Clone, PartialEq, Show)]
 586     struct RecCy {
 587         x: int,
 588         y: int,
 589         t: Taggy
 590     }
 591
 592     #[test]
 593     fn test_param_int() {
 594         test_parameterized::<int>(5, 72, 64, 175);
 595     }
 596
 597     #[test]
 598     fn test_param_at_int() {
 599         test_parameterized::<@int>(@5, @72, @64, @175);
 600     }
 601
 602     #[test]
 603     fn test_param_taggy() {
 604         test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
 605     }
 606
 607     #[test]
 608     fn test_param_taggypar() {
 609         test_parameterized::<Taggypar<int>>(Onepar::<int>(1),
 610                                             Twopar::<int>(1, 2),
 611                                             Threepar::<int>(1, 2, 3),
 612                                             Twopar::<int>(17, 42));
 613     }
 614
 615     #[test]
 616     fn test_param_reccy() {
 617         let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
 618         let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
 619         let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
 620         let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
 621         test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
 622     }
 623
 624     #[test]
 625     fn test_with_capacity() {
 626         let mut d = RingBuf::with_capacity(0);
 627         d.push_back(1);
 628         assert_eq!(d.len(), 1);
 629         let mut d = RingBuf::with_capacity(50);
 630         d.push_back(1);
 631         assert_eq!(d.len(), 1);
 632     }
 633
 634     #[test]
 635     fn test_reserve_exact() {
 636         let mut d = RingBuf::new();
 637         d.push_back(0u64);
 638         d.reserve_exact(50);
 639         assert_eq!(d.elts.capacity(), 50);
 640         let mut d = RingBuf::new();
 641         d.push_back(0u32);
 642         d.reserve_exact(50);
 643         assert_eq!(d.elts.capacity(), 50);
 644     }
 645
 646     #[test]
 647     fn test_reserve() {
 648         let mut d = RingBuf::new();
 649         d.push_back(0u64);
 650         d.reserve(50);
 651         assert_eq!(d.elts.capacity(), 64);
 652         let mut d = RingBuf::new();
 653         d.push_back(0u32);
 654         d.reserve(50);
 655         assert_eq!(d.elts.capacity(), 64);
 656     }
 657
 658     #[test]
 659     fn test_swap() {
 660         let mut d: RingBuf<int> = range(0, 5).collect();
 661         d.pop_front();
 662         d.swap(0, 3);
 663         assert_eq!(d.iter().map(|&x|x).collect::<Vec<int>>(), vec!(4, 2, 3, 1));
 664     }
 665
 666     #[test]
 667     fn test_iter() {
 668         let mut d = RingBuf::new();
 669         assert_eq!(d.iter().next(), None);
 670         assert_eq!(d.iter().size_hint(), (0, Some(0)));
 671
 672         for i in range(0, 5) {
 673             d.push_back(i);
 674         }
 675         assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), &[&0,&1,&2,&3,&4]);
 676
 677         for i in range(6, 9) {
 678             d.push_front(i);
 679         }
 680         assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), &[&8,&7,&6,&0,&1,&2,&3,&4]);
 681
 682         let mut it = d.iter();
 683         let mut len = d.len();
 684         loop {
 685             match it.next() {
 686                 None => break,
 687                 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
 688             }
 689         }
 690     }
 691
 692     #[test]
 693     fn test_rev_iter() {
 694         let mut d = RingBuf::new();
 695         assert_eq!(d.iter().rev().next(), None);
 696
 697         for i in range(0, 5) {
 698             d.push_back(i);
 699         }
 700         assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), &[&4,&3,&2,&1,&0]);
 701
 702         for i in range(6, 9) {
 703             d.push_front(i);
 704         }
 705         assert_eq!(d.iter().rev().collect::<Vec<&int>>().as_slice(), &[&4,&3,&2,&1,&0,&6,&7,&8]);
 706     }
 707
 708     #[test]
 709     fn test_mut_rev_iter_wrap() {
 710         let mut d = RingBuf::with_capacity(3);
 711         assert!(d.mut_iter().rev().next().is_none());
 712
 713         d.push_back(1);
 714         d.push_back(2);
 715         d.push_back(3);
 716         assert_eq!(d.pop_front(), Some(1));
 717         d.push_back(4);
 718
 719         assert_eq!(d.mut_iter().rev().map(|x| *x).collect::<Vec<int>>(),
 720                    vec!(4, 3, 2));
 721     }
 722
 723     #[test]
 724     fn test_mut_iter() {
 725         let mut d = RingBuf::new();
 726         assert!(d.mut_iter().next().is_none());
 727
 728         for i in range(0u, 3) {
 729             d.push_front(i);
 730         }
 731
 732         for (i, elt) in d.mut_iter().enumerate() {
 733             assert_eq!(*elt, 2 - i);
 734             *elt = i;
 735         }
 736
 737         {
 738             let mut it = d.mut_iter();
 739             assert_eq!(*it.next().unwrap(), 0);
 740             assert_eq!(*it.next().unwrap(), 1);
 741             assert_eq!(*it.next().unwrap(), 2);
 742             assert!(it.next().is_none());
 743         }
 744     }
 745
 746     #[test]
 747     fn test_mut_rev_iter() {
 748         let mut d = RingBuf::new();
 749         assert!(d.mut_iter().rev().next().is_none());
 750
 751         for i in range(0u, 3) {
 752             d.push_front(i);
 753         }
 754
 755         for (i, elt) in d.mut_iter().rev().enumerate() {
 756             assert_eq!(*elt, i);
 757             *elt = i;
 758         }
 759
 760         {
 761             let mut it = d.mut_iter().rev();
 762             assert_eq!(*it.next().unwrap(), 0);
 763             assert_eq!(*it.next().unwrap(), 1);
 764             assert_eq!(*it.next().unwrap(), 2);
 765             assert!(it.next().is_none());
 766         }
 767     }
 768
 769     #[test]
 770     fn test_from_iter() {
 771         use std::iter;
 772         let v = vec!(1,2,3,4,5,6,7);
 773         let deq: RingBuf<int> = v.iter().map(|&x| x).collect();
 774         let u: Vec<int> = deq.iter().map(|&x| x).collect();
 775         assert_eq!(u, v);
 776
 777         let mut seq = iter::count(0u, 2).take(256);
 778         let deq: RingBuf<uint> = seq.collect();
 779         for (i, &x) in deq.iter().enumerate() {
 780             assert_eq!(2*i, x);
 781         }
 782         assert_eq!(deq.len(), 256);
 783     }
 784
 785     #[test]
 786     fn test_clone() {
 787         let mut d = RingBuf::new();
 788         d.push_front(17);
 789         d.push_front(42);
 790         d.push_back(137);
 791         d.push_back(137);
 792         assert_eq!(d.len(), 4u);
 793         let mut e = d.clone();
 794         assert_eq!(e.len(), 4u);
 795         while !d.is_empty() {
 796             assert_eq!(d.pop_back(), e.pop_back());
 797         }
 798         assert_eq!(d.len(), 0u);
 799         assert_eq!(e.len(), 0u);
 800     }
 801
 802     #[test]
 803     fn test_eq() {
 804         let mut d = RingBuf::new();
 805         assert!(d == RingBuf::with_capacity(0));
 806         d.push_front(137);
 807         d.push_front(17);
 808         d.push_front(42);
 809         d.push_back(137);
 810         let mut e = RingBuf::with_capacity(0);
 811         e.push_back(42);
 812         e.push_back(17);
 813         e.push_back(137);
 814         e.push_back(137);
 815         assert!(&e == &d);
 816         e.pop_back();
 817         e.push_back(0);
 818         assert!(e != d);
 819         e.clear();
 820         assert!(e == RingBuf::new());
 821     }
 822 }