use std::cmp::Ordering;
use std::collections::BinaryHeap;
use std::time::Instant;
const DEFAULT_AGING_FACTOR: f64 = 10.0;
#[derive(Debug, Clone)]
pub struct ScheduledTask {
pub base_priority: u32,
pub enqueued_at: Instant,
aging_factor: f64,
cached_priority: f64,
}
impl ScheduledTask {
pub fn new(base_priority: u32) -> Self {
let enqueued_at = Instant::now();
Self {
base_priority,
enqueued_at,
aging_factor: DEFAULT_AGING_FACTOR,
cached_priority: base_priority as f64,
}
}
pub fn with_enqueued_at(base_priority: u32, enqueued_at: Instant) -> Self {
let waited_secs = enqueued_at.elapsed().as_secs_f64();
let cached_priority = base_priority as f64 + waited_secs / DEFAULT_AGING_FACTOR;
Self {
base_priority,
enqueued_at,
aging_factor: DEFAULT_AGING_FACTOR,
cached_priority,
}
}
pub fn with_aging_factor(base_priority: u32, aging_factor: f64) -> Self {
assert!(aging_factor > 0.0, "aging_factor must be positive");
let enqueued_at = Instant::now();
Self {
base_priority,
enqueued_at,
aging_factor,
cached_priority: base_priority as f64,
}
}
pub fn with_all(base_priority: u32, enqueued_at: Instant, aging_factor: f64) -> Self {
assert!(aging_factor > 0.0, "aging_factor must be positive");
let waited_secs = enqueued_at.elapsed().as_secs_f64();
let cached_priority = base_priority as f64 + waited_secs / aging_factor;
Self {
base_priority,
enqueued_at,
aging_factor,
cached_priority,
}
}
pub fn effective_priority(&self) -> f64 {
let waited_secs = self.enqueued_at.elapsed().as_secs_f64();
self.base_priority as f64 + waited_secs / self.aging_factor
}
pub fn refresh_priority(&mut self) {
self.cached_priority = self.effective_priority();
}
}
impl Ord for ScheduledTask {
fn cmp(&self, other: &Self) -> Ordering {
self.cached_priority
.partial_cmp(&other.cached_priority)
.unwrap_or(Ordering::Equal)
}
}
impl PartialOrd for ScheduledTask {
fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
Some(self.cmp(other))
}
}
impl PartialEq for ScheduledTask {
fn eq(&self, other: &Self) -> bool {
self.cached_priority == other.cached_priority
}
}
impl Eq for ScheduledTask {}
pub struct PriorityQueue {
heap: BinaryHeap<ScheduledTask>,
}
impl PriorityQueue {
pub fn new() -> Self {
Self {
heap: BinaryHeap::new(),
}
}
pub fn with_capacity(capacity: usize) -> Self {
Self {
heap: BinaryHeap::with_capacity(capacity),
}
}
pub fn push(&mut self, task: ScheduledTask) {
self.heap.push(task);
}
pub fn pop(&mut self) -> Option<ScheduledTask> {
self.heap.pop()
}
pub fn peek(&self) -> Option<&ScheduledTask> {
self.heap.peek()
}
pub fn len(&self) -> usize {
self.heap.len()
}
pub fn is_empty(&self) -> bool {
self.heap.is_empty()
}
}
impl Default for PriorityQueue {
fn default() -> Self {
Self::new()
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::time::Duration;
fn task_enqueued_ago(base_priority: u32, secs_ago: u64) -> ScheduledTask {
let enqueued_at = Instant::now() - Duration::from_secs(secs_ago);
ScheduledTask::with_enqueued_at(base_priority, enqueued_at)
}
#[test]
fn test_pop_returns_highest_base_priority_when_no_aging() {
let mut q = PriorityQueue::new();
q.push(ScheduledTask::new(1));
q.push(ScheduledTask::new(5));
q.push(ScheduledTask::new(3));
let first = q.pop().unwrap();
let second = q.pop().unwrap();
let third = q.pop().unwrap();
assert_eq!(first.base_priority, 5);
assert_eq!(second.base_priority, 3);
assert_eq!(third.base_priority, 1);
}
#[test]
fn test_pop_returns_none_when_empty() {
let mut q = PriorityQueue::new();
assert!(q.is_empty());
assert!(q.pop().is_none());
}
#[test]
fn test_peek_does_not_remove() {
let mut q = PriorityQueue::new();
q.push(ScheduledTask::new(10));
assert_eq!(q.len(), 1);
assert_eq!(q.peek().unwrap().base_priority, 10);
assert_eq!(q.len(), 1);
}
#[test]
fn test_len_and_is_empty() {
let mut q = PriorityQueue::new();
assert!(q.is_empty());
assert_eq!(q.len(), 0);
q.push(ScheduledTask::new(1));
q.push(ScheduledTask::new(2));
assert_eq!(q.len(), 2);
assert!(!q.is_empty());
q.pop();
assert_eq!(q.len(), 1);
}
#[test]
fn test_aging_promotes_low_priority_task_after_long_wait() {
let mut q = PriorityQueue::new();
q.push(task_enqueued_ago(1, 60));
q.push(ScheduledTask::new(5));
let first = q.pop().unwrap();
assert_eq!(
first.base_priority, 1,
"等待 60s 的低优先级任务(effective≈7)应先于新入队的高优先级任务(effective≈5)出队"
);
}
#[test]
fn test_aging_does_not_starve_high_priority_short_wait() {
let mut q = PriorityQueue::new();
q.push(task_enqueued_ago(10, 0));
q.push(task_enqueued_ago(1, 1));
let first = q.pop().unwrap();
assert_eq!(first.base_priority, 10);
}
#[test]
fn test_aging_cross_over_boundary() {
let mut q = PriorityQueue::new();
q.push(task_enqueued_ago(1, 91));
q.push(ScheduledTask::new(10));
let first = q.pop().unwrap();
assert_eq!(first.base_priority, 1);
}
#[test]
fn test_custom_aging_factor_accelerates_promotion() {
let mut q = PriorityQueue::new();
let enqueued_at = Instant::now() - Duration::from_secs(5);
q.push(ScheduledTask::with_all(1, enqueued_at, 1.0));
q.push(ScheduledTask::with_all(5, enqueued_at, 10.0));
let first = q.pop().unwrap();
assert_eq!(first.base_priority, 1);
}
#[test]
fn test_custom_aging_factor_slows_promotion() {
let mut q = PriorityQueue::new();
let enqueued_at = Instant::now() - Duration::from_secs(60);
q.push(ScheduledTask::with_all(1, enqueued_at, 100.0));
q.push(ScheduledTask::with_all(5, enqueued_at, 100.0));
let first = q.pop().unwrap();
assert_eq!(first.base_priority, 5);
}
#[test]
#[should_panic(expected = "aging_factor must be positive")]
fn test_zero_aging_factor_panics() {
let _ = ScheduledTask::with_aging_factor(1, 0.0);
}
#[test]
fn test_low_priority_eventually_dispatched_under_high_priority_stream() {
let mut q = PriorityQueue::new();
let low = task_enqueued_ago(1, 200); q.push(low);
for _ in 0..1000 {
q.push(ScheduledTask::new(10)); }
let first = q.pop().unwrap();
assert_eq!(first.base_priority, 1);
}
#[test]
fn test_effective_priority_increases_with_wait_time() {
let task = task_enqueued_ago(5, 0);
let p0 = task.effective_priority();
std::thread::sleep(Duration::from_millis(50));
let p1 = task.effective_priority();
assert!(p1 > p0, "等待后 effective_priority 必须上升");
assert!(p1 - p0 < 1.0, "50ms 内提升幅度应远小于 1.0");
}
#[test]
fn test_with_aging_factor_valid_value() {
let task = ScheduledTask::with_aging_factor(5, 2.0);
assert_eq!(task.base_priority, 5);
assert!((task.aging_factor - 2.0).abs() < f64::EPSILON);
}
#[test]
fn test_with_aging_factor_cached_priority_equals_base() {
let task = ScheduledTask::with_aging_factor(10, 5.0);
assert!((task.cached_priority - 10.0).abs() < 0.01);
}
#[test]
fn test_refresh_priority_updates_cached_value() {
let mut task = ScheduledTask::new(5);
let old_cached = task.cached_priority;
std::thread::sleep(Duration::from_millis(50));
task.refresh_priority();
assert!(
task.cached_priority >= old_cached,
"refresh_priority 应更新缓存值"
);
}
#[test]
fn test_partial_eq_same_priority() {
let a = ScheduledTask::new(5);
let b = ScheduledTask::new(5);
assert_eq!(a, b, "相同 base_priority 的任务应相等");
}
#[test]
fn test_partial_eq_different_priority() {
let a = ScheduledTask::new(5);
let b = ScheduledTask::new(10);
assert_ne!(a, b, "不同 base_priority 的任务不应相等");
}
#[test]
fn test_priority_queue_with_capacity() {
let q = PriorityQueue::with_capacity(100);
assert!(q.is_empty());
}
#[test]
fn test_priority_queue_default() {
let q = PriorityQueue::default();
assert!(q.is_empty());
assert_eq!(q.len(), 0);
}
}