fn quantile_function<const PRECISION: usize>(
        &self,
        quantile: Probability,
    ) -> (Symbol, Probability, Probability::NonZero) {
        assert!(PRECISION <= Probability::BITS);
        let max_probability = Probability::max_value() >> (Probability::BITS - PRECISION);
        assert!(quantile <= max_probability);

        let mut left = 0; // Smallest possible index.
        let mut right = self.support_size(); // One above largest possible index.

        // Bisect the symbol table to find the last entry whose left-sided cumulative is
        // `<= quantile`, exploiting the following facts:
        // - `self.as_ref.len() >= 2` (therefore, `left < right` initially)
        // - `cdf[0] == 0` (where `cdf[n] = self.left_cumulative_unchecked(n).0`)
        // - `quantile <= max_probability` (if this is violated then the method is still
        //   memory safe but will return the last bin; thus, memory safety doesn't hinge on
        //   `PRECISION` being correct).
        // - `cdf[self.as_ref().len() - 1] == max_probability.wrapping_add(1)`
        // - `cdf` is monotonically increasing except that it may wrap around only at the
        //   last entry (this happens iff `PRECISION == Probability::BITS`).
        //
        // The loop maintains the following two invariants:
        // (1) `0 <= left <= mid < right < self.as_ref().len()`
        // (2) `cdf[left] <= cdf[mid]`
        // (3) `cdf[mid] <= cdf[right]` unless `right == cdf.len() - 1`
        while left + 1 != right {
            let mid = (left + right) / 2;

            // SAFETY: safe by invariant (1)
            let pivot = unsafe { self.left_cumulative_unchecked(mid) };
            if pivot <= quantile {
                // Since `mid < right` and wrapping can occur only at the last entry,
                // `pivot` has not yet wrapped around
                left = mid;
            } else {
                right = mid;
            }
        }

        // SAFETY: invariant `0 <= left < right < self.as_ref().len()` still holds.
        let cdf = unsafe { self.left_cumulative_unchecked(left) };
        let symbol = unsafe { self.symbol_unchecked(left) };
        let next_cdf = unsafe { self.left_cumulative_unchecked(right) };

        let probability = unsafe {
            // SAFETY: The constructor ensures that all probabilities within bounds are
            // nonzero. (TODO)
            next_cdf.wrapping_sub(&cdf).into_nonzero_unchecked()
        };

        (symbol, cdf, probability)
    }
/// Bisects the symbol table to find the bin that contains `quantile`.
Bisects the symbol table to find the bin that contains `quantile`.
Bisects the symbol table to find the bin that contains ` quantile ` .
fn quantile_function<const PRECISION: usize>(
        &self,
        quantile: Probability,
    ) -> (Symbol, Probability, Probability::NonZero) {
        assert!(PRECISION <= Probability::BITS);
        let max_probability = Probability::max_value() >> (Probability::BITS - PRECISION);
        assert!(quantile <= max_probability);
        let mut left = 0; // Smallest possible index.
        let mut right = self.support_size(); // One above largest possible index.
        // Bisect the symbol table to find the last entry whose left-sided cumulative is
        // `<= quantile`, exploiting the following facts:
        // - `self.as_ref.len() >= 2` (therefore, `left < right` initially)
        // - `cdf[0] == 0` (where `cdf[n] = self.left_cumulative_unchecked(n).0`)
        // - `quantile <= max_probability` (if this is violated then the method is still
        //   memory safe but will return the last bin; thus, memory safety doesn't hinge on
        //   `PRECISION` being correct).
        // - `cdf[self.as_ref().len() - 1] == max_probability.wrapping_add(1)`
        // - `cdf` is monotonically increasing except that it may wrap around only at the
        //   last entry (this happens iff `PRECISION == Probability::BITS`).
        //
        // The loop maintains the following two invariants:
        // (1) `0 <= left <= mid < right < self.as_ref().len()`
        // (2) `cdf[left] <= cdf[mid]`
        // (3) `cdf[mid] <= cdf[right]` unless `right == cdf.len() - 1`
        while left + 1 != right {
            let mid = (left + right) / 2;
            // SAFETY: safe by invariant (1)
            let pivot = unsafe { self.left_cumulative_unchecked(mid) };
            if pivot <= quantile {
                // Since `mid < right` and wrapping can occur only at the last entry,
                // `pivot` has not yet wrapped around
                left = mid;
            } else {
                right = mid;
            }
        }
        // SAFETY: invariant `0 <= left < right < self.as_ref().len()` still holds.
        let cdf = unsafe { self.left_cumulative_unchecked(left) };
        let symbol = unsafe { self.symbol_unchecked(left) };
        let next_cdf = unsafe { self.left_cumulative_unchecked(right) };
        let probability = unsafe {
            // SAFETY: The constructor ensures that all probabilities within bounds are
            // nonzero. (TODO)
            next_cdf.wrapping_sub(&cdf).into_nonzero_unchecked()
        };
        (symbol, cdf, probability)
    }
fn quantile_function < const PRECISION : usize > ( & self , quantile : Probability , ) -> ( Symbol , Probability , Probability :: NonZero ) { assert ! ( PRECISION Probability BITS ) ; let max_probability = Probability :: max_value ( ) >> ( Probability :: BITS - PRECISION ) ; assert ! ( quantile max_probability ) ; let mut left = 0 ; // Smallest possible index. let mut right = self . support_size ( ) ; // One above largest possible index. // Bisect the symbol table to find the last entry whose left-sided cumulative is // `<= quantile`, exploiting the following facts: // - `self.as_ref.len() >= 2` (therefore, `left < right` initially) // - `cdf[0] == 0` (where `cdf[n] = self.left_cumulative_unchecked(n).0`) // - `quantile <= max_probability` (if this is violated then the method is still //   memory safe but will return the last bin; thus, memory safety doesn't hinge on //   `PRECISION` being correct). // - `cdf[self.as_ref().len() - 1] == max_probability.wrapping_add(1)` // - `cdf` is monotonically increasing except that it may wrap around only at the //   last entry (this happens iff `PRECISION == Probability::BITS`). // // The loop maintains the following two invariants: // (1) `0 <= left <= mid < right < self.as_ref().len()` // (2) `cdf[left] <= cdf[mid]` // (3) `cdf[mid] <= cdf[right]` unless `right == cdf.len() - 1` while left + 1 != right { let mid = ( left + right ) / 2 ; // SAFETY: safe by invariant (1) let pivot = unsafe { self . left_cumulative_unchecked ( mid ) } ; if pivot <= quantile { // Since `mid < right` and wrapping can occur only at the last entry, // `pivot` has not yet wrapped around left = mid ; } else { right = mid ; } } // SAFETY: invariant `0 <= left < right < self.as_ref().len()` still holds. let cdf = unsafe { self . left_cumulative_unchecked ( left ) } ; let symbol = unsafe { self . symbol_unchecked ( left ) } ; let next_cdf = unsafe { self . left_cumulative_unchecked ( right ) } ; let probability = unsafe { // SAFETY: The constructor ensures that all probabilities within bounds are // nonzero. (TODO) next_cdf . wrapping_sub ( & cdf ) . into_nonzero_unchecked ( ) } ; ( symbol , cdf , probability ) }
Bisects the symbol table to find the bin that contains `quantile`.
Bisects the symbol table to find the bin that contains ` quantile ` .
&self
quantile
Probability
&self
quantile
Probability