Import 'num-integer' crate version 0.2.11
Change-Id: I43f7b6de8a4ffae1f721423fce67e56c2137701e
diff --git a/tests/average.rs b/tests/average.rs
new file mode 100644
index 0000000..9fd8cf1
--- /dev/null
+++ b/tests/average.rs
@@ -0,0 +1,100 @@
+extern crate num_integer;
+extern crate num_traits;
+
+macro_rules! test_average {
+ ($I:ident, $U:ident) => {
+ mod $I {
+ mod ceil {
+ use num_integer::Average;
+
+ #[test]
+ fn same_sign() {
+ assert_eq!((14 as $I).average_ceil(&16), 15 as $I);
+ assert_eq!((14 as $I).average_ceil(&17), 16 as $I);
+
+ let max = $crate::std::$I::MAX;
+ assert_eq!((max - 3).average_ceil(&(max - 1)), max - 2);
+ assert_eq!((max - 3).average_ceil(&(max - 2)), max - 2);
+ }
+
+ #[test]
+ fn different_sign() {
+ assert_eq!((14 as $I).average_ceil(&-4), 5 as $I);
+ assert_eq!((14 as $I).average_ceil(&-5), 5 as $I);
+
+ let min = $crate::std::$I::MIN;
+ let max = $crate::std::$I::MAX;
+ assert_eq!(min.average_ceil(&max), 0 as $I);
+ }
+ }
+
+ mod floor {
+ use num_integer::Average;
+
+ #[test]
+ fn same_sign() {
+ assert_eq!((14 as $I).average_floor(&16), 15 as $I);
+ assert_eq!((14 as $I).average_floor(&17), 15 as $I);
+
+ let max = $crate::std::$I::MAX;
+ assert_eq!((max - 3).average_floor(&(max - 1)), max - 2);
+ assert_eq!((max - 3).average_floor(&(max - 2)), max - 3);
+ }
+
+ #[test]
+ fn different_sign() {
+ assert_eq!((14 as $I).average_floor(&-4), 5 as $I);
+ assert_eq!((14 as $I).average_floor(&-5), 4 as $I);
+
+ let min = $crate::std::$I::MIN;
+ let max = $crate::std::$I::MAX;
+ assert_eq!(min.average_floor(&max), -1 as $I);
+ }
+ }
+ }
+
+ mod $U {
+ mod ceil {
+ use num_integer::Average;
+
+ #[test]
+ fn bounded() {
+ assert_eq!((14 as $U).average_ceil(&16), 15 as $U);
+ assert_eq!((14 as $U).average_ceil(&17), 16 as $U);
+ }
+
+ #[test]
+ fn overflow() {
+ let max = $crate::std::$U::MAX;
+ assert_eq!((max - 3).average_ceil(&(max - 1)), max - 2);
+ assert_eq!((max - 3).average_ceil(&(max - 2)), max - 2);
+ }
+ }
+
+ mod floor {
+ use num_integer::Average;
+
+ #[test]
+ fn bounded() {
+ assert_eq!((14 as $U).average_floor(&16), 15 as $U);
+ assert_eq!((14 as $U).average_floor(&17), 15 as $U);
+ }
+
+ #[test]
+ fn overflow() {
+ let max = $crate::std::$U::MAX;
+ assert_eq!((max - 3).average_floor(&(max - 1)), max - 2);
+ assert_eq!((max - 3).average_floor(&(max - 2)), max - 3);
+ }
+ }
+ }
+ };
+}
+
+test_average!(i8, u8);
+test_average!(i16, u16);
+test_average!(i32, u32);
+test_average!(i64, u64);
+#[cfg(has_i128)]
+test_average!(i128, u128);
+test_average!(isize, usize);
diff --git a/tests/roots.rs b/tests/roots.rs
new file mode 100644
index 0000000..f85f9e0
--- /dev/null
+++ b/tests/roots.rs
@@ -0,0 +1,272 @@
+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);