src/libcore/iter/traits.rs

   1 // Copyright 2013-2016 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 use option::Option::{self, Some};
  12 use marker::Sized;
  13
  14 use super::Iterator;
  15
  16 /// Conversion from an `Iterator`.
  17 ///
  18 /// By implementing `FromIterator` for a type, you define how it will be
  19 /// created from an iterator. This is common for types which describe a
  20 /// collection of some kind.
  21 ///
  22 /// `FromIterator`'s [`from_iter()`] is rarely called explicitly, and is instead
  23 /// used through [`Iterator`]'s [`collect()`] method. See [`collect()`]'s
  24 /// documentation for more examples.
  25 ///
  26 /// [`from_iter()`]: #tymethod.from_iter
  27 /// [`Iterator`]: trait.Iterator.html
  28 /// [`collect()`]: trait.Iterator.html#method.collect
  29 ///
  30 /// See also: [`IntoIterator`].
  31 ///
  32 /// [`IntoIterator`]: trait.IntoIterator.html
  33 ///
  34 /// # Examples
  35 ///
  36 /// Basic usage:
  37 ///
  38 /// ```
  39 /// use std::iter::FromIterator;
  40 ///
  41 /// let five_fives = std::iter::repeat(5).take(5);
  42 ///
  43 /// let v = Vec::from_iter(five_fives);
  44 ///
  45 /// assert_eq!(v, vec![5, 5, 5, 5, 5]);
  46 /// ```
  47 ///
  48 /// Using [`collect()`] to implicitly use `FromIterator`:
  49 ///
  50 /// ```
  51 /// let five_fives = std::iter::repeat(5).take(5);
  52 ///
  53 /// let v: Vec<i32> = five_fives.collect();
  54 ///
  55 /// assert_eq!(v, vec![5, 5, 5, 5, 5]);
  56 /// ```
  57 ///
  58 /// Implementing `FromIterator` for your type:
  59 ///
  60 /// ```
  61 /// use std::iter::FromIterator;
  62 ///
  63 /// // A sample collection, that's just a wrapper over Vec<T>
  64 /// #[derive(Debug)]
  65 /// struct MyCollection(Vec<i32>);
  66 ///
  67 /// // Let's give it some methods so we can create one and add things
  68 /// // to it.
  69 /// impl MyCollection {
  70 ///     fn new() -> MyCollection {
  71 ///         MyCollection(Vec::new())
  72 ///     }
  73 ///
  74 ///     fn add(&mut self, elem: i32) {
  75 ///         self.0.push(elem);
  76 ///     }
  77 /// }
  78 ///
  79 /// // and we'll implement FromIterator
  80 /// impl FromIterator<i32> for MyCollection {
  81 ///     fn from_iter<I: IntoIterator<Item=i32>>(iter: I) -> Self {
  82 ///         let mut c = MyCollection::new();
  83 ///
  84 ///         for i in iter {
  85 ///             c.add(i);
  86 ///         }
  87 ///
  88 ///         c
  89 ///     }
  90 /// }
  91 ///
  92 /// // Now we can make a new iterator...
  93 /// let iter = (0..5).into_iter();
  94 ///
  95 /// // ... and make a MyCollection out of it
  96 /// let c = MyCollection::from_iter(iter);
  97 ///
  98 /// assert_eq!(c.0, vec![0, 1, 2, 3, 4]);
  99 ///
 100 /// // collect works too!
 101 ///
 102 /// let iter = (0..5).into_iter();
 103 /// let c: MyCollection = iter.collect();
 104 ///
 105 /// assert_eq!(c.0, vec![0, 1, 2, 3, 4]);
 106 /// ```
 107 #[stable(feature = "rust1", since = "1.0.0")]
 108 #[rustc_on_unimplemented="a collection of type `{Self}` cannot be \
 109                           built from an iterator over elements of type `{A}`"]
 110 pub trait FromIterator<A>: Sized {
 111     /// Creates a value from an iterator.
 112     ///
 113     /// See the [module-level documentation] for more.
 114     ///
 115     /// [module-level documentation]: trait.FromIterator.html
 116     ///
 117     /// # Examples
 118     ///
 119     /// Basic usage:
 120     ///
 121     /// ```
 122     /// use std::iter::FromIterator;
 123     ///
 124     /// let five_fives = std::iter::repeat(5).take(5);
 125     ///
 126     /// let v = Vec::from_iter(five_fives);
 127     ///
 128     /// assert_eq!(v, vec![5, 5, 5, 5, 5]);
 129     /// ```
 130     #[stable(feature = "rust1", since = "1.0.0")]
 131     fn from_iter<T: IntoIterator<Item=A>>(iter: T) -> Self;
 132 }
 133
 134 /// Conversion into an `Iterator`.
 135 ///
 136 /// By implementing `IntoIterator` for a type, you define how it will be
 137 /// converted to an iterator. This is common for types which describe a
 138 /// collection of some kind.
 139 ///
 140 /// One benefit of implementing `IntoIterator` is that your type will [work
 141 /// with Rust's `for` loop syntax](index.html#for-loops-and-intoiterator).
 142 ///
 143 /// See also: [`FromIterator`].
 144 ///
 145 /// [`FromIterator`]: trait.FromIterator.html
 146 ///
 147 /// # Examples
 148 ///
 149 /// Basic usage:
 150 ///
 151 /// ```
 152 /// let v = vec![1, 2, 3];
 153 ///
 154 /// let mut iter = v.into_iter();
 155 ///
 156 /// let n = iter.next();
 157 /// assert_eq!(Some(1), n);
 158 ///
 159 /// let n = iter.next();
 160 /// assert_eq!(Some(2), n);
 161 ///
 162 /// let n = iter.next();
 163 /// assert_eq!(Some(3), n);
 164 ///
 165 /// let n = iter.next();
 166 /// assert_eq!(None, n);
 167 /// ```
 168 ///
 169 /// Implementing `IntoIterator` for your type:
 170 ///
 171 /// ```
 172 /// // A sample collection, that's just a wrapper over Vec<T>
 173 /// #[derive(Debug)]
 174 /// struct MyCollection(Vec<i32>);
 175 ///
 176 /// // Let's give it some methods so we can create one and add things
 177 /// // to it.
 178 /// impl MyCollection {
 179 ///     fn new() -> MyCollection {
 180 ///         MyCollection(Vec::new())
 181 ///     }
 182 ///
 183 ///     fn add(&mut self, elem: i32) {
 184 ///         self.0.push(elem);
 185 ///     }
 186 /// }
 187 ///
 188 /// // and we'll implement IntoIterator
 189 /// impl IntoIterator for MyCollection {
 190 ///     type Item = i32;
 191 ///     type IntoIter = ::std::vec::IntoIter<i32>;
 192 ///
 193 ///     fn into_iter(self) -> Self::IntoIter {
 194 ///         self.0.into_iter()
 195 ///     }
 196 /// }
 197 ///
 198 /// // Now we can make a new collection...
 199 /// let mut c = MyCollection::new();
 200 ///
 201 /// // ... add some stuff to it ...
 202 /// c.add(0);
 203 /// c.add(1);
 204 /// c.add(2);
 205 ///
 206 /// // ... and then turn it into an Iterator:
 207 /// for (i, n) in c.into_iter().enumerate() {
 208 ///     assert_eq!(i as i32, n);
 209 /// }
 210 /// ```
 211 #[stable(feature = "rust1", since = "1.0.0")]
 212 pub trait IntoIterator {
 213     /// The type of the elements being iterated over.
 214     #[stable(feature = "rust1", since = "1.0.0")]
 215     type Item;
 216
 217     /// Which kind of iterator are we turning this into?
 218     #[stable(feature = "rust1", since = "1.0.0")]
 219     type IntoIter: Iterator<Item=Self::Item>;
 220
 221     /// Creates an iterator from a value.
 222     ///
 223     /// See the [module-level documentation] for more.
 224     ///
 225     /// [module-level documentation]: trait.IntoIterator.html
 226     ///
 227     /// # Examples
 228     ///
 229     /// Basic usage:
 230     ///
 231     /// ```
 232     /// let v = vec![1, 2, 3];
 233     ///
 234     /// let mut iter = v.into_iter();
 235     ///
 236     /// let n = iter.next();
 237     /// assert_eq!(Some(1), n);
 238     ///
 239     /// let n = iter.next();
 240     /// assert_eq!(Some(2), n);
 241     ///
 242     /// let n = iter.next();
 243     /// assert_eq!(Some(3), n);
 244     ///
 245     /// let n = iter.next();
 246     /// assert_eq!(None, n);
 247     /// ```
 248     #[stable(feature = "rust1", since = "1.0.0")]
 249     fn into_iter(self) -> Self::IntoIter;
 250 }
 251
 252 #[stable(feature = "rust1", since = "1.0.0")]
 253 impl<I: Iterator> IntoIterator for I {
 254     type Item = I::Item;
 255     type IntoIter = I;
 256
 257     fn into_iter(self) -> I {
 258         self
 259     }
 260 }
 261
 262 /// Extend a collection with the contents of an iterator.
 263 ///
 264 /// Iterators produce a series of values, and collections can also be thought
 265 /// of as a series of values. The `Extend` trait bridges this gap, allowing you
 266 /// to extend a collection by including the contents of that iterator.
 267 ///
 268 /// # Examples
 269 ///
 270 /// Basic usage:
 271 ///
 272 /// ```
 273 /// // You can extend a String with some chars:
 274 /// let mut message = String::from("The first three letters are: ");
 275 ///
 276 /// message.extend(&['a', 'b', 'c']);
 277 ///
 278 /// assert_eq!("abc", &message[29..32]);
 279 /// ```
 280 ///
 281 /// Implementing `Extend`:
 282 ///
 283 /// ```
 284 /// // A sample collection, that's just a wrapper over Vec<T>
 285 /// #[derive(Debug)]
 286 /// struct MyCollection(Vec<i32>);
 287 ///
 288 /// // Let's give it some methods so we can create one and add things
 289 /// // to it.
 290 /// impl MyCollection {
 291 ///     fn new() -> MyCollection {
 292 ///         MyCollection(Vec::new())
 293 ///     }
 294 ///
 295 ///     fn add(&mut self, elem: i32) {
 296 ///         self.0.push(elem);
 297 ///     }
 298 /// }
 299 ///
 300 /// // since MyCollection has a list of i32s, we implement Extend for i32
 301 /// impl Extend<i32> for MyCollection {
 302 ///
 303 ///     // This is a bit simpler with the concrete type signature: we can call
 304 ///     // extend on anything which can be turned into an Iterator which gives
 305 ///     // us i32s. Because we need i32s to put into MyCollection.
 306 ///     fn extend<T: IntoIterator<Item=i32>>(&mut self, iter: T) {
 307 ///
 308 ///         // The implementation is very straightforward: loop through the
 309 ///         // iterator, and add() each element to ourselves.
 310 ///         for elem in iter {
 311 ///             self.add(elem);
 312 ///         }
 313 ///     }
 314 /// }
 315 ///
 316 /// let mut c = MyCollection::new();
 317 ///
 318 /// c.add(5);
 319 /// c.add(6);
 320 /// c.add(7);
 321 ///
 322 /// // let's extend our collection with three more numbers
 323 /// c.extend(vec![1, 2, 3]);
 324 ///
 325 /// // we've added these elements onto the end
 326 /// assert_eq!("MyCollection([5, 6, 7, 1, 2, 3])", format!("{:?}", c));
 327 /// ```
 328 #[stable(feature = "rust1", since = "1.0.0")]
 329 pub trait Extend<A> {
 330     /// Extends a collection with the contents of an iterator.
 331     ///
 332     /// As this is the only method for this trait, the [trait-level] docs
 333     /// contain more details.
 334     ///
 335     /// [trait-level]: trait.Extend.html
 336     ///
 337     /// # Examples
 338     ///
 339     /// Basic usage:
 340     ///
 341     /// ```
 342     /// // You can extend a String with some chars:
 343     /// let mut message = String::from("abc");
 344     ///
 345     /// message.extend(['d', 'e', 'f'].iter());
 346     ///
 347     /// assert_eq!("abcdef", &message);
 348     /// ```
 349     #[stable(feature = "rust1", since = "1.0.0")]
 350     fn extend<T: IntoIterator<Item=A>>(&mut self, iter: T);
 351 }
 352
 353 /// An iterator able to yield elements from both ends.
 354 ///
 355 /// Something that implements `DoubleEndedIterator` has one extra capability
 356 /// over something that implements [`Iterator`]: the ability to also take
 357 /// `Item`s from the back, as well as the front.
 358 ///
 359 /// It is important to note that both back and forth work on the same range,
 360 /// and do not cross: iteration is over when they meet in the middle.
 361 ///
 362 /// In a similar fashion to the [`Iterator`] protocol, once a
 363 /// `DoubleEndedIterator` returns `None` from a `next_back()`, calling it again
 364 /// may or may not ever return `Some` again. `next()` and `next_back()` are
 365 /// interchangable for this purpose.
 366 ///
 367 /// [`Iterator`]: trait.Iterator.html
 368 ///
 369 /// # Examples
 370 ///
 371 /// Basic usage:
 372 ///
 373 /// ```
 374 /// let numbers = vec![1, 2, 3];
 375 ///
 376 /// let mut iter = numbers.iter();
 377 ///
 378 /// assert_eq!(Some(&1), iter.next());
 379 /// assert_eq!(Some(&3), iter.next_back());
 380 /// assert_eq!(Some(&2), iter.next_back());
 381 /// assert_eq!(None, iter.next());
 382 /// assert_eq!(None, iter.next_back());
 383 /// ```
 384 #[stable(feature = "rust1", since = "1.0.0")]
 385 pub trait DoubleEndedIterator: Iterator {
 386     /// An iterator able to yield elements from both ends.
 387     ///
 388     /// As this is the only method for this trait, the [trait-level] docs
 389     /// contain more details.
 390     ///
 391     /// [trait-level]: trait.DoubleEndedIterator.html
 392     ///
 393     /// # Examples
 394     ///
 395     /// Basic usage:
 396     ///
 397     /// ```
 398     /// let numbers = vec![1, 2, 3];
 399     ///
 400     /// let mut iter = numbers.iter();
 401     ///
 402     /// assert_eq!(Some(&1), iter.next());
 403     /// assert_eq!(Some(&3), iter.next_back());
 404     /// assert_eq!(Some(&2), iter.next_back());
 405     /// assert_eq!(None, iter.next());
 406     /// assert_eq!(None, iter.next_back());
 407     /// ```
 408     #[stable(feature = "rust1", since = "1.0.0")]
 409     fn next_back(&mut self) -> Option<Self::Item>;
 410 }
 411
 412 #[stable(feature = "rust1", since = "1.0.0")]
 413 impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
 414     fn next_back(&mut self) -> Option<I::Item> { (**self).next_back() }
 415 }
 416
 417 /// An iterator that knows its exact length.
 418 ///
 419 /// Many [`Iterator`]s don't know how many times they will iterate, but some do.
 420 /// If an iterator knows how many times it can iterate, providing access to
 421 /// that information can be useful. For example, if you want to iterate
 422 /// backwards, a good start is to know where the end is.
 423 ///
 424 /// When implementing an `ExactSizeIterator`, You must also implement
 425 /// [`Iterator`]. When doing so, the implementation of [`size_hint()`] *must*
 426 /// return the exact size of the iterator.
 427 ///
 428 /// [`Iterator`]: trait.Iterator.html
 429 /// [`size_hint()`]: trait.Iterator.html#method.size_hint
 430 ///
 431 /// The [`len()`] method has a default implementation, so you usually shouldn't
 432 /// implement it. However, you may be able to provide a more performant
 433 /// implementation than the default, so overriding it in this case makes sense.
 434 ///
 435 /// [`len()`]: #method.len
 436 ///
 437 /// # Examples
 438 ///
 439 /// Basic usage:
 440 ///
 441 /// ```
 442 /// // a finite range knows exactly how many times it will iterate
 443 /// let five = 0..5;
 444 ///
 445 /// assert_eq!(5, five.len());
 446 /// ```
 447 ///
 448 /// In the [module level docs][moddocs], we implemented an [`Iterator`],
 449 /// `Counter`. Let's implement `ExactSizeIterator` for it as well:
 450 ///
 451 /// [moddocs]: index.html
 452 ///
 453 /// ```
 454 /// # struct Counter {
 455 /// #     count: usize,
 456 /// # }
 457 /// # impl Counter {
 458 /// #     fn new() -> Counter {
 459 /// #         Counter { count: 0 }
 460 /// #     }
 461 /// # }
 462 /// # impl Iterator for Counter {
 463 /// #     type Item = usize;
 464 /// #     fn next(&mut self) -> Option<usize> {
 465 /// #         self.count += 1;
 466 /// #         if self.count < 6 {
 467 /// #             Some(self.count)
 468 /// #         } else {
 469 /// #             None
 470 /// #         }
 471 /// #     }
 472 /// # }
 473 /// impl ExactSizeIterator for Counter {
 474 ///     // We already have the number of iterations, so we can use it directly.
 475 ///     fn len(&self) -> usize {
 476 ///         self.count
 477 ///     }
 478 /// }
 479 ///
 480 /// // And now we can use it!
 481 ///
 482 /// let counter = Counter::new();
 483 ///
 484 /// assert_eq!(0, counter.len());
 485 /// ```
 486 #[stable(feature = "rust1", since = "1.0.0")]
 487 pub trait ExactSizeIterator: Iterator {
 488     /// Returns the exact number of times the iterator will iterate.
 489     ///
 490     /// This method has a default implementation, so you usually should not
 491     /// implement it directly. However, if you can provide a more efficient
 492     /// implementation, you can do so. See the [trait-level] docs for an
 493     /// example.
 494     ///
 495     /// This function has the same safety guarantees as the [`size_hint()`]
 496     /// function.
 497     ///
 498     /// [trait-level]: trait.ExactSizeIterator.html
 499     /// [`size_hint()`]: trait.Iterator.html#method.size_hint
 500     ///
 501     /// # Examples
 502     ///
 503     /// Basic usage:
 504     ///
 505     /// ```
 506     /// // a finite range knows exactly how many times it will iterate
 507     /// let five = 0..5;
 508     ///
 509     /// assert_eq!(5, five.len());
 510     /// ```
 511     #[inline]
 512     #[stable(feature = "rust1", since = "1.0.0")]
 513     fn len(&self) -> usize {
 514         let (lower, upper) = self.size_hint();
 515         // Note: This assertion is overly defensive, but it checks the invariant
 516         // guaranteed by the trait. If this trait were rust-internal,
 517         // we could use debug_assert!; assert_eq! will check all Rust user
 518         // implementations too.
 519         assert_eq!(upper, Some(lower));
 520         lower
 521     }
 522
 523     ///
 524     /// Returns whether the iterator is empty.
 525     ///
 526     /// This method has a default implementation using `self.len()`, so you
 527     /// don't need to implement it yourself.
 528     ///
 529     /// # Examples
 530     ///
 531     /// Basic usage:
 532     ///
 533     /// ```
 534     /// let mut one_element = [0].iter();
 535     /// assert!(!one_element.is_empty());
 536     ///
 537     /// assert_eq!(one_element.next(), Some(0));
 538     /// assert!(one_element.is_empty());
 539     ///
 540     /// assert_eq!(one_element.next(), None);
 541     /// ```
 542     #[inline]
 543     #[unstable(feature = "exact_size_is_empty", issue = "0")]
 544     fn is_empty(&self) -> bool {
 545         self.len() == 0
 546     }
 547 }
 548
 549 #[stable(feature = "rust1", since = "1.0.0")]
 550 impl<'a, I: ExactSizeIterator + ?Sized> ExactSizeIterator for &'a mut I {}
 551