// 使用有用的类型
use core::{marker::PhantomData, ops::Add};
use num_traits::{ConstOne, ConstZero, ops::overflowing::{OverflowingAdd, OverflowingSub}};

/// # 加法迭代器
/// 
/// 如果要创建迭代器，请使用`new`方法。
/// 
/// 使用方法：
/// 
/// ```
/// use crate::Adder; // 使用加法迭代器
/// let first = [0u32]; // 第一个操作数
/// let second = [0u32]; // 第二个操作数
/// let adder: Adder<_, _, u32>
/// = Adder::new(first.into_iter(), second.into_iter()); // 加法迭代器
/// let result: Vec<u32> = adder.collect(); // 收集为一个动态数组
/// assert_eq!(result, vec![1]); // 验证结果
/// ```
/// 
/// ## 泛型参数
/// `I: Iterator`：第一个NNA迭代器类型
/// `J: Iterator`：第二个NNA迭代器类型
/// `L: Copy = <I as Iterator>::Item`：输出的NNA迭代器的元素类型（Limb）
/// `C: Copy = L`：存储进位的类型，**需要存储0,1,2**
/// 
/// [加法理论](../../prove/operator/add/en.md)
pub struct Adder<I: Iterator, J: Iterator, L: Copy = <I as Iterator>::Item, C: Copy = L> {
    first: I, 
    second: J, 
    carry: C, 
    limb: PhantomData<L>, 
}
impl<I: Iterator, J: Iterator, L: Copy, C: Copy> Adder<I, J, L, C> {
    /// # 新建一个加法迭代器
    /// 
    /// `first`：第一个加数的NNA迭代器
    /// `second`：第二个加数的NNA迭代器
    pub const fn new (first: I, second: J) -> Self where C: ConstZero {
        Self {
            first: first, 
            second: second, 
            carry: C::ZERO, 
            limb: PhantomData
        }
    }
}

impl<I: Iterator, J: Iterator, L: Copy, C: Copy> Iterator for Adder<I, J, L, C> where
I::Item: Into<L>, 
J::Item: Into<L>, 
L: OverflowingAdd + OverflowingSub + ConstOne,  
C: Into<L> + From<bool> + ConstZero + Add<Output = C>
{
    type Item = L;
    fn next(&mut self) -> Option<Self::Item> {
        match (self.first.next(), self.second.next()) {
            (Some(first), Some(second)) => {
                let (tmp1, carry1) = first.into().overflowing_add(&second.into());
                let (tmp2, carry2) = tmp1.overflowing_add(&self.carry.into());
                let (limb, carry3) = tmp2.overflowing_add(&L::ONE);
                self.carry = C::from(carry1) + C::from(carry2) + C::from(carry3);
                Some(limb)
            }
            (Some(first), None) => {
                let (limb, carry) = first.into().overflowing_add(&self.carry.into());
                self.carry = carry.into();
                Some(limb)
            }
            (None, Some(second)) => {
                let (limb, carry) = second.into().overflowing_add(&self.carry.into());
                self.carry = carry.into();
                Some(limb)
            }
            (None, None) => {
                let (limb, carry) = self.carry.into().overflowing_sub(&L::ONE);
                if carry {
                    None
                } else {
                    self.carry = C::ZERO;
                    Some(limb)
                }
            }
        }
    }

    #[inline]
    fn size_hint(&self) -> (usize, Option<usize>) {
        let (first_min, first_max) = self.first.size_hint();
        let (second_min, second_max) = self.second.size_hint();
        (
            first_min.max(second_min), 
            first_max.and_then(
                |first| second_max.and_then(
                    |second| Some(first.max(second) + 1)
                )
            )
        )
    }
}

/// # 加法简化宏
/// 
/// 不需要将输入的容器用[`IntoIterator::into_iter`]方法转换为迭代器再将输出容器用[`Iterator::collect`]方法收集了。
/// 但是由于用的是[`IntoIterator::into_iter`]方法，所以会消耗所有权，后续版本可能会进行优化。
/// 
/// 使用时最好进行显式的类型标注。
/// 
/// - 可以接收两个实现[`IntoIterator`]的表达式，但是编译器可能会判断不出进位标志类型（即`C`），因此最好不要采用这种方式。
/// - 可以接收两个实现[`IntoIterator`]的表达式外加一个进位标志类型。
/// - 可以接收两个实现[`IntoIterator`]的表达式外加一个输出NNA的元素类型和一个进位标志类型。
/// 
/// 使用方法：
/// ```
/// use crate::add;
/// let first = [0u8];
/// let second = [0u8];
/// let result: Vec<u8> = add!(first, second, u8);
/// dbg!(result);
/// let result: Vec<u8> = add!(first, second, u8, u8);
/// dbg!(result);
/// ```
#[macro_export]
macro_rules! add {
    ($first: expr, $second: expr) => {
        $crate::Adder::new(IntoIterator::into_iter($first), IntoIterator::into_iter($second)).collect()
    };
    ($first: expr, $second: expr, $carry: ty) => {
        $crate::Adder::<_, _, _, $carry>::new(
            IntoIterator::into_iter($first), 
            IntoIterator::into_iter($second)
        ).collect()
    };
    ($first: expr, $second: expr, $digit: ty, $carry: ty) => {
        $crate::Adder::<_, _, $digit, $carry>::new(
            IntoIterator::into_iter($first), 
            IntoIterator::into_iter($second)
        ).collect()
    };
}
