Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Range is not inclusive. Not possible to generate Type::MAX values #188

Closed
rfdonnelly opened this issue Oct 26, 2017 · 5 comments
Closed

Comments

@rfdonnelly
Copy link
Contributor

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:

  1. Implement using the existing exclusive Range
  2. Implement from scratch similar to the uniform_int_distribution from 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:

  1. The range [MIN, MAX]

    Not possible to generate using Range. Use RNG directly.

  2. The range [x, MAX] where x > 0

    Implement using Range [x - 1, MAX) then add 1.

  3. 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)                                                                                                                                                                                                                                
    }                                                                                                                                                                                                                                                       
} 
@dhardy
Copy link
Member

dhardy commented Oct 26, 2017

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.

@rfdonnelly
Copy link
Contributor Author

Awesome! I'm looking forward to it. Thank you for your work on this crate.

rfdonnelly added a commit to rfdonnelly/rvs that referenced this issue Nov 11, 2017
* Fixes unable to use Rng trait object with range::sample

  rust-random/rand#190

* Adds support for inclusive range

  Replace rvs's own RangeInclusive with rand's new Range::new_inclusive

  rust-random/rand#188
@pitdicker
Copy link
Contributor

Since #274 available as Range::new_inclusive.

@vks
Copy link
Collaborator

vks commented Apr 12, 2018

Note that this does not work for floats yet.

@dhardy
Copy link
Member

dhardy commented Apr 12, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

4 participants