use std::collections::{HashMap, HashSet};
use uuid::Uuid;
pub const RRF_K: f32 = 60.0;
pub fn fuse(rankings: &[&[Uuid]], k: f32, top: usize) -> Vec<(Uuid, f32)> {
let mut scores: HashMap<Uuid, f32> = HashMap::new();
for list in rankings {
for (rank, id) in list.iter().enumerate() {
*scores.entry(*id).or_insert(0.0) += 1.0 / (k + (rank + 1) as f32);
}
}
let mut fused: Vec<(Uuid, f32)> = scores.into_iter().collect();
fused.sort_by(|a, b| {
b.1.partial_cmp(&a.1)
.unwrap_or(std::cmp::Ordering::Equal)
.then_with(|| a.0.cmp(&b.0))
});
fused.truncate(top);
fused
}
pub fn fuse_with_floor(rankings: &[&[Uuid]], k: f32, top: usize, floor: usize) -> Vec<(Uuid, f32)> {
let all = fuse(rankings, k, usize::MAX);
let kept: HashSet<Uuid> = rankings
.iter()
.flat_map(|list| list.iter().take(floor).copied())
.collect();
let mut fill = top.saturating_sub(kept.len());
all.into_iter()
.filter(|(id, _)| {
if kept.contains(id) {
true
} else if fill > 0 {
fill -= 1;
true
} else {
false
}
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
fn ids(n: usize) -> Vec<Uuid> {
(0..n).map(|_| Uuid::new_v4()).collect()
}
#[test]
fn id_on_both_lists_outranks_single_list_leaders() {
let shared = Uuid::new_v4();
let dense = [vec![shared], ids(3)].concat();
let lexical = [ids(2), vec![shared]].concat();
let fused = fuse(&[&dense, &lexical], RRF_K, 10);
assert_eq!(
fused[0].0, shared,
"rank 1 + rank 3 must beat any single-list id"
);
let expected = 1.0 / (RRF_K + 1.0) + 1.0 / (RRF_K + 3.0);
assert!((fused[0].1 - expected).abs() < 1e-6);
}
#[test]
fn preserves_order_within_a_single_list() {
let dense = ids(5);
let fused = fuse(&[&dense], RRF_K, 10);
let fused_ids: Vec<Uuid> = fused.iter().map(|(id, _)| *id).collect();
assert_eq!(fused_ids, dense);
}
#[test]
fn truncates_to_top() {
let dense = ids(200);
assert_eq!(fuse(&[&dense], RRF_K, 100).len(), 100);
}
#[test]
fn deterministic_on_score_ties() {
let a = ids(4);
let b: Vec<Uuid> = a.iter().rev().cloned().collect();
let first = fuse(&[&a, &b], RRF_K, 10);
let second = fuse(&[&a, &b], RRF_K, 10);
assert_eq!(first, second);
}
#[test]
fn a_zero_floor_is_plain_fusion() {
let dense = ids(40);
let lexical = [ids(10), dense[5..25].to_vec()].concat();
assert_eq!(
fuse_with_floor(&[&dense, &lexical], RRF_K, 20, 0),
fuse(&[&dense, &lexical], RRF_K, 20)
);
}
#[test]
fn the_floor_keeps_a_dense_only_rank_30_item_that_fusion_drops() {
let dense = ids(60);
let lexical: Vec<Uuid> = dense[30..60].to_vec();
let buried = dense[29];
let plain = fuse(&[&dense, &lexical], RRF_K, 20);
assert!(!plain.iter().any(|(id, _)| *id == buried));
let floored = fuse_with_floor(&[&dense, &lexical], RRF_K, 20, 30);
assert!(floored.iter().any(|(id, _)| *id == buried));
for id in dense[..30].iter().chain(&lexical[..30]) {
assert!(floored.iter().any(|(f, _)| f == id));
}
assert!(
floored.windows(2).all(|w| w[0].1 >= w[1].1),
"the floored list stays in RRF order"
);
}
#[test]
fn the_floor_fills_to_top_by_rrf_when_it_admits_fewer() {
let dense = ids(50);
let lexical = ids(50);
let floored = fuse_with_floor(&[&dense, &lexical], RRF_K, 20, 5);
assert_eq!(floored.len(), 20);
assert_eq!(floored, fuse(&[&dense, &lexical], RRF_K, 20));
}
}