use alloc::vec::Vec;
use core::num::NonZeroU32;
use super::first_rows::prefers_direct_ranking;
use super::{
OrderedRowLimit, OrderedSelectionFirstCuttingTiesOutcome,
OrderedSelectionFirstKeepingTiesOutcome,
};
use crate::storage::warp_table::query::Selection;
use crate::storage::warp_table::secondary_index::{SlotSet, SlotSetInsertOutcome, StableSlot};
use crate::storage::warp_table::{
Capacity, RangeIndexInconsistency, RangeIndexOrderingError, WarpTable, WarpTableInsertOutcome,
WarpTableRemoveOutcome, WarpTableRow,
};
#[derive(WarpTableRow)]
struct Player {
name: &'static str,
#[index(range)]
score: u16,
#[index(range)]
level: u8,
#[index(secondary)]
team: u8,
}
#[derive(Debug, Eq, PartialEq)]
enum Cut {
Exact(Vec<&'static str>),
TiesCut(Vec<&'static str>, usize),
}
#[derive(Debug, Eq, PartialEq)]
enum Kept {
Exact(Vec<&'static str>),
TiesKept(Vec<&'static str>, Vec<&'static str>),
}
const ROSTER: [(&str, u16, u8, u8); 7] = [
("ana", 90, 3, 1),
("bo", 70, 5, 2),
("cy", 90, 1, 1),
("di", 50, 2, 2),
("ed", 70, 5, 1),
("fi", 70, 2, 2),
("gu", 30, 4, 1),
];
#[test]
fn direct_ranking_is_reserved_for_sparse_occupied_blocks() -> Result<(), &'static str> {
let sparse = slot_set(&[0, 64, 128, 192])?;
let threshold = slot_set(&[0, 1, 64, 65])?;
let dense = slot_set(&[0, 1, 2, 64, 65, 66])?;
let maximum_sparse_slots = (0_u32..1_024)
.map(|slot| slot.saturating_mul(u64::BITS))
.collect::<Vec<_>>();
let maximum_sparse = slot_set(&maximum_sparse_slots)?;
let many_sparse_slots = (0_u32..=1_024)
.map(|slot| slot.saturating_mul(u64::BITS))
.collect::<Vec<_>>();
let many_sparse = slot_set(&many_sparse_slots)?;
assert!(prefers_direct_ranking(1, sparse.read()));
assert!(prefers_direct_ranking(1, threshold.read()));
assert!(prefers_direct_ranking(1, maximum_sparse.read()));
assert!(!prefers_direct_ranking(2, sparse.read()));
assert!(!prefers_direct_ranking(1, dense.read()));
assert!(!prefers_direct_ranking(1, many_sparse.read()));
Ok(())
}
#[test]
fn largest_first_returns_exact_rows_when_no_tie_straddles_the_limit() -> Result<(), &'static str> {
let players = players(&ROSTER)?;
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first())
.first_cutting_ties(limit(2)?))?,
Cut::Exact(names(["ana", "cy"]))
);
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first())
.first_cutting_ties(limit(5)?))?,
Cut::Exact(names(["ana", "cy", "bo", "ed", "fi"]))
);
assert_eq!(
kept(
players
.query()
.ordered_by(|q| q.score_largest_first())
.first_keeping_ties(limit(5)?)
)?,
Kept::Exact(names(["ana", "cy", "bo", "ed", "fi"]))
);
Ok(())
}
#[test]
fn first_returns_one_ordered_row_or_none() -> Result<(), &'static str> {
let empty = WarpTable::<Player>::try_new(Capacity::new(NonZeroU32::MIN))
.map_err(|_| "empty player storage was unavailable")?;
assert!(
empty
.query()
.ordered_by(|q| q.score_smallest_first())
.first()
.map_err(|_| "empty ordering was inconsistent")?
.is_none()
);
let players = players(&ROSTER)?;
assert_eq!(
players
.query()
.ordered_by(|q| q.score_smallest_first())
.first()
.map_err(|_| "ordering was inconsistent")?
.map(|row| *row.name),
Some("gu")
);
assert_eq!(
players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(|left, right| right.name.cmp(left.name))
.first()
.map_err(|_| "ordering was inconsistent")?
.map(|row| *row.name),
Some("cy")
);
assert_eq!(
players
.query()
.find_team(9)
.ordered_by(|q| q.score_smallest_first())
.first()
.map_err(|_| "ordering was inconsistent")?
.map(|row| *row.name),
None
);
Ok(())
}
#[test]
fn fewer_candidates_than_the_limit_come_back_complete_and_ordered() -> Result<(), &'static str> {
let players = players(&ROSTER)?;
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first())
.first_cutting_ties(limit(10)?))?,
Cut::Exact(names(["ana", "cy", "bo", "ed", "fi", "di", "gu"]))
);
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_smallest_first())
.first_cutting_ties(limit(10)?))?,
Cut::Exact(names(["gu", "di", "bo", "ed", "fi", "ana", "cy"]))
);
Ok(())
}
#[test]
fn ties_straddling_the_limit_are_cut_in_slot_order_or_kept_whole() -> Result<(), &'static str> {
let players = players(&ROSTER)?;
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first())
.first_cutting_ties(limit(3)?))?,
Cut::TiesCut(names(["ana", "cy", "bo"]), 2)
);
assert_eq!(
kept(
players
.query()
.ordered_by(|q| q.score_largest_first())
.first_keeping_ties(limit(3)?)
)?,
Kept::TiesKept(names(["ana", "cy"]), names(["bo", "ed", "fi"]))
);
assert_eq!(
kept(
players
.query()
.ordered_by(|q| q.score_smallest_first())
.first_keeping_ties(limit(3)?)
)?,
Kept::TiesKept(names(["gu", "di"]), names(["bo", "ed", "fi"]))
);
Ok(())
}
#[test]
fn later_range_levels_break_earlier_ties_in_their_own_direction() -> Result<(), &'static str> {
let players = players(&ROSTER)?;
assert_eq!(
kept(
players
.query()
.ordered_by(|q| q.score_largest_first().then(q.level_largest_first()))
.first_keeping_ties(limit(3)?)
)?,
Kept::TiesKept(names(["ana", "cy"]), names(["bo", "ed"]))
);
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first().then(q.level_smallest_first()))
.first_cutting_ties(limit(3)?))?,
Cut::Exact(names(["cy", "ana", "fi"]))
);
assert_eq!(
cut(players
.query()
.ordered_by(|q| {
q.score_largest_first()
.then(q.level_largest_first().then(q.level_smallest_first()))
})
.first_cutting_ties(limit(3)?))?,
Cut::TiesCut(names(["ana", "cy", "bo"]), 1)
);
Ok(())
}
#[test]
fn row_comparison_orders_leaders_and_breaks_boundary_ties() -> Result<(), &'static str> {
let players = players(&ROSTER)?;
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(|left, right| right.name.cmp(left.name))
.first_cutting_ties(limit(3)?))?,
Cut::Exact(names(["cy", "ana", "fi"]))
);
assert_eq!(
kept(
players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(|left, right| left.team.cmp(right.team))
.first_keeping_ties(limit(3)?)
)?,
Kept::Exact(names(["ana", "cy", "ed"]))
);
assert_eq!(
kept(
players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(|left, right| right.name.cmp(left.name))
.first_keeping_ties(limit(2)?)
)?,
Kept::Exact(names(["cy", "ana"]))
);
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(|left, right| right.name.cmp(left.name))
.first_cutting_ties(limit(2)?))?,
Cut::Exact(names(["cy", "ana"]))
);
Ok(())
}
#[test]
fn ties_the_row_comparison_leaves_are_cut_or_kept() -> Result<(), &'static str> {
let players = players(&ROSTER)?;
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(|left, right| right.team.cmp(left.team))
.first_cutting_ties(limit(3)?))?,
Cut::TiesCut(names(["ana", "cy", "bo"]), 1)
);
assert_eq!(
kept(
players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(|left, right| right.team.cmp(left.team))
.first_keeping_ties(limit(3)?)
)?,
Kept::TiesKept(names(["ana", "cy"]), names(["bo", "fi"]))
);
assert_eq!(
kept(
players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(|left, right| right.team.cmp(left.team))
.first_keeping_ties(limit(4)?)
)?,
Kept::Exact(names(["ana", "cy", "bo", "fi"]))
);
Ok(())
}
#[test]
fn row_comparison_separates_better_rows_from_the_rows_it_still_ties() -> Result<(), &'static str> {
let players = players(&[
("ana", 10, 1, 1),
("bo", 10, 1, 2),
("cy", 10, 1, 3),
("di", 10, 1, 2),
("ed", 10, 1, 2),
])?;
let by_team_descending =
|left: &PlayerRef<'_>, right: &PlayerRef<'_>| right.team.cmp(left.team);
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(by_team_descending)
.first_cutting_ties(limit(2)?))?,
Cut::TiesCut(names(["cy", "bo"]), 2)
);
assert_eq!(
kept(
players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(by_team_descending)
.first_keeping_ties(limit(2)?)
)?,
Kept::TiesKept(names(["cy"]), names(["bo", "di", "ed"]))
);
Ok(())
}
#[test]
fn row_comparison_finds_the_best_rows_across_repeated_buffer_selections() -> Result<(), &'static str>
{
let roster = NAMES
.iter()
.copied()
.cycle()
.zip(0..40_u8)
.map(|(name, level)| (name, 7, level, 1))
.collect::<Vec<_>>();
let players = players(&roster)?;
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(|left, right| right.level.cmp(left.level))
.first_cutting_ties(limit(3)?))?,
Cut::Exact(names(["hu", "gu", "fi"]))
);
Ok(())
}
#[test]
fn ordering_ranks_only_the_selection_it_starts_from() -> Result<(), &'static str> {
let players = players(&ROSTER)?;
assert_eq!(
cut(players
.query()
.find_team(2)
.ordered_by(|q| q.score_largest_first())
.first_cutting_ties(limit(2)?))?,
Cut::Exact(names(["bo", "fi"]))
);
assert_eq!(
cut(players
.query()
.find_score_in(..=70)
.map_err(|_| "score range was unavailable")?
.ordered_by(|q| q.score_largest_first())
.first_cutting_ties(limit(2)?))?,
Cut::TiesCut(names(["bo", "ed"]), 1)
);
assert_eq!(
cut(players
.query()
.find_team(2)
.and(|q| q
.find_score_in(60..)
.map_err(|_| "score range was unavailable"))?
.ordered_by(|q| q.level_smallest_first())
.first_cutting_ties(limit(1)?))?,
Cut::Exact(names(["fi"]))
);
assert_eq!(
kept(
players
.query()
.find_team(9)
.ordered_by(|q| q.score_largest_first())
.first_keeping_ties(limit(1)?)
)?,
Kept::Exact(Vec::new())
);
Ok(())
}
#[test]
fn direct_ranking_preserves_boundaries_across_storage_blocks() -> Result<(), &'static str> {
let roster = (0..130)
.map(|slot| match slot {
0 => ("ana", 90, 0, 9),
64 => ("bo", 70, 0, 9),
65 => ("ed", 40, 0, 9),
128 => ("cy", 70, 0, 9),
129 => ("di", 50, 0, 9),
_ => ("unused", 0, 0, 0),
})
.collect::<Vec<_>>();
let players = players(&roster)?;
assert_eq!(
cut(players
.query()
.find_team(9)
.ordered_by(|q| q.score_largest_first())
.first_cutting_ties(limit(2)?))?,
Cut::TiesCut(names(["ana", "bo"]), 1)
);
assert_eq!(
cut(players
.query()
.find_team(9)
.ordered_by(|q| q.score_largest_first())
.first_cutting_ties(limit(3)?))?,
Cut::Exact(names(["ana", "bo", "cy"]))
);
Ok(())
}
#[test]
fn whole_table_ordering_follows_removals_and_reused_rows() -> Result<(), &'static str> {
let mut players = players(&ROSTER)?;
let Some(ana) = players.ids().first().copied() else {
return Err("ana was absent");
};
assert!(matches!(
players.remove(ana),
WarpTableRemoveOutcome::Removed { .. }
));
assert!(matches!(
players.insert(Player {
name: "hu",
score: 95,
level: 1,
team: 2,
}),
WarpTableInsertOutcome::Inserted { .. }
));
assert_eq!(
cut(players
.query()
.ordered_by(|q| q.score_largest_first())
.first_cutting_ties(limit(2)?))?,
Cut::Exact(names(["hu", "cy"]))
);
Ok(())
}
#[test]
fn memberships_outside_the_table_are_reported_by_every_terminal() -> Result<(), &'static str> {
let players = players(&ROSTER)?;
let foreign = || {
Selection::owned(&players, SlotSet::one(StableSlot::new(999)))
.ordered_by(|q| q.score_largest_first())
};
let outside = RangeIndexOrderingError::Inconsistent {
field: "score",
reason: RangeIndexInconsistency::SlotOutsideCapacity { maximum_rows: 7 },
};
assert!(matches!(
foreign().first_cutting_ties(limit(1)?),
Err(failure) if failure == outside
));
assert!(matches!(
foreign().first(),
Err(failure) if failure == outside
));
assert!(matches!(
foreign().first_keeping_ties(limit(1)?),
Err(failure) if failure == outside
));
assert!(matches!(
foreign()
.then_compare_rows(|left, right| left.name.cmp(right.name))
.first_cutting_ties(limit(1)?),
Err(failure) if failure == outside
));
assert!(matches!(
foreign()
.then_compare_rows(|left, right| left.name.cmp(right.name))
.first(),
Err(failure) if failure == outside
));
assert!(matches!(
foreign()
.then_compare_rows(|left, right| left.name.cmp(right.name))
.first_keeping_ties(limit(1)?),
Err(failure) if failure == outside
));
Ok(())
}
const NAMES: [&str; 8] = ["ana", "bo", "cy", "di", "ed", "fi", "gu", "hu"];
fn players(roster: &[(&'static str, u16, u8, u8)]) -> Result<WarpTable<Player>, &'static str> {
let rows = u32::try_from(roster.len()).map_err(|_| "roster exceeded u32")?;
let capacity = Capacity::new(NonZeroU32::new(rows).ok_or("roster was empty")?);
let mut players = WarpTable::try_new(capacity).map_err(|_| "player storage was unavailable")?;
for (name, score, level, team) in roster.iter().copied() {
let WarpTableInsertOutcome::Inserted { .. } = players.insert(Player {
name,
score,
level,
team,
}) else {
return Err("player could not be inserted");
};
}
Ok(players)
}
fn limit(rows: u32) -> Result<OrderedRowLimit, &'static str> {
Ok(OrderedRowLimit::new(
NonZeroU32::new(rows).ok_or("limit was zero")?,
))
}
fn names<const N: usize>(names: [&'static str; N]) -> Vec<&'static str> {
names.to_vec()
}
fn slot_set(slots: &[u32]) -> Result<SlotSet, &'static str> {
let mut set = SlotSet::empty();
for slot in slots.iter().copied() {
let prepared = set
.try_prepare_insert(StableSlot::new(slot))
.map_err(|_| "slot was duplicated")?;
let SlotSetInsertOutcome::Inserted { .. } = prepared.commit();
}
Ok(set)
}
fn row_names(rows: Vec<PlayerRef<'_>>) -> Vec<&'static str> {
rows.into_iter().map(|row| *row.name).collect()
}
fn cut(
outcome: Result<
OrderedSelectionFirstCuttingTiesOutcome<PlayerRef<'_>>,
RangeIndexOrderingError,
>,
) -> Result<Cut, &'static str> {
match outcome.map_err(|_| "ordering was inconsistent")? {
OrderedSelectionFirstCuttingTiesOutcome::Exact { rows } => Ok(Cut::Exact(row_names(rows))),
OrderedSelectionFirstCuttingTiesOutcome::TiesCut {
rows,
tied_rows_left_out,
} => Ok(Cut::TiesCut(row_names(rows), tied_rows_left_out)),
}
}
fn kept(
outcome: Result<
OrderedSelectionFirstKeepingTiesOutcome<PlayerRef<'_>>,
RangeIndexOrderingError,
>,
) -> Result<Kept, &'static str> {
match outcome.map_err(|_| "ordering was inconsistent")? {
OrderedSelectionFirstKeepingTiesOutcome::Exact { rows } => Ok(Kept::Exact(row_names(rows))),
OrderedSelectionFirstKeepingTiesOutcome::TiesKept { leaders, tied } => {
Ok(Kept::TiesKept(row_names(leaders), row_names(tied)))
}
}
}
#[test]
fn an_empty_owned_selection_keeps_both_ordering_limits_empty() -> Result<(), &'static str> {
let players = players(&ROSTER)?;
let absent = || players.query().find_team(1).and(|query| query.find_team(2));
assert_eq!(
cut(absent()
.ordered_by(|query| query.score_largest_first())
.first_cutting_ties(limit(2)?))?,
Cut::Exact(Vec::new())
);
assert_eq!(
kept(
absent()
.ordered_by(|query| query.score_smallest_first())
.first_keeping_ties(limit(2)?)
)?,
Kept::Exact(Vec::new())
);
Ok(())
}
#[test]
fn an_absent_bucket_keeps_both_ordering_limits_empty() -> Result<(), &'static str> {
let players = players(&ROSTER)?;
assert_eq!(
cut(players
.query()
.find_team(99)
.ordered_by(|query| query.score_largest_first())
.first_cutting_ties(limit(2)?))?,
Cut::Exact(Vec::new())
);
assert_eq!(
kept(
players
.query()
.find_team(99)
.ordered_by(|query| query.score_smallest_first())
.first_keeping_ties(limit(2)?)
)?,
Kept::Exact(Vec::new())
);
Ok(())
}
#[test]
fn whole_table_ranking_preserves_foreign_index_count_refusals() -> Result<(), &'static str> {
let table = players(&ROSTER)?;
let foreign = players(ROSTER.get(..2).ok_or("short roster")?)?;
let expected = RangeIndexOrderingError::MemberCountMismatch {
field: "score",
table_rows: ROSTER.len(),
index_members: 2,
};
assert!(
matches!(table.query().ordered_by(|_| foreign.query().score_largest_first()).first_cutting_ties(limit(1)?), Err(error) if error == expected)
);
assert!(
matches!(table.query().ordered_by(|_| foreign.query().score_smallest_first()).first_keeping_ties(limit(1)?), Err(error) if error == expected)
);
assert_eq!(table.len(), ROSTER.len());
assert_eq!(foreign.len(), 2);
Ok(())
}
#[test]
fn sparse_first_preserves_ties_after_dense_relocation() -> Result<(), &'static str> {
let mut roster = alloc::vec![("unused", 0, 0, 0); 129];
for (slot, name, score, level) in [
(0, "minimum", 40, 0),
(64, "first", 90, 1),
(128, "last", 90, 2),
] {
*roster.get_mut(slot).ok_or("roster slot")? = (name, score, level, 9);
}
let mut table = players(&roster)?;
let removed = *table.ids().get(1).ok_or("removed row")?;
assert!(matches!(
table.remove(removed),
WarpTableRemoveOutcome::Removed { .. }
));
assert_eq!(table.rows().nth(1).map(|row| *row.name), Some("last"));
for owned in [false, true] {
for largest in [false, true] {
let selection = if owned {
table.query().find_team(9).or(|q| q.find_team(9))
} else {
table.query().find_team(9).into_selection()
};
let row = selection
.ordered_by(|q| {
if largest {
q.score_largest_first()
} else {
q.score_smallest_first()
}
})
.first()
.map_err(|_| "ranking")?;
assert_eq!(
row.map(|row| *row.name),
Some(if largest { "first" } else { "minimum" })
);
}
}
assert_eq!(
table
.query()
.find_team(9)
.ordered_by(|q| q.score_largest_first().then(q.level_largest_first()))
.first()
.map_err(|_| "second level")?
.map(|row| *row.name),
Some("last")
);
assert_eq!(
table
.query()
.find_team(9)
.ordered_by(|q| q.score_largest_first())
.then_compare_rows(|left, right| right.level.cmp(left.level))
.first()
.map_err(|_| "row comparison")?
.map(|row| *row.name),
Some("last")
);
assert!(
table
.query()
.find_team(9)
.and_not(|q| q.find_team(9))
.ordered_by(|q| q.score_largest_first())
.first()
.map_err(|_| "owned empty")?
.is_none()
);
Ok(())
}
#[test]
fn sparse_first_validates_losing_slots_after_an_extremum() -> Result<(), &'static str> {
let mut table = players(&[("best", u16::MAX, 0, 1), ("removed", 0, 0, 1)])?;
let removed = *table.ids().get(1).ok_or("removed row")?;
assert!(matches!(
table.remove(removed),
WarpTableRemoveOutcome::Removed { .. }
));
let selection = Selection::owned(&table, slot_set(&[0, 1])?);
assert!(matches!(
selection.ordered_by(|q| q.score_largest_first()).first(),
Err(RangeIndexOrderingError::Inconsistent {
field: "score",
reason: RangeIndexInconsistency::MemberAbsent
})
));
Ok(())
}
#[test]
fn first_matches_stable_extrema_across_ranking_strategies() -> Result<(), &'static str> {
for count in [1, 2, 3, 17, 64, 65, 130, 1_024, 1_025] {
for tied in [false, true] {
let roster = (0..count)
.map(|slot: u16| {
let score = if tied { 42 } else { slot.wrapping_mul(37) };
("player", score, 0, 1)
})
.collect::<Vec<_>>();
let table = players(&roster)?;
for largest in [false, true] {
let mut expected = table.rows().collect::<Vec<_>>();
expected.sort_by(|left, right| {
if largest {
right.score.cmp(left.score)
} else {
left.score.cmp(right.score)
}
});
let winner = table
.query()
.find_team(1)
.ordered_by(|q| {
if largest {
q.score_largest_first()
} else {
q.score_smallest_first()
}
})
.first()
.map_err(|_| "ranking")?;
assert_eq!(
winner.map(|row| *row.id),
expected.first().map(|row| *row.id)
);
}
}
}
Ok(())
}