use std::cmp::Ordering;
use std::collections::{BinaryHeap, HashMap};
use std::sync::Arc;
use parking_lot::Mutex;
use url::Url;
#[derive(Debug, Clone)]
pub struct ScoredUrl {
pub url: String,
pub score: f32,
pub domain: String,
}
impl ScoredUrl {
pub fn new(url: String, score: f32) -> Result<Self, FrontierError> {
let domain = Self::extract_domain(&url)?;
Ok(Self { url, score, domain })
}
#[must_use]
pub fn with_domain(url: String, score: f32, domain: String) -> Self {
Self { url, score, domain }
}
fn extract_domain(url_str: &str) -> Result<String, FrontierError> {
let parsed = Url::parse(url_str).map_err(|e| FrontierError::UrlParse(e.to_string()))?;
let host = parsed
.host_str()
.ok_or_else(|| FrontierError::NoHost(url_str.to_string()))?;
if host.is_empty() {
return Err(FrontierError::NoHost(url_str.to_string()));
}
Ok(host.to_ascii_lowercase())
}
}
impl PartialEq for ScoredUrl {
fn eq(&self, other: &Self) -> bool {
self.score == other.score
}
}
impl Eq for ScoredUrl {}
impl PartialOrd for ScoredUrl {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl Ord for ScoredUrl {
fn cmp(&self, other: &Self) -> Ordering {
self.score
.partial_cmp(&other.score)
.unwrap_or(Ordering::Equal)
}
}
pub struct Frontier {
inner: Mutex<FrontierInner>,
}
struct FrontierInner {
domains: HashMap<Arc<str>, BinaryHeap<ScoredUrl>>,
domain_order: Vec<Arc<str>>,
cursor: usize,
len: usize,
}
impl Frontier {
#[must_use]
pub fn new() -> Self {
Self {
inner: Mutex::new(FrontierInner {
domains: HashMap::new(),
domain_order: Vec::new(),
cursor: 0,
len: 0,
}),
}
}
pub fn push(&self, scored: ScoredUrl) {
let mut inner = self.inner.lock();
let domain: Arc<str> = Arc::from(scored.domain.as_str());
if !inner.domains.contains_key(&domain) {
inner.domain_order.push(domain.clone());
inner.domains.insert(domain.clone(), BinaryHeap::new());
}
inner.domains.get_mut(&domain).unwrap().push(scored);
inner.len += 1;
}
pub fn pop(&self) -> Option<ScoredUrl> {
let mut inner = self.inner.lock();
if inner.len == 0 || inner.domain_order.is_empty() {
return None;
}
let domain_count = inner.domain_order.len();
for offset in 0..domain_count {
let idx = (inner.cursor + offset) % domain_count;
let domain = inner.domain_order[idx].clone();
if let Some(heap) = inner.domains.get_mut(&domain) {
if let Some(scored) = heap.pop() {
inner.cursor = (idx + 1) % domain_count;
inner.len -= 1;
return Some(scored);
}
}
}
None
}
#[must_use]
pub fn len(&self) -> usize {
self.inner.lock().len
}
#[must_use]
pub fn is_empty(&self) -> bool {
self.len() == 0
}
#[must_use]
pub fn domain_count(&self) -> usize {
self.inner.lock().domain_order.len()
}
#[must_use]
pub fn domain_len(&self, domain: &str) -> usize {
let inner = self.inner.lock();
let lower = domain.to_ascii_lowercase();
inner.domains.get(lower.as_str()).map_or(0, |h| h.len())
}
}
impl Default for Frontier {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug, thiserror::Error)]
pub enum FrontierError {
#[error("URL parse error: {0}")]
UrlParse(String),
#[error("URL has no host: {0}")]
NoHost(String),
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn scored_url_new_extracts_domain() {
let scored = ScoredUrl::new("https://Example.COM/blog/post".to_string(), 0.8).unwrap();
assert_eq!(scored.domain, "example.com");
assert_eq!(scored.url, "https://Example.COM/blog/post");
assert!((scored.score - 0.8).abs() < 1e-6);
}
#[test]
fn scored_url_new_subdomain() {
let scored = ScoredUrl::new("https://blog.example.org/page".to_string(), 0.5).unwrap();
assert_eq!(scored.domain, "blog.example.org");
}
#[test]
fn scored_url_new_invalid_url_returns_err() {
assert!(ScoredUrl::new("not a url".to_string(), 0.5).is_err());
assert!(ScoredUrl::new("".to_string(), 0.5).is_err());
}
#[test]
fn scored_url_new_no_host_returns_err() {
assert!(ScoredUrl::new("file:///etc/passwd".to_string(), 0.5).is_err());
assert!(ScoredUrl::new("mailto:test@example.com".to_string(), 0.5).is_err());
assert!(ScoredUrl::new("javascript:void(0)".to_string(), 0.5).is_err());
}
#[test]
fn scored_url_ord_high_score_first() {
let heap = BinaryHeap::from(vec![
ScoredUrl::with_domain("https://a.com/low".to_string(), 0.1, "a.com".to_string()),
ScoredUrl::with_domain("https://a.com/high".to_string(), 0.9, "a.com".to_string()),
ScoredUrl::with_domain("https://a.com/mid".to_string(), 0.5, "a.com".to_string()),
]);
assert_eq!(heap.peek().unwrap().url, "https://a.com/high");
}
#[test]
fn scored_url_eq_by_score() {
let a = ScoredUrl::with_domain("https://a.com/1".to_string(), 0.5, "a.com".to_string());
let b = ScoredUrl::with_domain("https://b.com/2".to_string(), 0.5, "b.com".to_string());
assert_eq!(a, b); }
#[test]
fn frontier_new_is_empty() {
let f = Frontier::new();
assert!(f.is_empty());
assert_eq!(f.len(), 0);
assert_eq!(f.domain_count(), 0);
assert!(f.pop().is_none());
}
#[test]
fn frontier_push_increments_len() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/1".to_string(),
0.5,
"a.com".to_string(),
));
assert_eq!(f.len(), 1);
assert!(!f.is_empty());
assert_eq!(f.domain_count(), 1);
}
#[test]
fn frontier_push_multiple_domains() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/1".to_string(),
0.5,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://b.com/1".to_string(),
0.5,
"b.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://c.com/1".to_string(),
0.5,
"c.com".to_string(),
));
assert_eq!(f.len(), 3);
assert_eq!(f.domain_count(), 3);
}
#[test]
fn frontier_push_same_domain_multiple_urls() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/1".to_string(),
0.5,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/2".to_string(),
0.9,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/3".to_string(),
0.1,
"a.com".to_string(),
));
assert_eq!(f.len(), 3);
assert_eq!(f.domain_count(), 1);
assert_eq!(f.domain_len("a.com"), 3);
}
#[test]
fn frontier_pop_single_domain_high_score_first() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/low".to_string(),
0.1,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/high".to_string(),
0.9,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/mid".to_string(),
0.5,
"a.com".to_string(),
));
let first = f.pop().unwrap();
assert_eq!(first.url, "https://a.com/high");
let second = f.pop().unwrap();
assert_eq!(second.url, "https://a.com/mid");
let third = f.pop().unwrap();
assert_eq!(third.url, "https://a.com/low");
assert!(f.is_empty());
assert!(f.pop().is_none());
}
#[test]
fn frontier_pop_decrements_len() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/1".to_string(),
0.5,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/2".to_string(),
0.9,
"a.com".to_string(),
));
assert_eq!(f.len(), 2);
f.pop();
assert_eq!(f.len(), 1);
f.pop();
assert_eq!(f.len(), 0);
assert!(f.is_empty());
}
#[test]
fn frontier_round_robin_two_domains() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/1".to_string(),
0.9,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/2".to_string(),
0.8,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/3".to_string(),
0.7,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://b.com/1".to_string(),
0.1,
"b.com".to_string(),
));
let pop1 = f.pop().unwrap();
assert_eq!(pop1.domain, "a.com");
assert_eq!(pop1.url, "https://a.com/1");
let pop2 = f.pop().unwrap();
assert_eq!(pop2.domain, "b.com"); assert_eq!(pop2.url, "https://b.com/1");
let pop3 = f.pop().unwrap();
assert_eq!(pop3.domain, "a.com"); assert_eq!(pop3.url, "https://a.com/2");
let pop4 = f.pop().unwrap();
assert_eq!(pop4.domain, "a.com"); assert_eq!(pop4.url, "https://a.com/3");
assert!(f.is_empty());
}
#[test]
fn frontier_round_robin_three_domains() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/1".to_string(),
0.9,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://b.com/1".to_string(),
0.5,
"b.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://c.com/1".to_string(),
0.1,
"c.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/2".to_string(),
0.8,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://b.com/2".to_string(),
0.4,
"b.com".to_string(),
));
let domains: Vec<String> = vec![
f.pop().unwrap().domain,
f.pop().unwrap().domain,
f.pop().unwrap().domain,
f.pop().unwrap().domain,
f.pop().unwrap().domain,
];
assert_eq!(domains, vec!["a.com", "b.com", "c.com", "a.com", "b.com"]);
}
#[test]
fn frontier_round_robin_skips_empty_domain() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/1".to_string(),
0.9,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://b.com/1".to_string(),
0.5,
"b.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/2".to_string(),
0.8,
"a.com".to_string(),
));
let pop1 = f.pop().unwrap();
assert_eq!(pop1.domain, "a.com");
let pop2 = f.pop().unwrap();
assert_eq!(pop2.domain, "b.com");
let pop3 = f.pop().unwrap();
assert_eq!(pop3.domain, "a.com");
assert!(f.is_empty());
}
#[test]
fn frontier_round_robin_no_starvation() {
let f = Frontier::new();
for i in 0..5 {
f.push(ScoredUrl::with_domain(
format!("https://a.com/{i}"),
0.9,
"a.com".to_string(),
));
}
f.push(ScoredUrl::with_domain(
"https://b.com/1".to_string(),
0.1,
"b.com".to_string(),
));
let pop1 = f.pop().unwrap();
assert_eq!(pop1.domain, "a.com");
let pop2 = f.pop().unwrap();
assert_eq!(pop2.domain, "b.com"); }
#[test]
fn frontier_empty_pop_returns_none() {
let f = Frontier::new();
assert!(f.pop().is_none());
}
#[test]
fn frontier_all_domains_empty_pop_returns_none() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/1".to_string(),
0.5,
"a.com".to_string(),
));
f.pop();
assert!(f.pop().is_none());
assert_eq!(f.domain_count(), 1); assert_eq!(f.domain_len("a.com"), 0);
}
#[test]
fn frontier_domain_len_nonexistent_returns_zero() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/1".to_string(),
0.5,
"a.com".to_string(),
));
assert_eq!(f.domain_len("a.com"), 1);
assert_eq!(f.domain_len("b.com"), 0);
assert_eq!(f.domain_len("nonexistent"), 0);
}
#[test]
fn frontier_mixed_scores_and_domains() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/low".to_string(),
0.1,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://b.com/high".to_string(),
0.9,
"b.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/high".to_string(),
0.8,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://b.com/low".to_string(),
0.2,
"b.com".to_string(),
));
let pop1 = f.pop().unwrap();
assert_eq!(pop1.domain, "a.com");
assert_eq!(pop1.url, "https://a.com/high");
let pop2 = f.pop().unwrap();
assert_eq!(pop2.domain, "b.com");
assert_eq!(pop2.url, "https://b.com/high");
let pop3 = f.pop().unwrap();
assert_eq!(pop3.domain, "a.com");
assert_eq!(pop3.url, "https://a.com/low");
let pop4 = f.pop().unwrap();
assert_eq!(pop4.domain, "b.com");
assert_eq!(pop4.url, "https://b.com/low");
assert!(f.is_empty());
}
#[test]
fn frontier_same_score_fifo_within_domain() {
let f = Frontier::new();
f.push(ScoredUrl::with_domain(
"https://a.com/1".to_string(),
0.5,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/2".to_string(),
0.5,
"a.com".to_string(),
));
f.push(ScoredUrl::with_domain(
"https://a.com/3".to_string(),
0.5,
"a.com".to_string(),
));
let mut urls = Vec::new();
while let Some(s) = f.pop() {
urls.push(s.url);
}
assert_eq!(urls.len(), 3);
assert!(urls.contains(&"https://a.com/1".to_string()));
assert!(urls.contains(&"https://a.com/2".to_string()));
assert!(urls.contains(&"https://a.com/3".to_string()));
}
}