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 and over and
  43 /// over and over and 🔁.
  44 ///
  45 /// Infinite iterators like `repeat()` are often used with adapters like
  46 /// [`take`], in order to make them finite.
  47 ///
  48 /// [`take`]: trait.Iterator.html#method.take
  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 /// [`repeat_with`]: fn.repeat_with.html
  55 ///
  56 /// # Examples
  57 ///
  58 /// Basic usage:
  59 ///
  60 /// ```
  61 /// use std::iter;
  62 ///
  63 /// // the number four 4ever:
  64 /// let mut fours = iter::repeat(4);
  65 ///
  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 /// assert_eq!(Some(4), fours.next());
  71 ///
  72 /// // yup, still four
  73 /// assert_eq!(Some(4), fours.next());
  74 /// ```
  75 ///
  76 /// Going finite with [`take`]:
  77 ///
  78 /// ```
  79 /// use std::iter;
  80 ///
  81 /// // that last example was too many fours. Let's only have four fours.
  82 /// let mut four_fours = iter::repeat(4).take(4);
  83 ///
  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 /// assert_eq!(Some(4), four_fours.next());
  88 ///
  89 /// // ... and now we're done
  90 /// assert_eq!(None, four_fours.next());
  91 /// ```
  92 #[inline]
  93 #[stable(feature = "rust1", since = "1.0.0")]
  94 pub fn repeat<T: Clone>(elt: T) -> Repeat<T> {
  95     Repeat{element: elt}
  96 }
  97
  98 /// An iterator that repeats elements of type `A` endlessly by
  99 /// applying the provided closure `F: FnMut() -> A`.
 100 ///
 101 /// This `struct` is created by the [`repeat_with`] function.
 102 /// See its documentation for more.
 103 ///
 104 /// [`repeat_with`]: fn.repeat_with.html
 105 #[derive(Copy, Clone, Debug)]
 106 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
 107 pub struct RepeatWith<F> {
 108     repeater: F
 109 }
 110
 111 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
 112 impl<A, F: FnMut() -> A> Iterator for RepeatWith<F> {
 113     type Item = A;
 114
 115     #[inline]
 116     fn next(&mut self) -> Option<A> { Some((self.repeater)()) }
 117
 118     #[inline]
 119     fn size_hint(&self) -> (usize, Option<usize>) { (usize::MAX, None) }
 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 and over and
 132 /// over and over and 🔁.
 133 ///
 134 /// Infinite iterators like `repeat_with()` are often used with adapters like
 135 /// [`take`], in order to make them finite.
 136 ///
 137 /// [`take`]: trait.Iterator.html#method.take
 138 ///
 139 /// If the element type of the iterator you need implements `Clone`, and
 140 /// it is OK to keep the source element in memory, you should instead use
 141 /// the [`repeat`] function.
 142 ///
 143 /// [`repeat`]: fn.repeat.html
 144 ///
 145 /// An iterator produced by `repeat_with()` is not a `DoubleEndedIterator`.
 146 /// If you need `repeat_with()` to return a `DoubleEndedIterator`,
 147 /// please open a GitHub issue explaining your use case.
 148 ///
 149 /// # Examples
 150 ///
 151 /// Basic usage:
 152 ///
 153 /// ```
 154 /// use std::iter;
 155 ///
 156 /// // let's assume we have some value of a type that is not `Clone`
 157 /// // or which don't want to have in memory just yet because it is expensive:
 158 /// #[derive(PartialEq, Debug)]
 159 /// struct Expensive;
 160 ///
 161 /// // a particular value forever:
 162 /// let mut things = iter::repeat_with(|| Expensive);
 163 ///
 164 /// assert_eq!(Some(Expensive), things.next());
 165 /// assert_eq!(Some(Expensive), things.next());
 166 /// assert_eq!(Some(Expensive), things.next());
 167 /// assert_eq!(Some(Expensive), things.next());
 168 /// assert_eq!(Some(Expensive), things.next());
 169 /// ```
 170 ///
 171 /// Using mutation and going finite:
 172 ///
 173 /// ```rust
 174 /// use std::iter;
 175 ///
 176 /// // From the zeroth to the third power of two:
 177 /// let mut curr = 1;
 178 /// let mut pow2 = iter::repeat_with(|| { let tmp = curr; curr *= 2; tmp })
 179 ///                     .take(4);
 180 ///
 181 /// assert_eq!(Some(1), pow2.next());
 182 /// assert_eq!(Some(2), pow2.next());
 183 /// assert_eq!(Some(4), pow2.next());
 184 /// assert_eq!(Some(8), pow2.next());
 185 ///
 186 /// // ... and now we're done
 187 /// assert_eq!(None, pow2.next());
 188 /// ```
 189 #[inline]
 190 #[stable(feature = "iterator_repeat_with", since = "1.28.0")]
 191 pub fn repeat_with<A, F: FnMut() -> A>(repeater: F) -> RepeatWith<F> {
 192     RepeatWith { repeater }
 193 }
 194
 195 /// An iterator that yields nothing.
 196 ///
 197 /// This `struct` is created by the [`empty`] function. See its documentation for more.
 198 ///
 199 /// [`empty`]: fn.empty.html
 200 #[stable(feature = "iter_empty", since = "1.2.0")]
 201 pub struct Empty<T>(marker::PhantomData<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 pub const fn empty<T>() -> Empty<T> {
 277     Empty(marker::PhantomData)
 278 }
 279
 280 /// An iterator that yields an element exactly once.
 281 ///
 282 /// This `struct` is created by the [`once`] function. See its documentation for more.
 283 ///
 284 /// [`once`]: fn.once.html
 285 #[derive(Clone, Debug)]
 286 #[stable(feature = "iter_once", since = "1.2.0")]
 287 pub struct Once<T> {
 288     inner: ::option::IntoIter<T>
 289 }
 290
 291 #[stable(feature = "iter_once", since = "1.2.0")]
 292 impl<T> Iterator for Once<T> {
 293     type Item = T;
 294
 295     fn next(&mut self) -> Option<T> {
 296         self.inner.next()
 297     }
 298
 299     fn size_hint(&self) -> (usize, Option<usize>) {
 300         self.inner.size_hint()
 301     }
 302 }
 303
 304 #[stable(feature = "iter_once", since = "1.2.0")]
 305 impl<T> DoubleEndedIterator for Once<T> {
 306     fn next_back(&mut self) -> Option<T> {
 307         self.inner.next_back()
 308     }
 309 }
 310
 311 #[stable(feature = "iter_once", since = "1.2.0")]
 312 impl<T> ExactSizeIterator for Once<T> {
 313     fn len(&self) -> usize {
 314         self.inner.len()
 315     }
 316 }
 317
 318 #[unstable(feature = "trusted_len", issue = "37572")]
 319 unsafe impl<T> TrustedLen for Once<T> {}
 320
 321 #[stable(feature = "fused", since = "1.26.0")]
 322 impl<T> FusedIterator for Once<T> {}
 323
 324 /// Creates an iterator that yields an element exactly once.
 325 ///
 326 /// This is commonly used to adapt a single value into a [`chain`] of other
 327 /// kinds of iteration. Maybe you have an iterator that covers almost
 328 /// everything, but you need an extra special case. Maybe you have a function
 329 /// which works on iterators, but you only need to process one value.
 330 ///
 331 /// [`chain`]: trait.Iterator.html#method.chain
 332 ///
 333 /// # Examples
 334 ///
 335 /// Basic usage:
 336 ///
 337 /// ```
 338 /// use std::iter;
 339 ///
 340 /// // one is the loneliest number
 341 /// let mut one = iter::once(1);
 342 ///
 343 /// assert_eq!(Some(1), one.next());
 344 ///
 345 /// // just one, that's all we get
 346 /// assert_eq!(None, one.next());
 347 /// ```
 348 ///
 349 /// Chaining together with another iterator. Let's say that we want to iterate
 350 /// over each file of the `.foo` directory, but also a configuration file,
 351 /// `.foorc`:
 352 ///
 353 /// ```no_run
 354 /// use std::iter;
 355 /// use std::fs;
 356 /// use std::path::PathBuf;
 357 ///
 358 /// let dirs = fs::read_dir(".foo").unwrap();
 359 ///
 360 /// // we need to convert from an iterator of DirEntry-s to an iterator of
 361 /// // PathBufs, so we use map
 362 /// let dirs = dirs.map(|file| file.unwrap().path());
 363 ///
 364 /// // now, our iterator just for our config file
 365 /// let config = iter::once(PathBuf::from(".foorc"));
 366 ///
 367 /// // chain the two iterators together into one big iterator
 368 /// let files = dirs.chain(config);
 369 ///
 370 /// // this will give us all of the files in .foo as well as .foorc
 371 /// for f in files {
 372 ///     println!("{:?}", f);
 373 /// }
 374 /// ```
 375 #[stable(feature = "iter_once", since = "1.2.0")]
 376 pub fn once<T>(value: T) -> Once<T> {
 377     Once { inner: Some(value).into_iter() }
 378 }
 379
 380 /// An iterator that repeats elements of type `A` endlessly by
 381 /// applying the provided closure `F: FnMut() -> A`.
 382 ///
 383 /// This `struct` is created by the [`once_with`] function.
 384 /// See its documentation for more.
 385 ///
 386 /// [`once_with`]: fn.once_with.html
 387 #[derive(Copy, Clone, Debug)]
 388 #[unstable(feature = "iter_once_with", issue = "57581")]
 389 pub struct OnceWith<F> {
 390     gen: Option<F>,
 391 }
 392
 393 #[unstable(feature = "iter_once_with", issue = "57581")]
 394 impl<A, F: FnOnce() -> A> Iterator for OnceWith<F> {
 395     type Item = A;
 396
 397     #[inline]
 398     fn next(&mut self) -> Option<A> {
 399         self.gen.take().map(|f| f())
 400     }
 401
 402     #[inline]
 403     fn size_hint(&self) -> (usize, Option<usize>) {
 404         self.gen.iter().size_hint()
 405     }
 406 }
 407
 408 #[unstable(feature = "iter_once_with", issue = "57581")]
 409 impl<A, F: FnOnce() -> A> DoubleEndedIterator for OnceWith<F> {
 410     fn next_back(&mut self) -> Option<A> {
 411         self.next()
 412     }
 413 }
 414
 415 #[unstable(feature = "iter_once_with", issue = "57581")]
 416 impl<A, F: FnOnce() -> A> ExactSizeIterator for OnceWith<F> {
 417     fn len(&self) -> usize {
 418         self.gen.iter().len()
 419     }
 420 }
 421
 422 #[unstable(feature = "iter_once_with", issue = "57581")]
 423 impl<A, F: FnOnce() -> A> FusedIterator for OnceWith<F> {}
 424
 425 #[unstable(feature = "iter_once_with", issue = "57581")]
 426 unsafe impl<A, F: FnOnce() -> A> TrustedLen for OnceWith<F> {}
 427
 428 /// Creates an iterator that lazily generates a value exactly once by invoking
 429 /// the provided closure.
 430 ///
 431 /// This is commonly used to adapt a single value generator into a [`chain`] of
 432 /// other kinds of iteration. Maybe you have an iterator that covers almost
 433 /// everything, but you need an extra special case. Maybe you have a function
 434 /// which works on iterators, but you only need to process one value.
 435 ///
 436 /// Unlike [`once`], this function will lazily generate the value on request.
 437 ///
 438 /// [`once`]: fn.once.html
 439 /// [`chain`]: trait.Iterator.html#method.chain
 440 ///
 441 /// # Examples
 442 ///
 443 /// Basic usage:
 444 ///
 445 /// ```
 446 /// #![feature(iter_once_with)]
 447 ///
 448 /// use std::iter;
 449 ///
 450 /// // one is the loneliest number
 451 /// let mut one = iter::once_with(|| 1);
 452 ///
 453 /// assert_eq!(Some(1), one.next());
 454 ///
 455 /// // just one, that's all we get
 456 /// assert_eq!(None, one.next());
 457 /// ```
 458 ///
 459 /// Chaining together with another iterator. Let's say that we want to iterate
 460 /// over each file of the `.foo` directory, but also a configuration file,
 461 /// `.foorc`:
 462 ///
 463 /// ```no_run
 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(&mut St) -> 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 /// In addition to its captures and environment,
 499 /// the closure is given a mutable reference to some state
 500 /// that is preserved across iterations.
 501 /// That state starts as the given `initial_state` value.
 502 ///
 503 /// Note that the `Unfold` iterator doesn’t make assumptions about the behavior of the closure,
 504 /// and therefore conservatively does not implement [`FusedIterator`],
 505 /// or override [`Iterator::size_hint`] from its default `(0, None)`.
 506 ///
 507 /// [`FusedIterator`]: trait.FusedIterator.html
 508 /// [`Iterator::size_hint`]: trait.Iterator.html#method.size_hint
 509 ///
 510 /// # Examples
 511 ///
 512 /// Let’s re-implement the counter iterator from [module-level documentation]:
 513 ///
 514 /// [module-level documentation]: index.html
 515 ///
 516 /// ```
 517 /// #![feature(iter_unfold)]
 518 /// let counter = std::iter::unfold(0, |count| {
 519 ///     // Increment our count. This is why we started at zero.
 520 ///     *count += 1;
 521 ///
 522 ///     // Check to see if we've finished counting or not.
 523 ///     if *count < 6 {
 524 ///         Some(*count)
 525 ///     } else {
 526 ///         None
 527 ///     }
 528 /// });
 529 /// assert_eq!(counter.collect::<Vec<_>>(), &[1, 2, 3, 4, 5]);
 530 /// ```
 531 #[inline]
 532 #[unstable(feature = "iter_unfold", issue = "55977")]
 533 pub fn unfold<St, T, F>(initial_state: St, f: F) -> Unfold<St, F>
 534     where F: FnMut(&mut St) -> Option<T>
 535 {
 536     Unfold {
 537         state: initial_state,
 538         f,
 539     }
 540 }
 541
 542 /// An iterator where each iteration calls the provided closure `F: FnMut(&mut St) -> Option<T>`.
 543 ///
 544 /// This `struct` is created by the [`unfold`] function.
 545 /// See its documentation for more.
 546 ///
 547 /// [`unfold`]: fn.unfold.html
 548 #[derive(Clone)]
 549 #[unstable(feature = "iter_unfold", issue = "55977")]
 550 pub struct Unfold<St, F> {
 551     state: St,
 552     f: F,
 553 }
 554
 555 #[unstable(feature = "iter_unfold", issue = "55977")]
 556 impl<St, T, F> Iterator for Unfold<St, F>
 557     where F: FnMut(&mut St) -> Option<T>
 558 {
 559     type Item = T;
 560
 561     #[inline]
 562     fn next(&mut self) -> Option<Self::Item> {
 563         (self.f)(&mut self.state)
 564     }
 565 }
 566
 567 #[unstable(feature = "iter_unfold", issue = "55977")]
 568 impl<St: fmt::Debug, F> fmt::Debug for Unfold<St, F> {
 569     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 570         f.debug_struct("Unfold")
 571             .field("state", &self.state)
 572             .finish()
 573     }
 574 }
 575
 576 /// Creates a new iterator where each successive item is computed based on the preceding one.
 577 ///
 578 /// The iterator starts with the given first item (if any)
 579 /// and calls the given `FnMut(&T) -> Option<T>` closure to compute each item’s successor.
 580 ///
 581 /// ```
 582 /// #![feature(iter_unfold)]
 583 /// use std::iter::successors;
 584 ///
 585 /// let powers_of_10 = successors(Some(1_u16), |n| n.checked_mul(10));
 586 /// assert_eq!(powers_of_10.collect::<Vec<_>>(), &[1, 10, 100, 1_000, 10_000]);
 587 /// ```
 588 #[unstable(feature = "iter_unfold", issue = "55977")]
 589 pub fn successors<T, F>(first: Option<T>, succ: F) -> Successors<T, F>
 590     where F: FnMut(&T) -> Option<T>
 591 {
 592     // If this function returned `impl Iterator<Item=T>`
 593     // it could be based on `unfold` and not need a dedicated type.
 594     // However having a named `Successors<T, F>` type allows it to be `Clone` when `T` and `F` are.
 595     Successors {
 596         next: first,
 597         succ,
 598     }
 599 }
 600
 601 /// An new iterator where each successive item is computed based on the preceding one.
 602 ///
 603 /// This `struct` is created by the [`successors`] function.
 604 /// See its documentation for more.
 605 ///
 606 /// [`successors`]: fn.successors.html
 607 #[derive(Clone)]
 608 #[unstable(feature = "iter_unfold", issue = "55977")]
 609 pub struct Successors<T, F> {
 610     next: Option<T>,
 611     succ: F,
 612 }
 613
 614 #[unstable(feature = "iter_unfold", issue = "55977")]
 615 impl<T, F> Iterator for Successors<T, F>
 616     where F: FnMut(&T) -> Option<T>
 617 {
 618     type Item = T;
 619
 620     #[inline]
 621     fn next(&mut self) -> Option<Self::Item> {
 622         self.next.take().map(|item| {
 623             self.next = (self.succ)(&item);
 624             item
 625         })
 626     }
 627
 628     #[inline]
 629     fn size_hint(&self) -> (usize, Option<usize>) {
 630         if self.next.is_some() {
 631             (1, None)
 632         } else {
 633             (0, Some(0))
 634         }
 635     }
 636 }
 637
 638 #[unstable(feature = "iter_unfold", issue = "55977")]
 639 impl<T, F> FusedIterator for Successors<T, F>
 640     where F: FnMut(&T) -> Option<T>
 641 {}
 642
 643 #[unstable(feature = "iter_unfold", issue = "55977")]
 644 impl<T: fmt::Debug, F> fmt::Debug for Successors<T, F> {
 645     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 646         f.debug_struct("Successors")
 647             .field("next", &self.next)
 648             .finish()
 649     }
 650 }