use crate::natural::Natural;
use crate::platform::Limb;
use malachite_base::num::arithmetic::traits::{CheckedSub, OverflowingSubAssign};
use std::fmt::Display;
use std::ops::{Sub, SubAssign};
pub_crate_test! {limbs_sub_limb(xs: &[Limb], mut y: Limb) -> (Vec<Limb>, bool) {
let len = xs.len();
let mut out = Vec::with_capacity(len);
for i in 0..len {
let (diff, overflow) = xs[i].overflowing_sub(y);
out.push(diff);
if overflow {
y = 1;
} else {
y = 0;
out.extend_from_slice(&xs[i + 1..]);
break;
}
}
(out, y != 0)
}}
pub_crate_test! {limbs_sub_limb_to_out(out: &mut [Limb], xs: &[Limb], mut y: Limb) -> bool {
let len = xs.len();
assert!(out.len() >= len);
for i in 0..len {
let overflow;
(out[i], overflow) = xs[i].overflowing_sub(y);
if overflow {
y = 1;
} else {
y = 0;
let copy_index = i + 1;
out[copy_index..len].copy_from_slice(&xs[copy_index..]);
break;
}
}
y != 0
}}
pub_crate_test! {limbs_sub_limb_in_place(xs: &mut [Limb], mut y: Limb) -> bool {
for x in xs.iter_mut() {
if x.overflowing_sub_assign(y) {
y = 1;
} else {
return false;
}
}
y != 0
}}
fn sub_and_borrow(x: Limb, y: Limb, borrow: &mut bool) -> Limb {
let b = *borrow;
let mut diff;
(diff, *borrow) = x.overflowing_sub(y);
if b {
*borrow |= diff.overflowing_sub_assign(1);
}
diff
}
pub_crate_test! {limbs_sub(xs: &[Limb], ys: &[Limb]) -> (Vec<Limb>, bool) {
let xs_len = xs.len();
let ys_len = ys.len();
assert!(xs_len >= ys_len);
let mut out = Vec::with_capacity(xs_len);
let mut borrow = false;
for (&x, &y) in xs.iter().zip(ys.iter()) {
out.push(sub_and_borrow(x, y, &mut borrow));
}
if xs_len != ys_len {
out.extend_from_slice(&xs[ys_len..]);
if borrow {
borrow = limbs_sub_limb_in_place(&mut out[ys_len..], 1);
}
}
(out, borrow)
}}
pub_crate_test! {limbs_sub_same_length_to_out(out: &mut [Limb], xs: &[Limb], ys: &[Limb]) -> bool {
let len = xs.len();
assert_eq!(len, ys.len());
assert!(out.len() >= len);
let mut borrow = false;
for (out, (&x, &y)) in out.iter_mut().zip(xs.iter().zip(ys.iter())) {
*out = sub_and_borrow(x, y, &mut borrow);
}
borrow
}}
pub_crate_test! {limbs_sub_greater_to_out(out: &mut [Limb], xs: &[Limb], ys: &[Limb]) -> bool {
let xs_len = xs.len();
let ys_len = ys.len();
assert!(out.len() >= xs_len);
let (xs_lo, xs_hi) = xs.split_at(ys_len);
let borrow = limbs_sub_same_length_to_out(out, xs_lo, ys);
if xs_len == ys_len {
borrow
} else if borrow {
limbs_sub_limb_to_out(&mut out[ys_len..], xs_hi, 1)
} else {
out[ys_len..xs_len].copy_from_slice(xs_hi);
false
}
}}
pub_crate_test! {limbs_sub_same_length_in_place_left(xs: &mut [Limb], ys: &[Limb]) -> bool {
assert_eq!(xs.len(), ys.len());
let mut borrow = false;
for (x, &y) in xs.iter_mut().zip(ys.iter()) {
*x = sub_and_borrow(*x, y, &mut borrow);
}
borrow
}}
pub_crate_test! {limbs_sub_greater_in_place_left(xs: &mut [Limb], ys: &[Limb]) -> bool {
let xs_len = xs.len();
let ys_len = ys.len();
let (xs_lo, xs_hi) = xs.split_at_mut(ys_len);
let borrow = limbs_sub_same_length_in_place_left(xs_lo, ys);
if xs_len == ys_len {
borrow
} else if borrow {
limbs_sub_limb_in_place(xs_hi, 1)
} else {
false
}
}}
pub_crate_test! {limbs_sub_same_length_in_place_right(xs: &[Limb], ys: &mut [Limb]) -> bool {
assert_eq!(xs.len(), ys.len());
let mut borrow = false;
for (&x, y) in xs.iter().zip(ys.iter_mut()) {
*y = sub_and_borrow(x, *y, &mut borrow);
}
borrow
}}
pub_crate_test! {limbs_slice_sub_in_place_right(xs: &[Limb], ys: &mut [Limb], len: usize) -> bool {
let xs_len = xs.len();
assert_eq!(xs_len, ys.len());
let (xs_lo, xs_hi) = xs.split_at(len);
let (ys_lo, ys_hi) = ys.split_at_mut(len);
let borrow = limbs_sub_same_length_in_place_right(xs_lo, ys_lo);
if xs_len == len {
borrow
} else if borrow {
limbs_sub_limb_to_out(ys_hi, xs_hi, 1)
} else {
ys_hi.copy_from_slice(xs_hi);
false
}
}}
pub_crate_test! {limbs_vec_sub_in_place_right(xs: &[Limb], ys: &mut Vec<Limb>) -> bool {
let xs_len = xs.len();
let ys_len = ys.len();
assert!(xs_len >= ys_len);
let (xs_lo, xs_hi) = xs.split_at(ys_len);
let borrow = limbs_sub_same_length_in_place_right(xs_lo, ys);
if xs_len == ys_len {
borrow
} else {
ys.extend_from_slice(xs_hi);
if borrow {
limbs_sub_limb_in_place(&mut ys[ys_len..], 1)
} else {
false
}
}
}}
pub_crate_test! {limbs_sub_same_length_in_place_with_overlap(
xs: &mut [Limb],
right_start: usize
) -> bool {
let len = xs.len() - right_start;
let mut borrow = false;
for i in 0..len {
xs[i] = sub_and_borrow(xs[i], xs[i + right_start], &mut borrow);
}
borrow
}}
pub_crate_test! {limbs_sub_same_length_to_out_with_overlap(xs: &mut [Limb], ys: &[Limb]) -> bool {
let xs_len = xs.len();
let ys_len = ys.len();
assert!(xs_len >= ys_len);
let right_start = xs_len - ys_len;
let mut borrow = false;
for i in 0..ys_len {
xs[i] = sub_and_borrow(xs[i + right_start], ys[i], &mut borrow);
}
borrow
}}
pub_crate_test! {limbs_sub_same_length_with_borrow_in_to_out(
out: &mut [Limb],
xs: &[Limb],
ys: &[Limb],
borrow_in: bool,
) -> bool {
let mut borrow = limbs_sub_same_length_to_out(out, xs, ys);
if borrow_in {
borrow |= limbs_sub_limb_in_place(&mut out[..xs.len()], 1);
}
borrow
}}
pub_crate_test! {limbs_sub_same_length_with_borrow_in_in_place_left(
xs: &mut [Limb],
ys: &[Limb],
borrow_in: bool,
) -> bool {
let mut borrow = limbs_sub_same_length_in_place_left(xs, ys);
if borrow_in {
borrow |= limbs_sub_limb_in_place(xs, 1);
}
borrow
}}
pub_crate_test! {limbs_sub_same_length_with_borrow_in_in_place_right(
xs: &[Limb],
ys: &mut [Limb],
borrow_in: bool,
) -> bool {
let mut borrow = limbs_sub_same_length_in_place_right(xs, ys);
if borrow_in {
borrow |= limbs_sub_limb_in_place(ys, 1);
}
borrow
}}
fn sub_panic<S: Display, T: Display>(x: S, y: T) -> ! {
panic!(
"Cannot subtract a number from a smaller number. self: {}, other: {}",
x, y
);
}
impl Natural {
pub(crate) fn sub_limb(self, other: Limb) -> Natural {
self.checked_sub_limb(other)
.expect("Cannot subtract a Limb from a smaller Natural")
}
pub(crate) fn sub_limb_ref(&self, other: Limb) -> Natural {
self.checked_sub_limb_ref(other).unwrap_or_else(|| {
sub_panic(self, other);
})
}
}
impl Sub<Natural> for Natural {
type Output = Natural;
fn sub(self, other: Natural) -> Natural {
self.checked_sub(other)
.expect("Cannot subtract a Natural from a smaller Natural")
}
}
impl<'a> Sub<&'a Natural> for Natural {
type Output = Natural;
fn sub(self, other: &'a Natural) -> Natural {
self.checked_sub(other)
.expect("Cannot subtract a Natural from a smaller Natural")
}
}
impl<'a> Sub<Natural> for &'a Natural {
type Output = Natural;
fn sub(self, other: Natural) -> Natural {
self.checked_sub(other)
.expect("Cannot subtract a Natural from a smaller Natural")
}
}
impl<'a, 'b> Sub<&'a Natural> for &'b Natural {
type Output = Natural;
fn sub(self, other: &'a Natural) -> Natural {
self.checked_sub(other).unwrap_or_else(|| {
sub_panic(self, other);
})
}
}
impl SubAssign<Natural> for Natural {
fn sub_assign(&mut self, other: Natural) {
if self.sub_assign_no_panic(other) {
panic!("Cannot subtract a Natural from a smaller Natural");
}
}
}
impl<'a> SubAssign<&'a Natural> for Natural {
fn sub_assign(&mut self, other: &'a Natural) {
if self.sub_assign_ref_no_panic(other) {
panic!("Cannot subtract a Natural from a smaller Natural");
}
}
}