use crate::num::NonZeroUsize;
use crate::ops::{ControlFlow, Try};

/// 一个能够从两端产生元素的迭代器。
///
/// 实现 `DoubleEndedIterator` 的东西比实现 [`Iterator`] 的东西具有一项额外的功能：既可以从后面也可以从前面获得 `item` 的功能。
///
///
/// 重要的是要注意，来回运动都在相同的范围内，并且不会交叉：当它们在中间相遇时，迭代就结束了。
///
/// 以与 [`Iterator`] 协议类似的方式，一旦 `DoubleEndedIterator` 从 [`next_back()`] 返回 [`None`]，再次调用它可能会也可能不会再返回 [`Some`]。
/// 为此，[`next()`] 和 [`next_back()`] 可以互换。
///
/// [`next_back()`]: DoubleEndedIterator::next_back
/// [`next()`]: Iterator::next
///
/// # Examples
///
/// 基本用法：
///
/// ```
/// let numbers = vec![1, 2, 3, 4, 5, 6];
///
/// let mut iter = numbers.iter();
///
/// assert_eq!(Some(&1), iter.next());
/// assert_eq!(Some(&6), iter.next_back());
/// assert_eq!(Some(&5), iter.next_back());
/// assert_eq!(Some(&2), iter.next());
/// assert_eq!(Some(&3), iter.next());
/// assert_eq!(Some(&4), iter.next());
/// assert_eq!(None, iter.next());
/// assert_eq!(None, iter.next_back());
/// ```
///
///
///
///
#[stable(feature = "rust1", since = "1.0.0")]
#[cfg_attr(not(test), rustc_diagnostic_item = "DoubleEndedIterator")]
pub trait DoubleEndedIterator: Iterator {
    /// 从迭代器的末尾删除并返回一个元素。
    ///
    /// 没有更多元素时返回 `None`。
    ///
    /// [trait-level] 文档包含更多详细信息。
    ///
    /// [trait-level]: DoubleEndedIterator
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// let numbers = vec![1, 2, 3, 4, 5, 6];
    ///
    /// let mut iter = numbers.iter();
    ///
    /// assert_eq!(Some(&1), iter.next());
    /// assert_eq!(Some(&6), iter.next_back());
    /// assert_eq!(Some(&5), iter.next_back());
    /// assert_eq!(Some(&2), iter.next());
    /// assert_eq!(Some(&3), iter.next());
    /// assert_eq!(Some(&4), iter.next());
    /// assert_eq!(None, iter.next());
    /// assert_eq!(None, iter.next_back());
    /// ```
    ///
    /// # Remarks
    ///
    /// DoubleEndedIterator 方法产生的元素可能与 [`Iterator`] 方法产生的元素不同：
    ///
    ///
    /// ```
    /// let vec = vec![(1, 'a'), (1, 'b'), (1, 'c'), (2, 'a'), (2, 'b')];
    /// let uniq_by_fst_comp = || {
    ///     let mut seen = std::collections::HashSet::new();
    ///     vec.iter().copied().filter(move |x| seen.insert(x.0))
    /// };
    ///
    /// assert_eq!(uniq_by_fst_comp().last(), Some((2, 'a')));
    /// assert_eq!(uniq_by_fst_comp().next_back(), Some((2, 'b')));
    ///
    /// assert_eq!(
    ///     uniq_by_fst_comp().fold(vec![], |mut v, x| {v.push(x); v}),
    ///     vec![(1, 'a'), (2, 'a')]
    /// );
    /// assert_eq!(
    ///     uniq_by_fst_comp().rfold(vec![], |mut v, x| {v.push(x); v}),
    ///     vec![(2, 'b'), (1, 'c')]
    /// );
    /// ```
    #[stable(feature = "rust1", since = "1.0.0")]
    fn next_back(&mut self) -> Option<Self::Item>;

    /// 通过 `n` 元素从后向前推进迭代器。
    ///
    /// `advance_back_by` 是 [`advance_by`] 的反向版本。该方法将急切地从后面开始跳过 `n` 元素，方法是调用 [`next_back`] 最多 `n` 次，直到遇到 [`None`]。
    ///
    /// 如果迭代器成功前进了 `n` 个元素，`advance_back_by(n)` 将返回 `Ok(())`，如果遇到 [`None`]，则返回值为 `k` 的 `Err(NonZeroUsize)`，其中 `k` 是由于迭代器用完而无法前进的剩余步数。
    ///
    /// 如果 `self` 为空且 `n` 非零，则返回 `Err(n)`。
    /// 否则，`k` 总是小于 `n`。
    ///
    /// 调用 `advance_back_by(0)` 可以做有意义的工作，例如 [`Flatten`] 可以推进它的外部迭代器，直到它找到一个不为空的内部迭代器，然后通常允许它返回一个比初始状态更准确的 `size_hint()`。
    ///
    /// [`advance_by`]: Iterator::advance_by
    /// [`Flatten`]: crate::iter::Flatten
    /// [`next_back`]: DoubleEndedIterator::next_back
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// #![feature(iter_advance_by)]
    ///
    /// use std::num::NonZeroUsize;
    /// let a = [3, 4, 5, 6];
    /// let mut iter = a.iter();
    ///
    /// assert_eq!(iter.advance_back_by(2), Ok(()));
    /// assert_eq!(iter.next_back(), Some(&4));
    /// assert_eq!(iter.advance_back_by(0), Ok(()));
    /// assert_eq!(iter.advance_back_by(100), Err(NonZeroUsize::new(99).unwrap())); // 仅跳过 `&3`
    /// ```
    ///
    /// [`Ok(())`]: Ok
    /// [`Err(k)`]: Err
    ///
    ///
    ///
    ///
    ///
    #[inline]
    #[unstable(feature = "iter_advance_by", reason = "recently added", issue = "77404")]
    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
        for i in 0..n {
            if self.next_back().is_none() {
                // SAFETY: `i` 总是小于 `n`。
                return Err(unsafe { NonZeroUsize::new_unchecked(n - i) });
            }
        }
        Ok(())
    }

    /// 从迭代器的末尾返回第 n 个元素。
    ///
    /// 这实际上是 [`Iterator::nth()`] 的反向版本。
    /// 尽管像大多数索引操作一样，计数从零开始，所以 `nth_back(0)` 从末尾返回第一个值，`nth_back(1)` 从第二个开始返回，依此类推。
    ///
    ///
    /// 请注意，将消耗 end 和返回元素之间的所有元素，包括返回元素。
    /// 这也意味着在同一迭代器上多次调用 `nth_back(0)` 将返回不同的元素。
    ///
    /// 如果 `n` 大于或等于迭代器的长度，则 `nth_back()` 将返回 [`None`]。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// let a = [1, 2, 3];
    /// assert_eq!(a.iter().nth_back(2), Some(&1));
    /// ```
    ///
    /// 多次调用 `nth_back()` 不会回退迭代器：
    ///
    /// ```
    /// let a = [1, 2, 3];
    ///
    /// let mut iter = a.iter();
    ///
    /// assert_eq!(iter.nth_back(1), Some(&2));
    /// assert_eq!(iter.nth_back(1), None);
    /// ```
    ///
    /// 如果少于 `n + 1` 个元素，则返回 `None`：
    ///
    /// ```
    /// let a = [1, 2, 3];
    /// assert_eq!(a.iter().nth_back(10), None);
    /// ```
    ///
    ///
    ///
    ///
    #[inline]
    #[stable(feature = "iter_nth_back", since = "1.37.0")]
    fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
        if self.advance_back_by(n).is_err() {
            return None;
        }
        self.next_back()
    }

    /// 这是 [`Iterator::try_fold()`] 的反向版本：它从迭代器的后面开始接收元素。
    ///
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// let a = ["1", "2", "3"];
    /// let sum = a.iter()
    ///     .map(|&s| s.parse::<i32>())
    ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
    /// assert_eq!(sum, Ok(6));
    /// ```
    ///
    /// Short-circuiting:
    ///
    /// ```
    /// let a = ["1", "rust", "3"];
    /// let mut it = a.iter();
    /// let sum = it
    ///     .by_ref()
    ///     .map(|&s| s.parse::<i32>())
    ///     .try_rfold(0, |acc, x| x.and_then(|y| Ok(acc + y)));
    /// assert!(sum.is_err());
    ///
    /// // 由于发生短路，因此其余元素仍可通过迭代器使用。
    /////
    /// assert_eq!(it.next_back(), Some(&"1"));
    /// ```
    #[inline]
    #[stable(feature = "iterator_try_fold", since = "1.27.0")]
    fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> R,
        R: Try<Output = B>,
    {
        let mut accum = init;
        while let Some(x) = self.next_back() {
            accum = f(accum, x)?;
        }
        try { accum }
    }

    /// 一种迭代器方法，从后面开始，将迭代器的元素减少为单个最终值。
    ///
    /// 这是 [`Iterator::fold()`] 的反向版本：它从迭代器的后面开始接收元素。
    ///
    /// `rfold()` 有两个参数：一个初始值，一个闭包，有两个参数：一个 'accumulator' 和一个元素。
    /// 闭包返回累加器在下一次迭代中应具有的值。
    ///
    /// 初始值是累加器在第一次调用时将具有的值。
    ///
    /// 在将此闭包应用于迭代器的每个元素之后，`rfold()` 返回累加器。
    ///
    /// 该操作有时称为 'reduce' 或 'inject'。
    ///
    /// 当您拥有某个集合，并且希望从中产生单个值时，`fold` 非常有用。
    ///
    /// Note: `rfold()` 以*右关联*方式组合元素。
    /// 对于像 `+` 这样的关联性，元素组合的顺序并不重要，但对于像 `-` 这样的非关联性，顺序会影响最终结果。
    ///
    /// 对于 `rfold()` 的*左关联*版本，请参见 [`Iterator::fold()`]。
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// let a = [1, 2, 3];
    ///
    /// // a 的所有元素的总和
    /// let sum = a.iter()
    ///            .rfold(0, |acc, &x| acc + x);
    ///
    /// assert_eq!(sum, 6);
    /// ```
    ///
    /// 这个例子演示了 `rfold()` 的右结合性质：
    /// 它构建一个字符串，从一个初始值开始，从后面到前面的每个元素继续：
    ///
    /// ```
    /// let numbers = [1, 2, 3, 4, 5];
    ///
    /// let zero = "0".to_string();
    ///
    /// let result = numbers.iter().rfold(zero, |acc, &x| {
    ///     format!("({x} + {acc})")
    /// });
    ///
    /// assert_eq!(result, "(1 + (2 + (3 + (4 + (5 + 0)))))");
    /// ```
    ///
    ///
    ///
    ///
    ///
    ///
    ///
    #[doc(alias = "foldr")]
    #[inline]
    #[stable(feature = "iter_rfold", since = "1.27.0")]
    fn rfold<B, F>(mut self, init: B, mut f: F) -> B
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> B,
    {
        let mut accum = init;
        while let Some(x) = self.next_back() {
            accum = f(accum, x);
        }
        accum
    }

    /// 从后面搜索满足谓词的迭代器的元素。
    ///
    /// `rfind()` 接受一个返回 `true` 或 `false` 的闭包。
    /// 它将这个闭包应用到迭代器的每个元素 (从末尾开始)，如果其中任何一个返回 `true`，则 `rfind()` 返回 [`Some(element)`]。
    /// 如果它们都返回 `false`，则返回 [`None`]。
    ///
    /// `rfind()` 是短路的； 换句话说，一旦闭包返回 `true`，它将立即停止处理。
    ///
    /// 由于 `rfind()` 接受 quot，并且许多迭代器迭代 quot，因此导致参数为双 quot 的情况可能令人困惑。
    ///
    /// 在 `&&x` 的以下示例中，您可以看到这种效果。
    ///
    /// [`Some(element)`]: Some
    ///
    /// # Examples
    ///
    /// 基本用法：
    ///
    /// ```
    /// let a = [1, 2, 3];
    ///
    /// assert_eq!(a.iter().rfind(|&&x| x == 2), Some(&2));
    ///
    /// assert_eq!(a.iter().rfind(|&&x| x == 5), None);
    /// ```
    ///
    /// 在第一个 `true` 处停止：
    ///
    /// ```
    /// let a = [1, 2, 3];
    ///
    /// let mut iter = a.iter();
    ///
    /// assert_eq!(iter.rfind(|&&x| x == 2), Some(&2));
    ///
    /// // 我们仍然可以使用 `iter`，因为还有更多元素。
    /// assert_eq!(iter.next_back(), Some(&1));
    /// ```
    ///
    ///
    ///
    #[inline]
    #[stable(feature = "iter_rfind", since = "1.27.0")]
    fn rfind<P>(&mut self, predicate: P) -> Option<Self::Item>
    where
        Self: Sized,
        P: FnMut(&Self::Item) -> bool,
    {
        #[inline]
        fn check<T>(mut predicate: impl FnMut(&T) -> bool) -> impl FnMut((), T) -> ControlFlow<T> {
            move |(), x| {
                if predicate(&x) { ControlFlow::Break(x) } else { ControlFlow::Continue(()) }
            }
        }

        self.try_rfold((), check(predicate)).break_value()
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<'a, I: DoubleEndedIterator + ?Sized> DoubleEndedIterator for &'a mut I {
    fn next_back(&mut self) -> Option<I::Item> {
        (**self).next_back()
    }
    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZeroUsize> {
        (**self).advance_back_by(n)
    }
    fn nth_back(&mut self, n: usize) -> Option<I::Item> {
        (**self).nth_back(n)
    }
}