library/core/src/iter/sources.rs

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