(index<- ) ./libcore/iter.rs

 git branch: * master 5200215 auto merge of #14035 : alexcrichton/rust/experimental, r=huonw
 modified: Fri May 9 13:02:28 2014

1 // Copyright 2013-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 /*!
 12
 13 Composable external iterators
 14
 15 # The `Iterator` trait
 16
 17 This module defines Rust's core iteration trait. The `Iterator` trait has one
 18 unimplemented method, `next`. All other methods are derived through default
 19 methods to perform operations such as `zip`, `chain`, `enumerate`, and `fold`.
 20
 21 The goal of this module is to unify iteration across all containers in Rust.
 22 An iterator can be considered as a state machine which is used to track which
 23 element will be yielded next.
 24
 25 There are various extensions also defined in this module to assist with various
 26 types of iteration, such as the `DoubleEndedIterator` for iterating in reverse,
 27 the `FromIterator` trait for creating a container from an iterator, and much
 28 more.
 29
 30 ## Rust's `for` loop
 31
 32 The special syntax used by rust's `for` loop is based around the `Iterator`
 33 trait defined in this module. For loops can be viewed as a syntactical expansion
 34 into a `loop`, for example, the `for` loop in this example is essentially
 35 translated to the `loop` below.
 36
 37 ```rust
 38 let values = ~[1, 2, 3];
 39
 40 // "Syntactical sugar" taking advantage of an iterator
 41 for &x in values.iter() {
 42 println!("{}", x);
 43 }
 44
 45 // Rough translation of the iteration without a `for` iterator.
 46 let mut it = values.iter();
 47 loop {
 48 match it.next() {
 49 Some(&x) => {
 50 println!("{}", x);
 51 }
 52 None => { break }
 53 }
 54 }
 55 ```
 56
 57 This `for` loop syntax can be applied to any iterator over any type.
 58
 59 ## Iteration protocol and more
 60
 61 More detailed information about iterators can be found in the [container
 62 guide](http://static.rust-lang.org/doc/master/guide-container.html) with
 63 the rest of the rust manuals.
 64
 65 */
 66
 67 use cmp;
 68 use num::{Zero, One, CheckedAdd, CheckedSub, Saturating, ToPrimitive, Int};
 69 use option::{Option, Some, None};
 70 use ops::{Add, Mul, Sub};
 71 use cmp::{Eq, Ord, TotalOrd};
 72 use clone::Clone;
 73 use uint;
 74 use mem;
 75
 76 /// Conversion from an `Iterator`
 77 pub trait FromIterator<A> {
 78 /// Build a container with elements from an external iterator.
 79 fn from_iter<T: Iterator<A>>(iterator: T) -> Self;
 80 }
 81
 82 /// A type growable from an `Iterator` implementation
 83 pub trait Extendable<A>: FromIterator<A> {
 84 /// Extend a container with the elements yielded by an iterator
 85 fn extend<T: Iterator<A>>(&mut self, iterator: T);
 86 }
 87
 88 /// An interface for dealing with "external iterators". These types of iterators
 89 /// can be resumed at any time as all state is stored internally as opposed to
 90 /// being located on the call stack.
 91 ///
 92 /// The Iterator protocol states that an iterator yields a (potentially-empty,
 93 /// potentially-infinite) sequence of values, and returns `None` to signal that
 94 /// it's finished. The Iterator protocol does not define behavior after `None`
 95 /// is returned. A concrete Iterator implementation may choose to behave however
 96 /// it wishes, either by returning `None` infinitely, or by doing something
 97 /// else.
 98 pub trait Iterator<A> {
 99 /// Advance the iterator and return the next value. Return `None` when the end is reached.
 100 fn next(&mut self) -> Option<A>;
 101
 102 /// Return a lower bound and upper bound on the remaining length of the iterator.
 103 ///
 104 /// The common use case for the estimate is pre-allocating space to store the results.
 105 #[inline]
 106 fn size_hint(&self) -> (uint, Option<uint>) { (0, None) }
 107
 108 /// Chain this iterator with another, returning a new iterator which will
 109 /// finish iterating over the current iterator, and then it will iterate
 110 /// over the other specified iterator.
 111 ///
 112 /// # Example
 113 ///
 114 /// ```rust
 115 /// let a = [0];
 116 /// let b = [1];
 117 /// let mut it = a.iter().chain(b.iter());
 118 /// assert_eq!(it.next().unwrap(), &0);
 119 /// assert_eq!(it.next().unwrap(), &1);
 120 /// assert!(it.next().is_none());
 121 /// ```
 122 #[inline]
 123 fn chain<U: Iterator<A>>(self, other: U) -> Chain<Self, U> {
 124 Chain{a: self, b: other, flag: false}
 125 }
 126
 127 /// Creates an iterator which iterates over both this and the specified
 128 /// iterators simultaneously, yielding the two elements as pairs. When
 129 /// either iterator returns None, all further invocations of next() will
 130 /// return None.
 131 ///
 132 /// # Example
 133 ///
 134 /// ```rust
 135 /// let a = [0];
 136 /// let b = [1];
 137 /// let mut it = a.iter().zip(b.iter());
 138 /// assert_eq!(it.next().unwrap(), (&0, &1));
 139 /// assert!(it.next().is_none());
 140 /// ```
 141 #[inline]
 142 fn zip<B, U: Iterator>(self, other: U) -> Zip<Self, U> {
 143 Zip{a: self, b: other}
 144 }
 145
 146 /// Creates a new iterator which will apply the specified function to each
 147 /// element returned by the first, yielding the mapped element instead.
 148 ///
 149 /// # Example
 150 ///
 151 /// ```rust
 152 /// let a = [1, 2];
 153 /// let mut it = a.iter().map(|&x| 2 * x);
 154 /// assert_eq!(it.next().unwrap(), 2);
 155 /// assert_eq!(it.next().unwrap(), 4);
 156 /// assert!(it.next().is_none());
 157 /// ```
 158 #[inline]
 159 fn map<'r, B>(self, f: |A|: 'r -> B) -> Map<'r, A, B, Self> {
 160 Map{iter: self, f: f}
 161 }
 162
 163 /// Creates an iterator which applies the predicate to each element returned
 164 /// by this iterator. Only elements which have the predicate evaluate to
 165 /// `true` will be yielded.
 166 ///
 167 /// # Example
 168 ///
 169 /// ```rust
 170 /// let a = [1, 2];
 171 /// let mut it = a.iter().filter(|&x| *x > 1);
 172 /// assert_eq!(it.next().unwrap(), &2);
 173 /// assert!(it.next().is_none());
 174 /// ```
 175 #[inline]
 176 fn filter<'r>(self, predicate: |&A|: 'r -> bool) -> Filter<'r, A, Self> {
 177 Filter{iter: self, predicate: predicate}
 178 }
 179
 180 /// Creates an iterator which both filters and maps elements.
 181 /// If the specified function returns None, the element is skipped.
 182 /// Otherwise the option is unwrapped and the new value is yielded.
 183 ///
 184 /// # Example
 185 ///
 186 /// ```rust
 187 /// let a = [1, 2];
 188 /// let mut it = a.iter().filter_map(|&x| if x > 1 {Some(2 * x)} else {None});
 189 /// assert_eq!(it.next().unwrap(), 4);
 190 /// assert!(it.next().is_none());
 191 /// ```
 192 #[inline]
 193 fn filter_map<'r, B>(self, f: |A|: 'r -> Option) -> FilterMap<'r, A, B, Self> {
 194 FilterMap { iter: self, f: f }
 195 }
 196
 197 /// Creates an iterator which yields a pair of the value returned by this
 198 /// iterator plus the current index of iteration.
 199 ///
 200 /// # Example
 201 ///
 202 /// ```rust
 203 /// let a = [100, 200];
 204 /// let mut it = a.iter().enumerate();
 205 /// assert_eq!(it.next().unwrap(), (0, &100));
 206 /// assert_eq!(it.next().unwrap(), (1, &200));
 207 /// assert!(it.next().is_none());
 208 /// ```
 209 #[inline]
 210 fn enumerate(self) -> Enumerate<Self> {
 211 Enumerate{iter: self, count: 0}
 212 }
 213
 214
 215 /// Creates an iterator that has a `.peek()` method
 216 /// that returns an optional reference to the next element.
 217 ///
 218 /// # Example
 219 ///
 220 /// ```rust
 221 /// let xs = [100, 200, 300];
 222 /// let mut it = xs.iter().map(|x| *x).peekable();
 223 /// assert_eq!(it.peek().unwrap(), &100);
 224 /// assert_eq!(it.next().unwrap(), 100);
 225 /// assert_eq!(it.next().unwrap(), 200);
 226 /// assert_eq!(it.peek().unwrap(), &300);
 227 /// assert_eq!(it.peek().unwrap(), &300);
 228 /// assert_eq!(it.next().unwrap(), 300);
 229 /// assert!(it.peek().is_none());
 230 /// assert!(it.next().is_none());
 231 /// ```
 232 #[inline]
 233 fn peekable(self) -> Peekable<A, Self> {
 234 Peekable{iter: self, peeked: None}
 235 }
 236
 237 /// Creates an iterator which invokes the predicate on elements until it
 238 /// returns false. Once the predicate returns false, all further elements are
 239 /// yielded.
 240 ///
 241 /// # Example
 242 ///
 243 /// ```rust
 244 /// let a = [1, 2, 3, 2, 1];
 245 /// let mut it = a.iter().skip_while(|&a| *a < 3);
 246 /// assert_eq!(it.next().unwrap(), &3);
 247 /// assert_eq!(it.next().unwrap(), &2);
 248 /// assert_eq!(it.next().unwrap(), &1);
 249 /// assert!(it.next().is_none());
 250 /// ```
 251 #[inline]
 252 fn skip_while<'r>(self, predicate: |&A|: 'r -> bool) -> SkipWhile<'r, A, Self> {
 253 SkipWhile{iter: self, flag: false, predicate: predicate}
 254 }
 255
 256 /// Creates an iterator which yields elements so long as the predicate
 257 /// returns true. After the predicate returns false for the first time, no
 258 /// further elements will be yielded.
 259 ///
 260 /// # Example
 261 ///
 262 /// ```rust
 263 /// let a = [1, 2, 3, 2, 1];
 264 /// let mut it = a.iter().take_while(|&a| *a < 3);
 265 /// assert_eq!(it.next().unwrap(), &1);
 266 /// assert_eq!(it.next().unwrap(), &2);
 267 /// assert!(it.next().is_none());
 268 /// ```
 269 #[inline]
 270 fn take_while<'r>(self, predicate: |&A|: 'r -> bool) -> TakeWhile<'r, A, Self> {
 271 TakeWhile{iter: self, flag: false, predicate: predicate}
 272 }
 273
 274 /// Creates an iterator which skips the first `n` elements of this iterator,
 275 /// and then it yields all further items.
 276 ///
 277 /// # Example
 278 ///
 279 /// ```rust
 280 /// let a = [1, 2, 3, 4, 5];
 281 /// let mut it = a.iter().skip(3);
 282 /// assert_eq!(it.next().unwrap(), &4);
 283 /// assert_eq!(it.next().unwrap(), &5);
 284 /// assert!(it.next().is_none());
 285 /// ```
 286 #[inline]
 287 fn skip(self, n: uint) -> Skip<Self> {
 288 Skip{iter: self, n: n}
 289 }
 290
 291 /// Creates an iterator which yields the first `n` elements of this
 292 /// iterator, and then it will always return None.
 293 ///
 294 /// # Example
 295 ///
 296 /// ```rust
 297 /// let a = [1, 2, 3, 4, 5];
 298 /// let mut it = a.iter().take(3);
 299 /// assert_eq!(it.next().unwrap(), &1);
 300 /// assert_eq!(it.next().unwrap(), &2);
 301 /// assert_eq!(it.next().unwrap(), &3);
 302 /// assert!(it.next().is_none());
 303 /// ```
 304 #[inline]
 305 fn take(self, n: uint) -> Take<Self> {
 306 Take{iter: self, n: n}
 307 }
 308
 309 /// Creates a new iterator which behaves in a similar fashion to fold.
 310 /// There is a state which is passed between each iteration and can be
 311 /// mutated as necessary. The yielded values from the closure are yielded
 312 /// from the Scan instance when not None.
 313 ///
 314 /// # Example
 315 ///
 316 /// ```rust
 317 /// let a = [1, 2, 3, 4, 5];
 318 /// let mut it = a.iter().scan(1, |fac, &x| {
 319 /// *fac = *fac * x;
 320 /// Some(*fac)
 321 /// });
 322 /// assert_eq!(it.next().unwrap(), 1);
 323 /// assert_eq!(it.next().unwrap(), 2);
 324 /// assert_eq!(it.next().unwrap(), 6);
 325 /// assert_eq!(it.next().unwrap(), 24);
 326 /// assert_eq!(it.next().unwrap(), 120);
 327 /// assert!(it.next().is_none());
 328 /// ```
 329 #[inline]
 330 fn scan<'r, St, B>(self, initial_state: St, f: |&mut St, A|: 'r -> Option)
 331 -> Scan<'r, A, B, Self, St> {
 332 Scan{iter: self, f: f, state: initial_state}
 333 }
 334
 335 /// Creates an iterator that maps each element to an iterator,
 336 /// and yields the elements of the produced iterators
 337 ///
 338 /// # Example
 339 ///
 340 /// ```rust
 341 /// use std::iter::count;
 342 ///
 343 /// let xs = [2u, 3];
 344 /// let ys = [0u, 1, 0, 1, 2];
 345 /// let mut it = xs.iter().flat_map(|&x| count(0u, 1).take(x));
 346 /// // Check that `it` has the same elements as `ys`
 347 /// let mut i = 0;
 348 /// for x in it {
 349 /// assert_eq!(x, ys[i]);
 350 /// i += 1;
 351 /// }
 352 /// ```
 353 #[inline]
 354 fn flat_map<'r, B, U: Iterator>(self, f: |A|: 'r -> U)
 355 -> FlatMap<'r, A, Self, U> {
 356 FlatMap{iter: self, f: f, frontiter: None, backiter: None }
 357 }
 358
 359 /// Creates an iterator that yields `None` forever after the underlying
 360 /// iterator yields `None`. Random-access iterator behavior is not
 361 /// affected, only single and double-ended iterator behavior.
 362 ///
 363 /// # Example
 364 ///
 365 /// ```rust
 366 /// fn process<U: Iterator<int>>(it: U) -> int {
 367 /// let mut it = it.fuse();
 368 /// let mut sum = 0;
 369 /// for x in it {
 370 /// if x > 5 {
 371 /// continue;
 372 /// }
 373 /// sum += x;
 374 /// }
 375 /// // did we exhaust the iterator?
 376 /// if it.next().is_none() {
 377 /// sum += 1000;
 378 /// }
 379 /// sum
 380 /// }
 381 /// let x = ~[1,2,3,7,8,9];
 382 /// assert_eq!(process(x.move_iter()), 1006);
 383 /// ```
 384 #[inline]
 385 fn fuse(self) -> Fuse<Self> {
 386 Fuse{iter: self, done: false}
 387 }
 388
 389 /// Creates an iterator that calls a function with a reference to each
 390 /// element before yielding it. This is often useful for debugging an
 391 /// iterator pipeline.
 392 ///
 393 /// # Example
 394 ///
 395 /// ```rust
 396 /// use std::iter::AdditiveIterator;
 397 ///
 398 /// let xs = [1u, 4, 2, 3, 8, 9, 6];
 399 /// let sum = xs.iter()
 400 /// .map(|&x| x)
 401 /// .inspect(|&x| println!("filtering {}", x))
 402 /// .filter(|&x| x % 2 == 0)
 403 /// .inspect(|&x| println!("{} made it through", x))
 404 /// .sum();
 405 /// println!("{}", sum);
 406 /// ```
 407 #[inline]
 408 fn inspect<'r>(self, f: |&A|: 'r) -> Inspect<'r, A, Self> {
 409 Inspect{iter: self, f: f}
 410 }
 411
 412 /// Creates a wrapper around a mutable reference to the iterator.
 413 ///
 414 /// This is useful to allow applying iterator adaptors while still
 415 /// retaining ownership of the original iterator value.
 416 ///
 417 /// # Example
 418 ///
 419 /// ```rust
 420 /// let mut xs = range(0, 10);
 421 /// // sum the first five values
 422 /// let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
 423 /// assert!(partial_sum == 10);
 424 /// // xs.next() is now `5`
 425 /// assert!(xs.next() == Some(5));
 426 /// ```
 427 fn by_ref<'r>(&'r mut self) -> ByRef<'r, Self> {
 428 ByRef{iter: self}
 429 }
 430
 431 /// Apply a function to each element, or stop iterating if the
 432 /// function returns `false`.
 433 ///
 434 /// # Example
 435 ///
 436 /// ```rust
 437 /// range(0, 5).advance(|x| {print!("{} ", x); true});
 438 /// ```
 439 #[inline]
 440 fn advance(&mut self, f: |A| -> bool) -> bool {
 441 loop {
 442 match self.next() {
 443 Some(x) => {
 444 if !f(x) { return false; }
 445 }
 446 None => { return true; }
 447 }
 448 }
 449 }
 450
 451 /// Loops through the entire iterator, collecting all of the elements into
 452 /// a container implementing `FromIterator`.
 453 ///
 454 /// # Example
 455 ///
 456 /// ```rust
 457 /// let a = [1, 2, 3, 4, 5];
 458 /// let b: Vec<int> = a.iter().map(|&x| x).collect();
 459 /// assert!(a.as_slice() == b.as_slice());
 460 /// ```
 461 #[inline]
 462 fn collect<B: FromIterator<A>>(&mut self) -> B {
 463 FromIterator::from_iter(self.by_ref())
 464 }
 465
 466 /// Loops through `n` iterations, returning the `n`th element of the
 467 /// iterator.
 468 ///
 469 /// # Example
 470 ///
 471 /// ```rust
 472 /// let a = [1, 2, 3, 4, 5];
 473 /// let mut it = a.iter();
 474 /// assert!(it.nth(2).unwrap() == &3);
 475 /// assert!(it.nth(2) == None);
 476 /// ```
 477 #[inline]
 478 fn nth(&mut self, mut n: uint) -> Option<A> {
 479 loop {
 480 match self.next() {
 481 Some(x) => if n == 0 { return Some(x) },
 482 None => return None
 483 }
 484 n -= 1;
 485 }
 486 }
 487
 488 /// Loops through the entire iterator, returning the last element of the
 489 /// iterator.
 490 ///
 491 /// # Example
 492 ///
 493 /// ```rust
 494 /// let a = [1, 2, 3, 4, 5];
 495 /// assert!(a.iter().last().unwrap() == &5);
 496 /// ```
 497 #[inline]
 498 fn last(&mut self) -> Option<A> {
 499 let mut last = None;
 500 for x in *self { last = Some(x); }
 501 last
 502 }
 503
 504 /// Performs a fold operation over the entire iterator, returning the
 505 /// eventual state at the end of the iteration.
 506 ///
 507 /// # Example
 508 ///
 509 /// ```rust
 510 /// let a = [1, 2, 3, 4, 5];
 511 /// assert!(a.iter().fold(0, |a, &b| a + b) == 15);
 512 /// ```
 513 #[inline]
 514 fn fold(&mut self, init: B, f: |B, A| -> B) -> B {
 515 let mut accum = init;
 516 loop {
 517 match self.next() {
 518 Some(x) => { accum = f(accum, x); }
 519 None => { break; }
 520 }
 521 }
 522 accum
 523 }
 524
 525 /// Counts the number of elements in this iterator.
 526 ///
 527 /// # Example
 528 ///
 529 /// ```rust
 530 /// let a = [1, 2, 3, 4, 5];
 531 /// let mut it = a.iter();
 532 /// assert!(it.len() == 5);
 533 /// assert!(it.len() == 0);
 534 /// ```
 535 #[inline]
 536 fn len(&mut self) -> uint {
 537 self.fold(0, |cnt, _x| cnt + 1)
 538 }
 539
 540 /// Tests whether the predicate holds true for all elements in the iterator.
 541 ///
 542 /// # Example
 543 ///
 544 /// ```rust
 545 /// let a = [1, 2, 3, 4, 5];
 546 /// assert!(a.iter().all(|x| *x > 0));
 547 /// assert!(!a.iter().all(|x| *x > 2));
 548 /// ```
 549 #[inline]
 550 fn all(&mut self, f: |A| -> bool) -> bool {
 551 for x in *self { if !f(x) { return false; } }
 552 true
 553 }
 554
 555 /// Tests whether any element of an iterator satisfies the specified
 556 /// predicate.
 557 ///
 558 /// # Example
 559 ///
 560 /// ```rust
 561 /// let a = [1, 2, 3, 4, 5];
 562 /// let mut it = a.iter();
 563 /// assert!(it.any(|x| *x == 3));
 564 /// assert!(!it.any(|x| *x == 3));
 565 /// ```
 566 #[inline]
 567 fn any(&mut self, f: |A| -> bool) -> bool {
 568 for x in *self { if f(x) { return true; } }
 569 false
 570 }
 571
 572 /// Return the first element satisfying the specified predicate
 573 #[inline]
 574 fn find(&mut self, predicate: |&A| -> bool) -> Option<A> {
 575 for x in *self {
 576 if predicate(&x) { return Some(x) }
 577 }
 578 None
 579 }
 580
 581 /// Return the index of the first element satisfying the specified predicate
 582 #[inline]
 583 fn position(&mut self, predicate: |A| -> bool) -> Option<uint> {
 584 let mut i = 0;
 585 for x in *self {
 586 if predicate(x) {
 587 return Some(i);
 588 }
 589 i += 1;
 590 }
 591 None
 592 }
 593
 594 /// Count the number of elements satisfying the specified predicate
 595 #[inline]
 596 fn count(&mut self, predicate: |A| -> bool) -> uint {
 597 let mut i = 0;
 598 for x in *self {
 599 if predicate(x) { i += 1 }
 600 }
 601 i
 602 }
 603
 604 /// Return the element that gives the maximum value from the
 605 /// specified function.
 606 ///
 607 /// # Example
 608 ///
 609 /// ```rust
 610 /// let xs = [-3i, 0, 1, 5, -10];
 611 /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
 612 /// ```
 613 #[inline]
 614 fn max_by<B: TotalOrd>(&mut self, f: |&A| -> B) -> Option<A> {
 615 self.fold(None, |max: Option<(A, B)>, x| {
 616 let x_val = f(&x);
 617 match max {
 618 None => Some((x, x_val)),
 619 Some((y, y_val)) => if x_val > y_val {
 620 Some((x, x_val))
 621 } else {
 622 Some((y, y_val))
 623 }
 624 }
 625 }).map(|(x, _)| x)
 626 }
 627
 628 /// Return the element that gives the minimum value from the
 629 /// specified function.
 630 ///
 631 /// # Example
 632 ///
 633 /// ```rust
 634 /// let xs = [-3i, 0, 1, 5, -10];
 635 /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
 636 /// ```
 637 #[inline]
 638 fn min_by<B: TotalOrd>(&mut self, f: |&A| -> B) -> Option<A> {
 639 self.fold(None, |min: Option<(A, B)>, x| {
 640 let x_val = f(&x);
 641 match min {
 642 None => Some((x, x_val)),
 643 Some((y, y_val)) => if x_val < y_val {
 644 Some((x, x_val))
 645 } else {
 646 Some((y, y_val))
 647 }
 648 }
 649 }).map(|(x, _)| x)
 650 }
 651 }
 652
 653 /// A range iterator able to yield elements from both ends
 654 pub trait DoubleEndedIterator<A>: Iterator<A> {
 655 /// Yield an element from the end of the range, returning `None` if the range is empty.
 656 fn next_back(&mut self) -> Option<A>;
 657
 658 /// Change the direction of the iterator
 659 ///
 660 /// The flipped iterator swaps the ends on an iterator that can already
 661 /// be iterated from the front and from the back.
 662 ///
 663 ///
 664 /// If the iterator also implements RandomAccessIterator, the flipped
 665 /// iterator is also random access, with the indices starting at the back
 666 /// of the original iterator.
 667 ///
 668 /// Note: Random access with flipped indices still only applies to the first
 669 /// `uint::MAX` elements of the original iterator.
 670 #[inline]
 671 fn rev(self) -> Rev<Self> {
 672 Rev{iter: self}
 673 }
 674 }
 675
 676 /// A double-ended iterator yielding mutable references
 677 pub trait MutableDoubleEndedIterator {
 678 // FIXME: #5898: should be called `reverse`
 679 /// Use an iterator to reverse a container in-place
 680 fn reverse_(&mut self);
 681 }
 682
 683 impl<'a, A, T: DoubleEndedIterator<&'a mut A>> MutableDoubleEndedIterator for T {
 684 // FIXME: #5898: should be called `reverse`
 685 /// Use an iterator to reverse a container in-place
 686 fn reverse_(&mut self) {
 687 loop {
 688 match (self.next(), self.next_back()) {
 689 (Some(x), Some(y)) => mem::swap(x, y),
 690 _ => break
 691 }
 692 }
 693 }
 694 }
 695
 696
 697 /// An object implementing random access indexing by `uint`
 698 ///
 699 /// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
 700 pub trait RandomAccessIterator<A>: Iterator<A> {
 701 /// Return the number of indexable elements. At most `std::uint::MAX`
 702 /// elements are indexable, even if the iterator represents a longer range.
 703 fn indexable(&self) -> uint;
 704
 705 /// Return an element at an index
 706 fn idx(&mut self, index: uint) -> Option<A>;
 707 }
 708
 709 /// An iterator that knows its exact length
 710 ///
 711 /// This trait is a helper for iterators like the vector iterator, so that
 712 /// it can support double-ended enumeration.
 713 ///
 714 /// `Iterator::size_hint` *must* return the exact size of the iterator.
 715 /// Note that the size must fit in `uint`.
 716 pub trait ExactSize<A> : DoubleEndedIterator<A> {
 717 /// Return the index of the last element satisfying the specified predicate
 718 ///
 719 /// If no element matches, None is returned.
 720 #[inline]
 721 fn rposition(&mut self, predicate: |A| -> bool) -> Option<uint> {
 722 let (lower, upper) = self.size_hint();
 723 assert!(upper == Some(lower));
 724 let mut i = lower;
 725 loop {
 726 match self.next_back() {
 727 None => break,
 728 Some(x) => {
 729 i = match i.checked_sub(&1) {
 730 Some(x) => x,
 731 None => fail!("rposition: incorrect ExactSize")
 732 };
 733 if predicate(x) {
 734 return Some(i)
 735 }
 736 }
 737 }
 738 }
 739 None
 740 }
 741 }
 742
 743 // All adaptors that preserve the size of the wrapped iterator are fine
 744 // Adaptors that may overflow in `size_hint` are not, i.e. `Chain`.
 745 impl<A, T: ExactSize<A>> ExactSize<(uint, A)> for Enumerate<T> {}
 746 impl<'a, A, T: ExactSize<A>> ExactSize<A> for Inspect<'a, A, T> {}
 747 impl<A, T: ExactSize<A>> ExactSize<A> for Rev<T> {}
 748 impl<'a, A, B, T: ExactSize<A>> ExactSize for Map<'a, A, B, T> {}
 749 impl<A, B, T: ExactSize<A>, U: ExactSize> ExactSize<(A, B)> for Zip<T, U> {}
 750
 751 /// An double-ended iterator with the direction inverted
 752 #[deriving(Clone)]
 753 pub struct Rev<T> {
 754 iter: T
 755 }
 756
 757 impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Rev<T> {
 758 #[inline]
 759 fn next(&mut self) -> Option<A> { self.iter.next_back() }
 760 #[inline]
 761 fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 762 }
 763
 764 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Rev<T> {
 765 #[inline]
 766 fn next_back(&mut self) -> Option<A> { self.iter.next() }
 767 }
 768
 769 impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
 770 for Rev<T> {
 771 #[inline]
 772 fn indexable(&self) -> uint { self.iter.indexable() }
 773 #[inline]
 774 fn idx(&mut self, index: uint) -> Option<A> {
 775 let amt = self.indexable();
 776 self.iter.idx(amt - index - 1)
 777 }
 778 }
 779
 780 /// A mutable reference to an iterator
 781 pub struct ByRef<'a, T> {
 782 iter: &'a mut T
 783 }
 784
 785 impl<'a, A, T: Iterator<A>> Iterator<A> for ByRef<'a, T> {
 786 #[inline]
 787 fn next(&mut self) -> Option<A> { self.iter.next() }
 788 #[inline]
 789 fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
 790 }
 791
 792 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for ByRef<'a, T> {
 793 #[inline]
 794 fn next_back(&mut self) -> Option<A> { self.iter.next_back() }
 795 }
 796
 797 /// A trait for iterators over elements which can be added together
 798 pub trait AdditiveIterator<A> {
 799 /// Iterates over the entire iterator, summing up all the elements
 800 ///
 801 /// # Example
 802 ///
 803 /// ```rust
 804 /// use std::iter::AdditiveIterator;
 805 ///
 806 /// let a = [1, 2, 3, 4, 5];
 807 /// let mut it = a.iter().map(|&x| x);
 808 /// assert!(it.sum() == 15);
 809 /// ```
 810 fn sum(&mut self) -> A;
 811 }
 812
 813 impl<A: Add<A, A> + Zero, T: Iterator<A>> AdditiveIterator<A> for T {
 814 #[inline]
 815 fn sum(&mut self) -> A {
 816 let zero: A = Zero::zero();
 817 self.fold(zero, |s, x| s + x)
 818 }
 819 }
 820
 821 /// A trait for iterators over elements whose elements can be multiplied
 822 /// together.
 823 pub trait MultiplicativeIterator<A> {
 824 /// Iterates over the entire iterator, multiplying all the elements
 825 ///
 826 /// # Example
 827 ///
 828 /// ```rust
 829 /// use std::iter::{count, MultiplicativeIterator};
 830 ///
 831 /// fn factorial(n: uint) -> uint {
 832 /// count(1u, 1).take_while(|&i| i <= n).product()
 833 /// }
 834 /// assert!(factorial(0) == 1);
 835 /// assert!(factorial(1) == 1);
 836 /// assert!(factorial(5) == 120);
 837 /// ```
 838 fn product(&mut self) -> A;
 839 }
 840
 841 impl<A: Mul<A, A> + One, T: Iterator<A>> MultiplicativeIterator<A> for T {
 842 #[inline]
 843 fn product(&mut self) -> A {
 844 let one: A = One::one();
 845 self.fold(one, |p, x| p * x)
 846 }
 847 }
 848
 849 /// A trait for iterators over elements which can be compared to one another.
 850 /// The type of each element must ascribe to the `Ord` trait.
 851 pub trait OrdIterator<A> {
 852 /// Consumes the entire iterator to return the maximum element.
 853 ///
 854 /// # Example
 855 ///
 856 /// ```rust
 857 /// let a = [1, 2, 3, 4, 5];
 858 /// assert!(a.iter().max().unwrap() == &5);
 859 /// ```
 860 fn max(&mut self) -> Option<A>;
 861
 862 /// Consumes the entire iterator to return the minimum element.
 863 ///
 864 /// # Example
 865 ///
 866 /// ```rust
 867 /// let a = [1, 2, 3, 4, 5];
 868 /// assert!(a.iter().min().unwrap() == &1);
 869 /// ```
 870 fn min(&mut self) -> Option<A>;
 871
 872 /// `min_max` finds the minimum and maximum elements in the iterator.
 873 ///
 874 /// The return type `MinMaxResult` is an enum of three variants:
 875 /// - `NoElements` if the iterator is empty.
 876 /// - `OneElement(x)` if the iterator has exactly one element.
 877 /// - `MinMax(x, y)` is returned otherwise, where `x <= y`. Two values are equal if and only if
 878 /// there is more than one element in the iterator and all elements are equal.
 879 ///
 880 /// On an iterator of length `n`, `min_max` does `1.5 * n` comparisons,
 881 /// and so faster than calling `min` and `max separately which does `2 * n` comparisons.
 882 ///
 883 /// # Example
 884 ///
 885 /// ```rust
 886 /// use std::iter::{NoElements, OneElement, MinMax};
 887 ///
 888 /// let v: [int, ..0] = [];
 889 /// assert_eq!(v.iter().min_max(), NoElements);
 890 ///
 891 /// let v = [1i];
 892 /// assert!(v.iter().min_max() == OneElement(&1));
 893 ///
 894 /// let v = [1i, 2, 3, 4, 5];
 895 /// assert!(v.iter().min_max() == MinMax(&1, &5));
 896 ///
 897 /// let v = [1i, 2, 3, 4, 5, 6];
 898 /// assert!(v.iter().min_max() == MinMax(&1, &6));
 899 ///
 900 /// let v = [1i, 1, 1, 1];
 901 /// assert!(v.iter().min_max() == MinMax(&1, &1));
 902 /// ```
 903 fn min_max(&mut self) -> MinMaxResult<A>;
 904 }
 905
 906 impl<A: TotalOrd, T: Iterator<A>> OrdIterator<A> for T {
 907 #[inline]
 908 fn max(&mut self) -> Option<A> {
 909 self.fold(None, |max, x| {
 910 match max {
 911 None => Some(x),
 912 Some(y) => Some(cmp::max(x, y))
 913 }
 914 })
 915 }
 916
 917 #[inline]
 918 fn min(&mut self) -> Option<A> {
 919 self.fold(None, |min, x| {
 920 match min {
 921 None => Some(x),
 922 Some(y) => Some(cmp::min(x, y))
 923 }
 924 })
 925 }
 926
 927 fn min_max(&mut self) -> MinMaxResult<A> {
 928 let (mut min, mut max) = match self.next() {
 929 None => return NoElements,
 930 Some(x) => {
 931 match self.next() {
 932 None => return OneElement(x),
 933 Some(y) => if x < y {(x, y)} else {(y,x)}
 934 }
 935 }
 936 };
 937
 938 loop {
 939 // `first` and `second` are the two next elements we want to look at.
 940 // We first compare `first` and `second` (#1). The smaller one is then compared to
 941 // current minimum (#2). The larger one is compared to current maximum (#3). This
 942 // way we do 3 comparisons for 2 elements.
 943 let first = match self.next() {
 944 None => break,
 945 Some(x) => x
 946 };
 947 let second = match self.next() {
 948 None => {
 949 if first < min {
 950 min = first;
 951 } else if first > max {
 952 max = first;
 953 }
 954 break;
 955 }
 956 Some(x) => x
 957 };
 958 if first < second {
 959 if first < min {min = first;}
 960 if max < second {max = second;}
 961 } else {
 962 if second < min {min = second;}
 963 if max < first {max = first;}
 964 }
 965 }
 966
 967 MinMax(min, max)
 968 }
 969 }
 970
 971 /// `MinMaxResult` is an enum returned by `min_max`. See `OrdIterator::min_max` for more detail.
 972 #[deriving(Clone, Eq)]
 973 pub enum MinMaxResult<T> {
 974 /// Empty iterator
 975 NoElements,
 976
 977 /// Iterator with one element, so the minimum and maximum are the same
 978 OneElement(T),
 979
 980 /// More than one element in the iterator, the first element is not larger than the second
 981 MinMax(T, T)
 982 }
 983
 984 impl<T: Clone> MinMaxResult<T> {
 985 /// `into_option` creates an `Option` of type `(T,T)`. The returned `Option` has variant
 986 /// `None` if and only if the `MinMaxResult` has variant `NoElements`. Otherwise variant
 987 /// `Some(x,y)` is returned where `x <= y`. If `MinMaxResult` has variant `OneElement(x)`,
 988 /// performing this operation will make one clone of `x`.
 989 ///
 990 /// # Example
 991 ///
 992 /// ```rust
 993 /// use std::iter::{NoElements, OneElement, MinMax, MinMaxResult};
 994 ///
 995 /// let r: MinMaxResult<int> = NoElements;
 996 /// assert_eq!(r.into_option(), None)
 997 ///
 998 /// let r = OneElement(1);
 999 /// assert_eq!(r.into_option(), Some((1,1)));
1000 ///
1001 /// let r = MinMax(1,2);
1002 /// assert_eq!(r.into_option(), Some((1,2)));
1003 /// ```
1004 pub fn into_option(self) -> Option<(T,T)> {
1005 match self {
1006 NoElements => None,
1007 OneElement(x) => Some((x.clone(), x)),
1008 MinMax(x, y) => Some((x, y))
1009 }
1010 }
1011 }
1012
1013 /// A trait for iterators that are cloneable.
1014 pub trait CloneableIterator {
1015 /// Repeats an iterator endlessly
1016 ///
1017 /// # Example
1018 ///
1019 /// ```rust
1020 /// use std::iter::{CloneableIterator, count};
1021 ///
1022 /// let a = count(1,1).take(1);
1023 /// let mut cy = a.cycle();
1024 /// assert_eq!(cy.next(), Some(1));
1025 /// assert_eq!(cy.next(), Some(1));
1026 /// ```
1027 fn cycle(self) -> Cycle<Self>;
1028 }
1029
1030 impl<A, T: Clone + Iterator<A>> CloneableIterator for T {
1031 #[inline]
1032 fn cycle(self) -> Cycle<T> {
1033 Cycle{orig: self.clone(), iter: self}
1034 }
1035 }
1036
1037 /// An iterator that repeats endlessly
1038 #[deriving(Clone)]
1039 pub struct Cycle<T> {
1040 orig: T,
1041 iter: T,
1042 }
1043
1044 impl<A, T: Clone + Iterator<A>> Iterator<A> for Cycle<T> {
1045 #[inline]
1046 fn next(&mut self) -> Option<A> {
1047 match self.iter.next() {
1048 None => { self.iter = self.orig.clone(); self.iter.next() }
1049 y => y
1050 }
1051 }
1052
1053 #[inline]
1054 fn size_hint(&self) -> (uint, Option<uint>) {
1055 // the cycle iterator is either empty or infinite
1056 match self.orig.size_hint() {
1057 sz @ (0, Some(0)) => sz,
1058 (0, _) => (0, None),
1059 _ => (uint::MAX, None)
1060 }
1061 }
1062 }
1063
1064 impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> {
1065 #[inline]
1066 fn indexable(&self) -> uint {
1067 if self.orig.indexable() > 0 {
1068 uint::MAX
1069 } else {
1070 0
1071 }
1072 }
1073
1074 #[inline]
1075 fn idx(&mut self, index: uint) -> Option<A> {
1076 let liter = self.iter.indexable();
1077 let lorig = self.orig.indexable();
1078 if lorig == 0 {
1079 None
1080 } else if index < liter {
1081 self.iter.idx(index)
1082 } else {
1083 self.orig.idx((index - liter) % lorig)
1084 }
1085 }
1086 }
1087
1088 /// An iterator which strings two iterators together
1089 #[deriving(Clone)]
1090 pub struct Chain<T, U> {
1091 a: T,
1092 b: U,
1093 flag: bool,
1094 }
1095
1096 impl<A, T: Iterator<A>, U: Iterator<A>> Iterator<A> for Chain<T, U> {
1097 #[inline]
1098 fn next(&mut self) -> Option<A> {
1099 if self.flag {
1100 self.b.next()
1101 } else {
1102 match self.a.next() {
1103 Some(x) => return Some(x),
1104 _ => ()
1105 }
1106 self.flag = true;
1107 self.b.next()
1108 }
1109 }
1110
1111 #[inline]
1112 fn size_hint(&self) -> (uint, Option<uint>) {
1113 let (a_lower, a_upper) = self.a.size_hint();
1114 let (b_lower, b_upper) = self.b.size_hint();
1115
1116 let lower = a_lower.saturating_add(b_lower);
1117
1118 let upper = match (a_upper, b_upper) {
1119 (Some(x), Some(y)) => x.checked_add(&y),
1120 _ => None
1121 };
1122
1123 (lower, upper)
1124 }
1125 }
1126
1127 impl<A, T: DoubleEndedIterator<A>, U: DoubleEndedIterator<A>> DoubleEndedIterator<A>
1128 for Chain<T, U> {
1129 #[inline]
1130 fn next_back(&mut self) -> Option<A> {
1131 match self.b.next_back() {
1132 Some(x) => Some(x),
1133 None => self.a.next_back()
1134 }
1135 }
1136 }
1137
1138 impl<A, T: RandomAccessIterator<A>, U: RandomAccessIterator<A>> RandomAccessIterator<A>
1139 for Chain<T, U> {
1140 #[inline]
1141 fn indexable(&self) -> uint {
1142 let (a, b) = (self.a.indexable(), self.b.indexable());
1143 a.saturating_add(b)
1144 }
1145
1146 #[inline]
1147 fn idx(&mut self, index: uint) -> Option<A> {
1148 let len = self.a.indexable();
1149 if index < len {
1150 self.a.idx(index)
1151 } else {
1152 self.b.idx(index - len)
1153 }
1154 }
1155 }
1156
1157 /// An iterator which iterates two other iterators simultaneously
1158 #[deriving(Clone)]
1159 pub struct Zip<T, U> {
1160 a: T,
1161 b: U
1162 }
1163
1164 impl<A, B, T: Iterator<A>, U: Iterator> Iterator<(A, B)> for Zip<T, U> {
1165 #[inline]
1166 fn next(&mut self) -> Option<(A, B)> {
1167 match self.a.next() {
1168 None => None,
1169 Some(x) => match self.b.next() {
1170 None => None,
1171 Some(y) => Some((x, y))
1172 }
1173 }
1174 }
1175
1176 #[inline]
1177 fn size_hint(&self) -> (uint, Option<uint>) {
1178 let (a_lower, a_upper) = self.a.size_hint();
1179 let (b_lower, b_upper) = self.b.size_hint();
1180
1181 let lower = cmp::min(a_lower, b_lower);
1182
1183 let upper = match (a_upper, b_upper) {
1184 (Some(x), Some(y)) => Some(cmp::min(x,y)),
1185 (Some(x), None) => Some(x),
1186 (None, Some(y)) => Some(y),
1187 (None, None) => None
1188 };
1189
1190 (lower, upper)
1191 }
1192 }
1193
1194 impl<A, B, T: ExactSize<A>, U: ExactSize> DoubleEndedIterator<(A, B)>
1195 for Zip<T, U> {
1196 #[inline]
1197 fn next_back(&mut self) -> Option<(A, B)> {
1198 let (a_sz, a_upper) = self.a.size_hint();
1199 let (b_sz, b_upper) = self.b.size_hint();
1200 assert!(a_upper == Some(a_sz));
1201 assert!(b_upper == Some(b_sz));
1202 if a_sz < b_sz {
1203 for _ in range(0, b_sz - a_sz) { self.b.next_back(); }
1204 } else if a_sz > b_sz {
1205 for _ in range(0, a_sz - b_sz) { self.a.next_back(); }
1206 }
1207 let (a_sz, _) = self.a.size_hint();
1208 let (b_sz, _) = self.b.size_hint();
1209 assert!(a_sz == b_sz);
1210 match (self.a.next_back(), self.b.next_back()) {
1211 (Some(x), Some(y)) => Some((x, y)),
1212 _ => None
1213 }
1214 }
1215 }
1216
1217 impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator>
1218 RandomAccessIterator<(A, B)> for Zip<T, U> {
1219 #[inline]
1220 fn indexable(&self) -> uint {
1221 cmp::min(self.a.indexable(), self.b.indexable())
1222 }
1223
1224 #[inline]
1225 fn idx(&mut self, index: uint) -> Option<(A, B)> {
1226 match self.a.idx(index) {
1227 None => None,
1228 Some(x) => match self.b.idx(index) {
1229 None => None,
1230 Some(y) => Some((x, y))
1231 }
1232 }
1233 }
1234 }
1235
1236 /// An iterator which maps the values of `iter` with `f`
1237 pub struct Map<'a, A, B, T> {
1238 iter: T,
1239 f: |A|: 'a -> B
1240 }
1241
1242 impl<'a, A, B, T> Map<'a, A, B, T> {
1243 #[inline]
1244 fn do_map(&mut self, elt: Option<A>) -> Option {
1245 match elt {
1246 Some(a) => Some((self.f)(a)),
1247 _ => None
1248 }
1249 }
1250 }
1251
1252 impl<'a, A, B, T: Iterator<A>> Iterator for Map<'a, A, B, T> {
1253 #[inline]
1254 fn next(&mut self) -> Option {
1255 let next = self.iter.next();
1256 self.do_map(next)
1257 }
1258
1259 #[inline]
1260 fn size_hint(&self) -> (uint, Option<uint>) {
1261 self.iter.size_hint()
1262 }
1263 }
1264
1265 impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator for Map<'a, A, B, T> {
1266 #[inline]
1267 fn next_back(&mut self) -> Option {
1268 let next = self.iter.next_back();
1269 self.do_map(next)
1270 }
1271 }
1272
1273 impl<'a, A, B, T: RandomAccessIterator<A>> RandomAccessIterator for Map<'a, A, B, T> {
1274 #[inline]
1275 fn indexable(&self) -> uint {
1276 self.iter.indexable()
1277 }
1278
1279 #[inline]
1280 fn idx(&mut self, index: uint) -> Option {
1281 let elt = self.iter.idx(index);
1282 self.do_map(elt)
1283 }
1284 }
1285
1286 /// An iterator which filters the elements of `iter` with `predicate`
1287 pub struct Filter<'a, A, T> {
1288 iter: T,
1289 predicate: |&A|: 'a -> bool
1290 }
1291
1292 impl<'a, A, T: Iterator<A>> Iterator<A> for Filter<'a, A, T> {
1293 #[inline]
1294 fn next(&mut self) -> Option<A> {
1295 for x in self.iter {
1296 if (self.predicate)(&x) {
1297 return Some(x);
1298 } else {
1299 continue
1300 }
1301 }
1302 None
1303 }
1304
1305 #[inline]
1306 fn size_hint(&self) -> (uint, Option<uint>) {
1307 let (_, upper) = self.iter.size_hint();
1308 (0, upper) // can't know a lower bound, due to the predicate
1309 }
1310 }
1311
1312 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Filter<'a, A, T> {
1313 #[inline]
1314 fn next_back(&mut self) -> Option<A> {
1315 loop {
1316 match self.iter.next_back() {
1317 None => return None,
1318 Some(x) => {
1319 if (self.predicate)(&x) {
1320 return Some(x);
1321 } else {
1322 continue
1323 }
1324 }
1325 }
1326 }
1327 }
1328 }
1329
1330 /// An iterator which uses `f` to both filter and map elements from `iter`
1331 pub struct FilterMap<'a, A, B, T> {
1332 iter: T,
1333 f: |A|: 'a -> Option
1334 }
1335
1336 impl<'a, A, B, T: Iterator<A>> Iterator for FilterMap<'a, A, B, T> {
1337 #[inline]
1338 fn next(&mut self) -> Option {
1339 for x in self.iter {
1340 match (self.f)(x) {
1341 Some(y) => return Some(y),
1342 None => ()
1343 }
1344 }
1345 None
1346 }
1347
1348 #[inline]
1349 fn size_hint(&self) -> (uint, Option<uint>) {
1350 let (_, upper) = self.iter.size_hint();
1351 (0, upper) // can't know a lower bound, due to the predicate
1352 }
1353 }
1354
1355 impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator
1356 for FilterMap<'a, A, B, T> {
1357 #[inline]
1358 fn next_back(&mut self) -> Option {
1359 loop {
1360 match self.iter.next_back() {
1361 None => return None,
1362 Some(x) => {
1363 match (self.f)(x) {
1364 Some(y) => return Some(y),
1365 None => ()
1366 }
1367 }
1368 }
1369 }
1370 }
1371 }
1372
1373 /// An iterator which yields the current count and the element during iteration
1374 #[deriving(Clone)]
1375 pub struct Enumerate<T> {
1376 iter: T,
1377 count: uint
1378 }
1379
1380 impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> {
1381 #[inline]
1382 fn next(&mut self) -> Option<(uint, A)> {
1383 match self.iter.next() {
1384 Some(a) => {
1385 let ret = Some((self.count, a));
1386 self.count += 1;
1387 ret
1388 }
1389 _ => None
1390 }
1391 }
1392
1393 #[inline]
1394 fn size_hint(&self) -> (uint, Option<uint>) {
1395 self.iter.size_hint()
1396 }
1397 }
1398
1399 impl<A, T: ExactSize<A>> DoubleEndedIterator<(uint, A)> for Enumerate<T> {
1400 #[inline]
1401 fn next_back(&mut self) -> Option<(uint, A)> {
1402 match self.iter.next_back() {
1403 Some(a) => {
1404 let (lower, upper) = self.iter.size_hint();
1405 assert!(upper == Some(lower));
1406 Some((self.count + lower, a))
1407 }
1408 _ => None
1409 }
1410 }
1411 }
1412
1413 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<(uint, A)> for Enumerate<T> {
1414 #[inline]
1415 fn indexable(&self) -> uint {
1416 self.iter.indexable()
1417 }
1418
1419 #[inline]
1420 fn idx(&mut self, index: uint) -> Option<(uint, A)> {
1421 match self.iter.idx(index) {
1422 Some(a) => Some((self.count + index, a)),
1423 _ => None,
1424 }
1425 }
1426 }
1427
1428 /// An iterator with a `peek()` that returns an optional reference to the next element.
1429 pub struct Peekable<A, T> {
1430 iter: T,
1431 peeked: Option<A>,
1432 }
1433
1434 impl<A, T: Iterator<A>> Iterator<A> for Peekable<A, T> {
1435 #[inline]
1436 fn next(&mut self) -> Option<A> {
1437 if self.peeked.is_some() { self.peeked.take() }
1438 else { self.iter.next() }
1439 }
1440
1441 #[inline]
1442 fn size_hint(&self) -> (uint, Option<uint>) {
1443 let (lo, hi) = self.iter.size_hint();
1444 if self.peeked.is_some() {
1445 let lo = lo.saturating_add(1);
1446 let hi = match hi {
1447 Some(x) => x.checked_add(&1),
1448 None => None
1449 };
1450 (lo, hi)
1451 } else {
1452 (lo, hi)
1453 }
1454 }
1455 }
1456
1457 impl<'a, A, T: Iterator<A>> Peekable<A, T> {
1458 /// Return a reference to the next element of the iterator with out advancing it,
1459 /// or None if the iterator is exhausted.
1460 #[inline]
1461 pub fn peek(&'a mut self) -> Option<&'a A> {
1462 if self.peeked.is_none() {
1463 self.peeked = self.iter.next();
1464 }
1465 match self.peeked {
1466 Some(ref value) => Some(value),
1467 None => None,
1468 }
1469 }
1470
1471 /// Check whether peekable iterator is empty or not.
1472 #[inline]
1473 pub fn is_empty(&mut self) -> bool {
1474 self.peek().is_none()
1475 }
1476 }
1477
1478 /// An iterator which rejects elements while `predicate` is true
1479 pub struct SkipWhile<'a, A, T> {
1480 iter: T,
1481 flag: bool,
1482 predicate: |&A|: 'a -> bool
1483 }
1484
1485 impl<'a, A, T: Iterator<A>> Iterator<A> for SkipWhile<'a, A, T> {
1486 #[inline]
1487 fn next(&mut self) -> Option<A> {
1488 let mut next = self.iter.next();
1489 if self.flag {
1490 next
1491 } else {
1492 loop {
1493 match next {
1494 Some(x) => {
1495 if (self.predicate)(&x) {
1496 next = self.iter.next();
1497 continue
1498 } else {
1499 self.flag = true;
1500 return Some(x)
1501 }
1502 }
1503 None => return None
1504 }
1505 }
1506 }
1507 }
1508
1509 #[inline]
1510 fn size_hint(&self) -> (uint, Option<uint>) {
1511 let (_, upper) = self.iter.size_hint();
1512 (0, upper) // can't know a lower bound, due to the predicate
1513 }
1514 }
1515
1516 /// An iterator which only accepts elements while `predicate` is true
1517 pub struct TakeWhile<'a, A, T> {
1518 iter: T,
1519 flag: bool,
1520 predicate: |&A|: 'a -> bool
1521 }
1522
1523 impl<'a, A, T: Iterator<A>> Iterator<A> for TakeWhile<'a, A, T> {
1524 #[inline]
1525 fn next(&mut self) -> Option<A> {
1526 if self.flag {
1527 None
1528 } else {
1529 match self.iter.next() {
1530 Some(x) => {
1531 if (self.predicate)(&x) {
1532 Some(x)
1533 } else {
1534 self.flag = true;
1535 None
1536 }
1537 }
1538 None => None
1539 }
1540 }
1541 }
1542
1543 #[inline]
1544 fn size_hint(&self) -> (uint, Option<uint>) {
1545 let (_, upper) = self.iter.size_hint();
1546 (0, upper) // can't know a lower bound, due to the predicate
1547 }
1548 }
1549
1550 /// An iterator which skips over `n` elements of `iter`.
1551 #[deriving(Clone)]
1552 pub struct Skip<T> {
1553 iter: T,
1554 n: uint
1555 }
1556
1557 impl<A, T: Iterator<A>> Iterator<A> for Skip<T> {
1558 #[inline]
1559 fn next(&mut self) -> Option<A> {
1560 let mut next = self.iter.next();
1561 if self.n == 0 {
1562 next
1563 } else {
1564 let mut n = self.n;
1565 while n > 0 {
1566 n -= 1;
1567 match next {
1568 Some(_) => {
1569 next = self.iter.next();
1570 continue
1571 }
1572 None => {
1573 self.n = 0;
1574 return None
1575 }
1576 }
1577 }
1578 self.n = 0;
1579 next
1580 }
1581 }
1582
1583 #[inline]
1584 fn size_hint(&self) -> (uint, Option<uint>) {
1585 let (lower, upper) = self.iter.size_hint();
1586
1587 let lower = lower.saturating_sub(self.n);
1588
1589 let upper = match upper {
1590 Some(x) => Some(x.saturating_sub(self.n)),
1591 None => None
1592 };
1593
1594 (lower, upper)
1595 }
1596 }
1597
1598 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Skip<T> {
1599 #[inline]
1600 fn indexable(&self) -> uint {
1601 self.iter.indexable().saturating_sub(self.n)
1602 }
1603
1604 #[inline]
1605 fn idx(&mut self, index: uint) -> Option<A> {
1606 if index >= self.indexable() {
1607 None
1608 } else {
1609 self.iter.idx(index + self.n)
1610 }
1611 }
1612 }
1613
1614 /// An iterator which only iterates over the first `n` iterations of `iter`.
1615 #[deriving(Clone)]
1616 pub struct Take<T> {
1617 iter: T,
1618 n: uint
1619 }
1620
1621 impl<A, T: Iterator<A>> Iterator<A> for Take<T> {
1622 #[inline]
1623 fn next(&mut self) -> Option<A> {
1624 if self.n != 0 {
1625 self.n -= 1;
1626 self.iter.next()
1627 } else {
1628 None
1629 }
1630 }
1631
1632 #[inline]
1633 fn size_hint(&self) -> (uint, Option<uint>) {
1634 let (lower, upper) = self.iter.size_hint();
1635
1636 let lower = cmp::min(lower, self.n);
1637
1638 let upper = match upper {
1639 Some(x) if x < self.n => Some(x),
1640 _ => Some(self.n)
1641 };
1642
1643 (lower, upper)
1644 }
1645 }
1646
1647 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> {
1648 #[inline]
1649 fn indexable(&self) -> uint {
1650 cmp::min(self.iter.indexable(), self.n)
1651 }
1652
1653 #[inline]
1654 fn idx(&mut self, index: uint) -> Option<A> {
1655 if index >= self.n {
1656 None
1657 } else {
1658 self.iter.idx(index)
1659 }
1660 }
1661 }
1662
1663
1664 /// An iterator to maintain state while iterating another iterator
1665 pub struct Scan<'a, A, B, T, St> {
1666 iter: T,
1667 f: |&mut St, A|: 'a -> Option,
1668
1669 /// The current internal state to be passed to the closure next.
1670 pub state: St,
1671 }
1672
1673 impl<'a, A, B, T: Iterator<A>, St> Iterator for Scan<'a, A, B, T, St> {
1674 #[inline]
1675 fn next(&mut self) -> Option {
1676 self.iter.next().and_then(|a| (self.f)(&mut self.state, a))
1677 }
1678
1679 #[inline]
1680 fn size_hint(&self) -> (uint, Option<uint>) {
1681 let (_, upper) = self.iter.size_hint();
1682 (0, upper) // can't know a lower bound, due to the scan function
1683 }
1684 }
1685
1686 /// An iterator that maps each element to an iterator,
1687 /// and yields the elements of the produced iterators
1688 ///
1689 pub struct FlatMap<'a, A, T, U> {
1690 iter: T,
1691 f: |A|: 'a -> U,
1692 frontiter: Option,
1693 backiter: Option,
1694 }
1695
1696 impl<'a, A, T: Iterator<A>, B, U: Iterator> Iterator for FlatMap<'a, A, T, U> {
1697 #[inline]
1698 fn next(&mut self) -> Option {
1699 loop {
1700 for inner in self.frontiter.mut_iter() {
1701 for x in *inner {
1702 return Some(x)
1703 }
1704 }
1705 match self.iter.next().map(|x| (self.f)(x)) {
1706 None => return self.backiter.as_mut().and_then(|it| it.next()),
1707 next => self.frontiter = next,
1708 }
1709 }
1710 }
1711
1712 #[inline]
1713 fn size_hint(&self) -> (uint, Option<uint>) {
1714 let (flo, fhi) = self.frontiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
1715 let (blo, bhi) = self.backiter.as_ref().map_or((0, Some(0)), |it| it.size_hint());
1716 let lo = flo.saturating_add(blo);
1717 match (self.iter.size_hint(), fhi, bhi) {
1718 ((0, Some(0)), Some(a), Some(b)) => (lo, a.checked_add(&b)),
1719 _ => (lo, None)
1720 }
1721 }
1722 }
1723
1724 impl<'a,
1725 A, T: DoubleEndedIterator<A>,
1726 B, U: DoubleEndedIterator> DoubleEndedIterator
1727 for FlatMap<'a, A, T, U> {
1728 #[inline]
1729 fn next_back(&mut self) -> Option {
1730 loop {
1731 for inner in self.backiter.mut_iter() {
1732 match inner.next_back() {
1733 None => (),
1734 y => return y
1735 }
1736 }
1737 match self.iter.next_back().map(|x| (self.f)(x)) {
1738 None => return self.frontiter.as_mut().and_then(|it| it.next_back()),
1739 next => self.backiter = next,
1740 }
1741 }
1742 }
1743 }
1744
1745 /// An iterator that yields `None` forever after the underlying iterator
1746 /// yields `None` once.
1747 #[deriving(Clone)]
1748 pub struct Fuse<T> {
1749 iter: T,
1750 done: bool
1751 }
1752
1753 impl<A, T: Iterator<A>> Iterator<A> for Fuse<T> {
1754 #[inline]
1755 fn next(&mut self) -> Option<A> {
1756 if self.done {
1757 None
1758 } else {
1759 match self.iter.next() {
1760 None => {
1761 self.done = true;
1762 None
1763 }
1764 x => x
1765 }
1766 }
1767 }
1768
1769 #[inline]
1770 fn size_hint(&self) -> (uint, Option<uint>) {
1771 if self.done {
1772 (0, Some(0))
1773 } else {
1774 self.iter.size_hint()
1775 }
1776 }
1777 }
1778
1779 impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Fuse<T> {
1780 #[inline]
1781 fn next_back(&mut self) -> Option<A> {
1782 if self.done {
1783 None
1784 } else {
1785 match self.iter.next_back() {
1786 None => {
1787 self.done = true;
1788 None
1789 }
1790 x => x
1791 }
1792 }
1793 }
1794 }
1795
1796 // Allow RandomAccessIterators to be fused without affecting random-access behavior
1797 impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Fuse<T> {
1798 #[inline]
1799 fn indexable(&self) -> uint {
1800 self.iter.indexable()
1801 }
1802
1803 #[inline]
1804 fn idx(&mut self, index: uint) -> Option<A> {
1805 self.iter.idx(index)
1806 }
1807 }
1808
1809 impl<T> Fuse<T> {
1810 /// Resets the fuse such that the next call to .next() or .next_back() will
1811 /// call the underlying iterator again even if it previously returned None.
1812 #[inline]
1813 pub fn reset_fuse(&mut self) {
1814 self.done = false
1815 }
1816 }
1817
1818 /// An iterator that calls a function with a reference to each
1819 /// element before yielding it.
1820 pub struct Inspect<'a, A, T> {
1821 iter: T,
1822 f: |&A|: 'a
1823 }
1824
1825 impl<'a, A, T> Inspect<'a, A, T> {
1826 #[inline]
1827 fn do_inspect(&mut self, elt: Option<A>) -> Option<A> {
1828 match elt {
1829 Some(ref a) => (self.f)(a),
1830 None => ()
1831 }
1832
1833 elt
1834 }
1835 }
1836
1837 impl<'a, A, T: Iterator<A>> Iterator<A> for Inspect<'a, A, T> {
1838 #[inline]
1839 fn next(&mut self) -> Option<A> {
1840 let next = self.iter.next();
1841 self.do_inspect(next)
1842 }
1843
1844 #[inline]
1845 fn size_hint(&self) -> (uint, Option<uint>) {
1846 self.iter.size_hint()
1847 }
1848 }
1849
1850 impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A>
1851 for Inspect<'a, A, T> {
1852 #[inline]
1853 fn next_back(&mut self) -> Option<A> {
1854 let next = self.iter.next_back();
1855 self.do_inspect(next)
1856 }
1857 }
1858
1859 impl<'a, A, T: RandomAccessIterator<A>> RandomAccessIterator<A>
1860 for Inspect<'a, A, T> {
1861 #[inline]
1862 fn indexable(&self) -> uint {
1863 self.iter.indexable()
1864 }
1865
1866 #[inline]
1867 fn idx(&mut self, index: uint) -> Option<A> {
1868 let element = self.iter.idx(index);
1869 self.do_inspect(element)
1870 }
1871 }
1872
1873 /// An iterator which just modifies the contained state throughout iteration.
1874 pub struct Unfold<'a, A, St> {
1875 f: |&mut St|: 'a -> Option<A>,
1876 /// Internal state that will be yielded on the next iteration
1877 pub state: St,
1878 }
1879
1880 impl<'a, A, St> Unfold<'a, A, St> {
1881 /// Creates a new iterator with the specified closure as the "iterator
1882 /// function" and an initial state to eventually pass to the iterator
1883 #[inline]
1884 pub fn new<'a>(initial_state: St, f: |&mut St|: 'a -> Option<A>)
1885 -> Unfold<'a, A, St> {
1886 Unfold {
1887 f: f,
1888 state: initial_state
1889 }
1890 }
1891 }
1892
1893 impl<'a, A, St> Iterator<A> for Unfold<'a, A, St> {
1894 #[inline]
1895 fn next(&mut self) -> Option<A> {
1896 (self.f)(&mut self.state)
1897 }
1898
1899 #[inline]
1900 fn size_hint(&self) -> (uint, Option<uint>) {
1901 // no possible known bounds at this point
1902 (0, None)
1903 }
1904 }
1905
1906 /// An infinite iterator starting at `start` and advancing by `step` with each
1907 /// iteration
1908 #[deriving(Clone)]
1909 pub struct Counter<A> {
1910 /// The current state the counter is at (next value to be yielded)
1911 state: A,
1912 /// The amount that this iterator is stepping by
1913 step: A,
1914 }
1915
1916 /// Creates a new counter with the specified start/step
1917 #[inline]
1918 pub fn count<A>(start: A, step: A) -> Counter<A> {
1919 Counter{state: start, step: step}
1920 }
1921
1922 impl<A: Add<A, A> + Clone> Iterator<A> for Counter<A> {
1923 #[inline]
1924 fn next(&mut self) -> Option<A> {
1925 let result = self.state.clone();
1926 self.state = self.state + self.step;
1927 Some(result)
1928 }
1929
1930 #[inline]
1931 fn size_hint(&self) -> (uint, Option<uint>) {
1932 (uint::MAX, None) // Too bad we can't specify an infinite lower bound
1933 }
1934 }
1935
1936 /// An iterator over the range [start, stop)
1937 #[deriving(Clone)]
1938 pub struct Range<A> {
1939 state: A,
1940 stop: A,
1941 one: A
1942 }
1943
1944 /// Return an iterator over the range [start, stop)
1945 #[inline]
1946 pub fn range<A: Add<A, A> + Ord + Clone + One>(start: A, stop: A) -> Range<A> {
1947 Range{state: start, stop: stop, one: One::one()}
1948 }
1949
1950 // FIXME: #10414: Unfortunate type bound
1951 impl<A: Add<A, A> + Ord + Clone + ToPrimitive> Iterator<A> for Range<A> {
1952 #[inline]
1953 fn next(&mut self) -> Option<A> {
1954 if self.state < self.stop {
1955 let result = self.state.clone();
1956 self.state = self.state + self.one;
1957 Some(result)
1958 } else {
1959 None
1960 }
1961 }
1962
1963 #[inline]
1964 fn size_hint(&self) -> (uint, Option<uint>) {
1965 // This first checks if the elements are representable as i64. If they aren't, try u64 (to
1966 // handle cases like range(huge, huger)). We don't use uint/int because the difference of
1967 // the i64/u64 might lie within their range.
1968 let bound = match self.state.to_i64() {
1969 Some(a) => {
1970 let sz = self.stop.to_i64().map(|b| b.checked_sub(&a));
1971 match sz {
1972 Some(Some(bound)) => bound.to_uint(),
1973 _ => None,
1974 }
1975 },
1976 None => match self.state.to_u64() {
1977 Some(a) => {
1978 let sz = self.stop.to_u64().map(|b| b.checked_sub(&a));
1979 match sz {
1980 Some(Some(bound)) => bound.to_uint(),
1981 _ => None
1982 }
1983 },
1984 None => None
1985 }
1986 };
1987
1988 match bound {
1989 Some(b) => (b, Some(b)),
1990 // Standard fallback for unbounded/unrepresentable bounds
1991 None => (0, None)
1992 }
1993 }
1994 }
1995
1996 /// `Int` is required to ensure the range will be the same regardless of
1997 /// the direction it is consumed.
1998 impl<A: Int + Ord + Clone + ToPrimitive> DoubleEndedIterator<A> for Range<A> {
1999 #[inline]
2000 fn next_back(&mut self) -> Option<A> {
2001 if self.stop > self.state {
2002 self.stop = self.stop - self.one;
2003 Some(self.stop.clone())
2004 } else {
2005 None
2006 }
2007 }
2008 }
2009
2010 /// An iterator over the range [start, stop]
2011 #[deriving(Clone)]
2012 pub struct RangeInclusive<A> {
2013 range: Range<A>,
2014 done: bool,
2015 }
2016
2017 /// Return an iterator over the range [start, stop]
2018 #[inline]
2019 pub fn range_inclusive<A: Add<A, A> + Ord + Clone + One + ToPrimitive>(start: A, stop: A)
2020 -> RangeInclusive<A> {
2021 RangeInclusive{range: range(start, stop), done: false}
2022 }
2023
2024 impl<A: Add<A, A> + Ord + Clone + ToPrimitive> Iterator<A> for RangeInclusive<A> {
2025 #[inline]
2026 fn next(&mut self) -> Option<A> {
2027 match self.range.next() {
2028 Some(x) => Some(x),
2029 None => {
2030 if !self.done && self.range.state == self.range.stop {
2031 self.done = true;
2032 Some(self.range.stop.clone())
2033 } else {
2034 None
2035 }
2036 }
2037 }
2038 }
2039
2040 #[inline]
2041 fn size_hint(&self) -> (uint, Option<uint>) {
2042 let (lo, hi) = self.range.size_hint();
2043 if self.done {
2044 (lo, hi)
2045 } else {
2046 let lo = lo.saturating_add(1);
2047 let hi = match hi {
2048 Some(x) => x.checked_add(&1),
2049 None => None
2050 };
2051 (lo, hi)
2052 }
2053 }
2054 }
2055
2056 impl<A: Sub<A, A> + Int + Ord + Clone + ToPrimitive> DoubleEndedIterator<A>
2057 for RangeInclusive<A> {
2058 #[inline]
2059 fn next_back(&mut self) -> Option<A> {
2060 if self.range.stop > self.range.state {
2061 let result = self.range.stop.clone();
2062 self.range.stop = self.range.stop - self.range.one;
2063 Some(result)
2064 } else if !self.done && self.range.state == self.range.stop {
2065 self.done = true;
2066 Some(self.range.stop.clone())
2067 } else {
2068 None
2069 }
2070 }
2071 }
2072
2073 /// An iterator over the range [start, stop) by `step`. It handles overflow by stopping.
2074 #[deriving(Clone)]
2075 pub struct RangeStep<A> {
2076 state: A,
2077 stop: A,
2078 step: A,
2079 rev: bool,
2080 }
2081
2082 /// Return an iterator over the range [start, stop) by `step`. It handles overflow by stopping.
2083 #[inline]
2084 pub fn range_step<A: CheckedAdd + Ord + Clone + Zero>(start: A, stop: A, step: A) -> RangeStep<A> {
2085 let rev = step < Zero::zero();
2086 RangeStep{state: start, stop: stop, step: step, rev: rev}
2087 }
2088
2089 impl<A: CheckedAdd + Ord + Clone> Iterator<A> for RangeStep<A> {
2090 #[inline]
2091 fn next(&mut self) -> Option<A> {
2092 if (self.rev && self.state > self.stop) || (!self.rev && self.state < self.stop) {
2093 let result = self.state.clone();
2094 match self.state.checked_add(&self.step) {
2095 Some(x) => self.state = x,
2096 None => self.state = self.stop.clone()
2097 }
2098 Some(result)
2099 } else {
2100 None
2101 }
2102 }
2103 }
2104
2105 /// An iterator over the range [start, stop] by `step`. It handles overflow by stopping.
2106 #[deriving(Clone)]
2107 pub struct RangeStepInclusive<A> {
2108 state: A,
2109 stop: A,
2110 step: A,
2111 rev: bool,
2112 done: bool,
2113 }
2114
2115 /// Return an iterator over the range [start, stop] by `step`. It handles overflow by stopping.
2116 #[inline]
2117 pub fn range_step_inclusive<A: CheckedAdd + Ord + Clone + Zero>(start: A, stop: A,
2118 step: A) -> RangeStepInclusive<A> {
2119 let rev = step < Zero::zero();
2120 RangeStepInclusive{state: start, stop: stop, step: step, rev: rev, done: false}
2121 }
2122
2123 impl<A: CheckedAdd + Ord + Clone + Eq> Iterator<A> for RangeStepInclusive<A> {
2124 #[inline]
2125 fn next(&mut self) -> Option<A> {
2126 if !self.done && ((self.rev && self.state >= self.stop) ||
2127 (!self.rev && self.state <= self.stop)) {
2128 let result = self.state.clone();
2129 match self.state.checked_add(&self.step) {
2130 Some(x) => self.state = x,
2131 None => self.done = true
2132 }
2133 Some(result)
2134 } else {
2135 None
2136 }
2137 }
2138 }
2139
2140 /// An iterator that repeats an element endlessly
2141 #[deriving(Clone)]
2142 pub struct Repeat<A> {
2143 element: A
2144 }
2145
2146 impl<A: Clone> Repeat<A> {
2147 /// Create a new `Repeat` that endlessly repeats the element `elt`.
2148 #[inline]
2149 pub fn new(elt: A) -> Repeat<A> {
2150 Repeat{element: elt}
2151 }
2152 }
2153
2154 impl<A: Clone> Iterator<A> for Repeat<A> {
2155 #[inline]
2156 fn next(&mut self) -> Option<A> { self.idx(0) }
2157 #[inline]
2158 fn size_hint(&self) -> (uint, Option<uint>) { (uint::MAX, None) }
2159 }
2160
2161 impl<A: Clone> DoubleEndedIterator<A> for Repeat<A> {
2162 #[inline]
2163 fn next_back(&mut self) -> Option<A> { self.idx(0) }
2164 }
2165
2166 impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
2167 #[inline]
2168 fn indexable(&self) -> uint { uint::MAX }
2169 #[inline]
2170 fn idx(&mut self, _: uint) -> Option<A> { Some(self.element.clone()) }
2171 }
2172
2173 /// Functions for lexicographical ordering of sequences.
2174 ///
2175 /// Lexicographical ordering through `<`, `<=`, `>=`, `>` requires
2176 /// that the elements implement both `Eq` and `Ord`.
2177 ///
2178 /// If two sequences are equal up until the point where one ends,
2179 /// the shorter sequence compares less.
2180 pub mod order {
2181 use cmp;
2182 use cmp::{TotalEq, TotalOrd, Ord, Eq};
2183 use option::{Some, None};
2184 use super::Iterator;
2185
2186 /// Compare `a` and `b` for equality using `TotalEq`
2187 pub fn equals<A: TotalEq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2188 loop {
2189 match (a.next(), b.next()) {
2190 (None, None) => return true,
2191 (None, _) | (_, None) => return false,
2192 (Some(x), Some(y)) => if x != y { return false },
2193 }
2194 }
2195 }
2196
2197 /// Order `a` and `b` lexicographically using `TotalOrd`
2198 pub fn cmp<A: TotalOrd, T: Iterator<A>>(mut a: T, mut b: T) -> cmp::Ordering {
2199 loop {
2200 match (a.next(), b.next()) {
2201 (None, None) => return cmp::Equal,
2202 (None, _ ) => return cmp::Less,
2203 (_ , None) => return cmp::Greater,
2204 (Some(x), Some(y)) => match x.cmp(&y) {
2205 cmp::Equal => (),
2206 non_eq => return non_eq,
2207 },
2208 }
2209 }
2210 }
2211
2212 /// Compare `a` and `b` for equality (Using partial equality, `Eq`)
2213 pub fn eq<A: Eq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2214 loop {
2215 match (a.next(), b.next()) {
2216 (None, None) => return true,
2217 (None, _) | (_, None) => return false,
2218 (Some(x), Some(y)) => if !x.eq(&y) { return false },
2219 }
2220 }
2221 }
2222
2223 /// Compare `a` and `b` for nonequality (Using partial equality, `Eq`)
2224 pub fn ne<A: Eq, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2225 loop {
2226 match (a.next(), b.next()) {
2227 (None, None) => return false,
2228 (None, _) | (_, None) => return true,
2229 (Some(x), Some(y)) => if x.ne(&y) { return true },
2230 }
2231 }
2232 }
2233
2234 /// Return `a` < `b` lexicographically (Using partial order, `Ord`)
2235 pub fn lt<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2236 loop {
2237 match (a.next(), b.next()) {
2238 (None, None) => return false,
2239 (None, _ ) => return true,
2240 (_ , None) => return false,
2241 (Some(x), Some(y)) => if x.ne(&y) { return x.lt(&y) },
2242 }
2243 }
2244 }
2245
2246 /// Return `a` <= `b` lexicographically (Using partial order, `Ord`)
2247 pub fn le<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2248 loop {
2249 match (a.next(), b.next()) {
2250 (None, None) => return true,
2251 (None, _ ) => return true,
2252 (_ , None) => return false,
2253 (Some(x), Some(y)) => if x.ne(&y) { return x.le(&y) },
2254 }
2255 }
2256 }
2257
2258 /// Return `a` > `b` lexicographically (Using partial order, `Ord`)
2259 pub fn gt<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2260 loop {
2261 match (a.next(), b.next()) {
2262 (None, None) => return false,
2263 (None, _ ) => return false,
2264 (_ , None) => return true,
2265 (Some(x), Some(y)) => if x.ne(&y) { return x.gt(&y) },
2266 }
2267 }
2268 }
2269
2270 /// Return `a` >= `b` lexicographically (Using partial order, `Ord`)
2271 pub fn ge<A: Ord, T: Iterator<A>>(mut a: T, mut b: T) -> bool {
2272 loop {
2273 match (a.next(), b.next()) {
2274 (None, None) => return true,
2275 (None, _ ) => return false,
2276 (_ , None) => return true,
2277 (Some(x), Some(y)) => if x.ne(&y) { return x.ge(&y) },
2278 }
2279 }
2280 }
2281
2282 #[test]
2283 fn test_lt() {
2284 use slice::ImmutableVector;
2285
2286 let empty: [int, ..0] = [];
2287 let xs = [1,2,3];
2288 let ys = [1,2,0];
2289
2290 assert!(!lt(xs.iter(), ys.iter()));
2291 assert!(!le(xs.iter(), ys.iter()));
2292 assert!( gt(xs.iter(), ys.iter()));
2293 assert!( ge(xs.iter(), ys.iter()));
2294
2295 assert!( lt(ys.iter(), xs.iter()));
2296 assert!( le(ys.iter(), xs.iter()));
2297 assert!(!gt(ys.iter(), xs.iter()));
2298 assert!(!ge(ys.iter(), xs.iter()));
2299
2300 assert!( lt(empty.iter(), xs.iter()));
2301 assert!( le(empty.iter(), xs.iter()));
2302 assert!(!gt(empty.iter(), xs.iter()));
2303 assert!(!ge(empty.iter(), xs.iter()));
2304
2305 // Sequence with NaN
2306 let u = [1.0, 2.0];
2307 let v = [0.0/0.0, 3.0];
2308
2309 assert!(!lt(u.iter(), v.iter()));
2310 assert!(!le(u.iter(), v.iter()));
2311 assert!(!gt(u.iter(), v.iter()));
2312 assert!(!ge(u.iter(), v.iter()));
2313
2314 let a = [0.0/0.0];
2315 let b = [1.0];
2316 let c = [2.0];
2317
2318 assert!(lt(a.iter(), b.iter()) == (a[0] < b[0]));
2319 assert!(le(a.iter(), b.iter()) == (a[0] <= b[0]));
2320 assert!(gt(a.iter(), b.iter()) == (a[0] > b[0]));
2321 assert!(ge(a.iter(), b.iter()) == (a[0] >= b[0]));
2322
2323 assert!(lt(c.iter(), b.iter()) == (c[0] < b[0]));
2324 assert!(le(c.iter(), b.iter()) == (c[0] <= b[0]));
2325 assert!(gt(c.iter(), b.iter()) == (c[0] > b[0]));
2326 assert!(ge(c.iter(), b.iter()) == (c[0] >= b[0]));
2327 }
2328 }
2329
2330 #[cfg(test)]
2331 mod tests {
2332 use realstd::prelude::*;
2333 use realstd::iter::*;
2334 use realstd::num;
2335
2336 use cmp;
2337 use owned::Box;
2338 use uint;
2339
2340 #[test]
2341 fn test_counter_from_iter() {
2342 let it = count(0, 5).take(10);
2343 let xs: Vec<int> = FromIterator::from_iter(it);
2344 assert_eq!(xs, vec![0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
2345 }
2346
2347 #[test]
2348 fn test_iterator_chain() {
2349 let xs = [0u, 1, 2, 3, 4, 5];
2350 let ys = [30u, 40, 50, 60];
2351 let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
2352 let mut it = xs.iter().chain(ys.iter());
2353 let mut i = 0;
2354 for &x in it {
2355 assert_eq!(x, expected[i]);
2356 i += 1;
2357 }
2358 assert_eq!(i, expected.len());
2359
2360 let ys = count(30u, 10).take(4);
2361 let mut it = xs.iter().map(|&x| x).chain(ys);
2362 let mut i = 0;
2363 for x in it {
2364 assert_eq!(x, expected[i]);
2365 i += 1;
2366 }
2367 assert_eq!(i, expected.len());
2368 }
2369
2370 #[test]
2371 fn test_filter_map() {
2372 let mut it = count(0u, 1u).take(10)
2373 .filter_map(|x| if x % 2 == 0 { Some(x*x) } else { None });
2374 assert_eq!(it.collect::<Vec<uint>>(), vec![0*0, 2*2, 4*4, 6*6, 8*8]);
2375 }
2376
2377 #[test]
2378 fn test_iterator_enumerate() {
2379 let xs = [0u, 1, 2, 3, 4, 5];
2380 let mut it = xs.iter().enumerate();
2381 for (i, &x) in it {
2382 assert_eq!(i, x);
2383 }
2384 }
2385
2386 #[test]
2387 fn test_iterator_peekable() {
2388 let xs = box [0u, 1, 2, 3, 4, 5];
2389 let mut it = xs.iter().map(|&x|x).peekable();
2390 assert_eq!(it.peek().unwrap(), &0);
2391 assert_eq!(it.next().unwrap(), 0);
2392 assert_eq!(it.next().unwrap(), 1);
2393 assert_eq!(it.next().unwrap(), 2);
2394 assert_eq!(it.peek().unwrap(), &3);
2395 assert_eq!(it.peek().unwrap(), &3);
2396 assert_eq!(it.next().unwrap(), 3);
2397 assert_eq!(it.next().unwrap(), 4);
2398 assert_eq!(it.peek().unwrap(), &5);
2399 assert_eq!(it.next().unwrap(), 5);
2400 assert!(it.peek().is_none());
2401 assert!(it.next().is_none());
2402 }
2403
2404 #[test]
2405 fn test_iterator_take_while() {
2406 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2407 let ys = [0u, 1, 2, 3, 5, 13];
2408 let mut it = xs.iter().take_while(|&x| *x < 15u);
2409 let mut i = 0;
2410 for &x in it {
2411 assert_eq!(x, ys[i]);
2412 i += 1;
2413 }
2414 assert_eq!(i, ys.len());
2415 }
2416
2417 #[test]
2418 fn test_iterator_skip_while() {
2419 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2420 let ys = [15, 16, 17, 19];
2421 let mut it = xs.iter().skip_while(|&x| *x < 15u);
2422 let mut i = 0;
2423 for &x in it {
2424 assert_eq!(x, ys[i]);
2425 i += 1;
2426 }
2427 assert_eq!(i, ys.len());
2428 }
2429
2430 #[test]
2431 fn test_iterator_skip() {
2432 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19, 20, 30];
2433 let ys = [13, 15, 16, 17, 19, 20, 30];
2434 let mut it = xs.iter().skip(5);
2435 let mut i = 0;
2436 for &x in it {
2437 assert_eq!(x, ys[i]);
2438 i += 1;
2439 }
2440 assert_eq!(i, ys.len());
2441 }
2442
2443 #[test]
2444 fn test_iterator_take() {
2445 let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
2446 let ys = [0u, 1, 2, 3, 5];
2447 let mut it = xs.iter().take(5);
2448 let mut i = 0;
2449 for &x in it {
2450 assert_eq!(x, ys[i]);
2451 i += 1;
2452 }
2453 assert_eq!(i, ys.len());
2454 }
2455
2456 #[test]
2457 fn test_iterator_scan() {
2458 // test the type inference
2459 fn add(old: &mut int, new: &uint) -> Option<f64> {
2460 *old += *new as int;
2461 Some(*old as f64)
2462 }
2463 let xs = [0u, 1, 2, 3, 4];
2464 let ys = [0f64, 1.0, 3.0, 6.0, 10.0];
2465
2466 let mut it = xs.iter().scan(0, add);
2467 let mut i = 0;
2468 for x in it {
2469 assert_eq!(x, ys[i]);
2470 i += 1;
2471 }
2472 assert_eq!(i, ys.len());
2473 }
2474
2475 #[test]
2476 fn test_iterator_flat_map() {
2477 let xs = [0u, 3, 6];
2478 let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8];
2479 let mut it = xs.iter().flat_map(|&x| count(x, 1).take(3));
2480 let mut i = 0;
2481 for x in it {
2482 assert_eq!(x, ys[i]);
2483 i += 1;
2484 }
2485 assert_eq!(i, ys.len());
2486 }
2487
2488 #[test]
2489 fn test_inspect() {
2490 let xs = [1u, 2, 3, 4];
2491 let mut n = 0;
2492
2493 let ys = xs.iter()
2494 .map(|&x| x)
2495 .inspect(|_| n += 1)
2496 .collect::<Vec<uint>>();
2497
2498 assert_eq!(n, xs.len());
2499 assert_eq!(xs.as_slice(), ys.as_slice());
2500 }
2501
2502 #[test]
2503 fn test_unfoldr() {
2504 fn count(st: &mut uint) -> Option<uint> {
2505 if *st < 10 {
2506 let ret = Some(*st);
2507 *st += 1;
2508 ret
2509 } else {
2510 None
2511 }
2512 }
2513
2514 let mut it = Unfold::new(0, count);
2515 let mut i = 0;
2516 for counted in it {
2517 assert_eq!(counted, i);
2518 i += 1;
2519 }
2520 assert_eq!(i, 10);
2521 }
2522
2523 #[test]
2524 fn test_cycle() {
2525 let cycle_len = 3;
2526 let it = count(0u, 1).take(cycle_len).cycle();
2527 assert_eq!(it.size_hint(), (uint::MAX, None));
2528 for (i, x) in it.take(100).enumerate() {
2529 assert_eq!(i % cycle_len, x);
2530 }
2531
2532 let mut it = count(0u, 1).take(0).cycle();
2533 assert_eq!(it.size_hint(), (0, Some(0)));
2534 assert_eq!(it.next(), None);
2535 }
2536
2537 #[test]
2538 fn test_iterator_nth() {
2539 let v = &[0, 1, 2, 3, 4];
2540 for i in range(0u, v.len()) {
2541 assert_eq!(v.iter().nth(i).unwrap(), &v[i]);
2542 }
2543 }
2544
2545 #[test]
2546 fn test_iterator_last() {
2547 let v = &[0, 1, 2, 3, 4];
2548 assert_eq!(v.iter().last().unwrap(), &4);
2549 assert_eq!(v.slice(0, 1).iter().last().unwrap(), &0);
2550 }
2551
2552 #[test]
2553 fn test_iterator_len() {
2554 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2555 assert_eq!(v.slice(0, 4).iter().len(), 4);
2556 assert_eq!(v.slice(0, 10).iter().len(), 10);
2557 assert_eq!(v.slice(0, 0).iter().len(), 0);
2558 }
2559
2560 #[test]
2561 fn test_iterator_sum() {
2562 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2563 assert_eq!(v.slice(0, 4).iter().map(|&x| x).sum(), 6);
2564 assert_eq!(v.iter().map(|&x| x).sum(), 55);
2565 assert_eq!(v.slice(0, 0).iter().map(|&x| x).sum(), 0);
2566 }
2567
2568 #[test]
2569 fn test_iterator_product() {
2570 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2571 assert_eq!(v.slice(0, 4).iter().map(|&x| x).product(), 0);
2572 assert_eq!(v.slice(1, 5).iter().map(|&x| x).product(), 24);
2573 assert_eq!(v.slice(0, 0).iter().map(|&x| x).product(), 1);
2574 }
2575
2576 #[test]
2577 fn test_iterator_max() {
2578 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2579 assert_eq!(v.slice(0, 4).iter().map(|&x| x).max(), Some(3));
2580 assert_eq!(v.iter().map(|&x| x).max(), Some(10));
2581 assert_eq!(v.slice(0, 0).iter().map(|&x| x).max(), None);
2582 }
2583
2584 #[test]
2585 fn test_iterator_min() {
2586 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
2587 assert_eq!(v.slice(0, 4).iter().map(|&x| x).min(), Some(0));
2588 assert_eq!(v.iter().map(|&x| x).min(), Some(0));
2589 assert_eq!(v.slice(0, 0).iter().map(|&x| x).min(), None);
2590 }
2591
2592 #[test]
2593 fn test_iterator_size_hint() {
2594 let c = count(0, 1);
2595 let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
2596 let v2 = &[10, 11, 12];
2597 let vi = v.iter();
2598
2599 assert_eq!(c.size_hint(), (uint::MAX, None));
2600 assert_eq!(vi.size_hint(), (10, Some(10)));
2601
2602 assert_eq!(c.take(5).size_hint(), (5, Some(5)));
2603 assert_eq!(c.skip(5).size_hint().val1(), None);
2604 assert_eq!(c.take_while(|_| false).size_hint(), (0, None));
2605 assert_eq!(c.skip_while(|_| false).size_hint(), (0, None));
2606 assert_eq!(c.enumerate().size_hint(), (uint::MAX, None));
2607 assert_eq!(c.chain(vi.map(|&i| i)).size_hint(), (uint::MAX, None));
2608 assert_eq!(c.zip(vi).size_hint(), (10, Some(10)));
2609 assert_eq!(c.scan(0, |_,_| Some(0)).size_hint(), (0, None));
2610 assert_eq!(c.filter(|_| false).size_hint(), (0, None));
2611 assert_eq!(c.map(|_| 0).size_hint(), (uint::MAX, None));
2612 assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None));
2613
2614 assert_eq!(vi.take(5).size_hint(), (5, Some(5)));
2615 assert_eq!(vi.take(12).size_hint(), (10, Some(10)));
2616 assert_eq!(vi.skip(3).size_hint(), (7, Some(7)));
2617 assert_eq!(vi.skip(12).size_hint(), (0, Some(0)));
2618 assert_eq!(vi.take_while(|_| false).size_hint(), (0, Some(10)));
2619 assert_eq!(vi.skip_while(|_| false).size_hint(), (0, Some(10)));
2620 assert_eq!(vi.enumerate().size_hint(), (10, Some(10)));
2621 assert_eq!(vi.chain(v2.iter()).size_hint(), (13, Some(13)));
2622 assert_eq!(vi.zip(v2.iter()).size_hint(), (3, Some(3)));
2623 assert_eq!(vi.scan(0, |_,_| Some(0)).size_hint(), (0, Some(10)));
2624 assert_eq!(vi.filter(|_| false).size_hint(), (0, Some(10)));
2625 assert_eq!(vi.map(|i| i+1).size_hint(), (10, Some(10)));
2626 assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10)));
2627 }
2628
2629 #[test]
2630 fn test_collect() {
2631 let a = vec![1, 2, 3, 4, 5];
2632 let b: Vec<int> = a.iter().map(|&x| x).collect();
2633 assert_eq!(a, b);
2634 }
2635
2636 #[test]
2637 fn test_all() {
2638 let v: Box<&[int]> = box &[1, 2, 3, 4, 5];
2639 assert!(v.iter().all(|&x| x < 10));
2640 assert!(!v.iter().all(|&x| x % 2 == 0));
2641 assert!(!v.iter().all(|&x| x > 100));
2642 assert!(v.slice(0, 0).iter().all(|_| fail!()));
2643 }
2644
2645 #[test]
2646 fn test_any() {
2647 let v: Box<&[int]> = box &[1, 2, 3, 4, 5];
2648 assert!(v.iter().any(|&x| x < 10));
2649 assert!(v.iter().any(|&x| x % 2 == 0));
2650 assert!(!v.iter().any(|&x| x > 100));
2651 assert!(!v.slice(0, 0).iter().any(|_| fail!()));
2652 }
2653
2654 #[test]
2655 fn test_find() {
2656 let v: &[int] = &[1, 3, 9, 27, 103, 14, 11];
2657 assert_eq!(*v.iter().find(|x| *x & 1 == 0).unwrap(), 14);
2658 assert_eq!(*v.iter().find(|x| *x % 3 == 0).unwrap(), 3);
2659 assert!(v.iter().find(|x| *x % 12 == 0).is_none());
2660 }
2661
2662 #[test]
2663 fn test_position() {
2664 let v = &[1, 3, 9, 27, 103, 14, 11];
2665 assert_eq!(v.iter().position(|x| *x & 1 == 0).unwrap(), 5);
2666 assert_eq!(v.iter().position(|x| *x % 3 == 0).unwrap(), 1);
2667 assert!(v.iter().position(|x| *x % 12 == 0).is_none());
2668 }
2669
2670 #[test]
2671 fn test_count() {
2672 let xs = &[1, 2, 2, 1, 5, 9, 0, 2];
2673 assert_eq!(xs.iter().count(|x| *x == 2), 3);
2674 assert_eq!(xs.iter().count(|x| *x == 5), 1);
2675 assert_eq!(xs.iter().count(|x| *x == 95), 0);
2676 }
2677
2678 #[test]
2679 fn test_max_by() {
2680 let xs: &[int] = &[-3, 0, 1, 5, -10];
2681 assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
2682 }
2683
2684 #[test]
2685 fn test_min_by() {
2686 let xs: &[int] = &[-3, 0, 1, 5, -10];
2687 assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
2688 }
2689
2690 #[test]
2691 fn test_by_ref() {
2692 let mut xs = range(0, 10);
2693 // sum the first five values
2694 let partial_sum = xs.by_ref().take(5).fold(0, |a, b| a + b);
2695 assert_eq!(partial_sum, 10);
2696 assert_eq!(xs.next(), Some(5));
2697 }
2698
2699 #[test]
2700 fn test_rev() {
2701 let xs = [2, 4, 6, 8, 10, 12, 14, 16];
2702 let mut it = xs.iter();
2703 it.next();
2704 it.next();
2705 assert_eq!(it.rev().map(|&x| x).collect::<Vec<int>>(), vec![16, 14, 12, 10, 8, 6]);
2706 }
2707
2708 #[test]
2709 fn test_double_ended_map() {
2710 let xs = [1, 2, 3, 4, 5, 6];
2711 let mut it = xs.iter().map(|&x| x * -1);
2712 assert_eq!(it.next(), Some(-1));
2713 assert_eq!(it.next(), Some(-2));
2714 assert_eq!(it.next_back(), Some(-6));
2715 assert_eq!(it.next_back(), Some(-5));
2716 assert_eq!(it.next(), Some(-3));
2717 assert_eq!(it.next_back(), Some(-4));
2718 assert_eq!(it.next(), None);
2719 }
2720
2721 #[test]
2722 fn test_double_ended_enumerate() {
2723 let xs = [1, 2, 3, 4, 5, 6];
2724 let mut it = xs.iter().map(|&x| x).enumerate();
2725 assert_eq!(it.next(), Some((0, 1)));
2726 assert_eq!(it.next(), Some((1, 2)));
2727 assert_eq!(it.next_back(), Some((5, 6)));
2728 assert_eq!(it.next_back(), Some((4, 5)));
2729 assert_eq!(it.next_back(), Some((3, 4)));
2730 assert_eq!(it.next_back(), Some((2, 3)));
2731 assert_eq!(it.next(), None);
2732 }
2733
2734 #[test]
2735 fn test_double_ended_zip() {
2736 let xs = [1, 2, 3, 4, 5, 6];
2737 let ys = [1, 2, 3, 7];
2738 let a = xs.iter().map(|&x| x);
2739 let b = ys.iter().map(|&x| x);
2740 let mut it = a.zip(b);
2741 assert_eq!(it.next(), Some((1, 1)));
2742 assert_eq!(it.next(), Some((2, 2)));
2743 assert_eq!(it.next_back(), Some((4, 7)));
2744 assert_eq!(it.next_back(), Some((3, 3)));
2745 assert_eq!(it.next(), None);
2746 }
2747
2748 #[test]
2749 fn test_double_ended_filter() {
2750 let xs = [1, 2, 3, 4, 5, 6];
2751 let mut it = xs.iter().filter(|&x| *x & 1 == 0);
2752 assert_eq!(it.next_back().unwrap(), &6);
2753 assert_eq!(it.next_back().unwrap(), &4);
2754 assert_eq!(it.next().unwrap(), &2);
2755 assert_eq!(it.next_back(), None);
2756 }
2757
2758 #[test]
2759 fn test_double_ended_filter_map() {
2760 let xs = [1, 2, 3, 4, 5, 6];
2761 let mut it = xs.iter().filter_map(|&x| if x & 1 == 0 { Some(x * 2) } else { None });
2762 assert_eq!(it.next_back().unwrap(), 12);
2763 assert_eq!(it.next_back().unwrap(), 8);
2764 assert_eq!(it.next().unwrap(), 4);
2765 assert_eq!(it.next_back(), None);
2766 }
2767
2768 #[test]
2769 fn test_double_ended_chain() {
2770 let xs = [1, 2, 3, 4, 5];
2771 let ys = box [7, 9, 11];
2772 let mut it = xs.iter().chain(ys.iter()).rev();
2773 assert_eq!(it.next().unwrap(), &11)
2774 assert_eq!(it.next().unwrap(), &9)
2775 assert_eq!(it.next_back().unwrap(), &1)
2776 assert_eq!(it.next_back().unwrap(), &2)
2777 assert_eq!(it.next_back().unwrap(), &3)
2778 assert_eq!(it.next_back().unwrap(), &4)
2779 assert_eq!(it.next_back().unwrap(), &5)
2780 assert_eq!(it.next_back().unwrap(), &7)
2781 assert_eq!(it.next_back(), None)
2782 }
2783
2784 #[test]
2785 fn test_rposition() {
2786 fn f(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'b' }
2787 fn g(xy: &(int, char)) -> bool { let (_x, y) = *xy; y == 'd' }
2788 let v = box [(0, 'a'), (1, 'b'), (2, 'c'), (3, 'b')];
2789
2790 assert_eq!(v.iter().rposition(f), Some(3u));
2791 assert!(v.iter().rposition(g).is_none());
2792 }
2793
2794 #[test]
2795 #[should_fail]
2796 fn test_rposition_fail() {
2797 let v = [(box 0, @0), (box 0, @0), (box 0, @0), (box 0, @0)];
2798 let mut i = 0;
2799 v.iter().rposition(|_elt| {
2800 if i == 2 {
2801 fail!()
2802 }
2803 i += 1;
2804 false
2805 });
2806 }
2807
2808
2809 #[cfg(test)]
2810 fn check_randacc_iter<A: Eq, T: Clone + RandomAccessIterator<A>>(a: T, len: uint)
2811 {
2812 let mut b = a.clone();
2813 assert_eq!(len, b.indexable());
2814 let mut n = 0;
2815 for (i, elt) in a.enumerate() {
2816 assert!(Some(elt) == b.idx(i));
2817 n += 1;
2818 }
2819 assert_eq!(n, len);
2820 assert!(None == b.idx(n));
2821 // call recursively to check after picking off an element
2822 if len > 0 {
2823 b.next();
2824 check_randacc_iter(b, len-1);
2825 }
2826 }
2827
2828
2829 #[test]
2830 fn test_double_ended_flat_map() {
2831 let u = [0u,1];
2832 let v = [5,6,7,8];
2833 let mut it = u.iter().flat_map(|x| v.slice(*x, v.len()).iter());
2834 assert_eq!(it.next_back().unwrap(), &8);
2835 assert_eq!(it.next().unwrap(), &5);
2836 assert_eq!(it.next_back().unwrap(), &7);
2837 assert_eq!(it.next_back().unwrap(), &6);
2838 assert_eq!(it.next_back().unwrap(), &8);
2839 assert_eq!(it.next().unwrap(), &6);
2840 assert_eq!(it.next_back().unwrap(), &7);
2841 assert_eq!(it.next_back(), None);
2842 assert_eq!(it.next(), None);
2843 assert_eq!(it.next_back(), None);
2844 }
2845
2846 #[test]
2847 fn test_random_access_chain() {
2848 let xs = [1, 2, 3, 4, 5];
2849 let ys = box [7, 9, 11];
2850 let mut it = xs.iter().chain(ys.iter());
2851 assert_eq!(it.idx(0).unwrap(), &1);
2852 assert_eq!(it.idx(5).unwrap(), &7);
2853 assert_eq!(it.idx(7).unwrap(), &11);
2854 assert!(it.idx(8).is_none());
2855
2856 it.next();
2857 it.next();
2858 it.next_back();
2859
2860 assert_eq!(it.idx(0).unwrap(), &3);
2861 assert_eq!(it.idx(4).unwrap(), &9);
2862 assert!(it.idx(6).is_none());
2863
2864 check_randacc_iter(it, xs.len() + ys.len() - 3);
2865 }
2866
2867 #[test]
2868 fn test_random_access_enumerate() {
2869 let xs = [1, 2, 3, 4, 5];
2870 check_randacc_iter(xs.iter().enumerate(), xs.len());
2871 }
2872
2873 #[test]
2874 fn test_random_access_rev() {
2875 let xs = [1, 2, 3, 4, 5];
2876 check_randacc_iter(xs.iter().rev(), xs.len());
2877 let mut it = xs.iter().rev();
2878 it.next();
2879 it.next_back();
2880 it.next();
2881 check_randacc_iter(it, xs.len() - 3);
2882 }
2883
2884 #[test]
2885 fn test_random_access_zip() {
2886 let xs = [1, 2, 3, 4, 5];
2887 let ys = [7, 9, 11];
2888 check_randacc_iter(xs.iter().zip(ys.iter()), cmp::min(xs.len(), ys.len()));
2889 }
2890
2891 #[test]
2892 fn test_random_access_take() {
2893 let xs = [1, 2, 3, 4, 5];
2894 let empty: &[int] = [];
2895 check_randacc_iter(xs.iter().take(3), 3);
2896 check_randacc_iter(xs.iter().take(20), xs.len());
2897 check_randacc_iter(xs.iter().take(0), 0);
2898 check_randacc_iter(empty.iter().take(2), 0);
2899 }
2900
2901 #[test]
2902 fn test_random_access_skip() {
2903 let xs = [1, 2, 3, 4, 5];
2904 let empty: &[int] = [];
2905 check_randacc_iter(xs.iter().skip(2), xs.len() - 2);
2906 check_randacc_iter(empty.iter().skip(2), 0);
2907 }
2908
2909 #[test]
2910 fn test_random_access_inspect() {
2911 let xs = [1, 2, 3, 4, 5];
2912
2913 // test .map and .inspect that don't implement Clone
2914 let mut it = xs.iter().inspect(|_| {});
2915 assert_eq!(xs.len(), it.indexable());
2916 for (i, elt) in xs.iter().enumerate() {
2917 assert_eq!(Some(elt), it.idx(i));
2918 }
2919
2920 }
2921
2922 #[test]
2923 fn test_random_access_map() {
2924 let xs = [1, 2, 3, 4, 5];
2925
2926 let mut it = xs.iter().map(|x| *x);
2927 assert_eq!(xs.len(), it.indexable());
2928 for (i, elt) in xs.iter().enumerate() {
2929 assert_eq!(Some(*elt), it.idx(i));
2930 }
2931 }
2932
2933 #[test]
2934 fn test_random_access_cycle() {
2935 let xs = [1, 2, 3, 4, 5];
2936 let empty: &[int] = [];
2937 check_randacc_iter(xs.iter().cycle().take(27), 27);
2938 check_randacc_iter(empty.iter().cycle(), 0);
2939 }
2940
2941 #[test]
2942 fn test_double_ended_range() {
2943 assert_eq!(range(11i, 14).rev().collect::<Vec<int>>(), vec![13i, 12, 11]);
2944 for _ in range(10i, 0).rev() {
2945 fail!("unreachable");
2946 }
2947
2948 assert_eq!(range(11u, 14).rev().collect::<Vec<uint>>(), vec![13u, 12, 11]);
2949 for _ in range(10u, 0).rev() {
2950 fail!("unreachable");
2951 }
2952 }
2953
2954 #[test]
2955 fn test_range() {
2956 /// A mock type to check Range when ToPrimitive returns None
2957 struct Foo;
2958
2959 impl ToPrimitive for Foo {
2960 fn to_i64(&self) -> Option<i64> { None }
2961 fn to_u64(&self) -> Option<u64> { None }
2962 }
2963
2964 impl Add<Foo, Foo> for Foo {
2965 fn add(&self, _: &Foo) -> Foo {
2966 Foo
2967 }
2968 }
2969
2970 impl Eq for Foo {
2971 fn eq(&self, _: &Foo) -> bool {
2972 true
2973 }
2974 }
2975
2976 impl Ord for Foo {
2977 fn lt(&self, _: &Foo) -> bool {
2978 false
2979 }
2980 }
2981
2982 impl Clone for Foo {
2983 fn clone(&self) -> Foo {
2984 Foo
2985 }
2986 }
2987
2988 impl Mul<Foo, Foo> for Foo {
2989 fn mul(&self, _: &Foo) -> Foo {
2990 Foo
2991 }
2992 }
2993
2994 impl num::One for Foo {
2995 fn one() -> Foo {
2996 Foo
2997 }
2998 }
2999
3000 assert_eq!(range(0i, 5).collect::<Vec<int>>(), vec![0i, 1, 2, 3, 4]);
3001 assert_eq!(range(-10i, -1).collect::<Vec<int>>(),
3002 vec![-10, -9, -8, -7, -6, -5, -4, -3, -2]);
3003 assert_eq!(range(0i, 5).rev().collect::<Vec<int>>(), vec![4, 3, 2, 1, 0]);
3004 assert_eq!(range(200, -5).collect::<Vec<int>>(), vec![]);
3005 assert_eq!(range(200, -5).rev().collect::<Vec<int>>(), vec![]);
3006 assert_eq!(range(200, 200).collect::<Vec<int>>(), vec![]);
3007 assert_eq!(range(200, 200).rev().collect::<Vec<int>>(), vec![]);
3008
3009 assert_eq!(range(0i, 100).size_hint(), (100, Some(100)));
3010 // this test is only meaningful when sizeof uint < sizeof u64
3011 assert_eq!(range(uint::MAX - 1, uint::MAX).size_hint(), (1, Some(1)));
3012 assert_eq!(range(-10i, -1).size_hint(), (9, Some(9)));
3013 assert_eq!(range(Foo, Foo).size_hint(), (0, None));
3014 }
3015
3016 #[test]
3017 fn test_range_inclusive() {
3018 assert_eq!(range_inclusive(0i, 5).collect::<Vec<int>>(), vec![0i, 1, 2, 3, 4, 5]);
3019 assert_eq!(range_inclusive(0i, 5).rev().collect::<Vec<int>>(), vec![5i, 4, 3, 2, 1, 0]);
3020 assert_eq!(range_inclusive(200, -5).collect::<Vec<int>>(), vec![]);
3021 assert_eq!(range_inclusive(200, -5).rev().collect::<Vec<int>>(), vec![]);
3022 assert_eq!(range_inclusive(200, 200).collect::<Vec<int>>(), vec![200]);
3023 assert_eq!(range_inclusive(200, 200).rev().collect::<Vec<int>>(), vec![200]);
3024 }
3025
3026 #[test]
3027 fn test_range_step() {
3028 assert_eq!(range_step(0i, 20, 5).collect::<Vec<int>>(), vec![0, 5, 10, 15]);
3029 assert_eq!(range_step(20i, 0, -5).collect::<Vec<int>>(), vec![20, 15, 10, 5]);
3030 assert_eq!(range_step(20i, 0, -6).collect::<Vec<int>>(), vec![20, 14, 8, 2]);
3031 assert_eq!(range_step(200u8, 255, 50).collect::<Vec<u8>>(), vec![200u8, 250]);
3032 assert_eq!(range_step(200, -5, 1).collect::<Vec<int>>(), vec![]);
3033 assert_eq!(range_step(200, 200, 1).collect::<Vec<int>>(), vec![]);
3034 }
3035
3036 #[test]
3037 fn test_range_step_inclusive() {
3038 assert_eq!(range_step_inclusive(0i, 20, 5).collect::<Vec<int>>(), vec![0, 5, 10, 15, 20]);
3039 assert_eq!(range_step_inclusive(20i, 0, -5).collect::<Vec<int>>(), vec![20, 15, 10, 5, 0]);
3040 assert_eq!(range_step_inclusive(20i, 0, -6).collect::<Vec<int>>(), vec![20, 14, 8, 2]);
3041 assert_eq!(range_step_inclusive(200u8, 255, 50).collect::<Vec<u8>>(), vec![200u8, 250]);
3042 assert_eq!(range_step_inclusive(200, -5, 1).collect::<Vec<int>>(), vec![]);
3043 assert_eq!(range_step_inclusive(200, 200, 1).collect::<Vec<int>>(), vec![200]);
3044 }
3045
3046 #[test]
3047 fn test_reverse() {
3048 let mut ys = [1, 2, 3, 4, 5];
3049 ys.mut_iter().reverse_();
3050 assert!(ys == [5, 4, 3, 2, 1]);
3051 }
3052
3053 #[test]
3054 fn test_peekable_is_empty() {
3055 let a = [1];
3056 let mut it = a.iter().peekable();
3057 assert!( !it.is_empty() );
3058 it.next();
3059 assert!( it.is_empty() );
3060 }
3061
3062 #[test]
3063 fn test_min_max() {
3064 let v: [int, ..0] = [];
3065 assert_eq!(v.iter().min_max(), NoElements);
3066
3067 let v = [1i];
3068 assert!(v.iter().min_max() == OneElement(&1));
3069
3070 let v = [1i, 2, 3, 4, 5];
3071 assert!(v.iter().min_max() == MinMax(&1, &5));
3072
3073 let v = [1i, 2, 3, 4, 5, 6];
3074 assert!(v.iter().min_max() == MinMax(&1, &6));
3075
3076 let v = [1i, 1, 1, 1];
3077 assert!(v.iter().min_max() == MinMax(&1, &1));
3078 }
3079
3080 #[test]
3081 fn test_MinMaxResult() {
3082 let r: MinMaxResult<int> = NoElements;
3083 assert_eq!(r.into_option(), None)
3084
3085 let r = OneElement(1);
3086 assert_eq!(r.into_option(), Some((1,1)));
3087
3088 let r = MinMax(1,2);
3089 assert_eq!(r.into_option(), Some((1,2)));
3090 }
3091 }

libcore/iter.rs:1945:10-1945:10 -fn- definition:
pub fn range<A: Add<A, A> + Ord + Clone + One>(start: A, stop: A) -> Range<A> {
 Range{state: start, stop: stop, one: One::one()}
}
references:- 5
2020: -> RangeInclusive<A> {
2021: RangeInclusive{range: range(start, stop), done: false}
2022: }
libcore/should_not_exist.rs:
171: // we must be failing, clean up after ourselves
172: for j in range(0, *i as int) {
173: ptr::read(&*p.offset(j));
libcore/ptr.rs:
298: //let start_ptr = *arr;
299: for e in range(0, len) {
300: let n = arr.offset(e as int);

libcore/iter.rs:780:39-780:39 -struct- definition:
/// A mutable reference to an iterator
pub struct ByRef<'a, T> {
 iter: &'a mut T
references:- 4
785: impl<'a, A, T: Iterator<A>> Iterator<A> for ByRef<'a, T> {
786: #[inline]
--
792: impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for ByRef<'a, T> {
793: #[inline]

libcore/iter.rs:2141:19-2141:19 -struct- definition:
pub struct Repeat<A> {
 element: A
}
references:- 10
2149: pub fn new(elt: A) -> Repeat<A> {
2150: Repeat{element: elt}
2151: }
--
2161: impl<A: Clone> DoubleEndedIterator<A> for Repeat<A> {
2162: #[inline]
--
2166: impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
2167: #[inline]

libcore/iter.rs:1374:19-1374:19 -struct- definition:
pub struct Enumerate<T> {
 iter: T,
 count: uint
references:- 10
1373: /// An iterator which yields the current count and the element during iteration
1375: pub struct Enumerate<T> {
--
1380: impl<A, T: Iterator<A>> Iterator<(uint, A)> for Enumerate<T> {
1381: #[inline]
--
1413: impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<(uint, A)> for Enumerate<T> {
1414: #[inline]

libcore/iter.rs:1551:19-1551:19 -struct- definition:
pub struct Skip<T> {
 iter: T,
 n: uint
references:- 8
1550: /// An iterator which skips over `n` elements of `iter`.
1552: pub struct Skip<T> {
--
1557: impl<A, T: Iterator<A>> Iterator<A> for Skip<T> {
1558: #[inline]
--
1598: impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Skip<T> {
1599: #[inline]

libcore/iter.rs:1158:19-1158:19 -struct- definition:
pub struct Zip<T, U> {
 a: T,
 b: U
references:- 10
142: fn zip<B, U: Iterator>(self, other: U) -> Zip<Self, U> {
143: Zip{a: self, b: other}
144: }
--
1157: /// An iterator which iterates two other iterators simultaneously
1159: pub struct Zip<T, U> {
--
1164: impl<A, B, T: Iterator<A>, U: Iterator> Iterator<(A, B)> for Zip<T, U> {
1165: #[inline]
--
1217: impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator>
1218: RandomAccessIterator<(A, B)> for Zip<T, U> {
1219: #[inline]

libcore/iter.rs:97:10-97:10 -trait- definition:
/// else.
pub trait Iterator<A> {
 /// Advance the iterator and return the next value. Return `None` when the end is reached.
references:- 102
libcore/option.rs:
libcore/result.rs:
libcore/slice.rs:
libcore/str.rs:
libcore/should_not_exist.rs:
libcore/iter.rs:

libcore/iter.rs:653:59-653:59 -trait- definition:
/// A range iterator able to yield elements from both ends
pub trait DoubleEndedIterator<A>: Iterator<A> {
 /// Yield an element from the end of the range, returning `None` if the range is empty.
references:- 40
libcore/option.rs:
libcore/slice.rs:
libcore/str.rs:
libcore/iter.rs:

libcore/iter.rs:2106:19-2106:19 -struct- definition:
pub struct RangeStepInclusive<A> {
 state: A,
 stop: A,
references:- 7
2105: /// An iterator over the range [start, stop] by `step`. It handles overflow by stopping.
2107: pub struct RangeStepInclusive<A> {
--
2119: let rev = step < Zero::zero();
2120: RangeStepInclusive{state: start, stop: stop, step: step, rev: rev, done: false}
2121: }
2123: impl<A: CheckedAdd + Ord + Clone + Eq> Iterator<A> for RangeStepInclusive<A> {
2124: #[inline]

libcore/iter.rs:1615:19-1615:19 -struct- definition:
pub struct Take<T> {
 iter: T,
 n: uint
references:- 8
305: fn take(self, n: uint) -> Take<Self> {
306: Take{iter: self, n: n}
307: }
--
1614: /// An iterator which only iterates over the first `n` iterations of `iter`.
1616: pub struct Take<T> {
--
1621: impl<A, T: Iterator<A>> Iterator<A> for Take<T> {
1622: #[inline]
--
1647: impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Take<T> {
1648: #[inline]

libcore/iter.rs:1330:75-1330:75 -struct- definition:
/// An iterator which uses `f` to both filter and map elements from `iter`
pub struct FilterMap<'a, A, B, T> {
 iter: T,
references:- 4
193: fn filter_map<'r, B>(self, f: |A|: 'r -> Option) -> FilterMap<'r, A, B, Self> {
194: FilterMap { iter: self, f: f }
195: }
--
1336: impl<'a, A, B, T: Iterator<A>> Iterator for FilterMap<'a, A, B, T> {
1337: #[inline]
--
1355: impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator
1356: for FilterMap<'a, A, B, T> {
1357: #[inline]

libcore/iter.rs:1089:19-1089:19 -struct- definition:
pub struct Chain<T, U> {
 a: T,
 b: U,
references:- 9
1088: /// An iterator which strings two iterators together
1090: pub struct Chain<T, U> {
--
1096: impl<A, T: Iterator<A>, U: Iterator<A>> Iterator<A> for Chain<T, U> {
1097: #[inline]
--
1138: impl<A, T: RandomAccessIterator<A>, U: RandomAccessIterator<A>> RandomAccessIterator<A>
1139: for Chain<T, U> {
1140: #[inline]

libcore/iter.rs:752:19-752:19 -struct- definition:
pub struct Rev<T> {
 iter: T
}
references:- 26
671: fn rev(self) -> Rev<Self> {
672: Rev{iter: self}
673: }
--
751: /// An double-ended iterator with the direction inverted
753: pub struct Rev<T> {
--
757: impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Rev<T> {
758: #[inline]
--
769: impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
770: for Rev<T> {
771: #[inline]
libcore/slice.rs:
406: #[deprecated = "replaced by .split(pred).rev()"]
407: fn rsplit(self, pred: |&T|: 'a -> bool) -> Rev<Splits<'a, T>>;
408: /// Returns an iterator over the subslices of the vector which are
--
1347: pub type RevItems<'a, T> = Rev<Items<'a, T>>;
--
1358: pub type RevMutItems<'a, T> = Rev<MutItems<'a, T>>;
libcore/str.rs:
905: #[deprecated = "replaced by .chars().rev()"]
906: fn chars_rev(&self) -> Rev<Chars<'a>>;
--
919: #[deprecated = "replaced by .char_indices().rev()"]
920: fn char_indices_rev(&self) -> Rev<CharOffsets<'a>>;
--
984: #[deprecated = "replaced by .split(sep).rev()"]
985: fn rsplit<Sep: CharEq>(&self, sep: Sep) -> Rev<CharSplits<'a, Sep>>;

libcore/iter.rs:1688:4-1688:4 -struct- definition:
///
pub struct FlatMap<'a, A, T, U> {
 iter: T,
references:- 4
355: -> FlatMap<'r, A, Self, U> {
356: FlatMap{iter: self, f: f, frontiter: None, backiter: None }
357: }
--
1696: impl<'a, A, T: Iterator<A>, B, U: Iterator> Iterator for FlatMap<'a, A, T, U> {
1697: #[inline]
--
1726: B, U: DoubleEndedIterator> DoubleEndedIterator
1727: for FlatMap<'a, A, T, U> {
1728: #[inline]

libcore/iter.rs:76:34-76:34 -trait- definition:
/// Conversion from an `Iterator`
pub trait FromIterator<A> {
 /// Build a container with elements from an external iterator.
references:- 6
461: #[inline]
462: fn collect<B: FromIterator<A>>(&mut self) -> B {
463: FromIterator::from_iter(self.by_ref())
libcore/option.rs:
568: pub fn collect<T, Iter: Iterator<Option<T>>, V: FromIterator<T>>(iter: Iter) -> Option<V> {
569: // FIXME(#11084): This should be twice as fast once this bug is closed.
libcore/result.rs:
537: pub fn collect<T, E, Iter: Iterator<Result<T, E>>, V: FromIterator<T>>(iter: Iter) -> Result<V, E> {
538: // FIXME(#11084): This should be twice as fast once this bug is closed.
libcore/should_not_exist.rs:
82: impl FromIterator<char> for ~str {
83: #[inline]
libcore/iter.rs:
78: /// Build a container with elements from an external iterator.
79: fn from_iter<T: Iterator<A>>(iterator: T) -> Self;
80: }

libcore/iter.rs:1013:46-1013:46 -trait- definition:
/// A trait for iterators that are cloneable.
pub trait CloneableIterator {
 /// Repeats an iterator endlessly
references:- 2
1026: /// ```
1027: fn cycle(self) -> Cycle<Self>;
1028: }
1030: impl<A, T: Clone + Iterator<A>> CloneableIterator for T {
1031: #[inline]

libcore/iter.rs:972:23-972:23 -enum- definition:
pub enum MinMaxResult<T> {
 /// Empty iterator
 NoElements,
references:- 8
927: fn min_max(&mut self) -> MinMaxResult<A> {
928: let (mut min, mut max) = match self.next() {
--
971: /// `MinMaxResult` is an enum returned by `min_max`. See `OrdIterator::min_max` for more detail.
973: pub enum MinMaxResult<T> {
--
984: impl<T: Clone> MinMaxResult<T> {
985: /// `into_option` creates an `Option` of type `(T,T)`. The returned `Option` has variant

libcore/iter.rs:1236:57-1236:57 -struct- definition:
/// An iterator which maps the values of `iter` with `f`
pub struct Map<'a, A, B, T> {
 iter: T,
references:- 9
159: fn map<'r, B>(self, f: |A|: 'r -> B) -> Map<'r, A, B, Self> {
160: Map{iter: self, f: f}
161: }
--
1242: impl<'a, A, B, T> Map<'a, A, B, T> {
1243: #[inline]
--
1273: impl<'a, A, B, T: RandomAccessIterator<A>> RandomAccessIterator for Map<'a, A, B, T> {
1274: #[inline]
libcore/str.rs:
183: pub type Bytes<'a> =
184: Map<'a, &'a u8, u8, slice::Items<'a, u8>>;
--
219: pub type AnyLines<'a> =
220: Map<'a, &'a str, &'a str, CharSplits<'a, char>>;
libcore/iter.rs:
1265: impl<'a, A, B, T: DoubleEndedIterator<A>> DoubleEndedIterator for Map<'a, A, B, T> {
1266: #[inline]

libcore/iter.rs:1516:70-1516:70 -struct- definition:
/// An iterator which only accepts elements while `predicate` is true
pub struct TakeWhile<'a, A, T> {
 iter: T,
references:- 3
1523: impl<'a, A, T: Iterator<A>> Iterator<A> for TakeWhile<'a, A, T> {
1524: #[inline]

libcore/iter.rs:2074:19-2074:19 -struct- definition:
pub struct RangeStep<A> {
 state: A,
 stop: A,
references:- 7
2073: /// An iterator over the range [start, stop) by `step`. It handles overflow by stopping.
2075: pub struct RangeStep<A> {
--
2085: let rev = step < Zero::zero();
2086: RangeStep{state: start, stop: stop, step: step, rev: rev}
2087: }
2089: impl<A: CheckedAdd + Ord + Clone> Iterator<A> for RangeStep<A> {
2090: #[inline]

libcore/iter.rs:1747:19-1747:19 -struct- definition:
pub struct Fuse<T> {
 iter: T,
 done: bool
references:- 10
385: fn fuse(self) -> Fuse<Self> {
386: Fuse{iter: self, done: false}
387: }
--
1796: // Allow RandomAccessIterators to be fused without affecting random-access behavior
1797: impl<A, T: RandomAccessIterator<A>> RandomAccessIterator<A> for Fuse<T> {
1798: #[inline]
--
1809: impl<T> Fuse<T> {
1810: /// Resets the fuse such that the next call to .next() or .next_back() will

libcore/iter.rs:1664:67-1664:67 -struct- definition:
/// An iterator to maintain state while iterating another iterator
pub struct Scan<'a, A, B, T, St> {
 iter: T,
references:- 3
330: fn scan<'r, St, B>(self, initial_state: St, f: |&mut St, A|: 'r -> Option)
331: -> Scan<'r, A, B, Self, St> {
332: Scan{iter: self, f: f, state: initial_state}
--
1673: impl<'a, A, B, T: Iterator<A>, St> Iterator for Scan<'a, A, B, T, St> {
1674: #[inline]

libcore/iter.rs:1038:19-1038:19 -struct- definition:
pub struct Cycle<T> {
 orig: T,
 iter: T,
references:- 9
1037: /// An iterator that repeats endlessly
1039: pub struct Cycle<T> {
--
1064: impl<A, T: Clone + RandomAccessIterator<A>> RandomAccessIterator<A> for Cycle<T> {
1065: #[inline]

libcore/iter.rs:1873:78-1873:78 -struct- definition:
/// An iterator which just modifies the contained state throughout iteration.
pub struct Unfold<'a, A, St> {
 f: |&mut St|: 'a -> Option<A>,
references:- 4
1885: -> Unfold<'a, A, St> {
1886: Unfold {
1887: f: f,
--
1893: impl<'a, A, St> Iterator<A> for Unfold<'a, A, St> {
1894: #[inline]

libcore/iter.rs:1286:70-1286:70 -struct- definition:
/// An iterator which filters the elements of `iter` with `predicate`
pub struct Filter<'a, A, T> {
 iter: T,
references:- 5
176: fn filter<'r>(self, predicate: |&A|: 'r -> bool) -> Filter<'r, A, Self> {
177: Filter{iter: self, predicate: predicate}
178: }
--
1312: impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Filter<'a, A, T> {
1313: #[inline]
libcore/str.rs:
215: pub type Words<'a> =
216: Filter<'a, &'a str, CharSplits<'a, extern "Rust" fn(char) -> bool>>;
libcore/iter.rs:
175: #[inline]
176: fn filter<'r>(self, predicate: |&A|: 'r -> bool) -> Filter<'r, A, Self> {
177: Filter{iter: self, predicate: predicate}

libcore/iter.rs:1428:88-1428:88 -struct- definition:
/// An iterator with a `peek()` that returns an optional reference to the next element.
pub struct Peekable<A, T> {
 iter: T,
references:- 4
233: fn peekable(self) -> Peekable<A, Self> {
234: Peekable{iter: self, peeked: None}
235: }
--
1457: impl<'a, A, T: Iterator<A>> Peekable<A, T> {
1458: /// Return a reference to the next element of the iterator with out advancing it,

libcore/iter.rs:699:83-699:83 -trait- definition:
/// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
pub trait RandomAccessIterator<A>: Iterator<A> {
 /// Return the number of indexable elements. At most `std::uint::MAX`
references:- 25
1217: impl<A, B, T: RandomAccessIterator<A>, U: RandomAccessIterator>
1218: RandomAccessIterator<(A, B)> for Zip<T, U> {
--
1273: impl<'a, A, B, T: RandomAccessIterator<A>> RandomAccessIterator for Map<'a, A, B, T> {
1274: #[inline]
--
2166: impl<A: Clone> RandomAccessIterator<A> for Repeat<A> {
2167: #[inline]
libcore/slice.rs:
1326: impl<'a, T> RandomAccessIterator<&'a T> for Items<'a, T> {
1327: #[inline]
libcore/iter.rs:
1273: impl<'a, A, B, T: RandomAccessIterator<A>> RandomAccessIterator for Map<'a, A, B, T> {
1274: #[inline]

libcore/iter.rs:2011:19-2011:19 -struct- definition:
pub struct RangeInclusive<A> {
 range: Range<A>,
 done: bool,
references:- 8
2020: -> RangeInclusive<A> {
2021: RangeInclusive{range: range(start, stop), done: false}
2022: }
--
2056: impl<A: Sub<A, A> + Int + Ord + Clone + ToPrimitive> DoubleEndedIterator<A>
2057: for RangeInclusive<A> {
2058: #[inline]

libcore/iter.rs:1478:65-1478:65 -struct- definition:
/// An iterator which rejects elements while `predicate` is true
pub struct SkipWhile<'a, A, T> {
 iter: T,
references:- 3
251: #[inline]
252: fn skip_while<'r>(self, predicate: |&A|: 'r -> bool) -> SkipWhile<'r, A, Self> {
253: SkipWhile{iter: self, flag: false, predicate: predicate}
--
1485: impl<'a, A, T: Iterator<A>> Iterator<A> for SkipWhile<'a, A, T> {
1486: #[inline]

libcore/iter.rs:715:43-715:43 -trait- definition:
/// Note that the size must fit in `uint`.
pub trait ExactSize<A> : DoubleEndedIterator<A> {
 /// Return the index of the last element satisfying the specified predicate
references:- 17
1194: impl<A, B, T: ExactSize<A>, U: ExactSize> DoubleEndedIterator<(A, B)>
1195: for Zip<T, U> {
--
1399: impl<A, T: ExactSize<A>> DoubleEndedIterator<(uint, A)> for Enumerate<T> {
1400: #[inline]
libcore/option.rs:
547: impl<A> ExactSize<A> for Item<A> {}
libcore/slice.rs:
1349: impl<'a, T> ExactSize<&'a T> for Items<'a, T> {}
1350: impl<'a, T> ExactSize<&'a mut T> for MutItems<'a, T> {}
libcore/iter.rs:
746: impl<'a, A, T: ExactSize<A>> ExactSize<A> for Inspect<'a, A, T> {}
747: impl<A, T: ExactSize<A>> ExactSize<A> for Rev<T> {}
748: impl<'a, A, B, T: ExactSize<A>> ExactSize for Map<'a, A, B, T> {}

libcore/iter.rs:1937:19-1937:19 -struct- definition:
pub struct Range<A> {
 state: A,
 stop: A,
references:- 9
1946: pub fn range<A: Add<A, A> + Ord + Clone + One>(start: A, stop: A) -> Range<A> {
1947: Range{state: start, stop: stop, one: One::one()}
1948: }
--
2012: pub struct RangeInclusive<A> {
2013: range: Range<A>,
2014: done: bool,

libcore/iter.rs:1819:32-1819:32 -struct- definition:
/// element before yielding it.
pub struct Inspect<'a, A, T> {
 iter: T,
references:- 7
408: fn inspect<'r>(self, f: |&A|: 'r) -> Inspect<'r, A, Self> {
409: Inspect{iter: self, f: f}
410: }
--
745: impl<A, T: ExactSize<A>> ExactSize<(uint, A)> for Enumerate<T> {}
746: impl<'a, A, T: ExactSize<A>> ExactSize<A> for Inspect<'a, A, T> {}
747: impl<A, T: ExactSize<A>> ExactSize<A> for Rev<T> {}
--
1850: impl<'a, A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A>
1851: for Inspect<'a, A, T> {
1852: #[inline]
--
1859: impl<'a, A, T: RandomAccessIterator<A>> RandomAccessIterator<A>
1860: for Inspect<'a, A, T> {
1861: #[inline]

libcore/iter.rs:1908:19-1908:19 -struct- definition:
pub struct Counter<A> {
 /// The current state the counter is at (next value to be yielded)
 state: A,
references:- 7
1907: /// iteration
1909: pub struct Counter<A> {
--
1918: pub fn count<A>(start: A, step: A) -> Counter<A> {
1919: Counter{state: start, step: step}
1920: }
1922: impl<A: Add<A, A> + Clone> Iterator<A> for Counter<A> {
1923: #[inline]