src/libcollections/ringbuf.rs

   1 // Copyright 2012-2013 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::{Rev, 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     /// Back-to-front iterator.
 194     pub fn rev_iter<'a>(&'a self) -> Rev<Items<'a, T>> {
 195         self.iter().rev()
 196     }
 197
 198     /// Front-to-back iterator which returns mutable values.
 199     pub fn mut_iter<'a>(&'a mut self) -> MutItems<'a, T> {
 200         let start_index = raw_index(self.lo, self.elts.len(), 0);
 201         let end_index = raw_index(self.lo, self.elts.len(), self.nelts);
 202
 203         // Divide up the array
 204         if end_index <= start_index {
 205             // Items to iterate goes from:
 206             //    start_index to self.elts.len()
 207             // and then
 208             //    0 to end_index
 209             let (temp, remaining1) = self.elts.mut_split_at(start_index);
 210             let (remaining2, _) = temp.mut_split_at(end_index);
 211             MutItems { remaining1: remaining1,
 212                                  remaining2: remaining2,
 213                                  nelts: self.nelts }
 214         } else {
 215             // Items to iterate goes from start_index to end_index:
 216             let (empty, elts) = self.elts.mut_split_at(0);
 217             let remaining1 = elts.mut_slice(start_index, end_index);
 218             MutItems { remaining1: remaining1,
 219                                  remaining2: empty,
 220                                  nelts: self.nelts }
 221         }
 222     }
 223
 224     /// Back-to-front iterator which returns mutable values.
 225     pub fn mut_rev_iter<'a>(&'a mut self) -> Rev<MutItems<'a, T>> {
 226         self.mut_iter().rev()
 227     }
 228 }
 229
 230 /// RingBuf iterator
 231 pub struct Items<'a, T> {
 232     lo: uint,
 233     index: uint,
 234     rindex: uint,
 235     elts: &'a [Option<T>],
 236 }
 237
 238 impl<'a, T> Iterator<&'a T> for Items<'a, T> {
 239     #[inline]
 240     fn next(&mut self) -> Option<&'a T> {
 241         if self.index == self.rindex {
 242             return None;
 243         }
 244         let raw_index = raw_index(self.lo, self.elts.len(), self.index);
 245         self.index += 1;
 246         Some(self.elts[raw_index].get_ref())
 247     }
 248
 249     #[inline]
 250     fn size_hint(&self) -> (uint, Option<uint>) {
 251         let len = self.rindex - self.index;
 252         (len, Some(len))
 253     }
 254 }
 255
 256 impl<'a, T> DoubleEndedIterator<&'a T> for Items<'a, T> {
 257     #[inline]
 258     fn next_back(&mut self) -> Option<&'a T> {
 259         if self.index == self.rindex {
 260             return None;
 261         }
 262         self.rindex -= 1;
 263         let raw_index = raw_index(self.lo, self.elts.len(), self.rindex);
 264         Some(self.elts[raw_index].get_ref())
 265     }
 266 }
 267
 268 impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
 269
 270 impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
 271     #[inline]
 272     fn indexable(&self) -> uint { self.rindex - self.index }
 273
 274     #[inline]
 275     fn idx(&mut self, j: uint) -> Option<&'a T> {
 276         if j >= self.indexable() {
 277             None
 278         } else {
 279             let raw_index = raw_index(self.lo, self.elts.len(), self.index + j);
 280             Some(self.elts[raw_index].get_ref())
 281         }
 282     }
 283 }
 284
 285 /// RingBuf mutable iterator
 286 pub struct MutItems<'a, T> {
 287     remaining1: &'a mut [Option<T>],
 288     remaining2: &'a mut [Option<T>],
 289     nelts: uint,
 290 }
 291
 292 impl<'a, T> Iterator<&'a mut T> for MutItems<'a, T> {
 293     #[inline]
 294     fn next(&mut self) -> Option<&'a mut T> {
 295         if self.nelts == 0 {
 296             return None;
 297         }
 298         let r = if self.remaining1.len() > 0 {
 299             &mut self.remaining1
 300         } else {
 301             assert!(self.remaining2.len() > 0);
 302             &mut self.remaining2
 303         };
 304         self.nelts -= 1;
 305         Some(r.mut_shift_ref().unwrap().get_mut_ref())
 306     }
 307
 308     #[inline]
 309     fn size_hint(&self) -> (uint, Option<uint>) {
 310         (self.nelts, Some(self.nelts))
 311     }
 312 }
 313
 314 impl<'a, T> DoubleEndedIterator<&'a mut T> for MutItems<'a, T> {
 315     #[inline]
 316     fn next_back(&mut self) -> Option<&'a mut T> {
 317         if self.nelts == 0 {
 318             return None;
 319         }
 320         let r = if self.remaining2.len() > 0 {
 321             &mut self.remaining2
 322         } else {
 323             assert!(self.remaining1.len() > 0);
 324             &mut self.remaining1
 325         };
 326         self.nelts -= 1;
 327         Some(r.mut_pop_ref().unwrap().get_mut_ref())
 328     }
 329 }
 330
 331 impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
 332
 333 /// Grow is only called on full elts, so nelts is also len(elts), unlike
 334 /// elsewhere.
 335 fn grow<T>(nelts: uint, loptr: &mut uint, elts: &mut Vec<Option<T>>) {
 336     assert_eq!(nelts, elts.len());
 337     let lo = *loptr;
 338     let newlen = nelts * 2;
 339     elts.reserve(newlen);
 340
 341     /* fill with None */
 342     for _ in range(elts.len(), elts.capacity()) {
 343         elts.push(None);
 344     }
 345
 346     /*
 347       Move the shortest half into the newly reserved area.
 348       lo ---->|
 349       nelts ----------->|
 350         [o o o|o o o o o]
 351       A [. . .|o o o o o o o o|. . . . .]
 352       B [o o o|. . . . . . . .|o o o o o]
 353      */
 354
 355     assert!(newlen - nelts/2 >= nelts);
 356     if lo <= (nelts - lo) { // A
 357         for i in range(0u, lo) {
 358             elts.as_mut_slice().swap(i, nelts + i);
 359         }
 360     } else {                // B
 361         for i in range(lo, nelts) {
 362             elts.as_mut_slice().swap(i, newlen - nelts + i);
 363         }
 364         *loptr += newlen - nelts;
 365     }
 366 }
 367
 368 /// Return index in underlying vec for a given logical element index
 369 fn raw_index(lo: uint, len: uint, index: uint) -> uint {
 370     if lo >= len - index {
 371         lo + index - len
 372     } else {
 373         lo + index
 374     }
 375 }
 376
 377 impl<A: Eq> Eq for RingBuf<A> {
 378     fn eq(&self, other: &RingBuf<A>) -> bool {
 379         self.nelts == other.nelts &&
 380             self.iter().zip(other.iter()).all(|(a, b)| a.eq(b))
 381     }
 382     fn ne(&self, other: &RingBuf<A>) -> bool {
 383         !self.eq(other)
 384     }
 385 }
 386
 387 impl<A> FromIterator<A> for RingBuf<A> {
 388     fn from_iter<T: Iterator<A>>(iterator: T) -> RingBuf<A> {
 389         let (lower, _) = iterator.size_hint();
 390         let mut deq = RingBuf::with_capacity(lower);
 391         deq.extend(iterator);
 392         deq
 393     }
 394 }
 395
 396 impl<A> Extendable<A> for RingBuf<A> {
 397     fn extend<T: Iterator<A>>(&mut self, mut iterator: T) {
 398         for elt in iterator {
 399             self.push_back(elt);
 400         }
 401     }
 402 }
 403
 404 #[cfg(test)]
 405 mod tests {
 406     extern crate test;
 407     use self::test::Bencher;
 408     use deque::Deque;
 409     use std::clone::Clone;
 410     use std::cmp::Eq;
 411     use std::fmt::Show;
 412     use super::RingBuf;
 413
 414     #[test]
 415     fn test_simple() {
 416         let mut d = RingBuf::new();
 417         assert_eq!(d.len(), 0u);
 418         d.push_front(17);
 419         d.push_front(42);
 420         d.push_back(137);
 421         assert_eq!(d.len(), 3u);
 422         d.push_back(137);
 423         assert_eq!(d.len(), 4u);
 424         debug!("{:?}", d.front());
 425         assert_eq!(*d.front().unwrap(), 42);
 426         debug!("{:?}", d.back());
 427         assert_eq!(*d.back().unwrap(), 137);
 428         let mut i = d.pop_front();
 429         debug!("{:?}", i);
 430         assert_eq!(i, Some(42));
 431         i = d.pop_back();
 432         debug!("{:?}", i);
 433         assert_eq!(i, Some(137));
 434         i = d.pop_back();
 435         debug!("{:?}", i);
 436         assert_eq!(i, Some(137));
 437         i = d.pop_back();
 438         debug!("{:?}", i);
 439         assert_eq!(i, Some(17));
 440         assert_eq!(d.len(), 0u);
 441         d.push_back(3);
 442         assert_eq!(d.len(), 1u);
 443         d.push_front(2);
 444         assert_eq!(d.len(), 2u);
 445         d.push_back(4);
 446         assert_eq!(d.len(), 3u);
 447         d.push_front(1);
 448         assert_eq!(d.len(), 4u);
 449         debug!("{:?}", d.get(0));
 450         debug!("{:?}", d.get(1));
 451         debug!("{:?}", d.get(2));
 452         debug!("{:?}", d.get(3));
 453         assert_eq!(*d.get(0), 1);
 454         assert_eq!(*d.get(1), 2);
 455         assert_eq!(*d.get(2), 3);
 456         assert_eq!(*d.get(3), 4);
 457     }
 458
 459     #[test]
 460     fn test_boxes() {
 461         let a: @int = @5;
 462         let b: @int = @72;
 463         let c: @int = @64;
 464         let d: @int = @175;
 465
 466         let mut deq = RingBuf::new();
 467         assert_eq!(deq.len(), 0);
 468         deq.push_front(a);
 469         deq.push_front(b);
 470         deq.push_back(c);
 471         assert_eq!(deq.len(), 3);
 472         deq.push_back(d);
 473         assert_eq!(deq.len(), 4);
 474         assert_eq!(deq.front(), Some(&b));
 475         assert_eq!(deq.back(), Some(&d));
 476         assert_eq!(deq.pop_front(), Some(b));
 477         assert_eq!(deq.pop_back(), Some(d));
 478         assert_eq!(deq.pop_back(), Some(c));
 479         assert_eq!(deq.pop_back(), Some(a));
 480         assert_eq!(deq.len(), 0);
 481         deq.push_back(c);
 482         assert_eq!(deq.len(), 1);
 483         deq.push_front(b);
 484         assert_eq!(deq.len(), 2);
 485         deq.push_back(d);
 486         assert_eq!(deq.len(), 3);
 487         deq.push_front(a);
 488         assert_eq!(deq.len(), 4);
 489         assert_eq!(*deq.get(0), a);
 490         assert_eq!(*deq.get(1), b);
 491         assert_eq!(*deq.get(2), c);
 492         assert_eq!(*deq.get(3), d);
 493     }
 494
 495     #[cfg(test)]
 496     fn test_parameterized<T:Clone + Eq + Show>(a: T, b: T, c: T, d: T) {
 497         let mut deq = RingBuf::new();
 498         assert_eq!(deq.len(), 0);
 499         deq.push_front(a.clone());
 500         deq.push_front(b.clone());
 501         deq.push_back(c.clone());
 502         assert_eq!(deq.len(), 3);
 503         deq.push_back(d.clone());
 504         assert_eq!(deq.len(), 4);
 505         assert_eq!((*deq.front().unwrap()).clone(), b.clone());
 506         assert_eq!((*deq.back().unwrap()).clone(), d.clone());
 507         assert_eq!(deq.pop_front().unwrap(), b.clone());
 508         assert_eq!(deq.pop_back().unwrap(), d.clone());
 509         assert_eq!(deq.pop_back().unwrap(), c.clone());
 510         assert_eq!(deq.pop_back().unwrap(), a.clone());
 511         assert_eq!(deq.len(), 0);
 512         deq.push_back(c.clone());
 513         assert_eq!(deq.len(), 1);
 514         deq.push_front(b.clone());
 515         assert_eq!(deq.len(), 2);
 516         deq.push_back(d.clone());
 517         assert_eq!(deq.len(), 3);
 518         deq.push_front(a.clone());
 519         assert_eq!(deq.len(), 4);
 520         assert_eq!((*deq.get(0)).clone(), a.clone());
 521         assert_eq!((*deq.get(1)).clone(), b.clone());
 522         assert_eq!((*deq.get(2)).clone(), c.clone());
 523         assert_eq!((*deq.get(3)).clone(), d.clone());
 524     }
 525
 526     #[test]
 527     fn test_push_front_grow() {
 528         let mut deq = RingBuf::new();
 529         for i in range(0u, 66) {
 530             deq.push_front(i);
 531         }
 532         assert_eq!(deq.len(), 66);
 533
 534         for i in range(0u, 66) {
 535             assert_eq!(*deq.get(i), 65 - i);
 536         }
 537
 538         let mut deq = RingBuf::new();
 539         for i in range(0u, 66) {
 540             deq.push_back(i);
 541         }
 542
 543         for i in range(0u, 66) {
 544             assert_eq!(*deq.get(i), i);
 545         }
 546     }
 547
 548     #[bench]
 549     fn bench_new(b: &mut test::Bencher) {
 550         b.iter(|| {
 551             let _: RingBuf<u64> = RingBuf::new();
 552         })
 553     }
 554
 555     #[bench]
 556     fn bench_push_back(b: &mut test::Bencher) {
 557         let mut deq = RingBuf::new();
 558         b.iter(|| {
 559             deq.push_back(0);
 560         })
 561     }
 562
 563     #[bench]
 564     fn bench_push_front(b: &mut test::Bencher) {
 565         let mut deq = RingBuf::new();
 566         b.iter(|| {
 567             deq.push_front(0);
 568         })
 569     }
 570
 571     #[bench]
 572     fn bench_grow(b: &mut test::Bencher) {
 573         let mut deq = RingBuf::new();
 574         b.iter(|| {
 575             for _ in range(0, 65) {
 576                 deq.push_front(1);
 577             }
 578         })
 579     }
 580
 581     #[deriving(Clone, Eq, Show)]
 582     enum Taggy {
 583         One(int),
 584         Two(int, int),
 585         Three(int, int, int),
 586     }
 587
 588     #[deriving(Clone, Eq, Show)]
 589     enum Taggypar<T> {
 590         Onepar(int),
 591         Twopar(int, int),
 592         Threepar(int, int, int),
 593     }
 594
 595     #[deriving(Clone, Eq, Show)]
 596     struct RecCy {
 597         x: int,
 598         y: int,
 599         t: Taggy
 600     }
 601
 602     #[test]
 603     fn test_param_int() {
 604         test_parameterized::<int>(5, 72, 64, 175);
 605     }
 606
 607     #[test]
 608     fn test_param_at_int() {
 609         test_parameterized::<@int>(@5, @72, @64, @175);
 610     }
 611
 612     #[test]
 613     fn test_param_taggy() {
 614         test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
 615     }
 616
 617     #[test]
 618     fn test_param_taggypar() {
 619         test_parameterized::<Taggypar<int>>(Onepar::<int>(1),
 620                                             Twopar::<int>(1, 2),
 621                                             Threepar::<int>(1, 2, 3),
 622                                             Twopar::<int>(17, 42));
 623     }
 624
 625     #[test]
 626     fn test_param_reccy() {
 627         let reccy1 = RecCy { x: 1, y: 2, t: One(1) };
 628         let reccy2 = RecCy { x: 345, y: 2, t: Two(1, 2) };
 629         let reccy3 = RecCy { x: 1, y: 777, t: Three(1, 2, 3) };
 630         let reccy4 = RecCy { x: 19, y: 252, t: Two(17, 42) };
 631         test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
 632     }
 633
 634     #[test]
 635     fn test_with_capacity() {
 636         let mut d = RingBuf::with_capacity(0);
 637         d.push_back(1);
 638         assert_eq!(d.len(), 1);
 639         let mut d = RingBuf::with_capacity(50);
 640         d.push_back(1);
 641         assert_eq!(d.len(), 1);
 642     }
 643
 644     #[test]
 645     fn test_reserve_exact() {
 646         let mut d = RingBuf::new();
 647         d.push_back(0u64);
 648         d.reserve_exact(50);
 649         assert_eq!(d.elts.capacity(), 50);
 650         let mut d = RingBuf::new();
 651         d.push_back(0u32);
 652         d.reserve_exact(50);
 653         assert_eq!(d.elts.capacity(), 50);
 654     }
 655
 656     #[test]
 657     fn test_reserve() {
 658         let mut d = RingBuf::new();
 659         d.push_back(0u64);
 660         d.reserve(50);
 661         assert_eq!(d.elts.capacity(), 64);
 662         let mut d = RingBuf::new();
 663         d.push_back(0u32);
 664         d.reserve(50);
 665         assert_eq!(d.elts.capacity(), 64);
 666     }
 667
 668     #[test]
 669     fn test_swap() {
 670         let mut d: RingBuf<int> = range(0, 5).collect();
 671         d.pop_front();
 672         d.swap(0, 3);
 673         assert_eq!(d.iter().map(|&x|x).collect::<Vec<int>>(), vec!(4, 2, 3, 1));
 674     }
 675
 676     #[test]
 677     fn test_iter() {
 678         let mut d = RingBuf::new();
 679         assert_eq!(d.iter().next(), None);
 680         assert_eq!(d.iter().size_hint(), (0, Some(0)));
 681
 682         for i in range(0, 5) {
 683             d.push_back(i);
 684         }
 685         assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), &[&0,&1,&2,&3,&4]);
 686
 687         for i in range(6, 9) {
 688             d.push_front(i);
 689         }
 690         assert_eq!(d.iter().collect::<Vec<&int>>().as_slice(), &[&8,&7,&6,&0,&1,&2,&3,&4]);
 691
 692         let mut it = d.iter();
 693         let mut len = d.len();
 694         loop {
 695             match it.next() {
 696                 None => break,
 697                 _ => { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
 698             }
 699         }
 700     }
 701
 702     #[test]
 703     fn test_rev_iter() {
 704         let mut d = RingBuf::new();
 705         assert_eq!(d.rev_iter().next(), None);
 706
 707         for i in range(0, 5) {
 708             d.push_back(i);
 709         }
 710         assert_eq!(d.rev_iter().collect::<Vec<&int>>().as_slice(), &[&4,&3,&2,&1,&0]);
 711
 712         for i in range(6, 9) {
 713             d.push_front(i);
 714         }
 715         assert_eq!(d.rev_iter().collect::<Vec<&int>>().as_slice(), &[&4,&3,&2,&1,&0,&6,&7,&8]);
 716     }
 717
 718     #[test]
 719     fn test_mut_rev_iter_wrap() {
 720         let mut d = RingBuf::with_capacity(3);
 721         assert!(d.mut_rev_iter().next().is_none());
 722
 723         d.push_back(1);
 724         d.push_back(2);
 725         d.push_back(3);
 726         assert_eq!(d.pop_front(), Some(1));
 727         d.push_back(4);
 728
 729         assert_eq!(d.mut_rev_iter().map(|x| *x).collect::<Vec<int>>(),
 730                    vec!(4, 3, 2));
 731     }
 732
 733     #[test]
 734     fn test_mut_iter() {
 735         let mut d = RingBuf::new();
 736         assert!(d.mut_iter().next().is_none());
 737
 738         for i in range(0u, 3) {
 739             d.push_front(i);
 740         }
 741
 742         for (i, elt) in d.mut_iter().enumerate() {
 743             assert_eq!(*elt, 2 - i);
 744             *elt = i;
 745         }
 746
 747         {
 748             let mut it = d.mut_iter();
 749             assert_eq!(*it.next().unwrap(), 0);
 750             assert_eq!(*it.next().unwrap(), 1);
 751             assert_eq!(*it.next().unwrap(), 2);
 752             assert!(it.next().is_none());
 753         }
 754     }
 755
 756     #[test]
 757     fn test_mut_rev_iter() {
 758         let mut d = RingBuf::new();
 759         assert!(d.mut_rev_iter().next().is_none());
 760
 761         for i in range(0u, 3) {
 762             d.push_front(i);
 763         }
 764
 765         for (i, elt) in d.mut_rev_iter().enumerate() {
 766             assert_eq!(*elt, i);
 767             *elt = i;
 768         }
 769
 770         {
 771             let mut it = d.mut_rev_iter();
 772             assert_eq!(*it.next().unwrap(), 0);
 773             assert_eq!(*it.next().unwrap(), 1);
 774             assert_eq!(*it.next().unwrap(), 2);
 775             assert!(it.next().is_none());
 776         }
 777     }
 778
 779     #[test]
 780     fn test_from_iter() {
 781         use std::iter;
 782         let v = vec!(1,2,3,4,5,6,7);
 783         let deq: RingBuf<int> = v.iter().map(|&x| x).collect();
 784         let u: Vec<int> = deq.iter().map(|&x| x).collect();
 785         assert_eq!(u, v);
 786
 787         let mut seq = iter::count(0u, 2).take(256);
 788         let deq: RingBuf<uint> = seq.collect();
 789         for (i, &x) in deq.iter().enumerate() {
 790             assert_eq!(2*i, x);
 791         }
 792         assert_eq!(deq.len(), 256);
 793     }
 794
 795     #[test]
 796     fn test_clone() {
 797         let mut d = RingBuf::new();
 798         d.push_front(17);
 799         d.push_front(42);
 800         d.push_back(137);
 801         d.push_back(137);
 802         assert_eq!(d.len(), 4u);
 803         let mut e = d.clone();
 804         assert_eq!(e.len(), 4u);
 805         while !d.is_empty() {
 806             assert_eq!(d.pop_back(), e.pop_back());
 807         }
 808         assert_eq!(d.len(), 0u);
 809         assert_eq!(e.len(), 0u);
 810     }
 811
 812     #[test]
 813     fn test_eq() {
 814         let mut d = RingBuf::new();
 815         assert!(d == RingBuf::with_capacity(0));
 816         d.push_front(137);
 817         d.push_front(17);
 818         d.push_front(42);
 819         d.push_back(137);
 820         let mut e = RingBuf::with_capacity(0);
 821         e.push_back(42);
 822         e.push_back(17);
 823         e.push_back(137);
 824         e.push_back(137);
 825         assert!(&e == &d);
 826         e.pop_back();
 827         e.push_back(0);
 828         assert!(e != d);
 829         e.clear();
 830         assert!(e == RingBuf::new());
 831     }
 832 }