uqa_core/
ordering.rs

1//
2// Unified Query Algebra
3//
4// Copyright (c) 2023-2026 Cognica, Inc.
5//
6
7//! Fallible in-place ordering with bounded cancellation checks and no scratch allocation.
8
9use std::cmp::Ordering;
10
11/// Order a mutable slice without scratch allocation, forwarding cancellation and comparison failures.
12///
13/// The sort is unstable. A failure preserves every element but may leave the order partially changed; retained allocation guards stay attached to their elements. Long element comparisons must check the supplied callback themselves.
14pub fn sort_by_with_control<T, E>(
15    values: &mut [T],
16    poll: &mut dyn FnMut() -> Result<(), E>,
17    mut compare: impl FnMut(&T, &T, &mut dyn FnMut() -> Result<(), E>) -> Result<Ordering, E>,
18) -> Result<(), E> {
19    fn sift<T, E>(
20        values: &mut [T],
21        mut root: usize,
22        poll: &mut dyn FnMut() -> Result<(), E>,
23        compare: &mut impl FnMut(&T, &T, &mut dyn FnMut() -> Result<(), E>) -> Result<Ordering, E>,
24    ) -> Result<(), E> {
25        while root < values.len() / 2 {
26            poll()?;
27            let mut child = root * 2 + 1;
28            if child + 1 < values.len()
29                && compare(&values[child], &values[child + 1], poll)?.is_lt()
30            {
31                child += 1;
32            }
33            if !compare(&values[root], &values[child], poll)?.is_lt() {
34                break;
35            }
36            values.swap(root, child);
37            root = child;
38        }
39        Ok(())
40    }
41    poll()?;
42    for root in (0..values.len() / 2).rev() {
43        sift(values, root, poll, &mut compare)?;
44    }
45    for end in (1..values.len()).rev() {
46        poll()?;
47        values.swap(0, end);
48        sift(&mut values[..end], 0, poll, &mut compare)?;
49    }
50    poll()
51}
52
53#[cfg(test)]
54mod tests;
uqa_core/ordering.rs

uqa_core/
ordering.rs
