use crate::fmt;
use crate::iter::{adapters::SourceIter, FusedIterator, InPlaceIterable};
use crate::ops::Try;
use core::array;
use core::mem::{ManuallyDrop, MaybeUninit};
use core::ops::ControlFlow;

/// 一个用 `predicate` 过滤 `iter` 元素的迭代器。
///
/// 该 `struct` 是通过 [`Iterator`] 上的 [`filter`] 方法创建的。
/// 有关更多信息，请参见其文档。
///
/// [`filter`]: Iterator::filter
/// [`Iterator`]: trait.Iterator.html
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
#[derive(Clone)]
pub struct Filter<I, P> {
    // 用于 `SplitWhitespace` 和 `SplitAsciiWhitespace` `as_str` 方法
    pub(crate) iter: I,
    predicate: P,
}
impl<I, P> Filter<I, P> {
    pub(in crate::iter) fn new(iter: I, predicate: P) -> Filter<I, P> {
        Filter { iter, predicate }
    }
}

#[stable(feature = "core_impl_debug", since = "1.9.0")]
impl<I: fmt::Debug, P> fmt::Debug for Filter<I, P> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Filter").field("iter", &self.iter).finish()
    }
}

fn filter_fold<T, Acc>(
    mut predicate: impl FnMut(&T) -> bool,
    mut fold: impl FnMut(Acc, T) -> Acc,
) -> impl FnMut(Acc, T) -> Acc {
    move |acc, item| if predicate(&item) { fold(acc, item) } else { acc }
}

fn filter_try_fold<'a, T, Acc, R: Try<Output = Acc>>(
    predicate: &'a mut impl FnMut(&T) -> bool,
    mut fold: impl FnMut(Acc, T) -> R + 'a,
) -> impl FnMut(Acc, T) -> R + 'a {
    move |acc, item| if predicate(&item) { fold(acc, item) } else { try { acc } }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<I: Iterator, P> Iterator for Filter<I, P>
where
    P: FnMut(&I::Item) -> bool,
{
    type Item = I::Item;

    #[inline]
    fn next(&mut self) -> Option<I::Item> {
        self.iter.find(&mut self.predicate)
    }

    #[inline]
    fn next_chunk<const N: usize>(
        &mut self,
    ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>> {
        let mut array: [MaybeUninit<Self::Item>; N] = MaybeUninit::uninit_array();

        struct Guard<'a, T> {
            array: &'a mut [MaybeUninit<T>],
            initialized: usize,
        }

        impl<T> Drop for Guard<'_, T> {
            #[inline]
            fn drop(&mut self) {
                if const { crate::mem::needs_drop::<T>() } {
                    // SAFETY: self.initialized 总是 <= N，这也是数组的长度。
                    unsafe {
                        core::ptr::drop_in_place(MaybeUninit::slice_assume_init_mut(
                            self.array.get_unchecked_mut(..self.initialized),
                        ));
                    }
                }
            }
        }

        let mut guard = Guard { array: &mut array, initialized: 0 };

        let result = self.iter.try_for_each(|element| {
            let idx = guard.initialized;
            guard.initialized = idx + (self.predicate)(&element) as usize;

            // SAFETY: 循环条件确保索引在边界内。
            unsafe { guard.array.get_unchecked_mut(idx) }.write(element);

            if guard.initialized < N { ControlFlow::Continue(()) } else { ControlFlow::Break(()) }
        });

        let guard = ManuallyDrop::new(guard);

        match result {
            ControlFlow::Break(()) => {
                // SAFETY: 上面的循环只有在数组完全初始化后才会显式中断
                Ok(unsafe { MaybeUninit::array_assume_init(array) })
            }
            ControlFlow::Continue(()) => {
                let initialized = guard.initialized;
                // SAFETY: 该范围在边界内，因为循环在到达 N 个元素时中断。
                Err(unsafe { array::IntoIter::new_unchecked(array, 0..initialized) })
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let (_, upper) = self.iter.size_hint();
        (0, upper) // 由于谓词，无法知道下界
    }

    // 这种特殊情况允许编译器使 `.filter(_).count()` 无分支。
    // 除非有完美的分支预测 (这在一般情况下是无法实现的)，否则在超过 90% 的情况下 (几乎包含所有实际工作量)，这将更快，而在其余情况下，速度则稍慢。
    //
    // 因此，拥有这种专业化知识使我们可以编写 `.filter(p).count()`，而在其他情况下则可以编写 `.map(|x| p(x) as usize).sum()`，因为它不那么可读，而且与 1.10 之前的 Rust 的向后兼容性也较低。
    //
    //
    // 使用无分支版本还将简化 LLVM 字节码，从而为 LLVM 优化留出更多预算。
    //
    //
    //
    //
    #[inline]
    fn count(self) -> usize {
        #[inline]
        fn to_usize<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut(T) -> usize {
            move |x| predicate(&x) as usize
        }

        self.iter.map(to_usize(self.predicate)).sum()
    }

    #[inline]
    fn try_fold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
    where
        Self: Sized,
        Fold: FnMut(Acc, Self::Item) -> R,
        R: Try<Output = Acc>,
    {
        self.iter.try_fold(init, filter_try_fold(&mut self.predicate, fold))
    }

    #[inline]
    fn fold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
    where
        Fold: FnMut(Acc, Self::Item) -> Acc,
    {
        self.iter.fold(init, filter_fold(self.predicate, fold))
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<I: DoubleEndedIterator, P> DoubleEndedIterator for Filter<I, P>
where
    P: FnMut(&I::Item) -> bool,
{
    #[inline]
    fn next_back(&mut self) -> Option<I::Item> {
        self.iter.rfind(&mut self.predicate)
    }

    #[inline]
    fn try_rfold<Acc, Fold, R>(&mut self, init: Acc, fold: Fold) -> R
    where
        Self: Sized,
        Fold: FnMut(Acc, Self::Item) -> R,
        R: Try<Output = Acc>,
    {
        self.iter.try_rfold(init, filter_try_fold(&mut self.predicate, fold))
    }

    #[inline]
    fn rfold<Acc, Fold>(self, init: Acc, fold: Fold) -> Acc
    where
        Fold: FnMut(Acc, Self::Item) -> Acc,
    {
        self.iter.rfold(init, filter_fold(self.predicate, fold))
    }
}

#[stable(feature = "fused", since = "1.26.0")]
impl<I: FusedIterator, P> FusedIterator for Filter<I, P> where P: FnMut(&I::Item) -> bool {}

#[unstable(issue = "none", feature = "inplace_iteration")]
unsafe impl<P, I> SourceIter for Filter<I, P>
where
    I: SourceIter,
{
    type Source = I::Source;

    #[inline]
    unsafe fn as_inner(&mut self) -> &mut I::Source {
        // SAFETY: 将不安全的函数转发到具有相同要求的不安全的函数
        unsafe { SourceIter::as_inner(&mut self.iter) }
    }
}

#[unstable(issue = "none", feature = "inplace_iteration")]
unsafe impl<I: InPlaceIterable, P> InPlaceIterable for Filter<I, P> where P: FnMut(&I::Item) -> bool {}