use crate::rank::bm25_score;
use crate::types::ResultItem;
use std::cmp::Ordering;
use std::collections::BinaryHeap;
#[derive(Debug, Clone)]
struct ScoredCandidate {
item: ResultItem,
pre_score: f64,
}
impl PartialEq for ScoredCandidate {
fn eq(&self, other: &Self) -> bool {
self.pre_score == other.pre_score
}
}
impl Eq for ScoredCandidate {}
impl PartialOrd for ScoredCandidate {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for ScoredCandidate {
fn cmp(&self, other: &Self) -> Ordering {
other
.pre_score
.partial_cmp(&self.pre_score)
.unwrap_or(Ordering::Equal)
}
}
pub struct SpreRanker {
query: String,
heap: BinaryHeap<ScoredCandidate>,
capacity: usize,
backend_counts: std::collections::HashMap<String, usize>,
total_ingested: usize,
}
#[derive(Debug, Clone)]
pub struct SpreConfig {
pub top_k: usize,
pub diversity_weight: f64,
pub score_threshold: f64,
}
impl Default for SpreConfig {
fn default() -> Self {
Self {
top_k: 20,
diversity_weight: 0.15,
score_threshold: 0.01,
}
}
}
#[derive(Debug, Clone)]
pub struct SpreSnapshot {
pub results: Vec<ResultItem>,
pub total_ingested: usize,
pub backends_contributing: usize,
}
impl SpreRanker {
pub fn new(query: &str, config: SpreConfig) -> Self {
Self {
query: query.to_string(),
heap: BinaryHeap::with_capacity(config.top_k + 1),
capacity: config.top_k,
backend_counts: std::collections::HashMap::new(),
total_ingested: 0,
}
}
pub fn ingest(&mut self, results: Vec<ResultItem>, config: &SpreConfig) {
for item in results {
self.total_ingested += 1;
let text = format!("{} {}", item.title, item.snippet);
let bm25 = bm25_score(&text, &self.query);
if bm25 < config.score_threshold {
continue;
}
let backend_key = item.backend.to_string();
let backend_count = self.backend_counts.get(&backend_key).copied().unwrap_or(0);
let diversity_bonus = if backend_count == 0 {
config.diversity_weight
} else {
config.diversity_weight / (backend_count as f64 + 1.0)
};
let pre_score = bm25 + diversity_bonus;
let candidate = ScoredCandidate {
item: ResultItem {
score: Some(pre_score),
..item
},
pre_score,
};
if self.heap.len() < self.capacity {
*self.backend_counts.entry(backend_key).or_insert(0) += 1;
self.heap.push(candidate);
} else if let Some(weakest) = self.heap.peek() {
if pre_score > weakest.pre_score {
let evicted = self.heap.pop().unwrap();
let evicted_key = evicted.item.backend.to_string();
if let Some(c) = self.backend_counts.get_mut(&evicted_key) {
*c = c.saturating_sub(1);
}
*self.backend_counts.entry(backend_key).or_insert(0) += 1;
self.heap.push(candidate);
}
}
}
}
pub fn snapshot(&self) -> SpreSnapshot {
let mut results: Vec<ResultItem> = self.heap.iter().map(|c| c.item.clone()).collect();
results.sort_by(|a, b| {
let sa = a.score.unwrap_or(0.0);
let sb = b.score.unwrap_or(0.0);
sb.partial_cmp(&sa).unwrap_or(Ordering::Equal)
});
for (i, item) in results.iter_mut().enumerate() {
item.rank = (i + 1) as u32;
}
SpreSnapshot {
results,
total_ingested: self.total_ingested,
backends_contributing: self.backend_counts.values().filter(|&&c| c > 0).count(),
}
}
pub fn len(&self) -> usize {
self.heap.len()
}
pub fn is_empty(&self) -> bool {
self.heap.is_empty()
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::types::BackendId;
fn make_item(title: &str, url: &str, snippet: &str, backend: BackendId) -> ResultItem {
ResultItem {
title: title.into(),
url: url.into(),
snippet: snippet.into(),
rank: 0,
backend,
score: None,
published_date: None,
}
}
#[test]
fn spre_basic_insertion() {
let config = SpreConfig {
top_k: 3,
..SpreConfig::default()
};
let mut ranker = SpreRanker::new("rust programming", config.clone());
let results = vec![
make_item(
"Rust Book",
"https://doc.rust-lang.org",
"Learn Rust programming",
BackendId::DuckDuckGo,
),
make_item(
"Python Tutorial",
"https://python.org",
"Learn Python basics",
BackendId::DuckDuckGo,
),
];
ranker.ingest(results, &config);
let snap = ranker.snapshot();
assert!(snap.results.len() <= 3);
assert_eq!(snap.total_ingested, 2);
assert_eq!(snap.results[0].title, "Rust Book");
}
#[test]
fn spre_evicts_weakest() {
let config = SpreConfig {
top_k: 2,
diversity_weight: 0.0,
score_threshold: 0.0,
};
let mut ranker = SpreRanker::new("rust", config.clone());
ranker.ingest(
vec![make_item(
"Weak",
"https://a.com",
"unrelated content about dogs",
BackendId::Wikipedia,
)],
&config,
);
ranker.ingest(
vec![
make_item(
"Strong",
"https://b.com",
"rust systems programming",
BackendId::DuckDuckGo,
),
make_item(
"Strongest",
"https://c.com",
"rust rust rust programming",
BackendId::Google,
),
],
&config,
);
let snap = ranker.snapshot();
assert_eq!(snap.results.len(), 2);
assert!(snap.results.iter().all(|r| r.title != "Weak"));
}
#[test]
fn spre_diversity_bonus() {
let config = SpreConfig {
top_k: 5,
diversity_weight: 0.3,
score_threshold: 0.0,
};
let mut ranker = SpreRanker::new("programming", config.clone());
ranker.ingest(
vec![
make_item(
"A",
"https://a.com",
"programming basics",
BackendId::DuckDuckGo,
),
make_item(
"B",
"https://b.com",
"programming intro",
BackendId::DuckDuckGo,
),
make_item(
"C",
"https://c.com",
"programming tips",
BackendId::DuckDuckGo,
),
],
&config,
);
ranker.ingest(
vec![make_item(
"D",
"https://d.com",
"programming guide",
BackendId::Wikipedia,
)],
&config,
);
let snap = ranker.snapshot();
assert!(snap.backends_contributing >= 2);
}
#[test]
fn spre_filters_low_scores() {
let config = SpreConfig {
top_k: 10,
score_threshold: 0.5,
..SpreConfig::default()
};
let mut ranker = SpreRanker::new("quantum computing", config.clone());
ranker.ingest(
vec![make_item(
"Irrelevant",
"https://a.com",
"cooking recipes for dinner",
BackendId::DuckDuckGo,
)],
&config,
);
let snap = ranker.snapshot();
assert_eq!(
snap.results.len(),
0,
"Low-scoring result should be filtered"
);
assert_eq!(snap.total_ingested, 1);
}
#[test]
fn spre_snapshot_sorted_descending() {
let config = SpreConfig::default();
let mut ranker = SpreRanker::new("rust", config.clone());
ranker.ingest(
vec![
make_item(
"Low",
"https://a.com",
"some text about code",
BackendId::Wikipedia,
),
make_item(
"High",
"https://b.com",
"rust programming rust language",
BackendId::DuckDuckGo,
),
make_item("Medium", "https://c.com", "rust basics", BackendId::Google),
],
&config,
);
let snap = ranker.snapshot();
for i in 1..snap.results.len() {
let prev = snap.results[i - 1].score.unwrap_or(0.0);
let curr = snap.results[i].score.unwrap_or(0.0);
assert!(prev >= curr, "Results not sorted: {prev} < {curr}");
}
for (i, item) in snap.results.iter().enumerate() {
assert_eq!(item.rank, (i + 1) as u32);
}
}
}