vihaco_stdlib/clock/
queue.rs

1// SPDX-FileCopyrightText: 2026 The vihaco Authors
2// SPDX-License-Identifier: MIT
3
4use std::cmp::Ordering;
5use std::collections::BinaryHeap;
6
7use super::{ClockFault, GlobalDuration, GlobalTick};
8
9/// A deterministic event queue ordered by global tick and insertion sequence.
10pub struct GlobalClock<E> {
11    now: GlobalTick,
12    seq: u64,
13    pending: BinaryHeap<Scheduled<E>>,
14}
15
16struct Scheduled<E> {
17    tick: GlobalTick,
18    seq: u64,
19    event: E,
20}
21
22// `BinaryHeap` is a max-heap, so reverse the natural `(tick, seq)` ordering.
23impl<E> Ord for Scheduled<E> {
24    fn cmp(&self, other: &Self) -> Ordering {
25        other
26            .tick
27            .cmp(&self.tick)
28            .then_with(|| other.seq.cmp(&self.seq))
29    }
30}
31
32impl<E> PartialOrd for Scheduled<E> {
33    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
34        Some(self.cmp(other))
35    }
36}
37
38impl<E> PartialEq for Scheduled<E> {
39    fn eq(&self, other: &Self) -> bool {
40        (self.tick, self.seq) == (other.tick, other.seq)
41    }
42}
43
44impl<E> Eq for Scheduled<E> {}
45
46impl<E> GlobalClock<E> {
47    pub fn new() -> Self {
48        Self {
49            now: GlobalTick::ZERO,
50            seq: 0,
51            pending: BinaryHeap::new(),
52        }
53    }
54
55    /// Inserts owned scheduling work at an absolute global tick.
56    pub fn schedule_at(&mut self, tick: GlobalTick, event: E) -> Result<(), ClockFault> {
57        if tick < self.now {
58            return Err(ClockFault::SchedulingInPast);
59        }
60
61        let seq = self
62            .seq
63            .checked_add(1)
64            .ok_or(ClockFault::SequenceOverflow)?;
65        self.seq = seq;
66        self.pending.push(Scheduled { tick, seq, event });
67        Ok(())
68    }
69
70    /// Converts relative work into an absolute global tick.
71    pub fn schedule_after(&mut self, after: GlobalDuration, event: E) -> Result<(), ClockFault> {
72        self.schedule_at(self.now.checked_add(after)?, event)
73    }
74
75    /// Removes the earliest event and advances the current global tick to it.
76    pub fn pop_earliest(&mut self) -> Option<(GlobalTick, E)> {
77        let Scheduled { tick, event, .. } = self.pending.pop()?;
78        self.now = tick;
79        Some((tick, event))
80    }
81
82    pub fn now(&self) -> GlobalTick {
83        self.now
84    }
85
86    pub fn is_empty(&self) -> bool {
87        self.pending.is_empty()
88    }
89}
90
91impl<E> Default for GlobalClock<E> {
92    fn default() -> Self {
93        Self::new()
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100
101    #[test]
102    fn events_are_ordered_by_tick_then_insertion_order() {
103        let mut clock = GlobalClock::new();
104        clock.schedule_at(GlobalTick(10), 10).unwrap();
105        clock.schedule_at(GlobalTick(2), 2).unwrap();
106        clock.schedule_at(GlobalTick(2), 3).unwrap();
107        clock.schedule_at(GlobalTick(1), 1).unwrap();
108
109        assert_eq!(clock.pop_earliest(), Some((GlobalTick(1), 1)));
110        assert_eq!(clock.pop_earliest(), Some((GlobalTick(2), 2)));
111        assert_eq!(clock.pop_earliest(), Some((GlobalTick(2), 3)));
112        assert_eq!(clock.pop_earliest(), Some((GlobalTick(10), 10)));
113        assert_eq!(clock.pop_earliest(), None);
114        assert_eq!(clock.now(), GlobalTick(10));
115    }
116
117    #[test]
118    fn relative_scheduling_uses_current_time() {
119        let mut clock = GlobalClock::new();
120        clock.schedule_at(GlobalTick(4), "first").unwrap();
121        assert_eq!(clock.pop_earliest(), Some((GlobalTick(4), "first")));
122
123        clock.schedule_after(GlobalDuration(3), "second").unwrap();
124        assert_eq!(clock.pop_earliest(), Some((GlobalTick(7), "second")));
125    }
126
127    #[test]
128    fn rejects_scheduling_in_the_past() {
129        let mut clock = GlobalClock::new();
130        clock.schedule_at(GlobalTick(4), ()).unwrap();
131        clock.pop_earliest();
132
133        assert_eq!(
134            clock.schedule_at(GlobalTick(3), ()),
135            Err(ClockFault::SchedulingInPast)
136        );
137    }
138}
vihaco_stdlib/clock/queue.rs

vihaco_stdlib/clock/
queue.rs
