#[derive(Debug, Clone, Copy, PartialEq, Eq, thiserror::Error)]
#[error("integer overflow computing {what}")]
#[non_exhaustive]
pub struct Overflow {
pub what: &'static str,
}
impl Overflow {
#[must_use]
pub const fn new(what: &'static str) -> Self {
Self { what }
}
}
pub type Cost = i64;
pub type Capacity = i64;
pub type Flow = i64;
pub type Price = i64;
pub type Objective = i128;
#[inline]
pub(crate) fn add(a: i64, b: i64, what: &'static str) -> Result<i64, Overflow> {
a.checked_add(b).ok_or(Overflow::new(what))
}
#[inline]
pub(crate) fn sub(a: i64, b: i64, what: &'static str) -> Result<i64, Overflow> {
a.checked_sub(b).ok_or(Overflow::new(what))
}
#[inline]
pub(crate) fn mul(a: i64, b: i64, what: &'static str) -> Result<i64, Overflow> {
a.checked_mul(b).ok_or(Overflow::new(what))
}
#[inline]
pub(crate) fn neg(a: i64, what: &'static str) -> Result<i64, Overflow> {
a.checked_neg().ok_or(Overflow::new(what))
}
#[inline]
pub(crate) fn add_i128(a: i128, b: i128, what: &'static str) -> Result<i128, Overflow> {
a.checked_add(b).ok_or(Overflow::new(what))
}
#[inline]
pub(crate) fn mul_i128(a: i128, b: i128, what: &'static str) -> Result<i128, Overflow> {
a.checked_mul(b).ok_or(Overflow::new(what))
}
#[inline]
pub(crate) fn reduced_cost(
cost: Cost,
price_tail: Price,
price_head: Price,
) -> Result<Cost, Overflow> {
let t = sub(cost, price_tail, "reduced cost")?;
add(t, price_head, "reduced cost")
}
#[inline]
pub(crate) const fn gcd(mut a: u128, mut b: u128) -> u128 {
while b != 0 {
let t = a % b;
a = b;
b = t;
}
a
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn checked_ops_report_the_quantity_that_overflowed() {
assert_eq!(add(i64::MAX, 1, "q"), Err(Overflow::new("q")));
assert_eq!(sub(i64::MIN, 1, "q"), Err(Overflow::new("q")));
assert_eq!(mul(i64::MAX, 2, "q"), Err(Overflow::new("q")));
assert_eq!(neg(i64::MIN, "q"), Err(Overflow::new("q")));
}
#[test]
fn checked_ops_pass_values_through_at_the_type_bounds() {
assert_eq!(add(i64::MAX - 1, 1, "q"), Ok(i64::MAX));
assert_eq!(sub(i64::MIN + 1, 1, "q"), Ok(i64::MIN));
assert_eq!(mul(i64::MIN / 2, 2, "q"), Ok(i64::MIN));
assert_eq!(neg(i64::MIN + 1, "q"), Ok(i64::MAX));
}
#[test]
fn reduced_cost_follows_the_declared_convention() {
assert_eq!(reduced_cost(10, 3, 1), Ok(8));
assert_eq!(reduced_cost(10, 1, 3), Ok(12));
assert_eq!(reduced_cost(0, 5, 5), Ok(0));
assert_eq!(
reduced_cost(1, i64::MIN, 0),
Err(Overflow::new("reduced cost"))
);
}
#[test]
fn gcd_normalises_rationals() {
assert_eq!(gcd(12, 18), 6);
assert_eq!(gcd(7, 13), 1);
assert_eq!(gcd(0, 5), 5);
assert_eq!(gcd(5, 0), 5);
}
}