binary_search.rs

use num::traits::{Num, NumOps};
use std::cmp::Ordering;

fn binary_search<T, F>(lower_bound: T, upper_bound: T, f: F) -> Result<T, T>
where
    T: Copy + PartialOrd + Num + NumOps,
    F: Fn(T) -> Ordering,
{
    let mut size = upper_bound;
    let mut left = lower_bound;
    let mut right = upper_bound;
    let two = T::one() + T::one();

    while left < right {
        let mid = left + size / two;
        let cmp = f(mid);
        match cmp {
            Ordering::Less => {
                left = mid + T::one();
            }
            Ordering::Equal => return Ok(mid),
            Ordering::Greater => {
                right = mid;
            }
        }
        size = right - left;
    }
    Err(left)
}

fn partition_point<T, F>(lower_bound: T, upper_bound: T, pred: F) -> T
where
    T: Copy + PartialOrd + Num + NumOps,
    F: Fn(T) -> bool,
{
    binary_search(lower_bound, upper_bound, |x| {
        if pred(x) {
            Ordering::Less
        } else {
            Ordering::Greater
        }
    })
    .unwrap_or_else(|i| i)
}

fn ln_ceil(input: u64) -> u64 {
    (input as f64).ln().ceil() as u64
}

fn main() {
    // Find the expontent of the last value in the search space, so we can find the smallest argument to receive given exponent in ceil(ln(argument)).
    let all_exponents = ln_ceil(u64::MAX);

    let mut table = Vec::new();
    for exponent in 0..=all_exponents {
        // Partition the search space for elements smaller than the exponent, and greater than the exponent.
        let argument = partition_point(1, u64::MAX, |argument| ln_ceil(argument) < exponent);
        table.push(argument);
    }

    // Verify each exponent is the smallest one for given argument.
    assert_eq!(ln_ceil(table[0]) as usize, 0);
    assert_eq!(ln_ceil(table[1]) as usize, 1);

    for (exponent, argument) in table.iter().enumerate().skip(2) {
        assert_eq!(ln_ceil(*argument) as usize, exponent);
        assert_eq!(ln_ceil(*argument - 1) as usize, exponent - 1);
        assert_eq!(ln_ceil(*argument + 1) as usize, exponent);
    }

    println!("const LN_CEIL_LOOKUP_TABLE: &[usize] = &[");
    for argument in table {
        println!("  {argument},");
    }
    println!("];");
}