In generics, is it possible to add 1 if integer or 0.1 if float?-CodePudding

I have this generics where Num is defined in num crate:

//finds `x` where `f(x) == Equal` for `x ∈ [left, right)`
fn binary_search<T: Debug   Copy   PartialOrd   Num, F: FnMut(T) -> Ordering>(
    mut left: T,
    mut right: T, //exclusive
    mut f: F,
) -> Result<T, T> {
    while (left < right) {
        let mid = left   (right - left) / (T::one()   T::one());
        match f(mid) {
            Less => left = mid   T::one(),
            Greater => right = mid,
            Equal => return Ok(mid),
        }
    }
    Err(left)
}

This binary search works correctly for integer types but NOT for float types (like f64). The evil part is this:

Less => left = mid   T::one(),

The T::one() should instead be 1e-6 for float and 1 for integer. Is it possible?

Here's the Rust Playground with some automated tests available. I want to make binary_search_02() pass without breaking binary_search_01().

CodePudding user response：

The Less and Greater arms aren't symmetrical, which is why you have to adjust the midpoint in one but not the other. You can fix it by making both endpoints inclusive. Then there's no need to nudge the midpoint.

pub fn binary_search<
    T: Debug   Copy   PartialOrd   Num,
    F: FnMut(T) -> Ordering,
>(
    mut left: T,  // inclusive
    mut right: T, // inclusive
    mut f: F,
) -> Result<T, T> {
    loop {
        let mid = left   (right - left) / (T::one()   T::one());
        match f(mid) {
            Less => {
                if left == mid {
                    break;
                }
                left = mid;
            }
            Greater => {
                if right == mid {
                    break;
                }
                right = mid;
            }
            Equal => return Ok(mid),
        }
    }
    Err(right)
}

Playground

Note that I changed the final return value to Err(right) to get the tests to pass. I'm not sure if that's correct? You can play with it if it isn't.

CodePudding user response：

You can use num::FromPrimitive trait where some conversion methods are defined:

pub trait FromPrimitive {
    pub fn from_i64(n: i64) -> Option<Self>;
    pub fn from_u64(n: u64) -> Option<Self>;
    /* snip */
    pub fn from_f32(n: f32) -> Option<Self> { ... }
    pub fn from_f64(n: f64) -> Option<Self> { ... }
}

So define delta as

let delta = {
    let delta = T::from_f64(1e-9).unwrap();
    if (delta == T::zero()) { //if integer types
        T::one()
    } else { //if float types
        delta
    }
};

and add it instead of T::one()

Less => left = mid   delta,

The final code is this, making all the tests pass:

fn binary_search<
    T: fmt::Debug   Copy   cmp::PartialOrd   Num   FromPrimitive,
    F: FnMut(T) -> Ordering,
>(
    mut left: T,
    mut right: T, //exclusive
    mut f: F,
) -> Result<T, T> {
    let delta = {
        let delta = T::from_f64(1e-9).unwrap();
        if (delta == T::zero()) {
            T::one()
        } else {
            delta
        }
    };
    while (left < right) {
        let mid = left   (right - left) / (T::one()   T::one());
        match f(mid) {
            Less => left = mid   delta,
            Greater => right = mid,
            Equal => return Ok(mid),
        }
    }
    Err(left)
}