elevator_core/dispatch/
scan.rs

1//! SCAN (elevator) dispatch algorithm — sweeps end-to-end before reversing.
2//!
3//! Originally described for disk-arm scheduling in Denning, P. J. (1967),
4//! "Effects of Scheduling on File Memory Operations", *Proc. AFIPS Spring
5//! Joint Computer Conference*, 9–21. The same sweep discipline is the
6//! textbook "elevator" algorithm.
7
8use std::collections::{BTreeMap, HashMap};
9
10use crate::entity::EntityId;
11use crate::world::World;
12
13use super::sweep::{self, SweepDirection, SweepMode};
14use super::{DispatchManifest, DispatchStrategy, ElevatorGroup, RankContext, pair_is_useful};
15
16/// Elevator dispatch using the SCAN (elevator) algorithm.
17///
18/// Each car tracks a sweep direction; stops demanded in that direction
19/// receive a positional cost while stops behind are excluded. When
20/// nothing remains ahead, the sweep reverses and the car considers the
21/// reverse side. Direction and mode are resolved once per pass in
22/// [`DispatchStrategy::prepare_car`] so ranking is independent of the
23/// iteration order over stops.
24#[derive(serde::Serialize, serde::Deserialize)]
25pub struct ScanDispatch {
26    /// Per-elevator sweep direction. Persisted across dispatch passes
27    /// (reversed once a sweep exhausts demand ahead) and round-tripped
28    /// through [`DispatchStrategy::snapshot_config`] so a restored sim
29    /// continues the current sweep instead of defaulting to `Up` for
30    /// every car. `BTreeMap` so RON serialization in `snapshot_config`
31    /// is byte-identical across processes (#254 follow-up).
32    direction: BTreeMap<EntityId, SweepDirection>,
33    /// Per-elevator accept mode for the current dispatch pass.
34    /// Overwritten in full by `prepare_car` every pass, so no round-
35    /// trip is needed; `#[serde(skip)]` keeps snapshot bytes compact
36    /// and deterministic across process runs.
37    #[serde(skip)]
38    mode: HashMap<EntityId, SweepMode>,
39}
40
41impl ScanDispatch {
42    /// Create a new `ScanDispatch` with no initial direction state.
43    #[must_use]
44    pub fn new() -> Self {
45        Self {
46            direction: BTreeMap::new(),
47            mode: HashMap::new(),
48        }
49    }
50
51    /// Sweep direction for `car`, defaulting to `Up` for first-time callers.
52    fn direction_for(&self, car: EntityId) -> SweepDirection {
53        self.direction
54            .get(&car)
55            .copied()
56            .unwrap_or(SweepDirection::Up)
57    }
58
59    /// Accept mode for `car` in the current pass, defaulting to `Strict`.
60    fn mode_for(&self, car: EntityId) -> SweepMode {
61        self.mode.get(&car).copied().unwrap_or(SweepMode::Strict)
62    }
63}
64
65impl Default for ScanDispatch {
66    fn default() -> Self {
67        Self::new()
68    }
69}
70
71impl DispatchStrategy for ScanDispatch {
72    fn prepare_car(
73        &mut self,
74        car: EntityId,
75        car_position: f64,
76        group: &ElevatorGroup,
77        manifest: &DispatchManifest,
78        world: &World,
79    ) {
80        let current = self.direction_for(car);
81        if sweep::strict_demand_ahead(current, car_position, group, manifest, world) {
82            self.mode.insert(car, SweepMode::Strict);
83        } else {
84            self.direction.insert(car, current.reversed());
85            self.mode.insert(car, SweepMode::Lenient);
86        }
87    }
88
89    fn rank(&self, ctx: &RankContext<'_>) -> Option<f64> {
90        // Reject un-servable pairs so a full car with only
91        // over-capacity waiting demand at its own stop can't open/close
92        // doors indefinitely. SCAN's direction reversal normally lifts
93        // it out of the self-stop within one tick (strict-ahead excludes
94        // the current position), but the Lenient transition tick would
95        // still rank the self-pair at cost 0 without this guard.
96        if !pair_is_useful(ctx, false) {
97            return None;
98        }
99        sweep::rank(
100            self.mode_for(ctx.car),
101            self.direction_for(ctx.car),
102            ctx.car_position,
103            ctx.stop_position,
104        )
105    }
106
107    fn notify_removed(&mut self, elevator: EntityId) {
108        self.direction.remove(&elevator);
109        self.mode.remove(&elevator);
110    }
111
112    fn builtin_id(&self) -> Option<super::BuiltinStrategy> {
113        Some(super::BuiltinStrategy::Scan)
114    }
115
116    fn snapshot_config(&self) -> Option<String> {
117        ron::to_string(self).ok()
118    }
119
120    fn restore_config(&mut self, serialized: &str) -> Result<(), String> {
121        let restored: Self = ron::from_str(serialized).map_err(|e| e.to_string())?;
122        *self = restored;
123        Ok(())
124    }
125}
elevator_core/dispatch/scan.rs

elevator_core/dispatch/
scan.rs
