empty-fallback-chain 2.0.0

//! [core-iter-chain]: `core::iter::Chain`
//! [iterator-ext-method]: `IteratorExt::empty_fallback_chain`
#![doc = include_str!("../README.md")]
#![cfg_attr(not(test), no_std)]

// TODO: in next major version, change the [`empty_fallback_chain`], [`maybe_empty_fallback_chain`],
// and [`pre_empty_fallback_chain`] functions to use IntoIterator and make them non-const, to align
// them with how std does free functions and make them not just glorified invokers of the constructor.

/// Construct an [`EmptyFallbackChain`] iterator. See [`IteratorExt::empty_fallback_chain`] for
/// more information.
#[inline]
pub fn empty_fallback_chain<A: IntoIterator, B: IntoIterator<Item = A::Item>>(
    a: A,
    b: B,
) -> EmptyFallbackChain<A::IntoIter, B::IntoIter> {
    EmptyFallbackChain::new(a.into_iter(), b.into_iter())
}

/// Construct an [`EmptyFallbackChain`] iterator with the second one optionally "pre-emptively made
/// empty"
///
/// See [`IteratorExt::maybe_empty_fallback_chain`] for more information.
#[inline]
pub fn maybe_empty_fallback_chain<A: IntoIterator, B: IntoIterator<Item = A::Item>>(
    a: A,
    b: Option<B>,
) -> EmptyFallbackChain<A::IntoIter, B::IntoIter> {
    EmptyFallbackChain::new_with_pre_empty(Some(a.into_iter()), b.map(IntoIterator::into_iter))
}

/// Create an [`EmptyFallbackChain`] with (optionally) one or more of the iterators set to "empty"
/// pre-emptively, by providing it as [`None`].
///
/// This is useful when creating conditional combinators as it prevents nested iterator type explosion, and the
/// associated indirection.
///
/// See also: [`IteratorExt::maybe_empty_fallback_chain`]
///
/// ```rust
/// use empty_fallback_chain as efc;
///
/// let o = efc::pre_empty_fallback_chain::<core::iter::Empty<usize>, _>(
///     None,
///     Some([3, 4, 5].into_iter())
/// ).collect::<Vec<usize>>();
/// assert_eq!(o, vec![3, 4, 5]);
/// ```
#[inline]
pub fn pre_empty_fallback_chain<A: IntoIterator, B: IntoIterator<Item = A::Item>>(
    a: Option<A>,
    b: Option<B>,
) -> EmptyFallbackChain<A::IntoIter, B::IntoIter> {
    EmptyFallbackChain::new_with_pre_empty(
        a.map(IntoIterator::into_iter),
        b.map(IntoIterator::into_iter),
    )
}

/// An iterator that links two iterators together, in a chain, if the first produces nothing.
///
/// This iterator is double ended - like [`core::iter::Chain`] - and behaves symmetrically in
/// reverse - once you call either [`Iterator::next`] or [`DoubleEndedIterator::next_back`], the first
/// iterator *in that direction* determines if the second iterator *in that direction* is
/// preserved.
///
/// For more information, see [`IteratorExt::empty_fallback_chain`]
#[derive(Debug, Clone)]
#[must_use = "iterators are lazy and do nothing unless consumed"]
pub struct EmptyFallbackChain<A, B> {
    // This is like in `core::iter::Chain` - the Option values act to fuse the iterators.
    //
    // Destroying the second iterator is acheived by setting it to `None` in the and_then_or_clear
    // function (mirroring the internal function of the same name inside rust stdlib).
    //
    // This also works (in reverse) for the double-ended case, with flipped behaviour
    a: Option<A>,
    b: Option<B>,
}

impl<A, B> EmptyFallbackChain<A, B> {
    /// Construct a new [`EmptyFallbackChain`] from the two iterators.
    #[inline]
    pub const fn new(a: A, b: B) -> EmptyFallbackChain<A, B> {
        Self {
            a: Some(a),
            b: Some(b),
        }
    }

    /// Allow creating a new [`EmptyFallbackChain`] while implicitly allowing one or both of the
    /// iterators to be pre-emptively considered "empty" by setting them to [`None`]. See
    /// [`pre_empty_fallback_chain`] for more information.
    #[inline]
    pub const fn new_with_pre_empty(a: Option<A>, b: Option<B>) -> EmptyFallbackChain<A, B> {
        Self { a, b }
    }
}

/// Implementation of [`Iterator`] - takes significant work and code from [`core::iter::Chain`]'s
/// implementation.
impl<A, B> Iterator for EmptyFallbackChain<A, B>
where
    A: Iterator,
    B: Iterator<Item = A::Item>,
{
    type Item = A::Item;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        and_then_or_clear(&mut self.a, Iterator::next, || self.b = None)
            .or_else(|| self.b.as_mut()?.next())
    }

    #[inline]
    fn count(self) -> usize
    where
        Self: Sized,
    {
        let a_count = match self.a {
            Some(a) => a.count(),
            None => 0,
        };
        // `self.b` would get dumped anyway, and this function is consuming.
        //
        if a_count != 0 {
            return a_count;
        }
        // If `self.a` was totally consumed but hadn't yet returned `None`, then on the
        // first call, `self.b` would have been destroyed anyway, so continuing when a.count()
        // is zero is still fine - there can't be an issue where:
        // * `a` has cnt zero
        // * `a` was not an empty iterator
        // * `b` was not None
        match self.b {
            Some(b) => b.count(),
            None => 0,
        }
    }

    /*
     * Not yet stable
    fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R
        where
            Self: Sized,
            F: FnMut(B, Self::Item) -> R,
            R: core::ops::Try<Output = B>, { Cannot use this because it's unstable

    }
    */

    fn fold<Acc, F>(self, mut acc: Acc, mut f: F) -> Acc
    where
        Self: Sized,
        F: FnMut(Acc, Self::Item) -> Acc,
    {
        let mut had_element = false;
        if let Some(a) = self.a {
            acc = a.fold(acc, |acc, item| {
                had_element = true;
                f(acc, item)
            });
        }
        if had_element {
            // No need to reset b - this function consumes self
            return acc;
        }

        // Once again, it's fine to exclusively depend on `b` being `None` to determine if `a`
        // ever had any values - even if at the point of calling this function it didn't, it
        // should only ever have been advanced by this iterator in the past and hence `b` would
        // have been set to `None`
        if let Some(b) = self.b {
            acc = b.fold(acc, f);
        }
        acc
    }

    /*
    #[inline]
    fn advance_by(&mut self, mut n: usize) -> Result<(), core::num::NonZero<usize>> {
        if let Some(ref mut a) = self.a {
            n = match (a.advance_by(n), n) {
                // `a` actually did not advance at all, and there were no elements.
                (Ok(()), 0) => return Ok(()),
                // `a` failed to advance any amount, meaning it was an empty iterator (if it wasn't
                // earlier, then `b` would have already been destroyed and that's ok).
                // We destroy `a` for cleanup and fusion reasons.
                (Err(k), tried) if tried == k.get() => {
                    self.a = None;
                    tried
                }
                (Ok(()), a_advanced_by) => {
                    // `a` finished (though not actually "completed completed") with a
                    // nonzero advancement count. This means it isn't empty, and we need to
                    // destroy `b`.
                    self.b = None;
                    return Ok(());
                },
                // `a` failed to complete, but it did manage to advance. This still means that `a`
                // is nonempty, and `b` should be destroyed. This also means *we* cannot advance
                // further, so should forward up the error (also destroy `a` again.
                (Err(k), tried) => {
                    self.a = None;
                    self.b = None;
                    return Err(k)
                }
            };
        }

        if let Some(ref mut b) = self.b {
            return b.advance_by(n);
        }

        // Nothing could actually do anything with `advance_by`, as we have no more iterators,
        // so make it all error-y anyway if the advancement is not zero
        NonZero::new(n).map_or(Ok(()), Err)
    }
    Cannot currently implement because unstable lol
    */

    /* Can't easily do any "proper" better-than-default implementation without using
     * unstable features. TODO: still implement this
    fn nth(&mut self, n: usize) -> Option<Self::Item> {

    }
    */

    #[inline]
    fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item>
    where
        Self: Sized,
        P: FnMut(&Self::Item) -> bool,
    {
        let mut did_have_elements = false;
        // Run through `a`. We've injected our boolean into the predicate, so we can determine
        // if `a` ever called it (which it would have to do at least once if it had any elements)
        let a_found = and_then_or_clear(
            &mut self.a,
            |a| {
                a.find(|v| {
                    did_have_elements = true;
                    predicate(v)
                })
            },
            || {},
        );
        if did_have_elements {
            self.b = None;
            return a_found;
        }
        // Run find on `b`. `b` would be `None` if `a` had ever had any elements
        self.b.as_mut()?.find(predicate)
    }

    #[inline]
    fn last(self) -> Option<Self::Item>
    where
        Self: Sized,
    {
        // We get the last of `a`, if `a` is not None
        let a_last = self.a.and_then(Iterator::last);
        // If this was Some, then `b` must be cleared. If it was `None`, then `b` was either
        // cleared earlier (by `a` not being empty, and being run through), or `a` is empty and `b`
        // is set to Some and can be used directly.
        //
        // We are actually consuming self, so no need to update anything.
        if a_last.is_some() {
            return a_last;
        }

        self.b.and_then(Iterator::last)
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        match (&self.a, &self.b) {
            (None, None) => (0, Some(0)),
            (None, Some(b)) => b.size_hint(),
            (Some(a), None) => a.size_hint(),
            (Some(a), Some(b)) => {
                // If `a` has a nonzero lower bound, then we know `b` will be removed.
                // If `a` has a zero upper bound, then we know `b` is all that will be iterated
                // If `b` has a zero upper bound, then we know `a` is all that will be iterated
                // If `b` has a nonzero lower bound, then we know that if iterating backwards, `a`
                // will not be iterated. However, size_hint is for forward iteration.
                // Other than this, we can guaruntee that the lower bound is one of the two (we can
                // be safe by picking minimum), and the upper bound is one of the two (we can be
                // safe by picking maximum, or `None` if either of them have `None`)
                match (a.size_hint(), b.size_hint()) {
                    (a_size_hint @ (1.., _), _) => a_size_hint,
                    ((_, Some(0)), b_size_hint) => b_size_hint,
                    (a_size_hint, (_, Some(0))) => a_size_hint,
                    (
                        (a_lower_bound, maybe_a_upper_bound),
                        (b_lower_bound, maybe_b_upper_bound),
                    ) => {
                        let maybe_upper_bound = match (maybe_a_upper_bound, maybe_b_upper_bound) {
                            (Some(a_upper), Some(b_upper)) => Some(a_upper.max(b_upper)),
                            _ => None,
                        };
                        let lower_bound = a_lower_bound.min(b_lower_bound);
                        (lower_bound, maybe_upper_bound)
                    }
                }
            }
        }
    }
}

impl<A, B> DoubleEndedIterator for EmptyFallbackChain<A, B>
where
    A: DoubleEndedIterator,
    B: DoubleEndedIterator<Item = A::Item>,
{
    #[inline]
    fn next_back(&mut self) -> Option<Self::Item> {
        // Implement the same as `next`, but flip which thing gets called and reset.
        and_then_or_clear(&mut self.b, DoubleEndedIterator::next_back, || {
            self.a = None;
        })
        .or_else(|| self.a.as_mut()?.next_back())
    }

    /* unstable
    fn advance_back_by(&mut self, n: usize) -> Result<(), core::num::NonZero<usize>> {}
    */

    /* Cannot easily implement without unstable advance_back_by - TODO: implement
    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {

    }*/

    #[inline]
    fn rfind<P>(&mut self, mut predicate: P) -> Option<Self::Item>
    where
        Self: Sized,
        P: FnMut(&Self::Item) -> bool,
    {
        let mut had_any_elements = false;
        // Run the find function, injecting into the predicate - which must be called
        // at least once for any non-empty iterator.
        let b_found = and_then_or_clear(
            &mut self.b,
            |b| {
                b.rfind(|v| {
                    had_any_elements = true;
                    predicate(v)
                })
            },
            || {},
        );
        if had_any_elements {
            self.a = None;
            return b_found;
        }
        self.a.as_mut()?.rfind(predicate)
    }

    /* unstable
    fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
        where
            Self: Sized,
            F: FnMut(B, Self::Item) -> R,
            R: core::ops::Try<Output = B>, {

    }
    */

    fn rfold<Acc, F>(self, mut acc: Acc, mut f: F) -> Acc
    where
        Self: Sized,
        F: FnMut(Acc, Self::Item) -> Acc,
    {
        // This function is consuming, so we don't need to worry much about disposing of
        // anything, just returning when needed :)
        let mut had_any_elements = false;
        if let Some(b) = self.b {
            acc = b.rfold(acc, |acc, item| {
                had_any_elements = true;
                f(acc, item)
            });
        }
        if had_any_elements {
            // Consuming function, no need to deinit `a`
            return acc;
        }

        if let Some(a) = self.a {
            acc = a.rfold(acc, f);
        }
        acc
    }
}

/// Execute the given function on the option, clearing the option if the output from the function
/// was [`None`]. Also allows providing a callback to run if the output of `f` was `Some`.
///
/// This is pretty much identical to the function inside the standard library, except with added
/// callback.
#[inline]
fn and_then_or_clear<T, U>(
    resetting_input: &mut Option<T>,
    with_some_input: impl FnOnce(&mut T) -> Option<U>,
    on_some: impl FnOnce(),
) -> Option<U> {
    let output = with_some_input(resetting_input.as_mut()?);
    if output.is_none() {
        *resetting_input = None;
    } else {
        on_some();
    };
    output
}

/// Trait for extending [`Iterator`]s with methods to create [`EmptyFallbackChain`] iterators.
pub trait IteratorExt: Iterator {
    /// Takes two iterators and creates a new iterator that runs through the second only if the
    /// first produces no output. Can take anything implementing [`IntoIterator`] as a second
    /// argument (as long as it produces an iterator over the same type).
    ///
    /// `empty_fallback_chain()` will return a new iterator which will iterate over this (first) iterator - if
    /// it produces any values, then the second iterator is dropped. However, if the first iterator doesn't 
    /// produce any values, then the second iterator is iterated over instead (i.e. "as a
    /// fallback").
    ///
    /// In other words, it links two iterators in a chain, but only if the first is empty. 
    ///
    /// This also applies in reverse direction when iterating backwards (i.e. with [`DoubleEndedIterator::next_back`], 
    /// the second iterator is attempted to be iterated backwards first - only if nothing is
    /// emitted, is the first iterator then iterated backwards instead, else the first iterator is simply dropped).
    ///
    /// # Examples
    ///
    /// Basic usage:
    /// ```
    /// use empty_fallback_chain::prelude::*;
    /// let higher_priority = [1, 2, 3];
    /// let lower_priority = [4, 5, 6];
    ///
    /// let iter = higher_priority.into_iter().empty_fallback_chain(lower_priority.into_iter());
    /// assert_eq!(iter.collect::<Vec<_>>(), vec![1, 2, 3]);
    /// ```
    ///
    /// The major feature of [`EmptyFallbackChain`] is that if the first iterator produces
    /// no values, then the second iterator will be used instead.
    /// ```
    /// use empty_fallback_chain::IteratorExt as _;
    ///
    /// let higher_priority = [1, 3, 5];
    /// let lower_priority = [10, 11, 78];
    ///
    /// /// Filter for even numbers - no data in the higher priority iterator matches this,
    /// /// so when the filtered version is used as the first half of an `EmptyFallbackChain`,
    /// /// the "fallback" iterator is what's used.
    /// fn even(v: &u32) -> bool {
    ///     v % 2 == 0
    /// }
    ///
    /// let iter = higher_priority.into_iter().filter(even)
    ///     .empty_fallback_chain(lower_priority.into_iter());
    /// assert_eq!(iter.collect::<Vec<_>>(), vec![10, 11, 78]);
    /// ```
    ///
    /// If the higher priority iterator produces *any* values, then the lower priority iterator is
    /// never used. For example, with a filter that doesn't remove all of the higher-priority
    /// information:
    /// ```
    /// use empty_fallback_chain::prelude::*;
    ///
    /// let higher_priority = [1, 3, 5];
    /// let lower_priority = [10, 11, 78];
    ///
    /// fn incomplete_higher_filter(v: &u32) -> bool {
    ///    *v != 3
    /// }
    ///
    /// let iter = higher_priority.into_iter().filter(incomplete_higher_filter)
    ///     .empty_fallback_chain(lower_priority.into_iter());
    /// assert_eq!(iter.collect::<Vec<_>>(), vec![1, 5]);
    /// ```
    ///
    /// This can be used to create incredibly powerful, lazily evaluated, fallback systems.
    /// If you use multiple [`EmptyFallbackChain`] in sequence, you can create a sort of
    /// "iterator priority" construction.
    /// ```
    /// use empty_fallback_chain::prelude::*;
    ///
    /// #[derive(Debug, Clone, PartialEq, Eq, Hash)]
    /// pub struct Contact {
    ///     pub name: &'static str,
    ///     pub email: &'static str,
    ///     pub pronouns: &'static str
    /// }
    ///
    ///# impl Contact {
    ///#    /// Just example - You'd probably use owned, interned, or referenced strings
    ///#    /// here.
    ///#    pub const fn new(
    ///#        name: &'static str,
    ///#        email: &'static str,
    ///#        pronouns: &'static str
    ///#    ) -> Self {
    ///#        Self { name, email, pronouns }
    ///#    }
    ///# }
    /// // Example conditions
    /// fn is_tuesday() -> bool { true }
    /// fn is_wednesday() -> bool { false }
    /// fn is_weekend() -> bool { false }
    ///
    /// use Contact as C;
    /// use core::iter as iter;
    ///
    /// const bob: C = C::new("Bob Angie", "the-eponymous-bob@example.com", "he/him");
    /// const tracey: C = C::new("Tracy Mill", "tracy-mill@corpo.example.com", "she/her");
    /// const alan: C = C::new("Alan", "alanspace@example.com", "he/him");
    /// const matriss: C = C::new("Matriss Karisle", "matriss@example.com", "they/them");
    /// const charlie: C = C::new("Charlie Stone", "charlie-charlie@example.com", "she/her");
    /// const harri: C = C::new("Harri", "harri-up@example.com", "they/she");
    /// const mel: C = C::new("Mel", "mel@corpo.example.com", "she/her");
    /// const troy: C = C::new("Troy", "helenofcity@example.com", "he/him");
    ///
    /// // Define the contact lists as functions producing iterators, in order of preference.
    /// // In reality, you'd use some better means of determining availability, but the principle
    /// // of using fallbacks is sound, and can be used for many scenarios
    ///
    /// fn emergency_contacts() -> impl Iterator<Item = Contact> {
    ///     iter::empty()
    ///         .chain(iter::once(troy).filter(|_| !is_tuesday() && !is_weekend()))
    ///         .chain(iter::once(charlie).filter(|_| !is_weekend()))
    ///         .chain([bob, matriss, harri].into_iter().filter(|_| !is_tuesday() &&
    ///             !is_wednesday()))
    /// }
    ///
    /// fn distant_family_contacts() -> impl Iterator<Item = Contact> {
    ///     // fill in here
    ///#    iter::empty()
    ///#        .chain(iter::once(tracey).filter(|_| !is_weekend() && !is_tuesday()))
    /// }
    ///
    /// fn corpo_contacts() -> impl Iterator<Item = Contact> {
    ///     // fill in here
    ///#    iter::empty()
    ///#        .chain(iter::once(mel).filter(|_| !is_weekend()))
    ///#        .chain(iter::once(tracey))
    /// }
    ///
    /// fn friendly_evening_contacts() -> impl Iterator<Item = Contact> {
    ///     // fill in here
    ///#    iter::empty()
    ///#        .chain([matriss, harri, mel].into_iter()
    ///#            .filter(|_| !is_weekend() && !is_tuesday()))
    ///#        .chain([alan, troy, charlie].into_iter()
    ///#            .filter(|_| !is_weekend() && !is_wednesday()))
    /// }
    ///
    /// // Then, build contact scenarios, using `empty_fallback_chain`
    /// // If there are no contacts available for emergency situations, then
    /// // this will iterate for contacts who can just be messaged for a "friendly evening".
    /// // If that fails, then it will iterate over all distant family contacts.
    /// fn i_have_an_emergency() -> impl Iterator<Item = Contact> {
    ///     emergency_contacts()
    ///         .empty_fallback_chain(friendly_evening_contacts())
    ///         .empty_fallback_chain(distant_family_contacts())
    ///
    /// }
    ///
    /// fn i_want_a_friendly_time() -> impl Iterator<Item = Contact> {
    ///     friendly_evening_contacts()
    ///         .empty_fallback_chain(distant_family_contacts())
    ///         .empty_fallback_chain(corpo_contacts())
    /// }
    ///
    /// fn i_am_having_an_existential_crisis() -> impl Iterator<Item = Contact> {
    ///     // fill in here
    ///#    distant_family_contacts()
    ///#        .empty_fallback_chain(friendly_evening_contacts())
    /// }
    /// ```
    #[inline]
    fn empty_fallback_chain<U>(self, other: U) -> EmptyFallbackChain<Self, U::IntoIter>
    where
        Self: Sized,
        U: IntoIterator<Item = Self::Item>,
    {
        EmptyFallbackChain::new(self, other.into_iter())
    }

    /// Provide an empty fallback chain to this iterator, but only optionally so.
    ///
    /// Should it be a common case that you wish to only provide an empty fallback sometimes but
    /// not others, then this function will let you efficiently create an [`EmptyFallbackChain`]
    /// where the second iterator can be set to empty easily by just passing [`None`], equivalent
    /// to there being no fallback, or a fallback which produces no iterator items.
    ///
    /// This creates less type-nesting and less indirection than using some other mechanisms to
    /// "optionally" iterate something. Note that should you wish to provide [`None`] directly as a
    /// parameter, you may need to use the `::<>` turbofish syntax to manage type deductions - use
    /// any iterator that makes sense in the context here, as you will be setting it to [`None`]
    /// anyway.
    ///
    /// # Basic Illustration
    /// ```rust
    /// use empty_fallback_chain::IteratorExt as _;
    /// use core::iter::Empty;
    ///
    /// fn maybe_empty_fb<A: IntoIterator, B: IntoIterator<Item = A::Item>>(a: A, b: Option<B>) -> Vec<A::Item> {
    ///     a.into_iter().maybe_empty_fallback_chain(b.map(IntoIterator::into_iter)).collect::<Vec<_>>()
    /// }
    ///
    /// assert_eq!(maybe_empty_fb([1,2,3], Some([4, 5, 6])), vec![1, 2, 3]);
    /// assert_eq!(maybe_empty_fb::<_, Empty<usize>>([1,2,3], None), vec![1, 2, 3]);
    /// assert_eq!(maybe_empty_fb([], Some([4, 5, 6])), vec![4, 5, 6]);
    /// assert_eq!(maybe_empty_fb::<_, Empty<usize>>([], None), vec![]);
    /// ```
    ///
    /// # Conditionally Providing Fallback
    /// ```rust
    /// use empty_fallback_chain::{IteratorExt as _, EmptyFallbackChain};
    /// use core::iter;
    ///
    /// fn apply_fallback_conditionally(
    ///     a: impl IntoIterator<Item = usize>,
    ///     do_fallback: bool
    /// ) -> impl Iterator<Item = usize> {
    ///     if do_fallback {
    ///         a.into_iter().empty_fallback_chain([3, 4, 5].iter().copied())
    ///     } else {
    ///         // Note here that we need to provide some help with deduction by providing the
    ///         // outermost iterator of the chain as a hint, because `maybe_empty_fallback_chain`
    ///         // takes an `IntoIterator` as it's parameter and then uses the associated
    ///         // `IntoIter` type, rather than only taking `Iterator`s
    ///         //
    ///         // Another way to solve this problem is to only use one call to
    ///         // `maybe_empty_fallback_chain`, and unify the `Some` and `None` cases into a
    ///         // single `Option` beforehand.
    ///         a.into_iter().maybe_empty_fallback_chain::<iter::Copied<_>>(None)
    ///     }
    /// }
    ///
    /// assert_eq!(apply_fallback_conditionally([1, 2], true).collect::<Vec<_>>(), vec![1, 2]);
    /// assert_eq!(apply_fallback_conditionally([], true).collect::<Vec<_>>(), vec![3, 4, 5]);
    /// assert_eq!(apply_fallback_conditionally([1, 2], false).collect::<Vec<_>>(), vec![1, 2]);
    /// assert_eq!(apply_fallback_conditionally([], false).collect::<Vec<_>>(), vec![]);
    /// ```
    #[inline]
    fn maybe_empty_fallback_chain<U>(
        self,
        other: Option<U>,
    ) -> EmptyFallbackChain<Self, U::IntoIter>
    where
        Self: Sized,
        U: IntoIterator<Item = Self::Item>,
    {
        EmptyFallbackChain::new_with_pre_empty(Some(self), other.map(IntoIterator::into_iter))
    }
}

impl<T: Iterator + ?Sized> IteratorExt for T {}

pub mod prelude {
    pub use super::IteratorExt as _;
}

#[cfg(test)]
mod tests {
    use core::iter;

    fn none_iter<T: Iterator>() -> iter::Flatten<core::option::IntoIter<T>> {
        None.into_iter().flatten()
    }

    fn some_iter<T: Iterator>(t: T) -> iter::Flatten<core::option::IntoIter<T>> {
        Some(t).into_iter().flatten()
    }

    use super::*;
    /// Make the "first" iterator to compose [`make_conditional_iter`]
    fn make_first_iter() -> impl DoubleEndedIterator<Item = u32> + Clone {
        [0].into_iter()
    }

    /// Make the "second" iterator to compose [`make_conditional_iter`]
    fn make_second_iter() -> impl DoubleEndedIterator<Item = u32> + Clone {
        [10, 11].into_iter()
    }

    /// Make the "third" iterator to compose [`make_conditional_iter`]
    fn make_third_iter() -> impl DoubleEndedIterator<Item = u32> + Clone {
        [20, 21, 22, 23, 24, 25].into_iter()
    }

    /// All values that might be emitted from an iterator made by [`make_conditional_iter`]
    /// Not intended for direct comparison, but just for getting all the values.
    fn make_all_values_iter() -> impl Iterator<Item = u32> + Clone {
        make_first_iter()
            .chain(make_second_iter())
            .chain(make_third_iter())
    }

    /// Get a value not present in any possible [`make_conditional_iter`] combination.
    fn non_present_value() -> u32 {
        make_all_values_iter().max().unwrap() + 1
    }

    /// Make an "equivalent" known-good iterator for the given 3-boolean configuration,
    /// only for the forward-order though
    fn make_ideal_equivalent_iter_for(
        include_values: [bool; 3],
    ) -> impl Iterator<Item = u32> + Clone {
        match include_values {
            [true, _, _] => some_iter(make_first_iter())
                .chain(none_iter())
                .chain(none_iter()),
            [false, true, _] => none_iter()
                .chain(some_iter(make_second_iter()))
                .chain(none_iter()),
            [false, false, true] => none_iter()
                .chain(none_iter())
                .chain(some_iter(make_third_iter())),
            [false, false, false] => none_iter().chain(none_iter()).chain(none_iter()),
        }
    }

    /// Make an "equivalent" known-good (for the reverse direction) [`DoubleEndedIterator`] for the
    /// given 3-boolean configuration, only for the reverse order functions though.
    fn make_ideal_equivalent_reverse_iter_for(
        include_values: [bool; 3],
    ) -> impl DoubleEndedIterator<Item = u32> + Clone {
        match include_values {
            [_, _, true] => none_iter()
                .chain(none_iter())
                .chain(some_iter(make_third_iter())),
            [_, true, false] => none_iter()
                .chain(some_iter(make_second_iter()))
                .chain(none_iter()),
            [true, false, false] => some_iter(make_first_iter())
                .chain(none_iter())
                .chain(none_iter()),
            [false, false, false] => none_iter().chain(none_iter()).chain(none_iter()),
        }
    }

    /// Create a 3 element iterator chained with [`EmptyFallbackChain`] and where each given
    /// subiterator either has values or does not depending on the booleans.
    ///
    /// The values in question are, if present, for the iterators in order:
    /// * `[0]`,
    /// * `[10, 11]`
    /// * `[20, 21, 22, 23, 24, 25]`
    fn make_conditional_iter(
        include_values: [bool; 3],
    ) -> impl DoubleEndedIterator<Item = u32> + Clone {
        let first_iter = make_first_iter().filter(move |_| include_values[0]);
        let second_iter = make_second_iter().filter(move |_| include_values[1]);
        let third_iter = make_third_iter().filter(move |_| include_values[2]);
        first_iter
            .empty_fallback_chain(second_iter)
            .empty_fallback_chain(third_iter)
    }

    /// Compare the functionality of a pair of iterators that should be "equivalent"
    /// This means basic things, but also the more advanced iterator methods.
    ///
    /// Note that this will not compare [`DoubleEndedIterator`] methods - because the equivalent
    /// "known good" iterator might be different for the opposite direction.
    fn compare_iters(
        known_good: impl Iterator<Item = u32> + Clone,
        to_test: impl Iterator<Item = u32> + Clone,
    ) {
        // Test contents
        assert_eq!(
            known_good.clone().collect::<Vec<_>>(),
            to_test.clone().collect::<Vec<_>>()
        );

        assert_eq!(known_good.clone().count(), to_test.clone().count());

        assert_eq!(
            known_good.clone().fold(3, |a, b| a + b),
            to_test.clone().fold(3, |a, b| a + b)
        );

        for possible_value in make_all_values_iter().chain(iter::once(non_present_value())) {
            assert_eq!(
                known_good.clone().find(|v| *v == possible_value),
                to_test.clone().find(|v| *v == possible_value)
            )
        }

        assert_eq!(known_good.last(), to_test.last());
    }

    /// Compare specifically the reverse-based functionality of a pair of double ended iterators.
    /// This is separated out from [`compare_iters`] because of divergent inverse behaviour which
    /// means there is a different "ideal" model for the inverse mode.
    fn compare_inverse_iters(
        known_good: impl DoubleEndedIterator<Item = u32> + Clone,
        to_test: impl DoubleEndedIterator<Item = u32> + Clone,
    ) {
        // Test inverse contents.
        assert_eq!(
            known_good.clone().rev().collect::<Vec<_>>(),
            to_test.clone().rev().collect::<Vec<_>>()
        );

        // Test reverse-find
        for possible_value in make_all_values_iter().chain(iter::once(non_present_value())) {
            assert_eq!(
                known_good.clone().rfind(|v| *v == possible_value),
                to_test.clone().rfind(|v| *v == possible_value)
            );
        }

        // Test rfold
        assert_eq!(
            known_good.rfold(3, |acc, v| acc + v),
            to_test.rfold(3, |acc, v| acc + v)
        );
    }

    /// Run tests for the [`make_conditional_iter`] generated by the given boolean triplet, against
    /// the "ideal" iterator that it should be equivalent to if [`EmptyFallbackChain`] works
    /// correctly.
    fn compare_boolean_made_iters(include_values: [bool; 3]) {
        compare_iters(
            make_ideal_equivalent_iter_for(include_values),
            make_conditional_iter(include_values),
        );
    }

    /// Run tests for the [`make_conditional_iter`] generated by the given boolean triplet, against
    /// the "ideal" double ended iterator that it's inverse "double-ended" methods should be
    /// equivalent to if [`EmptyFallbackChain`] works correctly.
    fn compare_boolean_made_inverse_iters(include_values: [bool; 3]) {
        compare_inverse_iters(
            make_ideal_equivalent_reverse_iter_for(include_values),
            make_conditional_iter(include_values),
        )
    }

    #[test]
    fn chained_priority_basics() {
        for i0 in [false, true] {
            for i1 in [false, true] {
                for i2 in [false, true] {
                    compare_boolean_made_iters([i0, i1, i2]);
                    compare_boolean_made_inverse_iters([i0, i1, i2]);
                }
            }
        }
    }
}

// This Source Code Form is subject to the terms of the Mozilla Public
//  License, v. 2.0. If a copy of the MPL was not distributed with this
//  file, You can obtain one at http://mozilla.org/MPL/2.0/.