ozzy-journal 0.7.0

//! Bounded metadata computation shared by state and storage codecs.
//! Callers supply scheduling; this module performs no I/O or clock reads.

use std::cmp::Ordering;

/// Sort in place with constant scratch space. Each callback follows at most
/// two comparisons and one swap, reporting a conservative byte-work charge.
/// The callback may yield or remain ready. Cancellation leaves a permutation;
/// callers must keep partially sorted metadata private until validation ends.
pub async fn sort_by<T>(
    values: &mut [T],
    compare: fn(&T, &T) -> Ordering,
    step: &mut impl AsyncFnMut(usize),
) {
    for root in (0..values.len() / 2).rev() {
        sift_down(values, root, compare, step).await;
    }
    for end in (1..values.len()).rev() {
        values.swap(0, end);
        step(size_of::<T>().saturating_mul(2)).await;
        if let Some(heap) = values.get_mut(..end) {
            sift_down(heap, 0, compare, step).await;
        }
    }
}

async fn sift_down<T>(
    values: &mut [T],
    mut root: usize,
    compare: fn(&T, &T) -> Ordering,
    step: &mut impl AsyncFnMut(usize),
) {
    while let Some(left) = root.checked_mul(2).and_then(|value| value.checked_add(1)) {
        let Some(left_value) = values.get(left) else {
            break;
        };
        let child = match values.get(left + 1) {
            Some(right) if compare(left_value, right) == Ordering::Less => left + 1,
            _ => left,
        };
        let (Some(parent), Some(larger)) = (values.get(root), values.get(child)) else {
            break;
        };
        let ordered = compare(parent, larger) != Ordering::Less;
        if !ordered {
            values.swap(root, child);
            root = child;
        }
        step(size_of::<T>().saturating_mul(4)).await;
        if ordered {
            break;
        }
    }
}