#[cfg(not(feature = "ferrocene_certified"))]

use super::super::{

    ArrayChunks, ByRefSized, Chain, Cloned, Copied, Cycle, Enumerate, Filter, FilterMap, FlatMap,

    Flatten, Fuse, Inspect, Intersperse, IntersperseWith, Map, MapWhile, MapWindows, Peekable,

    Product, Rev, Scan, Skip, SkipWhile, StepBy, Sum, Take, TakeWhile, TrustedRandomAccessNoCoerce,

    Zip, try_process,

};

#[cfg(not(feature = "ferrocene_certified"))]

use crate::array;

#[cfg(not(feature = "ferrocene_certified"))]

use crate::cmp::{self, Ordering};

#[cfg(not(feature = "ferrocene_certified"))]

use crate::num::NonZero;

#[cfg(not(feature = "ferrocene_certified"))]

use crate::ops::{ChangeOutputType, ControlFlow, FromResidual, Residual, Try};

#[cfg(not(feature = "ferrocene_certified"))]

fn _assert_is_dyn_compatible(_: &dyn Iterator<Item = ()>) {}

/// A trait for dealing with iterators.

///

/// This is the main iterator trait. For more about the concept of iterators

/// generally, please see the [module-level documentation]. In particular, you

/// may want to know how to [implement `Iterator`][impl].

///

/// [module-level documentation]: crate::iter

/// [impl]: crate::iter#implementing-iterator

#[stable(feature = "rust1", since = "1.0.0")]

#[rustc_on_unimplemented(

    on(

        Self = "core::ops::range::RangeTo<Idx>",

        note = "you might have meant to use a bounded `Range`"

    ),

    on(

        Self = "core::ops::range::RangeToInclusive<Idx>",

        note = "you might have meant to use a bounded `RangeInclusive`"

    ),

    label = "`{Self}` is not an iterator",

    message = "`{Self}` is not an iterator"

)]

#[cfg_attr(not(feature = "ferrocene_certified"), doc(notable_trait))]

#[lang = "iterator"]

#[rustc_diagnostic_item = "Iterator"]

#[must_use = "iterators are lazy and do nothing unless consumed"]

pub trait Iterator {

    /// The type of the elements being iterated over.

    #[rustc_diagnostic_item = "IteratorItem"]

    #[stable(feature = "rust1", since = "1.0.0")]

    type Item;

    /// Advances the iterator and returns the next value.

    ///

    /// Returns [`None`] when iteration is finished. Individual iterator

    /// implementations may choose to resume iteration, and so calling `next()`

    /// again may or may not eventually start returning [`Some(Item)`] again at some

    /// point.

    ///

    /// [`Some(Item)`]: Some

    ///

    /// # Examples

    ///

    /// ```

    /// let a = [1, 2, 3];

    ///

    /// let mut iter = a.into_iter();

    ///

    /// // A call to next() returns the next value...

    /// assert_eq!(Some(1), iter.next());

    /// assert_eq!(Some(2), iter.next());

    /// assert_eq!(Some(3), iter.next());

    ///

    /// // ... and then None once it's over.

    /// assert_eq!(None, iter.next());

    ///

    /// // More calls may or may not return `None`. Here, they always will.

    /// assert_eq!(None, iter.next());

    /// assert_eq!(None, iter.next());

    /// ```

    #[lang = "next"]

    #[stable(feature = "rust1", since = "1.0.0")]

    fn next(&mut self) -> Option<Self::Item>;

    /// Advances the iterator and returns an array containing the next `N` values.

    ///

    /// If there are not enough elements to fill the array then `Err` is returned

    /// containing an iterator over the remaining elements.

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// #![feature(iter_next_chunk)]

    ///

    /// let mut iter = "lorem".chars();

    ///

    /// assert_eq!(iter.next_chunk().unwrap(), ['l', 'o']);              // N is inferred as 2

    /// assert_eq!(iter.next_chunk().unwrap(), ['r', 'e', 'm']);         // N is inferred as 3

    /// assert_eq!(iter.next_chunk::<4>().unwrap_err().as_slice(), &[]); // N is explicitly 4

    /// ```

    ///

    /// Split a string and get the first three items.

    ///

    /// ```

    /// #![feature(iter_next_chunk)]

    ///

    /// let quote = "not all those who wander are lost";

    /// let [first, second, third] = quote.split_whitespace().next_chunk().unwrap();

    /// assert_eq!(first, "not");

    /// assert_eq!(second, "all");

    /// assert_eq!(third, "those");

    /// ```

    #[inline]

    #[unstable(feature = "iter_next_chunk", reason = "recently added", issue = "98326")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn next_chunk<const N: usize>(

        &mut self,

    ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>>

    where

        Self: Sized,

    {

        array::iter_next_chunk(self)

    }

    /// Returns the bounds on the remaining length of the iterator.

    ///

    /// Specifically, `size_hint()` returns a tuple where the first element

    /// is the lower bound, and the second element is the upper bound.

    ///

    /// The second half of the tuple that is returned is an <code>[Option]<[usize]></code>.

    /// A [`None`] here means that either there is no known upper bound, or the

    /// upper bound is larger than [`usize`].

    ///

    /// # Implementation notes

    ///

    /// It is not enforced that an iterator implementation yields the declared

    /// number of elements. A buggy iterator may yield less than the lower bound

    /// or more than the upper bound of elements.

    ///

    /// `size_hint()` is primarily intended to be used for optimizations such as

    /// reserving space for the elements of the iterator, but must not be

    /// trusted to e.g., omit bounds checks in unsafe code. An incorrect

    /// implementation of `size_hint()` should not lead to memory safety

    /// violations.

    ///

    /// That said, the implementation should provide a correct estimation,

    /// because otherwise it would be a violation of the trait's protocol.

    ///

    /// The default implementation returns <code>(0, [None])</code> which is correct for any

    /// iterator.

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let a = [1, 2, 3];

    /// let mut iter = a.iter();

    ///

    /// assert_eq!((3, Some(3)), iter.size_hint());

    /// let _ = iter.next();

    /// assert_eq!((2, Some(2)), iter.size_hint());

    /// ```

    ///

    /// A more complex example:

    ///

    /// ```

    /// // The even numbers in the range of zero to nine.

    /// let iter = (0..10).filter(|x| x % 2 == 0);

    ///

    /// // We might iterate from zero to ten times. Knowing that it's five

    /// // exactly wouldn't be possible without executing filter().

    /// assert_eq!((0, Some(10)), iter.size_hint());

    ///

    /// // Let's add five more numbers with chain()

    /// let iter = (0..10).filter(|x| x % 2 == 0).chain(15..20);

    ///

    /// // now both bounds are increased by five

    /// assert_eq!((5, Some(15)), iter.size_hint());

    /// ```

    ///

    /// Returning `None` for an upper bound:

    ///

    /// ```

    /// // an infinite iterator has no upper bound

    /// // and the maximum possible lower bound

    /// let iter = 0..;

    ///

    /// assert_eq!((usize::MAX, None), iter.size_hint());

    /// ```

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn size_hint(&self) -> (usize, Option<usize>) {

        (0, None)

    }

    /// Consumes the iterator, counting the number of iterations and returning it.

    ///

    /// This method will call [`next`] repeatedly until [`None`] is encountered,

    /// returning the number of times it saw [`Some`]. Note that [`next`] has to be

    /// called at least once even if the iterator does not have any elements.

    ///

    /// [`next`]: Iterator::next

    ///

    /// # Overflow Behavior

    ///

    /// The method does no guarding against overflows, so counting elements of

    /// an iterator with more than [`usize::MAX`] elements either produces the

    /// wrong result or panics. If overflow checks are enabled, a panic is

    /// guaranteed.

    ///

    /// # Panics

    ///

    /// This function might panic if the iterator has more than [`usize::MAX`]

    /// elements.

    ///

    /// # Examples

    ///

    /// ```

    /// let a = [1, 2, 3];

    /// assert_eq!(a.iter().count(), 3);

    ///

    /// let a = [1, 2, 3, 4, 5];

    /// assert_eq!(a.iter().count(), 5);

    /// ```

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn count(self) -> usize

    where

        Self: Sized,

    {

        self.fold(

            0,

            #[rustc_inherit_overflow_checks]

            |count, _| count + 1,

        )

    }

    /// Consumes the iterator, returning the last element.

    ///

    /// This method will evaluate the iterator until it returns [`None`]. While

    /// doing so, it keeps track of the current element. After [`None`] is

    /// returned, `last()` will then return the last element it saw.

    ///

    /// # Examples

    ///

    /// ```

    /// let a = [1, 2, 3];

    /// assert_eq!(a.into_iter().last(), Some(3));

    ///

    /// let a = [1, 2, 3, 4, 5];

    /// assert_eq!(a.into_iter().last(), Some(5));

    /// ```

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn last(self) -> Option<Self::Item>

    where

        Self: Sized,

    {

        #[inline]

        fn some<T>(_: Option<T>, x: T) -> Option<T> {

            Some(x)

        }

        self.fold(None, some)

    }

    /// Advances the iterator by `n` elements.

    ///

    /// This method will eagerly skip `n` elements by calling [`next`] up to `n`

    /// times until [`None`] is encountered.

    ///

    /// `advance_by(n)` will return `Ok(())` if the iterator successfully advances by

    /// `n` elements, or a `Err(NonZero<usize>)` with value `k` if [`None`] is encountered,

    /// where `k` is remaining number of steps that could not be advanced because the iterator ran out.

    /// If `self` is empty and `n` is non-zero, then this returns `Err(n)`.

    /// Otherwise, `k` is always less than `n`.

    ///

    /// Calling `advance_by(0)` can do meaningful work, for example [`Flatten`]

    /// can advance its outer iterator until it finds an inner iterator that is not empty, which

    /// then often allows it to return a more accurate `size_hint()` than in its initial state.

    ///

    /// [`Flatten`]: crate::iter::Flatten

    /// [`next`]: Iterator::next

    ///

    /// # Examples

    ///

    /// ```

    /// #![feature(iter_advance_by)]

    ///

    /// use std::num::NonZero;

    ///

    /// let a = [1, 2, 3, 4];

    /// let mut iter = a.into_iter();

    ///

    /// assert_eq!(iter.advance_by(2), Ok(()));

    /// assert_eq!(iter.next(), Some(3));

    /// assert_eq!(iter.advance_by(0), Ok(()));

    /// assert_eq!(iter.advance_by(100), Err(NonZero::new(99).unwrap())); // only `4` was skipped

    /// ```

    #[inline]

    #[unstable(feature = "iter_advance_by", reason = "recently added", issue = "77404")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {

        /// Helper trait to specialize `advance_by` via `try_fold` for `Sized` iterators.

        trait SpecAdvanceBy {

            fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>>;

        }

        impl<I: Iterator + ?Sized> SpecAdvanceBy for I {

            default fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {

                for i in 0..n {

                    if self.next().is_none() {

                        // SAFETY: `i` is always less than `n`.

                        return Err(unsafe { NonZero::new_unchecked(n - i) });

                    }

                }

                Ok(())

            }

        }

        impl<I: Iterator> SpecAdvanceBy for I {

            fn spec_advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {

                let Some(n) = NonZero::new(n) else {

                    return Ok(());

                };

                let res = self.try_fold(n, |n, _| NonZero::new(n.get() - 1));

                match res {

                    None => Ok(()),

                    Some(n) => Err(n),

                }

            }

        }

        self.spec_advance_by(n)

    }

    /// Returns the `n`th element of the iterator.

    ///

    /// Like most indexing operations, the count starts from zero, so `nth(0)`

    /// returns the first value, `nth(1)` the second, and so on.

    ///

    /// Note that all preceding elements, as well as the returned element, will be

    /// consumed from the iterator. That means that the preceding elements will be

    /// discarded, and also that calling `nth(0)` multiple times on the same iterator

    /// will return different elements.

    ///

    /// `nth()` will return [`None`] if `n` is greater than or equal to the length of the

    /// iterator.

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let a = [1, 2, 3];

    /// assert_eq!(a.into_iter().nth(1), Some(2));

    /// ```

    ///

    /// Calling `nth()` multiple times doesn't rewind the iterator:

    ///

    /// ```

    /// let a = [1, 2, 3];

    ///

    /// let mut iter = a.into_iter();

    ///

    /// assert_eq!(iter.nth(1), Some(2));

    /// assert_eq!(iter.nth(1), None);

    /// ```

    ///

    /// Returning `None` if there are less than `n + 1` elements:

    ///

    /// ```

    /// let a = [1, 2, 3];

    /// assert_eq!(a.into_iter().nth(10), None);

    /// ```

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn nth(&mut self, n: usize) -> Option<Self::Item> {

        self.advance_by(n).ok()?;

        self.next()

    }

    /// Creates an iterator starting at the same point, but stepping by

    /// the given amount at each iteration.

    ///

    /// Note 1: The first element of the iterator will always be returned,

    /// regardless of the step given.

    ///

    /// Note 2: The time at which ignored elements are pulled is not fixed.

    /// `StepBy` behaves like the sequence `self.next()`, `self.nth(step-1)`,

    /// `self.nth(step-1)`, …, but is also free to behave like the sequence

    /// `advance_n_and_return_first(&mut self, step)`,

    /// `advance_n_and_return_first(&mut self, step)`, …

    /// Which way is used may change for some iterators for performance reasons.

    /// The second way will advance the iterator earlier and may consume more items.

    ///

    /// `advance_n_and_return_first` is the equivalent of:

    /// ```

    /// fn advance_n_and_return_first<I>(iter: &mut I, n: usize) -> Option<I::Item>

    /// where

    ///     I: Iterator,

    /// {

    ///     let next = iter.next();

    ///     if n > 1 {

    ///         iter.nth(n - 2);

    ///     }

    ///     next

    /// }

    /// ```

    ///

    /// # Panics

    ///

    /// The method will panic if the given step is `0`.

    ///

    /// # Examples

    ///

    /// ```

    /// let a = [0, 1, 2, 3, 4, 5];

    /// let mut iter = a.into_iter().step_by(2);

    ///

    /// assert_eq!(iter.next(), Some(0));

    /// assert_eq!(iter.next(), Some(2));

    /// assert_eq!(iter.next(), Some(4));

    /// assert_eq!(iter.next(), None);

    /// ```

    #[inline]

    #[stable(feature = "iterator_step_by", since = "1.28.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn step_by(self, step: usize) -> StepBy<Self>

    where

        Self: Sized,

    {

        StepBy::new(self, step)

    }

    /// Takes two iterators and creates a new iterator over both in sequence.

    ///

    /// `chain()` will return a new iterator which will first iterate over

    /// values from the first iterator and then over values from the second

    /// iterator.

    ///

    /// In other words, it links two iterators together, in a chain. 🔗

    ///

    /// [`once`] is commonly used to adapt a single value into a chain of

    /// other kinds of iteration.

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let s1 = "abc".chars();

    /// let s2 = "def".chars();

    ///

    /// let mut iter = s1.chain(s2);

    ///

    /// assert_eq!(iter.next(), Some('a'));

    /// assert_eq!(iter.next(), Some('b'));

    /// assert_eq!(iter.next(), Some('c'));

    /// assert_eq!(iter.next(), Some('d'));

    /// assert_eq!(iter.next(), Some('e'));

    /// assert_eq!(iter.next(), Some('f'));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Since the argument to `chain()` uses [`IntoIterator`], we can pass

    /// anything that can be converted into an [`Iterator`], not just an

    /// [`Iterator`] itself. For example, arrays (`[T]`) implement

    /// [`IntoIterator`], and so can be passed to `chain()` directly:

    ///

    /// ```

    /// let a1 = [1, 2, 3];

    /// let a2 = [4, 5, 6];

    ///

    /// let mut iter = a1.into_iter().chain(a2);

    ///

    /// assert_eq!(iter.next(), Some(1));

    /// assert_eq!(iter.next(), Some(2));

    /// assert_eq!(iter.next(), Some(3));

    /// assert_eq!(iter.next(), Some(4));

    /// assert_eq!(iter.next(), Some(5));

    /// assert_eq!(iter.next(), Some(6));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// If you work with Windows API, you may wish to convert [`OsStr`] to `Vec<u16>`:

    ///

    /// ```

    /// #[cfg(windows)]

    /// fn os_str_to_utf16(s: &std::ffi::OsStr) -> Vec<u16> {

    ///     use std::os::windows::ffi::OsStrExt;

    ///     s.encode_wide().chain(std::iter::once(0)).collect()

    /// }

    /// ```

    ///

    /// [`once`]: crate::iter::once

    /// [`OsStr`]: ../../std/ffi/struct.OsStr.html

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn chain<U>(self, other: U) -> Chain<Self, U::IntoIter>

    where

        Self: Sized,

        U: IntoIterator<Item = Self::Item>,

    {

        Chain::new(self, other.into_iter())

    }

    /// 'Zips up' two iterators into a single iterator of pairs.

    ///

    /// `zip()` returns a new iterator that will iterate over two other

    /// iterators, returning a tuple where the first element comes from the

    /// first iterator, and the second element comes from the second iterator.

    ///

    /// In other words, it zips two iterators together, into a single one.

    ///

    /// If either iterator returns [`None`], [`next`] from the zipped iterator

    /// will return [`None`].

    /// If the zipped iterator has no more elements to return then each further attempt to advance

    /// it will first try to advance the first iterator at most one time and if it still yielded an item

    /// try to advance the second iterator at most one time.

    ///

    /// To 'undo' the result of zipping up two iterators, see [`unzip`].

    ///

    /// [`unzip`]: Iterator::unzip

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let s1 = "abc".chars();

    /// let s2 = "def".chars();

    ///

    /// let mut iter = s1.zip(s2);

    ///

    /// assert_eq!(iter.next(), Some(('a', 'd')));

    /// assert_eq!(iter.next(), Some(('b', 'e')));

    /// assert_eq!(iter.next(), Some(('c', 'f')));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Since the argument to `zip()` uses [`IntoIterator`], we can pass

    /// anything that can be converted into an [`Iterator`], not just an

    /// [`Iterator`] itself. For example, arrays (`[T]`) implement

    /// [`IntoIterator`], and so can be passed to `zip()` directly:

    ///

    /// ```

    /// let a1 = [1, 2, 3];

    /// let a2 = [4, 5, 6];

    ///

    /// let mut iter = a1.into_iter().zip(a2);

    ///

    /// assert_eq!(iter.next(), Some((1, 4)));

    /// assert_eq!(iter.next(), Some((2, 5)));

    /// assert_eq!(iter.next(), Some((3, 6)));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// `zip()` is often used to zip an infinite iterator to a finite one.

    /// This works because the finite iterator will eventually return [`None`],

    /// ending the zipper. Zipping with `(0..)` can look a lot like [`enumerate`]:

    ///

    /// ```

    /// let enumerate: Vec<_> = "foo".chars().enumerate().collect();

    ///

    /// let zipper: Vec<_> = (0..).zip("foo".chars()).collect();

    ///

    /// assert_eq!((0, 'f'), enumerate[0]);

    /// assert_eq!((0, 'f'), zipper[0]);

    ///

    /// assert_eq!((1, 'o'), enumerate[1]);

    /// assert_eq!((1, 'o'), zipper[1]);

    ///

    /// assert_eq!((2, 'o'), enumerate[2]);

    /// assert_eq!((2, 'o'), zipper[2]);

    /// ```

    ///

    /// If both iterators have roughly equivalent syntax, it may be more readable to use [`zip`]:

    ///

    /// ```

    /// use std::iter::zip;

    ///

    /// let a = [1, 2, 3];

    /// let b = [2, 3, 4];

    ///

    /// let mut zipped = zip(

    ///     a.into_iter().map(|x| x * 2).skip(1),

    ///     b.into_iter().map(|x| x * 2).skip(1),

    /// );

    ///

    /// assert_eq!(zipped.next(), Some((4, 6)));

    /// assert_eq!(zipped.next(), Some((6, 8)));

    /// assert_eq!(zipped.next(), None);

    /// ```

    ///

    /// compared to:

    ///

    /// ```

    /// # let a = [1, 2, 3];

    /// # let b = [2, 3, 4];

    /// #

    /// let mut zipped = a

    ///     .into_iter()

    ///     .map(|x| x * 2)

    ///     .skip(1)

    ///     .zip(b.into_iter().map(|x| x * 2).skip(1));

    /// #

    /// # assert_eq!(zipped.next(), Some((4, 6)));

    /// # assert_eq!(zipped.next(), Some((6, 8)));

    /// # assert_eq!(zipped.next(), None);

    /// ```

    ///

    /// [`enumerate`]: Iterator::enumerate

    /// [`next`]: Iterator::next

    /// [`zip`]: crate::iter::zip

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn zip<U>(self, other: U) -> Zip<Self, U::IntoIter>

    where

        Self: Sized,

        U: IntoIterator,

    {

        Zip::new(self, other.into_iter())

    }

    /// Creates a new iterator which places a copy of `separator` between adjacent

    /// items of the original iterator.

    ///

    /// In case `separator` does not implement [`Clone`] or needs to be

    /// computed every time, use [`intersperse_with`].

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// #![feature(iter_intersperse)]

    ///

    /// let mut a = [0, 1, 2].into_iter().intersperse(100);

    /// assert_eq!(a.next(), Some(0));   // The first element from `a`.

    /// assert_eq!(a.next(), Some(100)); // The separator.

    /// assert_eq!(a.next(), Some(1));   // The next element from `a`.

    /// assert_eq!(a.next(), Some(100)); // The separator.

    /// assert_eq!(a.next(), Some(2));   // The last element from `a`.

    /// assert_eq!(a.next(), None);       // The iterator is finished.

    /// ```

    ///

    /// `intersperse` can be very useful to join an iterator's items using a common element:

    /// ```

    /// #![feature(iter_intersperse)]

    ///

    /// let words = ["Hello", "World", "!"];

    /// let hello: String = words.into_iter().intersperse(" ").collect();

    /// assert_eq!(hello, "Hello World !");

    /// ```

    ///

    /// [`Clone`]: crate::clone::Clone

    /// [`intersperse_with`]: Iterator::intersperse_with

    #[inline]

    #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn intersperse(self, separator: Self::Item) -> Intersperse<Self>

    where

        Self: Sized,

        Self::Item: Clone,

    {

        Intersperse::new(self, separator)

    }

    /// Creates a new iterator which places an item generated by `separator`

    /// between adjacent items of the original iterator.

    ///

    /// The closure will be called exactly once each time an item is placed

    /// between two adjacent items from the underlying iterator; specifically,

    /// the closure is not called if the underlying iterator yields less than

    /// two items and after the last item is yielded.

    ///

    /// If the iterator's item implements [`Clone`], it may be easier to use

    /// [`intersperse`].

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// #![feature(iter_intersperse)]

    ///

    /// #[derive(PartialEq, Debug)]

    /// struct NotClone(usize);

    ///

    /// let v = [NotClone(0), NotClone(1), NotClone(2)];

    /// let mut it = v.into_iter().intersperse_with(|| NotClone(99));

    ///

    /// assert_eq!(it.next(), Some(NotClone(0)));  // The first element from `v`.

    /// assert_eq!(it.next(), Some(NotClone(99))); // The separator.

    /// assert_eq!(it.next(), Some(NotClone(1)));  // The next element from `v`.

    /// assert_eq!(it.next(), Some(NotClone(99))); // The separator.

    /// assert_eq!(it.next(), Some(NotClone(2)));  // The last element from `v`.

    /// assert_eq!(it.next(), None);               // The iterator is finished.

    /// ```

    ///

    /// `intersperse_with` can be used in situations where the separator needs

    /// to be computed:

    /// ```

    /// #![feature(iter_intersperse)]

    ///

    /// let src = ["Hello", "to", "all", "people", "!!"].iter().copied();

    ///

    /// // The closure mutably borrows its context to generate an item.

    /// let mut happy_emojis = [" ❤️ ", " 😀 "].into_iter();

    /// let separator = || happy_emojis.next().unwrap_or(" 🦀 ");

    ///

    /// let result = src.intersperse_with(separator).collect::<String>();

    /// assert_eq!(result, "Hello ❤️ to 😀 all 🦀 people 🦀 !!");

    /// ```

    /// [`Clone`]: crate::clone::Clone

    /// [`intersperse`]: Iterator::intersperse

    #[inline]

    #[unstable(feature = "iter_intersperse", reason = "recently added", issue = "79524")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn intersperse_with<G>(self, separator: G) -> IntersperseWith<Self, G>

    where

        Self: Sized,

        G: FnMut() -> Self::Item,

    {

        IntersperseWith::new(self, separator)

    }

    /// Takes a closure and creates an iterator which calls that closure on each

    /// element.

    ///

    /// `map()` transforms one iterator into another, by means of its argument:

    /// something that implements [`FnMut`]. It produces a new iterator which

    /// calls this closure on each element of the original iterator.

    ///

    /// If you are good at thinking in types, you can think of `map()` like this:

    /// If you have an iterator that gives you elements of some type `A`, and

    /// you want an iterator of some other type `B`, you can use `map()`,

    /// passing a closure that takes an `A` and returns a `B`.

    ///

    /// `map()` is conceptually similar to a [`for`] loop. However, as `map()` is

    /// lazy, it is best used when you're already working with other iterators.

    /// If you're doing some sort of looping for a side effect, it's considered

    /// more idiomatic to use [`for`] than `map()`.

    ///

    /// [`for`]: ../../book/ch03-05-control-flow.html#looping-through-a-collection-with-for

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let a = [1, 2, 3];

    ///

    /// let mut iter = a.iter().map(|x| 2 * x);

    ///

    /// assert_eq!(iter.next(), Some(2));

    /// assert_eq!(iter.next(), Some(4));

    /// assert_eq!(iter.next(), Some(6));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// If you're doing some sort of side effect, prefer [`for`] to `map()`:

    ///

    /// ```

    /// # #![allow(unused_must_use)]

    /// // don't do this:

    /// (0..5).map(|x| println!("{x}"));

    ///

    /// // it won't even execute, as it is lazy. Rust will warn you about this.

    ///

    /// // Instead, use a for-loop:

    /// for x in 0..5 {

    ///     println!("{x}");

    /// }

    /// ```

    #[rustc_diagnostic_item = "IteratorMap"]

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn map<B, F>(self, f: F) -> Map<Self, F>

    where

        Self: Sized,

        F: FnMut(Self::Item) -> B,

    {

        Map::new(self, f)

    }

    /// Calls a closure on each element of an iterator.

    ///

    /// This is equivalent to using a [`for`] loop on the iterator, although

    /// `break` and `continue` are not possible from a closure. It's generally

    /// more idiomatic to use a `for` loop, but `for_each` may be more legible

    /// when processing items at the end of longer iterator chains. In some

    /// cases `for_each` may also be faster than a loop, because it will use

    /// internal iteration on adapters like `Chain`.

    ///

    /// [`for`]: ../../book/ch03-05-control-flow.html#looping-through-a-collection-with-for

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// use std::sync::mpsc::channel;

    ///

    /// let (tx, rx) = channel();

    /// (0..5).map(|x| x * 2 + 1)

    ///       .for_each(move |x| tx.send(x).unwrap());

    ///

    /// let v: Vec<_> = rx.iter().collect();

    /// assert_eq!(v, vec![1, 3, 5, 7, 9]);

    /// ```

    ///

    /// For such a small example, a `for` loop may be cleaner, but `for_each`

    /// might be preferable to keep a functional style with longer iterators:

    ///

    /// ```

    /// (0..5).flat_map(|x| (x * 100)..(x * 110))

    ///       .enumerate()

    ///       .filter(|&(i, x)| (i + x) % 3 == 0)

    ///       .for_each(|(i, x)| println!("{i}:{x}"));

    /// ```

    #[inline]

    #[stable(feature = "iterator_for_each", since = "1.21.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn for_each<F>(self, f: F)

    where

        Self: Sized,

        F: FnMut(Self::Item),

    {

        #[inline]

        fn call<T>(mut f: impl FnMut(T)) -> impl FnMut((), T) {

            move |(), item| f(item)

        }

        self.fold((), call(f));

    }

    /// Creates an iterator which uses a closure to determine if an element

    /// should be yielded.

    ///

    /// Given an element the closure must return `true` or `false`. The returned

    /// iterator will yield only the elements for which the closure returns

    /// `true`.

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let a = [0i32, 1, 2];

    ///

    /// let mut iter = a.into_iter().filter(|x| x.is_positive());

    ///

    /// assert_eq!(iter.next(), Some(1));

    /// assert_eq!(iter.next(), Some(2));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Because the closure passed to `filter()` takes a reference, and many

    /// iterators iterate over references, this leads to a possibly confusing

    /// situation, where the type of the closure is a double reference:

    ///

    /// ```

    /// let s = &[0, 1, 2];

    ///

    /// let mut iter = s.iter().filter(|x| **x > 1); // needs two *s!

    ///

    /// assert_eq!(iter.next(), Some(&2));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// It's common to instead use destructuring on the argument to strip away one:

    ///

    /// ```

    /// let s = &[0, 1, 2];

    ///

    /// let mut iter = s.iter().filter(|&x| *x > 1); // both & and *

    ///

    /// assert_eq!(iter.next(), Some(&2));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// or both:

    ///

    /// ```

    /// let s = &[0, 1, 2];

    ///

    /// let mut iter = s.iter().filter(|&&x| x > 1); // two &s

    ///

    /// assert_eq!(iter.next(), Some(&2));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// of these layers.

    ///

    /// Note that `iter.filter(f).next()` is equivalent to `iter.find(f)`.

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[rustc_diagnostic_item = "iter_filter"]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn filter<P>(self, predicate: P) -> Filter<Self, P>

    where

        Self: Sized,

        P: FnMut(&Self::Item) -> bool,

    {

        Filter::new(self, predicate)

    }

    /// Creates an iterator that both filters and maps.

    ///

    /// The returned iterator yields only the `value`s for which the supplied

    /// closure returns `Some(value)`.

    ///

    /// `filter_map` can be used to make chains of [`filter`] and [`map`] more

    /// concise. The example below shows how a `map().filter().map()` can be

    /// shortened to a single call to `filter_map`.

    ///

    /// [`filter`]: Iterator::filter

    /// [`map`]: Iterator::map

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let a = ["1", "two", "NaN", "four", "5"];

    ///

    /// let mut iter = a.iter().filter_map(|s| s.parse().ok());

    ///

    /// assert_eq!(iter.next(), Some(1));

    /// assert_eq!(iter.next(), Some(5));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Here's the same example, but with [`filter`] and [`map`]:

    ///

    /// ```

    /// let a = ["1", "two", "NaN", "four", "5"];

    /// let mut iter = a.iter().map(|s| s.parse()).filter(|s| s.is_ok()).map(|s| s.unwrap());

    /// assert_eq!(iter.next(), Some(1));

    /// assert_eq!(iter.next(), Some(5));

    /// assert_eq!(iter.next(), None);

    /// ```

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn filter_map<B, F>(self, f: F) -> FilterMap<Self, F>

    where

        Self: Sized,

        F: FnMut(Self::Item) -> Option<B>,

    {

        FilterMap::new(self, f)

    }

    /// Creates an iterator which gives the current iteration count as well as

    /// the next value.

    ///

    /// The iterator returned yields pairs `(i, val)`, where `i` is the

    /// current index of iteration and `val` is the value returned by the

    /// iterator.

    ///

    /// `enumerate()` keeps its count as a [`usize`]. If you want to count by a

    /// different sized integer, the [`zip`] function provides similar

    /// functionality.

    ///

    /// # Overflow Behavior

    ///

    /// The method does no guarding against overflows, so enumerating more than

    /// [`usize::MAX`] elements either produces the wrong result or panics. If

    /// overflow checks are enabled, a panic is guaranteed.

    ///

    /// # Panics

    ///

    /// The returned iterator might panic if the to-be-returned index would

    /// overflow a [`usize`].

    ///

    /// [`zip`]: Iterator::zip

    ///

    /// # Examples

    ///

    /// ```

    /// let a = ['a', 'b', 'c'];

    ///

    /// let mut iter = a.into_iter().enumerate();

    ///

    /// assert_eq!(iter.next(), Some((0, 'a')));

    /// assert_eq!(iter.next(), Some((1, 'b')));

    /// assert_eq!(iter.next(), Some((2, 'c')));

    /// assert_eq!(iter.next(), None);

    /// ```

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[rustc_diagnostic_item = "enumerate_method"]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn enumerate(self) -> Enumerate<Self>

    where

        Self: Sized,

    {

        Enumerate::new(self)

    }

    /// Creates an iterator which can use the [`peek`] and [`peek_mut`] methods

    /// to look at the next element of the iterator without consuming it. See

    /// their documentation for more information.

    ///

    /// Note that the underlying iterator is still advanced when [`peek`] or

    /// [`peek_mut`] are called for the first time: In order to retrieve the

    /// next element, [`next`] is called on the underlying iterator, hence any

    /// side effects (i.e. anything other than fetching the next value) of

    /// the [`next`] method will occur.

    ///

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let xs = [1, 2, 3];

    ///

    /// let mut iter = xs.into_iter().peekable();

    ///

    /// // peek() lets us see into the future

    /// assert_eq!(iter.peek(), Some(&1));

    /// assert_eq!(iter.next(), Some(1));

    ///

    /// assert_eq!(iter.next(), Some(2));

    ///

    /// // we can peek() multiple times, the iterator won't advance

    /// assert_eq!(iter.peek(), Some(&3));

    /// assert_eq!(iter.peek(), Some(&3));

    ///

    /// assert_eq!(iter.next(), Some(3));

    ///

    /// // after the iterator is finished, so is peek()

    /// assert_eq!(iter.peek(), None);

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Using [`peek_mut`] to mutate the next item without advancing the

    /// iterator:

    ///

    /// ```

    /// let xs = [1, 2, 3];

    ///

    /// let mut iter = xs.into_iter().peekable();

    ///

    /// // `peek_mut()` lets us see into the future

    /// assert_eq!(iter.peek_mut(), Some(&mut 1));

    /// assert_eq!(iter.peek_mut(), Some(&mut 1));

    /// assert_eq!(iter.next(), Some(1));

    ///

    /// if let Some(p) = iter.peek_mut() {

    ///     assert_eq!(*p, 2);

    ///     // put a value into the iterator

    ///     *p = 1000;

    /// }

    ///

    /// // The value reappears as the iterator continues

    /// assert_eq!(iter.collect::<Vec<_>>(), vec![1000, 3]);

    /// ```

    /// [`peek`]: Peekable::peek

    /// [`peek_mut`]: Peekable::peek_mut

    /// [`next`]: Iterator::next

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn peekable(self) -> Peekable<Self>

    where

        Self: Sized,

    {

        Peekable::new(self)

    }

    /// Creates an iterator that [`skip`]s elements based on a predicate.

    ///

    /// [`skip`]: Iterator::skip

    ///

    /// `skip_while()` takes a closure as an argument. It will call this

    /// closure on each element of the iterator, and ignore elements

    /// until it returns `false`.

    ///

    /// After `false` is returned, `skip_while()`'s job is over, and the

    /// rest of the elements are yielded.

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let a = [-1i32, 0, 1];

    ///

    /// let mut iter = a.into_iter().skip_while(|x| x.is_negative());

    ///

    /// assert_eq!(iter.next(), Some(0));

    /// assert_eq!(iter.next(), Some(1));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Because the closure passed to `skip_while()` takes a reference, and many

    /// iterators iterate over references, this leads to a possibly confusing

    /// situation, where the type of the closure argument is a double reference:

    ///

    /// ```

    /// let s = &[-1, 0, 1];

    ///

    /// let mut iter = s.iter().skip_while(|x| **x < 0); // need two *s!

    ///

    /// assert_eq!(iter.next(), Some(&0));

    /// assert_eq!(iter.next(), Some(&1));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Stopping after an initial `false`:

    ///

    /// ```

    /// let a = [-1, 0, 1, -2];

    ///

    /// let mut iter = a.into_iter().skip_while(|&x| x < 0);

    ///

    /// assert_eq!(iter.next(), Some(0));

    /// assert_eq!(iter.next(), Some(1));

    ///

    /// // while this would have been false, since we already got a false,

    /// // skip_while() isn't used any more

    /// assert_eq!(iter.next(), Some(-2));

    ///

    /// assert_eq!(iter.next(), None);

    /// ```

    #[inline]

    #[doc(alias = "drop_while")]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn skip_while<P>(self, predicate: P) -> SkipWhile<Self, P>

    where

        Self: Sized,

        P: FnMut(&Self::Item) -> bool,

    {

        SkipWhile::new(self, predicate)

    }

    /// Creates an iterator that yields elements based on a predicate.

    ///

    /// `take_while()` takes a closure as an argument. It will call this

    /// closure on each element of the iterator, and yield elements

    /// while it returns `true`.

    ///

    /// After `false` is returned, `take_while()`'s job is over, and the

    /// rest of the elements are ignored.

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let a = [-1i32, 0, 1];

    ///

    /// let mut iter = a.into_iter().take_while(|x| x.is_negative());

    ///

    /// assert_eq!(iter.next(), Some(-1));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Because the closure passed to `take_while()` takes a reference, and many

    /// iterators iterate over references, this leads to a possibly confusing

    /// situation, where the type of the closure is a double reference:

    ///

    /// ```

    /// let s = &[-1, 0, 1];

    ///

    /// let mut iter = s.iter().take_while(|x| **x < 0); // need two *s!

    ///

    /// assert_eq!(iter.next(), Some(&-1));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Stopping after an initial `false`:

    ///

    /// ```

    /// let a = [-1, 0, 1, -2];

    ///

    /// let mut iter = a.into_iter().take_while(|&x| x < 0);

    ///

    /// assert_eq!(iter.next(), Some(-1));

    ///

    /// // We have more elements that are less than zero, but since we already

    /// // got a false, take_while() ignores the remaining elements.

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Because `take_while()` needs to look at the value in order to see if it

    /// should be included or not, consuming iterators will see that it is

    /// removed:

    ///

    /// ```

    /// let a = [1, 2, 3, 4];

    /// let mut iter = a.into_iter();

    ///

    /// let result: Vec<i32> = iter.by_ref().take_while(|&n| n != 3).collect();

    ///

    /// assert_eq!(result, [1, 2]);

    ///

    /// let result: Vec<i32> = iter.collect();

    ///

    /// assert_eq!(result, [4]);

    /// ```

    ///

    /// The `3` is no longer there, because it was consumed in order to see if

    /// the iteration should stop, but wasn't placed back into the iterator.

    #[inline]

    #[stable(feature = "rust1", since = "1.0.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn take_while<P>(self, predicate: P) -> TakeWhile<Self, P>

    where

        Self: Sized,

        P: FnMut(&Self::Item) -> bool,

    {

        TakeWhile::new(self, predicate)

    }

    /// Creates an iterator that both yields elements based on a predicate and maps.

    ///

    /// `map_while()` takes a closure as an argument. It will call this

    /// closure on each element of the iterator, and yield elements

    /// while it returns [`Some(_)`][`Some`].

    ///

    /// # Examples

    ///

    /// Basic usage:

    ///

    /// ```

    /// let a = [-1i32, 4, 0, 1];

    ///

    /// let mut iter = a.into_iter().map_while(|x| 16i32.checked_div(x));

    ///

    /// assert_eq!(iter.next(), Some(-16));

    /// assert_eq!(iter.next(), Some(4));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Here's the same example, but with [`take_while`] and [`map`]:

    ///

    /// [`take_while`]: Iterator::take_while

    /// [`map`]: Iterator::map

    ///

    /// ```

    /// let a = [-1i32, 4, 0, 1];

    ///

    /// let mut iter = a.into_iter()

    ///                 .map(|x| 16i32.checked_div(x))

    ///                 .take_while(|x| x.is_some())

    ///                 .map(|x| x.unwrap());

    ///

    /// assert_eq!(iter.next(), Some(-16));

    /// assert_eq!(iter.next(), Some(4));

    /// assert_eq!(iter.next(), None);

    /// ```

    ///

    /// Stopping after an initial [`None`]:

    ///

    /// ```

    /// let a = [0, 1, 2, -3, 4, 5, -6];

    ///

    /// let iter = a.into_iter().map_while(|x| u32::try_from(x).ok());

    /// let vec: Vec<_> = iter.collect();

    ///

    /// // We have more elements that could fit in u32 (such as 4, 5), but `map_while` returned `None` for `-3`

    /// // (as the `predicate` returned `None`) and `collect` stops at the first `None` encountered.

    /// assert_eq!(vec, [0, 1, 2]);

    /// ```

    ///

    /// Because `map_while()` needs to look at the value in order to see if it

    /// should be included or not, consuming iterators will see that it is

    /// removed:

    ///

    /// ```

    /// let a = [1, 2, -3, 4];

    /// let mut iter = a.into_iter();

    ///

    /// let result: Vec<u32> = iter.by_ref()

    ///                            .map_while(|n| u32::try_from(n).ok())

    ///                            .collect();

    ///

    /// assert_eq!(result, [1, 2]);

    ///

    /// let result: Vec<i32> = iter.collect();

    ///

    /// assert_eq!(result, [4]);

    /// ```

    ///

    /// The `-3` is no longer there, because it was consumed in order to see if

    /// the iteration should stop, but wasn't placed back into the iterator.

    ///

    /// Note that unlike [`take_while`] this iterator is **not** fused.

    /// It is also not specified what this iterator returns after the first [`None`] is returned.

    /// If you need a fused iterator, use [`fuse`].

    ///

    /// [`fuse`]: Iterator::fuse

    #[inline]

    #[stable(feature = "iter_map_while", since = "1.57.0")]

    #[cfg(not(feature = "ferrocene_certified"))]

    fn map_while<B, P>(self, predicate: P) -> MapWhile<Self, P>

    where

        Self: Sized,

        P: FnMut(Self::Item) -> Option<B>,

    {

        MapWhile::new(self, predicate)

    }

    /// Creates an iterator that skips the first `n` elements.

    ///

    /// `skip(n)` skips elements until `n` elements are skipped or the end of the

    /// iterator is reached (whichever happens first). After that, all the remaining

    /// elements are yielded. In particular, if the original iterator is too short,

    /// then the returned iterator is empty.

    ///

    /// Rather than overriding this method directly, instead override the `nth` method.

    ///

    /// # Examples

    ///

    /// ```

    /// let a = [1, 2, 3];