weighted_selection.rs

use rand::Rng;

/// You have an array of items. Each item is an unsigned 32-bit integer.
/// The value of each item determines its weight.
/// Higher the weight, higher the chance of rolling it.

/// This algorithm uses a simple approach.
/// Keep moving in a straight line till your weights sum up to (or get reduced to)
/// a weight less than a single item's weight. Return the index of the result.

pub fn roll_with_linear_search(items: &[u32], total_chance: usize) -> u32 {
    let mut rng = rand::thread_rng().gen_range(0..total_chance) as u32;
    for x in 0..items.len() {
        if rng < (items[x] as u32) {
            return x as u32;
        }
        rng -= items[x] as u32;
    }
    return 0;
}

                          
/// You have an array of items. Each item is an unsigned 32-bit integer.
/// The value of the first item determines its weight. The weight of the
/// second item is the value of the second item minus that of the previous item.

/// This algorithm uses a more complex approach, where the weights are added
/// cumulatively. Such a structure helps with faster rolling since it makes it
/// easier to use binary search. When it finds a match, it returns the index
/// of the result.
                          
#[no_mangle]
pub fn roll_with_binary_search(items: &[u32], total_chance: usize) -> u32 {
    let rng = rand::thread_rng().gen_range(0..total_chance) as u32;
    let mut min = 0;
    let mut max = items.len() - 1;
    let mut mid = (min + max) / 2;

    while min <= max && mid != 0 {
        if (items[mid] > rng && items[mid - 1] < rng) || items[mid] == rng {
            return mid as u32;
        }
        if items[mid] < rng {
            min = mid + 1;
            mid = (max + min) / 2;
        } else {
            max = mid - 1;
            mid = (max + min) / 2;
        }
    }
    return mid as u32;
}