extern crate num_integer;
extern crate num_traits;

use num_integer::Roots;
use num_traits::checked_pow;
use num_traits::{AsPrimitive, PrimInt, Signed};
use std::f64::MANTISSA_DIGITS;
use std::fmt::Debug;
use std::mem;

trait TestInteger: Roots + PrimInt + Debug + AsPrimitive<f64> + 'static {}

impl<T> TestInteger for T
where
    T: Roots + PrimInt + Debug + AsPrimitive<f64> + 'static,
{
}

/// Check that each root is correct
///
/// If `x` is positive, check `rⁿ ≤ x < (r+1)ⁿ`.
/// If `x` is negative, check `(r-1)ⁿ < x ≤ rⁿ`.
fn check<T>(v: &[T], n: u32)
where
    T: TestInteger,
{
    for i in v {
        let rt = i.nth_root(n);
        // println!("nth_root({:?}, {}) = {:?}", i, n, rt);
        if n == 2 {
            assert_eq!(rt, i.sqrt());
        } else if n == 3 {
            assert_eq!(rt, i.cbrt());
        }
        if *i >= T::zero() {
            let rt1 = rt + T::one();
            assert!(rt.pow(n) <= *i);
            if let Some(x) = checked_pow(rt1, n as usize) {
                assert!(*i < x);
            }
        } else {
            let rt1 = rt - T::one();
            assert!(rt < T::zero());
            assert!(*i <= rt.pow(n));
            if let Some(x) = checked_pow(rt1, n as usize) {
                assert!(x < *i);
            }
        };
    }
}

/// Get the maximum value that will round down as `f64` (if any),
/// and its successor that will round up.
///
/// Important because the `std` implementations cast to `f64` to
/// get a close approximation of the roots.
fn mantissa_max<T>() -> Option<(T, T)>
where
    T: TestInteger,
{
    let bits = if T::min_value().is_zero() {
        8 * mem::size_of::<T>()
    } else {
        8 * mem::size_of::<T>() - 1
    };
    if bits > MANTISSA_DIGITS as usize {
        let rounding_bit = T::one() << (bits - MANTISSA_DIGITS as usize - 1);
        let x = T::max_value() - rounding_bit;

        let x1 = x + T::one();
        let x2 = x1 + T::one();
        assert!(x.as_() < x1.as_());
        assert_eq!(x1.as_(), x2.as_());

        Some((x, x1))
    } else {
        None
    }
}

fn extend<T>(v: &mut Vec<T>, start: T, end: T)
where
    T: TestInteger,
{
    let mut i = start;
    while i < end {
        v.push(i);
        i = i + T::one();
    }
    v.push(i);
}

fn extend_shl<T>(v: &mut Vec<T>, start: T, end: T, mask: T)
where
    T: TestInteger,
{
    let mut i = start;
    while i != end {
        v.push(i);
        i = (i << 1) & mask;
    }
}

fn extend_shr<T>(v: &mut Vec<T>, start: T, end: T)
where
    T: TestInteger,
{
    let mut i = start;
    while i != end {
        v.push(i);
        i = i >> 1;
    }
}

fn pos<T>() -> Vec<T>
where
    T: TestInteger,
    i8: AsPrimitive<T>,
{
    let mut v: Vec<T> = vec![];
    if mem::size_of::<T>() == 1 {
        extend(&mut v, T::zero(), T::max_value());
    } else {
        extend(&mut v, T::zero(), i8::max_value().as_());
        extend(
            &mut v,
            T::max_value() - i8::max_value().as_(),
            T::max_value(),
        );
        if let Some((i, j)) = mantissa_max::<T>() {
            v.push(i);
            v.push(j);
        }
        extend_shl(&mut v, T::max_value(), T::zero(), !T::min_value());
        extend_shr(&mut v, T::max_value(), T::zero());
    }
    v
}

fn neg<T>() -> Vec<T>
where
    T: TestInteger + Signed,
    i8: AsPrimitive<T>,
{
    let mut v: Vec<T> = vec![];
    if mem::size_of::<T>() <= 1 {
        extend(&mut v, T::min_value(), T::zero());
    } else {
        extend(&mut v, i8::min_value().as_(), T::zero());
        extend(
            &mut v,
            T::min_value(),
            T::min_value() - i8::min_value().as_(),
        );
        if let Some((i, j)) = mantissa_max::<T>() {
            v.push(-i);
            v.push(-j);
        }
        extend_shl(&mut v, -T::one(), T::min_value(), !T::zero());
        extend_shr(&mut v, T::min_value(), -T::one());
    }
    v
}

macro_rules! test_roots {
    ($I:ident, $U:ident) => {
        mod $I {
            use check;
            use neg;
            use num_integer::Roots;
            use pos;
            use std::mem;

            #[test]
            #[should_panic]
            fn zeroth_root() {
                (123 as $I).nth_root(0);
            }

            #[test]
            fn sqrt() {
                check(&pos::<$I>(), 2);
            }

            #[test]
            #[should_panic]
            fn sqrt_neg() {
                (-123 as $I).sqrt();
            }

            #[test]
            fn cbrt() {
                check(&pos::<$I>(), 3);
            }

            #[test]
            fn cbrt_neg() {
                check(&neg::<$I>(), 3);
            }

            #[test]
            fn nth_root() {
                let bits = 8 * mem::size_of::<$I>() as u32 - 1;
                let pos = pos::<$I>();
                for n in 4..bits {
                    check(&pos, n);
                }
            }

            #[test]
            fn nth_root_neg() {
                let bits = 8 * mem::size_of::<$I>() as u32 - 1;
                let neg = neg::<$I>();
                for n in 2..bits / 2 {
                    check(&neg, 2 * n + 1);
                }
            }

            #[test]
            fn bit_size() {
                let bits = 8 * mem::size_of::<$I>() as u32 - 1;
                assert_eq!($I::max_value().nth_root(bits - 1), 2);
                assert_eq!($I::max_value().nth_root(bits), 1);
                assert_eq!($I::min_value().nth_root(bits), -2);
                assert_eq!(($I::min_value() + 1).nth_root(bits), -1);
            }
        }

        mod $U {
            use check;
            use num_integer::Roots;
            use pos;
            use std::mem;

            #[test]
            #[should_panic]
            fn zeroth_root() {
                (123 as $U).nth_root(0);
            }

            #[test]
            fn sqrt() {
                check(&pos::<$U>(), 2);
            }

            #[test]
            fn cbrt() {
                check(&pos::<$U>(), 3);
            }

            #[test]
            fn nth_root() {
                let bits = 8 * mem::size_of::<$I>() as u32 - 1;
                let pos = pos::<$I>();
                for n in 4..bits {
                    check(&pos, n);
                }
            }

            #[test]
            fn bit_size() {
                let bits = 8 * mem::size_of::<$U>() as u32;
                assert_eq!($U::max_value().nth_root(bits - 1), 2);
                assert_eq!($U::max_value().nth_root(bits), 1);
            }
        }
    };
}

test_roots!(i8, u8);
test_roots!(i16, u16);
test_roots!(i32, u32);
test_roots!(i64, u64);
#[cfg(has_i128)]
test_roots!(i128, u128);
test_roots!(isize, usize);