use crate::storage::warp_table::inconsistency::invariant_violation;
pub(super) fn sort(rows: &mut [usize], maximum: usize, scratch: &mut [usize]) {
if rows.len() == maximum {
if !rows.is_sorted() {
for (position, row) in rows.iter_mut().enumerate() {
*row = position;
}
}
return;
}
let words = maximum.div_ceil(usize::BITS as usize);
if rows.len() < words {
rows.sort_unstable();
return;
}
let Some(scratch) = scratch.get_mut(..words) else {
rows.sort_unstable();
return;
};
if rows.is_sorted() {
return;
}
if rows.is_sorted_by(|left, right| left >= right) {
rows.reverse();
} else {
bitmap(rows, scratch);
}
}
#[allow(
clippy::arithmetic_side_effects,
clippy::indexing_slicing,
reason = "unique dense positions are below the table length; scratch has one bit per table row; expansion writes exactly the selected cardinality"
)]
fn bitmap(rows: &mut [usize], words: &mut [usize]) {
words.fill(0);
for row in &*rows {
words[row / usize::BITS as usize] |= 1 << (row % usize::BITS as usize);
}
let mut output = rows.iter_mut();
for (index, word) in words.iter().enumerate() {
let mut word = *word;
for row in output.by_ref().take(word.count_ones() as usize) {
*row = index * usize::BITS as usize + word.trailing_zeros() as usize;
word &= word - 1;
}
}
if output.next().is_some() {
invariant_violation("dense selection contains duplicate rows");
}
}
#[cfg(test)]
mod tests {
extern crate std;
use super::*;
use alloc::{collections::BTreeSet, vec, vec::Vec};
use proptest::prelude::*;
fn check(input: &[usize], maximum: usize) -> Result<(), &'static str> {
let mut expected = input.to_vec();
expected.sort_unstable();
for words in [0, maximum.div_ceil(usize::BITS as usize)] {
let mut scratch = vec![usize::MAX; words.saturating_add(3)];
let mut actual = input.to_vec();
sort(
&mut actual,
maximum,
scratch.get_mut(..words).ok_or("scratch")?,
);
assert_eq!(actual, expected);
assert_eq!(scratch.get(words..), Some([usize::MAX; 3].as_slice()));
}
Ok(())
}
#[test]
fn physical_permutations_and_word_boundaries_preserve_exact_members() -> Result<(), &'static str>
{
for maximum in [
0, 1, 2, 31, 32, 33, 63, 64, 65, 255, 256, 257, 4095, 4096, 4097,
] {
let forward = (0..maximum).collect::<Vec<_>>();
check(&forward, maximum)?;
let reverse = forward.iter().rev().copied().collect::<Vec<_>>();
check(&reverse, maximum)?;
for stride in [1, 2, 3, 17, 129] {
let mut selected = forward.iter().step_by(stride).copied().collect::<Vec<_>>();
let half = selected.len() / 2;
selected.rotate_left(half);
check(&selected, maximum)?;
selected.sort_unstable_by(|left, right| right.cmp(left));
check(&selected, maximum)?;
}
}
check(&[7, 1, 4], 100_000)
}
#[test]
fn duplicate_dense_positions_refuse_bitmap_compaction() {
assert!(
std::panic::catch_unwind(|| {
bitmap(&mut [3, 1, 3], &mut [0]);
})
.is_err()
);
}
proptest! {
#![proptest_config(ProptestConfig::with_cases(128))]
#[test]
fn arbitrary_unique_selections_match_comparison_sort(
maximum in 1_usize..20_000,
values in proptest::collection::vec(any::<u16>(), 0..3000),
) {
let mut seen = BTreeSet::new();
let bounded = values.into_iter().map(|value| usize::from(value).checked_rem(maximum)
.ok_or_else(|| proptest::test_runner::TestCaseError::fail("zero bound")))
.collect::<Result<Vec<_>, _>>()?;
let input = bounded.into_iter()
.filter(|value| seen.insert(*value)).collect::<Vec<_>>();
check(&input, maximum).map_err(proptest::test_runner::TestCaseError::fail)?;
}
}
}