Range is not inclusive. Not possible to generate Type::MAX values
rfdonnelly opened this issue · 5 comments
Problem
Range is consistent with Rust ranges but this makes it impossible to generate <T>::max_value() samples without special cases.
Possible Solution
Implement a RangeInclusive
Implementations
I see two ways of implementing a RangeInclusive:
- Implement using the existing exclusive
Range - Implement from scratch similar to the
uniform_int_distributionfrom the C++ standard library.
Option 2 is likely the best performance wise. In the meantime, I've implemented Option 1 for u32.
Implementing RangeInclusive using Range
I've included the details for implementing Option 1 here only to show how obtuse it is and to illustrate why something like C++'s uniform_int_distribution is needed.
Implementing Option 1 requires three cases:
-
The range [MIN, MAX]
Not possible to generate using
Range. Use RNG directly. -
The range [x, MAX] where x > 0
Implement using
Range[x - 1, MAX) then add 1. -
The range [x, y] where y < MAX
Implement using
Range[x, y + 1)
Source for Option 1
use rand::Rng;
use rand::distributions::Range;
use rand::distributions::Sample;
use rand::distributions::IndependentSample;
pub struct RangeInclusive {
range: Range<u32>,
use_range: bool,
offset: bool,
}
impl RangeInclusive {
fn new(low: u32, high: u32) -> RangeInclusive {
// Implement the inclusive range [x, y] using the exlusive range [x, y + 1) by handling
// three different cases:
//
// * The range [::std::u32::MIN, ::std::u32::MAX]
//
// Cannot use rand::distributions::Range. Use RNG directly.
//
// [x, y] => [x, y]
//
// * The range [x, ::std::u32::MAX]
//
// Can use rand::distributions::Range but must adjust the range down artifically, then
// re-adjust up after sampling.
//
// [x, y] => [x - 1, y) + 1
//
// * All other ranges
//
// Use rand::distributions::Range normally.
//
// [x, y] => [x, y + 1)
let (x, y, use_range, offset) = match (low, high) {
// Sample directly from RNG w/o Range
(::std::u32::MIN, ::std::u32::MAX) => (::std::u32::MIN, ::std::u32::MAX, false, false),
// Sample with Range + offset
(x, ::std::u32::MAX) => (x - 1, ::std::u32::MAX, true, true),
// Sample with Range normally
(x, y) => (x, y + 1, true, false)
};
RangeInclusive {
offset: offset,
use_range: use_range,
range: Range::new(x, y),
}
}
}
impl IndependentSample<u32> for RangeInclusive {
fn ind_sample<R: Rng>(&self, rng: &mut R) -> u32 {
// Should never see this case. Could cause a panic due to overflow.
assert!(!(self.use_range == false && self.offset == true));
let sample =
if self.use_range {
self.range.ind_sample(rng)
} else {
rng.gen()
};
if self.offset {
sample + 1
} else {
sample
}
}
}
impl Sample<u32> for RangeInclusive {
fn sample<R: Rng>(&mut self, rng: &mut R) -> u32 {
self.ind_sample(rng)
}
} Wow, a lot of work. @pitdicker already implemented this, it's just that this is part of a major refactor we haven't tried to merge yet.
Awesome! I'm looking forward to it. Thank you for your work on this crate.
Note that this does not work for floats yet.