CODEWITHSUNDEEP
rust
Erlich
Erlich

Reputation: 345

Finding the maximum allowable value for generic type T

I am implementing a merge sort which will sort an array of type T. In my merge method, the algorithm calls for the the last element of the left and right list be positive infinity. How can I get the maximum value a given data type can hold?

fn merge<T: PartialOrd + Copy + std::fmt::Debug>(p: usize, q: usize, r: usize, array: &mut Vec<T>) {
    let left_size: usize = q - p;
    let right_size: usize = r - q;

    let mut left: Vec<T> = Vec::new();
    let mut right: Vec<T> = Vec::new();

    for i in 0..left_size {
        left.push(array[p + i]);
    }

    for i in 0..right_size {
        right.push(array[q + i]);
    }

    left.push(T::max_value()); //where I would put the max value
    right.push(T::max_value()); //where I would put the max value

    let mut i: usize = 0;
    let mut j: usize = 0;

    for k in p..r {
        if left[i] <= right[j] {
            array[k] = left[i];
            i += 1;
        } else {
            array[k] = right[j];
            j += 1;
        }
    }
}

Upvotes: 8

Views: 1617

Answers (2)

Stefan
Stefan

Reputation: 5530

For a generic upper bound you could also wrap the type in an enum:

#[derive(Clone, Copy, PartialEq, PartialOrd, Debug)]
enum UpperBounded<T> {
    Value(T),
    Max,
}

The derived order is documented to sort Value(_) before Max.

UpperBounded<T> can then be used for the left and right vectors.

Upvotes: 1

StarSheriff
StarSheriff

Reputation: 1637

As far as I know, there is no way of doing that with the standard library at this time. One way to solve it would be make your own trait, add another trait bound to merge and implement your trait for the types you are expecting.

The specific trait implementation for u32 would then return std::u32::MAX and so on for the other types.

Here is a discussion from earlier this year.

As oli_obk - ker pointed out below, the num crate already has such a trait: Bounded.

Upvotes: 5

Related Questions