use crate::iter::{DoubleEndedIterator, FusedIterator, Iterator, TrustedLen};
use crate::ops::Try;

/// 链中将两个迭代器链接在一起的迭代器。
///
/// 该 `struct` 由 [`Iterator::chain`] 创建。
/// 有关更多信息，请参见其文档。
///
/// # Examples
///
/// ```
/// use std::iter::Chain;
/// use std::slice::Iter;
///
/// let a1 = [1, 2, 3];
/// let a2 = [4, 5, 6];
/// let iter: Chain<Iter<_>, Iter<_>> = a1.iter().chain(a2.iter());
/// ```
#[derive(Clone, Debug)]
#[must_use = "iterators are lazy and do nothing unless consumed"]
#[stable(feature = "rust1", since = "1.0.0")]
pub struct Chain<A, B> {
    // 它们是带有 `Option` 的 "fused"，因此我们不需要单独的状态来跟踪已经用尽的部分，并且我们还可以获得 `None` 的细分布局。
    // 我们不使用真正的 `Fuse` 适配器，因为它对 `FusedIterator` 的专门化无条件地属于迭代器，而要继续访问嵌套链之类的东西可能会很昂贵。
    //
    // 向 `Chain` 添加更多的迭代器层也损害了编译器的性能。
    //
    // 实际用完时，只有 "first" 迭代器才实际设置为 `None`，具体取决于您是向前还是向后迭代。如果混合方向，则两边都可能是 `None`。
    //
    //
    a: Option<A>,
    b: Option<B>,
}
impl<A, B> Chain<A, B> {
    pub(in super::super) fn new(a: A, b: B) -> Chain<A, B> {
        Chain { a: Some(a), b: Some(b) }
    }
}

/// 如果表达式为 `None`，则对迭代器进行融合。
macro_rules! fuse {
    ($self:ident . $iter:ident . $($call:tt)+) => {
        match $self.$iter {
            Some(ref mut iter) => match iter.$($call)+ {
                None => {
                    $self.$iter = None;
                    None
                }
                item => item,
            },
            None => None,
        }
    };
}

/// 尝试使用不带融合功能的迭代器方法，例如内联 `.as_mut().and_then(...)`
///
macro_rules! maybe {
    ($self:ident . $iter:ident . $($call:tt)+) => {
        match $self.$iter {
            Some(ref mut iter) => iter.$($call)+,
            None => None,
        }
    };
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> Iterator for Chain<A, B>
where
    A: Iterator,
    B: Iterator<Item = A::Item>,
{
    type Item = A::Item;

    #[inline]
    fn next(&mut self) -> Option<A::Item> {
        match fuse!(self.a.next()) {
            None => maybe!(self.b.next()),
            item => item,
        }
    }

    #[inline]
    #[rustc_inherit_overflow_checks]
    fn count(self) -> usize {
        let a_count = match self.a {
            Some(a) => a.count(),
            None => 0,
        };
        let b_count = match self.b {
            Some(b) => b.count(),
            None => 0,
        };
        a_count + b_count
    }

    fn try_fold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
    where
        Self: Sized,
        F: FnMut(Acc, Self::Item) -> R,
        R: Try<Output = Acc>,
    {
        if let Some(ref mut a) = self.a {
            acc = a.try_fold(acc, &mut f)?;
            self.a = None;
        }
        if let Some(ref mut b) = self.b {
            acc = b.try_fold(acc, f)?;
            // 我们不融合第二个迭代器
        }
        try { acc }
    }

    fn fold<Acc, F>(self, mut acc: Acc, mut f: F) -> Acc
    where
        F: FnMut(Acc, Self::Item) -> Acc,
    {
        if let Some(a) = self.a {
            acc = a.fold(acc, &mut f);
        }
        if let Some(b) = self.b {
            acc = b.fold(acc, f);
        }
        acc
    }

    #[inline]
    fn advance_by(&mut self, n: usize) -> Result<(), usize> {
        let mut rem = n;

        if let Some(ref mut a) = self.a {
            match a.advance_by(rem) {
                Ok(()) => return Ok(()),
                Err(k) => rem -= k,
            }
            self.a = None;
        }

        if let Some(ref mut b) = self.b {
            match b.advance_by(rem) {
                Ok(()) => return Ok(()),
                Err(k) => rem -= k,
            }
            // 我们不融合第二个迭代器
        }

        if rem == 0 { Ok(()) } else { Err(n - rem) }
    }

    #[inline]
    fn nth(&mut self, mut n: usize) -> Option<Self::Item> {
        if let Some(ref mut a) = self.a {
            match a.advance_by(n) {
                Ok(()) => match a.next() {
                    None => n = 0,
                    x => return x,
                },
                Err(k) => n -= k,
            }

            self.a = None;
        }

        maybe!(self.b.nth(n))
    }

    #[inline]
    fn find<P>(&mut self, mut predicate: P) -> Option<Self::Item>
    where
        P: FnMut(&Self::Item) -> bool,
    {
        match fuse!(self.a.find(&mut predicate)) {
            None => maybe!(self.b.find(predicate)),
            item => item,
        }
    }

    #[inline]
    fn last(self) -> Option<A::Item> {
        // 必须在 b 之前用尽 a。
        let a_last = match self.a {
            Some(a) => a.last(),
            None => None,
        };
        let b_last = match self.b {
            Some(b) => b.last(),
            None => None,
        };
        b_last.or(a_last)
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        match self {
            Chain { a: Some(a), b: Some(b) } => {
                let (a_lower, a_upper) = a.size_hint();
                let (b_lower, b_upper) = b.size_hint();

                let lower = a_lower.saturating_add(b_lower);

                let upper = match (a_upper, b_upper) {
                    (Some(x), Some(y)) => x.checked_add(y),
                    _ => None,
                };

                (lower, upper)
            }
            Chain { a: Some(a), b: None } => a.size_hint(),
            Chain { a: None, b: Some(b) } => b.size_hint(),
            Chain { a: None, b: None } => (0, Some(0)),
        }
    }
}

#[stable(feature = "rust1", since = "1.0.0")]
impl<A, B> DoubleEndedIterator for Chain<A, B>
where
    A: DoubleEndedIterator,
    B: DoubleEndedIterator<Item = A::Item>,
{
    #[inline]
    fn next_back(&mut self) -> Option<A::Item> {
        match fuse!(self.b.next_back()) {
            None => maybe!(self.a.next_back()),
            item => item,
        }
    }

    #[inline]
    fn advance_back_by(&mut self, n: usize) -> Result<(), usize> {
        let mut rem = n;

        if let Some(ref mut b) = self.b {
            match b.advance_back_by(rem) {
                Ok(()) => return Ok(()),
                Err(k) => rem -= k,
            }
            self.b = None;
        }

        if let Some(ref mut a) = self.a {
            match a.advance_back_by(rem) {
                Ok(()) => return Ok(()),
                Err(k) => rem -= k,
            }
            // 我们不融合第二个迭代器
        }

        if rem == 0 { Ok(()) } else { Err(n - rem) }
    }

    #[inline]
    fn nth_back(&mut self, mut n: usize) -> Option<Self::Item> {
        if let Some(ref mut b) = self.b {
            match b.advance_back_by(n) {
                Ok(()) => match b.next_back() {
                    None => n = 0,
                    x => return x,
                },
                Err(k) => n -= k,
            }

            self.b = None;
        }

        maybe!(self.a.nth_back(n))
    }

    #[inline]
    fn rfind<P>(&mut self, mut predicate: P) -> Option<Self::Item>
    where
        P: FnMut(&Self::Item) -> bool,
    {
        match fuse!(self.b.rfind(&mut predicate)) {
            None => maybe!(self.a.rfind(predicate)),
            item => item,
        }
    }

    fn try_rfold<Acc, F, R>(&mut self, mut acc: Acc, mut f: F) -> R
    where
        Self: Sized,
        F: FnMut(Acc, Self::Item) -> R,
        R: Try<Output = Acc>,
    {
        if let Some(ref mut b) = self.b {
            acc = b.try_rfold(acc, &mut f)?;
            self.b = None;
        }
        if let Some(ref mut a) = self.a {
            acc = a.try_rfold(acc, f)?;
            // 我们不融合第二个迭代器
        }
        try { acc }
    }

    fn rfold<Acc, F>(self, mut acc: Acc, mut f: F) -> Acc
    where
        F: FnMut(Acc, Self::Item) -> Acc,
    {
        if let Some(b) = self.b {
            acc = b.rfold(acc, &mut f);
        }
        if let Some(a) = self.a {
            acc = a.rfold(acc, f);
        }
        acc
    }
}

// Note: *两个* 都必须融合以处理双端迭代器。
#[stable(feature = "fused", since = "1.26.0")]
impl<A, B> FusedIterator for Chain<A, B>
where
    A: FusedIterator,
    B: FusedIterator<Item = A::Item>,
{
}

#[unstable(feature = "trusted_len", issue = "37572")]
unsafe impl<A, B> TrustedLen for Chain<A, B>
where
    A: TrustedLen,
    B: TrustedLen<Item = A::Item>,
{
}