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));
assert!(prefers_direct_ranking(1, &threshold));
assert!(prefers_direct_ranking(1, &maximum_sparse));
assert!(!prefers_direct_ranking(2, &sparse));
assert!(!prefers_direct_ranking(1, &dense));
assert!(!prefers_direct_ranking(1, &many_sparse));
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(())
}