use std::cmp::Ordering;
use std::collections::BinaryHeap;
use crate::format::FrameId;
use super::Hit;
#[derive(Clone, Copy, PartialEq, Eq)]
struct HeapEntry {
score_bits: u32,
frame_id: u64,
}
impl Ord for HeapEntry {
#[inline]
fn cmp(&self, other: &Self) -> Ordering {
other
.score_bits
.cmp(&self.score_bits)
.then_with(|| self.frame_id.cmp(&other.frame_id))
}
}
impl PartialOrd for HeapEntry {
#[inline]
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
pub(crate) fn select_top_k_from_touched(
touched: &[u32],
scores: &[f32],
top_k: Option<usize>,
) -> Vec<Hit> {
let cap = top_k.unwrap_or(usize::MAX);
if cap == 0 || touched.is_empty() {
return Vec::new();
}
if cap >= touched.len() {
let mut hits: Vec<Hit> = touched
.iter()
.filter_map(|&fid32| {
let s = scores[fid32 as usize];
if s == 0.0 {
None
} else {
Some(Hit {
frame_id: FrameId(fid32 as u64),
score: s,
})
}
})
.collect();
sort_hits_descending(&mut hits);
return hits;
}
let mut heap: BinaryHeap<HeapEntry> = BinaryHeap::with_capacity(cap + 1);
for &fid32 in touched {
let s = scores[fid32 as usize];
if s <= 0.0 {
continue;
}
let entry = HeapEntry {
score_bits: s.to_bits(),
frame_id: fid32 as u64,
};
if heap.len() < cap {
heap.push(entry);
} else if let Some(worst) = heap.peek()
&& entry.cmp(worst) == Ordering::Less
{
heap.pop();
heap.push(entry);
}
}
let mut hits: Vec<Hit> = heap
.into_iter()
.map(|e| Hit {
frame_id: FrameId(e.frame_id),
score: f32::from_bits(e.score_bits),
})
.collect();
sort_hits_descending(&mut hits);
hits
}
pub(crate) fn select_top_k_from_touched_signed(
touched: &[u32],
scores: &[f32],
top_k: Option<usize>,
) -> Vec<Hit> {
let cap = top_k.unwrap_or(usize::MAX);
if cap == 0 || touched.is_empty() {
return Vec::new();
}
if cap >= touched.len() {
let mut hits: Vec<Hit> = touched
.iter()
.filter_map(|&fid32| {
let s = scores[fid32 as usize];
if s == 0.0 {
None
} else {
Some(Hit {
frame_id: FrameId(fid32 as u64),
score: s,
})
}
})
.collect();
hits.sort_unstable_by(|a, b| {
b.score
.partial_cmp(&a.score)
.unwrap_or(Ordering::Equal)
.then_with(|| a.frame_id.0.cmp(&b.frame_id.0))
});
return hits;
}
#[derive(Copy, Clone)]
struct Entry {
score: f32,
frame_id: u64,
}
impl PartialEq for Entry {
fn eq(&self, other: &Self) -> bool {
self.score == other.score && self.frame_id == other.frame_id
}
}
impl Eq for Entry {}
impl Ord for Entry {
fn cmp(&self, other: &Self) -> Ordering {
other
.score
.partial_cmp(&self.score)
.unwrap_or(Ordering::Equal)
.then_with(|| self.frame_id.cmp(&other.frame_id))
}
}
impl PartialOrd for Entry {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
let mut heap: BinaryHeap<Entry> = BinaryHeap::with_capacity(cap + 1);
for &fid32 in touched {
let s = scores[fid32 as usize];
if s == 0.0 {
continue;
}
let entry = Entry {
score: s,
frame_id: fid32 as u64,
};
if heap.len() < cap {
heap.push(entry);
} else if let Some(worst) = heap.peek()
&& entry.cmp(worst) == Ordering::Less
{
heap.pop();
heap.push(entry);
}
}
let mut hits: Vec<Hit> = heap
.into_iter()
.map(|e| Hit {
frame_id: FrameId(e.frame_id),
score: e.score,
})
.collect();
hits.sort_unstable_by(|a, b| {
b.score
.partial_cmp(&a.score)
.unwrap_or(Ordering::Equal)
.then_with(|| a.frame_id.0.cmp(&b.frame_id.0))
});
hits
}
#[inline]
fn sort_hits_descending(hits: &mut [Hit]) {
hits.sort_unstable_by(|a, b| {
b.score
.to_bits()
.cmp(&a.score.to_bits())
.then_with(|| a.frame_id.0.cmp(&b.frame_id.0))
});
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn small_touched_returns_all_sorted() {
let scores = vec![0.0, 0.3, 0.8, 0.1, 0.5];
let touched = vec![1, 2, 3, 4];
let hits = select_top_k_from_touched(&touched, &scores, Some(10));
let expected: Vec<u64> = vec![2, 4, 1, 3];
let got: Vec<u64> = hits.iter().map(|h| h.frame_id.0).collect();
assert_eq!(got, expected);
}
#[test]
fn top_k_caps_result() {
let mut scores = vec![0.0_f32; 1000];
let mut touched: Vec<u32> = Vec::new();
for i in 1..1000 {
scores[i] = (i as f32) * 0.001;
touched.push(i as u32);
}
let hits = select_top_k_from_touched(&touched, &scores, Some(5));
assert_eq!(hits.len(), 5);
let got: Vec<u64> = hits.iter().map(|h| h.frame_id.0).collect();
assert_eq!(got, vec![999, 998, 997, 996, 995]);
}
#[test]
fn ties_broken_by_lowest_frame_id() {
let scores = vec![0.0, 0.5, 0.5, 0.5, 0.5];
let touched = vec![4, 2, 1, 3];
let hits = select_top_k_from_touched(&touched, &scores, Some(2));
let got: Vec<u64> = hits.iter().map(|h| h.frame_id.0).collect();
assert_eq!(got, vec![1, 2]);
}
#[test]
fn zero_scores_skipped() {
let scores = vec![0.0, 0.0, 0.5, 0.0];
let touched = vec![1, 2, 3];
let hits = select_top_k_from_touched(&touched, &scores, Some(10));
assert_eq!(hits.len(), 1);
assert_eq!(hits[0].frame_id, FrameId(2));
}
#[test]
fn none_top_k_returns_everything() {
let scores = vec![0.0, 0.3, 0.5, 0.1];
let touched = vec![1, 2, 3];
let hits = select_top_k_from_touched(&touched, &scores, None);
assert_eq!(hits.len(), 3);
let got: Vec<u64> = hits.iter().map(|h| h.frame_id.0).collect();
assert_eq!(got, vec![2, 1, 3]);
}
}