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