src/libcore/iter/sources.rs

   1 use fmt;
   2 use marker;
   3 use usize;
   4
   5 use super::{FusedIterator, TrustedLen};
   6
   7 /// An iterator that repeats an element endlessly.
   8 ///
   9 /// This `struct` is created by the [`repeat`] function. See its documentation for more.
  10 ///
  11 /// [`repeat`]: fn.repeat.html
  12 #[derive(Clone, Debug)]
  13 #[stable(feature = "rust1", since = "1.0.0")]
  14 pub struct Repeat<A> {
  15     element: A
  16 }
  17
  18 #[stable(feature = "rust1", since = "1.0.0")]
  19 impl<A: Clone> Iterator for Repeat<A> {
  20     type Item = A;
  21
  22     #[inline]
  23     fn next(&mut self) -> Option<A> { Some(self.element.clone()) }
  24     #[inline]
  25     fn size_hint(&self) -> (usize, Option<usize>) { (usize::MAX, None) }
  26 }
  27
  28 #[stable(feature = "rust1", since = "1.0.0")]
  29 impl<A: Clone> DoubleEndedIterator for Repeat<A> {
  30     #[inline]
  31     fn next_back(&mut self) -> Option<A> { Some(self.element.clone()) }
  32 }
  33
  34 #[stable(feature = "fused", since = "1.26.0")]
  35 impl<A: Clone> FusedIterator for Repeat<A> {}
  36
  37 #[unstable(feature = "trusted_len", issue = "37572")]
  38 unsafe impl<A: Clone> TrustedLen for Repeat<A> {}
  39
  40 /// Creates a new iterator that endlessly repeats a single element.
  41 ///
  42 /// The `repeat()` function repeats a single value over and over again.
  43 ///
  44 /// Infinite iterators like `repeat()` are often used with adapters like
  45 /// [`take`], in order to make them finite.
  46 ///
  47 /// [`take`]: trait.Iterator.html#method.take
  48 ///
  49 /// If the element type of the iterator you need does not implement `Clone`,
  50 /// or if you do not want to keep the repeated element in memory, you can
  51 /// instead use the [`repeat_with`] function.
  52 ///
  53 /// [`repeat_with`]: fn.repeat_with.html
  54 ///
  55 /// # Examples
  56 ///
  57 /// Basic usage:
  58 ///
  59 /// ```
  60 /// use std::iter;
  61 ///
  62 /// // the number four 4ever:
  63 /// let mut fours = iter::repeat(4);
  64 ///
  65 /// assert_eq!(Some(4), fours.next());
  66 /// assert_eq!(Some(4), fours.next());
  67 /// assert_eq!(Some(4), fours.next());
  68 /// assert_eq!(Some(4), fours.next());
  69 /// assert_eq!(Some(4), fours.next());
  70 ///
  71 /// // yup, still four
  72 /// assert_eq!(Some(4), fours.next());
  73 /// ```
  74 ///
  75 /// Going finite with [`take`]:
  76 ///
  77 /// ```
  78 /// use std::iter;
  79 ///
  80 /// // that last example was too many fours. Let's only have four fours.
  81 /// let mut four_fours = iter::repeat(4).take(4);
  82 ///
  83 /// assert_eq!(Some(4), four_fours.next());
  84 /// assert_eq!(Some(4), four_fours.next());
  85 /// assert_eq!(Some(4), four_fours.next());
  86 /// assert_eq!(Some(4), four_fours.next());
  87 ///
  88 /// // ... and now we're done
  89 /// assert_eq!(None, four_fours.next());
  90 /// ```
  91 #[inline]
  92 #[stable(feature = "rust1", since = "1.0.0")]
  93 pub fn repeat<T: Clone>(elt: T) -> Repeat<T> {
  94     Repeat{element: elt}
  95 }
  96
  97 /// An iterator that repeats elements of type `A` endlessly by
  98 /// applying the provided closure `F: FnMut() -> A`.
  99 ///
 100 /// This `struct` is created by the [`repeat_with`] function.
 101 /// See its documentation for more.
 102 ///
 103 /// [`repeat_with`]: fn.repeat_with.html
 104 #[derive(Copy, Clone, Debug)]
 105 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
 106 pub struct RepeatWith<F> {
 107     repeater: F
 108 }
 109
 110 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
 111 impl<A, F: FnMut() -> A> Iterator for RepeatWith<F> {
 112     type Item = A;
 113
 114     #[inline]
 115     fn next(&mut self) -> Option<A> { Some((self.repeater)()) }
 116
 117     #[inline]
 118     fn size_hint(&self) -> (usize, Option<usize>) { (usize::MAX, None) }
 119 }
 120
 121 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
 122 impl<A, F: FnMut() -> A> FusedIterator for RepeatWith<F> {}
 123
 124 #[unstable(feature = "trusted_len", issue = "37572")]
 125 unsafe impl<A, F: FnMut() -> A> TrustedLen for RepeatWith<F> {}
 126
 127 /// Creates a new iterator that repeats elements of type `A` endlessly by
 128 /// applying the provided closure, the repeater, `F: FnMut() -> A`.
 129 ///
 130 /// The `repeat_with()` function calls the repeater over and over again.
 131 ///
 132 /// Infinite iterators like `repeat_with()` are often used with adapters like
 133 /// [`take`], in order to make them finite.
 134 ///
 135 /// [`take`]: trait.Iterator.html#method.take
 136 ///
 137 /// If the element type of the iterator you need implements `Clone`, and
 138 /// it is OK to keep the source element in memory, you should instead use
 139 /// the [`repeat`] function.
 140 ///
 141 /// [`repeat`]: fn.repeat.html
 142 ///
 143 /// An iterator produced by `repeat_with()` is not a `DoubleEndedIterator`.
 144 /// If you need `repeat_with()` to return a `DoubleEndedIterator`,
 145 /// please open a GitHub issue explaining your use case.
 146 ///
 147 /// # Examples
 148 ///
 149 /// Basic usage:
 150 ///
 151 /// ```
 152 /// use std::iter;
 153 ///
 154 /// // let's assume we have some value of a type that is not `Clone`
 155 /// // or which don't want to have in memory just yet because it is expensive:
 156 /// #[derive(PartialEq, Debug)]
 157 /// struct Expensive;
 158 ///
 159 /// // a particular value forever:
 160 /// let mut things = iter::repeat_with(|| Expensive);
 161 ///
 162 /// assert_eq!(Some(Expensive), things.next());
 163 /// assert_eq!(Some(Expensive), things.next());
 164 /// assert_eq!(Some(Expensive), things.next());
 165 /// assert_eq!(Some(Expensive), things.next());
 166 /// assert_eq!(Some(Expensive), things.next());
 167 /// ```
 168 ///
 169 /// Using mutation and going finite:
 170 ///
 171 /// ```rust
 172 /// use std::iter;
 173 ///
 174 /// // From the zeroth to the third power of two:
 175 /// let mut curr = 1;
 176 /// let mut pow2 = iter::repeat_with(|| { let tmp = curr; curr *= 2; tmp })
 177 ///                     .take(4);
 178 ///
 179 /// assert_eq!(Some(1), pow2.next());
 180 /// assert_eq!(Some(2), pow2.next());
 181 /// assert_eq!(Some(4), pow2.next());
 182 /// assert_eq!(Some(8), pow2.next());
 183 ///
 184 /// // ... and now we're done
 185 /// assert_eq!(None, pow2.next());
 186 /// ```
 187 #[inline]
 188 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
 189 pub fn repeat_with<A, F: FnMut() -> A>(repeater: F) -> RepeatWith<F> {
 190     RepeatWith { repeater }
 191 }
 192
 193 /// An iterator that yields nothing.
 194 ///
 195 /// This `struct` is created by the [`empty`] function. See its documentation for more.
 196 ///
 197 /// [`empty`]: fn.empty.html
 198 #[stable(feature = "iter_empty", since = "1.2.0")]
 199 pub struct Empty<T>(marker::PhantomData<T>);
 200
 201 #[stable(feature = "core_impl_debug", since = "1.9.0")]
 202 impl<T> fmt::Debug for Empty<T> {
 203     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 204         f.pad("Empty")
 205     }
 206 }
 207
 208 #[stable(feature = "iter_empty", since = "1.2.0")]
 209 impl<T> Iterator for Empty<T> {
 210     type Item = T;
 211
 212     fn next(&mut self) -> Option<T> {
 213         None
 214     }
 215
 216     fn size_hint(&self) -> (usize, Option<usize>){
 217         (0, Some(0))
 218     }
 219 }
 220
 221 #[stable(feature = "iter_empty", since = "1.2.0")]
 222 impl<T> DoubleEndedIterator for Empty<T> {
 223     fn next_back(&mut self) -> Option<T> {
 224         None
 225     }
 226 }
 227
 228 #[stable(feature = "iter_empty", since = "1.2.0")]
 229 impl<T> ExactSizeIterator for Empty<T> {
 230     fn len(&self) -> usize {
 231         0
 232     }
 233 }
 234
 235 #[unstable(feature = "trusted_len", issue = "37572")]
 236 unsafe impl<T> TrustedLen for Empty<T> {}
 237
 238 #[stable(feature = "fused", since = "1.26.0")]
 239 impl<T> FusedIterator for Empty<T> {}
 240
 241 // not #[derive] because that adds a Clone bound on T,
 242 // which isn't necessary.
 243 #[stable(feature = "iter_empty", since = "1.2.0")]
 244 impl<T> Clone for Empty<T> {
 245     fn clone(&self) -> Empty<T> {
 246         Empty(marker::PhantomData)
 247     }
 248 }
 249
 250 // not #[derive] because that adds a Default bound on T,
 251 // which isn't necessary.
 252 #[stable(feature = "iter_empty", since = "1.2.0")]
 253 impl<T> Default for Empty<T> {
 254     fn default() -> Empty<T> {
 255         Empty(marker::PhantomData)
 256     }
 257 }
 258
 259 /// Creates an iterator that yields nothing.
 260 ///
 261 /// # Examples
 262 ///
 263 /// Basic usage:
 264 ///
 265 /// ```
 266 /// use std::iter;
 267 ///
 268 /// // this could have been an iterator over i32, but alas, it's just not.
 269 /// let mut nope = iter::empty::<i32>();
 270 ///
 271 /// assert_eq!(None, nope.next());
 272 /// ```
 273 #[stable(feature = "iter_empty", since = "1.2.0")]
 274 pub const fn empty<T>() -> Empty<T> {
 275     Empty(marker::PhantomData)
 276 }
 277
 278 /// An iterator that yields an element exactly once.
 279 ///
 280 /// This `struct` is created by the [`once`] function. See its documentation for more.
 281 ///
 282 /// [`once`]: fn.once.html
 283 #[derive(Clone, Debug)]
 284 #[stable(feature = "iter_once", since = "1.2.0")]
 285 pub struct Once<T> {
 286     inner: ::option::IntoIter<T>
 287 }
 288
 289 #[stable(feature = "iter_once", since = "1.2.0")]
 290 impl<T> Iterator for Once<T> {
 291     type Item = T;
 292
 293     fn next(&mut self) -> Option<T> {
 294         self.inner.next()
 295     }
 296
 297     fn size_hint(&self) -> (usize, Option<usize>) {
 298         self.inner.size_hint()
 299     }
 300 }
 301
 302 #[stable(feature = "iter_once", since = "1.2.0")]
 303 impl<T> DoubleEndedIterator for Once<T> {
 304     fn next_back(&mut self) -> Option<T> {
 305         self.inner.next_back()
 306     }
 307 }
 308
 309 #[stable(feature = "iter_once", since = "1.2.0")]
 310 impl<T> ExactSizeIterator for Once<T> {
 311     fn len(&self) -> usize {
 312         self.inner.len()
 313     }
 314 }
 315
 316 #[unstable(feature = "trusted_len", issue = "37572")]
 317 unsafe impl<T> TrustedLen for Once<T> {}
 318
 319 #[stable(feature = "fused", since = "1.26.0")]
 320 impl<T> FusedIterator for Once<T> {}
 321
 322 /// Creates an iterator that yields an element exactly once.
 323 ///
 324 /// This is commonly used to adapt a single value into a [`chain`] of other
 325 /// kinds of iteration. Maybe you have an iterator that covers almost
 326 /// everything, but you need an extra special case. Maybe you have a function
 327 /// which works on iterators, but you only need to process one value.
 328 ///
 329 /// [`chain`]: trait.Iterator.html#method.chain
 330 ///
 331 /// # Examples
 332 ///
 333 /// Basic usage:
 334 ///
 335 /// ```
 336 /// use std::iter;
 337 ///
 338 /// // one is the loneliest number
 339 /// let mut one = iter::once(1);
 340 ///
 341 /// assert_eq!(Some(1), one.next());
 342 ///
 343 /// // just one, that's all we get
 344 /// assert_eq!(None, one.next());
 345 /// ```
 346 ///
 347 /// Chaining together with another iterator. Let's say that we want to iterate
 348 /// over each file of the `.foo` directory, but also a configuration file,
 349 /// `.foorc`:
 350 ///
 351 /// ```no_run
 352 /// use std::iter;
 353 /// use std::fs;
 354 /// use std::path::PathBuf;
 355 ///
 356 /// let dirs = fs::read_dir(".foo").unwrap();
 357 ///
 358 /// // we need to convert from an iterator of DirEntry-s to an iterator of
 359 /// // PathBufs, so we use map
 360 /// let dirs = dirs.map(|file| file.unwrap().path());
 361 ///
 362 /// // now, our iterator just for our config file
 363 /// let config = iter::once(PathBuf::from(".foorc"));
 364 ///
 365 /// // chain the two iterators together into one big iterator
 366 /// let files = dirs.chain(config);
 367 ///
 368 /// // this will give us all of the files in .foo as well as .foorc
 369 /// for f in files {
 370 ///     println!("{:?}", f);
 371 /// }
 372 /// ```
 373 #[stable(feature = "iter_once", since = "1.2.0")]
 374 pub fn once<T>(value: T) -> Once<T> {
 375     Once { inner: Some(value).into_iter() }
 376 }
 377
 378 /// An iterator that yields a single element of type `A` by
 379 /// applying the provided closure `F: FnOnce() -> A`.
 380 ///
 381 /// This `struct` is created by the [`once_with`] function.
 382 /// See its documentation for more.
 383 ///
 384 /// [`once_with`]: fn.once_with.html
 385 #[derive(Copy, Clone, Debug)]
 386 #[unstable(feature = "iter_once_with", issue = "57581")]
 387 pub struct OnceWith<F> {
 388     gen: Option<F>,
 389 }
 390
 391 #[unstable(feature = "iter_once_with", issue = "57581")]
 392 impl<A, F: FnOnce() -> A> Iterator for OnceWith<F> {
 393     type Item = A;
 394
 395     #[inline]
 396     fn next(&mut self) -> Option<A> {
 397         self.gen.take().map(|f| f())
 398     }
 399
 400     #[inline]
 401     fn size_hint(&self) -> (usize, Option<usize>) {
 402         self.gen.iter().size_hint()
 403     }
 404 }
 405
 406 #[unstable(feature = "iter_once_with", issue = "57581")]
 407 impl<A, F: FnOnce() -> A> DoubleEndedIterator for OnceWith<F> {
 408     fn next_back(&mut self) -> Option<A> {
 409         self.next()
 410     }
 411 }
 412
 413 #[unstable(feature = "iter_once_with", issue = "57581")]
 414 impl<A, F: FnOnce() -> A> ExactSizeIterator for OnceWith<F> {
 415     fn len(&self) -> usize {
 416         self.gen.iter().len()
 417     }
 418 }
 419
 420 #[unstable(feature = "iter_once_with", issue = "57581")]
 421 impl<A, F: FnOnce() -> A> FusedIterator for OnceWith<F> {}
 422
 423 #[unstable(feature = "iter_once_with", issue = "57581")]
 424 unsafe impl<A, F: FnOnce() -> A> TrustedLen for OnceWith<F> {}
 425
 426 /// Creates an iterator that lazily generates a value exactly once by invoking
 427 /// the provided closure.
 428 ///
 429 /// This is commonly used to adapt a single value generator into a [`chain`] of
 430 /// other kinds of iteration. Maybe you have an iterator that covers almost
 431 /// everything, but you need an extra special case. Maybe you have a function
 432 /// which works on iterators, but you only need to process one value.
 433 ///
 434 /// Unlike [`once`], this function will lazily generate the value on request.
 435 ///
 436 /// [`once`]: fn.once.html
 437 /// [`chain`]: trait.Iterator.html#method.chain
 438 ///
 439 /// # Examples
 440 ///
 441 /// Basic usage:
 442 ///
 443 /// ```
 444 /// #![feature(iter_once_with)]
 445 ///
 446 /// use std::iter;
 447 ///
 448 /// // one is the loneliest number
 449 /// let mut one = iter::once_with(|| 1);
 450 ///
 451 /// assert_eq!(Some(1), one.next());
 452 ///
 453 /// // just one, that's all we get
 454 /// assert_eq!(None, one.next());
 455 /// ```
 456 ///
 457 /// Chaining together with another iterator. Let's say that we want to iterate
 458 /// over each file of the `.foo` directory, but also a configuration file,
 459 /// `.foorc`:
 460 ///
 461 /// ```no_run
 462 /// #![feature(iter_once_with)]
 463 ///
 464 /// use std::iter;
 465 /// use std::fs;
 466 /// use std::path::PathBuf;
 467 ///
 468 /// let dirs = fs::read_dir(".foo").unwrap();
 469 ///
 470 /// // we need to convert from an iterator of DirEntry-s to an iterator of
 471 /// // PathBufs, so we use map
 472 /// let dirs = dirs.map(|file| file.unwrap().path());
 473 ///
 474 /// // now, our iterator just for our config file
 475 /// let config = iter::once_with(|| PathBuf::from(".foorc"));
 476 ///
 477 /// // chain the two iterators together into one big iterator
 478 /// let files = dirs.chain(config);
 479 ///
 480 /// // this will give us all of the files in .foo as well as .foorc
 481 /// for f in files {
 482 ///     println!("{:?}", f);
 483 /// }
 484 /// ```
 485 #[inline]
 486 #[unstable(feature = "iter_once_with", issue = "57581")]
 487 pub fn once_with<A, F: FnOnce() -> A>(gen: F) -> OnceWith<F> {
 488     OnceWith { gen: Some(gen) }
 489 }
 490
 491 /// Creates a new iterator where each iteration calls the provided closure
 492 /// `F: FnMut() -> Option<T>`.
 493 ///
 494 /// This allows creating a custom iterator with any behavior
 495 /// without using the more verbose syntax of creating a dedicated type
 496 /// and implementing the `Iterator` trait for it.
 497 ///
 498 /// Note that the `FromFn` iterator doesn’t make assumptions about the behavior of the closure,
 499 /// and therefore conservatively does not implement [`FusedIterator`],
 500 /// or override [`Iterator::size_hint`] from its default `(0, None)`.
 501 ///
 502 /// [`FusedIterator`]: trait.FusedIterator.html
 503 /// [`Iterator::size_hint`]: trait.Iterator.html#method.size_hint
 504 ///
 505 /// The closure can use captures and its environment to track state across iterations. Depending on
 506 /// how the iterator is used, this may require specifying the `move` keyword on the closure.
 507 ///
 508 /// # Examples
 509 ///
 510 /// Let’s re-implement the counter iterator from [module-level documentation]:
 511 ///
 512 /// [module-level documentation]: index.html
 513 ///
 514 /// ```
 515 /// let mut count = 0;
 516 /// let counter = std::iter::from_fn(move || {
 517 ///     // Increment our count. This is why we started at zero.
 518 ///     count += 1;
 519 ///
 520 ///     // Check to see if we've finished counting or not.
 521 ///     if count < 6 {
 522 ///         Some(count)
 523 ///     } else {
 524 ///         None
 525 ///     }
 526 /// });
 527 /// assert_eq!(counter.collect::<Vec<_>>(), &[1, 2, 3, 4, 5]);
 528 /// ```
 529 #[inline]
 530 #[stable(feature = "iter_from_fn", since = "1.34.0")]
 531 pub fn from_fn<T, F>(f: F) -> FromFn<F>
 532     where F: FnMut() -> Option<T>
 533 {
 534     FromFn(f)
 535 }
 536
 537 /// An iterator where each iteration calls the provided closure `F: FnMut() -> Option<T>`.
 538 ///
 539 /// This `struct` is created by the [`iter::from_fn`] function.
 540 /// See its documentation for more.
 541 ///
 542 /// [`iter::from_fn`]: fn.from_fn.html
 543 #[derive(Clone)]
 544 #[stable(feature = "iter_from_fn", since = "1.34.0")]
 545 pub struct FromFn<F>(F);
 546
 547 #[stable(feature = "iter_from_fn", since = "1.34.0")]
 548 impl<T, F> Iterator for FromFn<F>
 549     where F: FnMut() -> Option<T>
 550 {
 551     type Item = T;
 552
 553     #[inline]
 554     fn next(&mut self) -> Option<Self::Item> {
 555         (self.0)()
 556     }
 557 }
 558
 559 #[stable(feature = "iter_from_fn", since = "1.34.0")]
 560 impl<F> fmt::Debug for FromFn<F> {
 561     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 562         f.debug_struct("FromFn").finish()
 563     }
 564 }
 565
 566 /// Creates a new iterator where each successive item is computed based on the preceding one.
 567 ///
 568 /// The iterator starts with the given first item (if any)
 569 /// and calls the given `FnMut(&T) -> Option<T>` closure to compute each item’s successor.
 570 ///
 571 /// ```
 572 /// use std::iter::successors;
 573 ///
 574 /// let powers_of_10 = successors(Some(1_u16), |n| n.checked_mul(10));
 575 /// assert_eq!(powers_of_10.collect::<Vec<_>>(), &[1, 10, 100, 1_000, 10_000]);
 576 /// ```
 577 #[stable(feature = "iter_successors", since = "1.34.0")]
 578 pub fn successors<T, F>(first: Option<T>, succ: F) -> Successors<T, F>
 579     where F: FnMut(&T) -> Option<T>
 580 {
 581     // If this function returned `impl Iterator<Item=T>`
 582     // it could be based on `unfold` and not need a dedicated type.
 583     // However having a named `Successors<T, F>` type allows it to be `Clone` when `T` and `F` are.
 584     Successors {
 585         next: first,
 586         succ,
 587     }
 588 }
 589
 590 /// An new iterator where each successive item is computed based on the preceding one.
 591 ///
 592 /// This `struct` is created by the [`successors`] function.
 593 /// See its documentation for more.
 594 ///
 595 /// [`successors`]: fn.successors.html
 596 #[derive(Clone)]
 597 #[stable(feature = "iter_successors", since = "1.34.0")]
 598 pub struct Successors<T, F> {
 599     next: Option<T>,
 600     succ: F,
 601 }
 602
 603 #[stable(feature = "iter_successors", since = "1.34.0")]
 604 impl<T, F> Iterator for Successors<T, F>
 605     where F: FnMut(&T) -> Option<T>
 606 {
 607     type Item = T;
 608
 609     #[inline]
 610     fn next(&mut self) -> Option<Self::Item> {
 611         self.next.take().map(|item| {
 612             self.next = (self.succ)(&item);
 613             item
 614         })
 615     }
 616
 617     #[inline]
 618     fn size_hint(&self) -> (usize, Option<usize>) {
 619         if self.next.is_some() {
 620             (1, None)
 621         } else {
 622             (0, Some(0))
 623         }
 624     }
 625 }
 626
 627 #[stable(feature = "iter_successors", since = "1.34.0")]
 628 impl<T, F> FusedIterator for Successors<T, F>
 629     where F: FnMut(&T) -> Option<T>
 630 {}
 631
 632 #[stable(feature = "iter_successors", since = "1.34.0")]
 633 impl<T: fmt::Debug, F> fmt::Debug for Successors<T, F> {
 634     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 635         f.debug_struct("Successors")
 636             .field("next", &self.next)
 637             .finish()
 638     }
 639 }