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::HashMap;
9
10use crate::entity::EntityId;
11use crate::world::World;
12
13use super::sweep::{self, SweepDirection, SweepMode};
14use super::{DispatchManifest, DispatchStrategy, ElevatorGroup, RankContext, pair_can_do_work};
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.
24pub struct ScanDispatch {
25    /// Per-elevator sweep direction.
26    direction: HashMap<EntityId, SweepDirection>,
27    /// Per-elevator accept mode for the current dispatch pass.
28    mode: HashMap<EntityId, SweepMode>,
29}
30
31impl ScanDispatch {
32    /// Create a new `ScanDispatch` with no initial direction state.
33    #[must_use]
34    pub fn new() -> Self {
35        Self {
36            direction: HashMap::new(),
37            mode: HashMap::new(),
38        }
39    }
40
41    /// Sweep direction for `car`, defaulting to `Up` for first-time callers.
42    fn direction_for(&self, car: EntityId) -> SweepDirection {
43        self.direction
44            .get(&car)
45            .copied()
46            .unwrap_or(SweepDirection::Up)
47    }
48
49    /// Accept mode for `car` in the current pass, defaulting to `Strict`.
50    fn mode_for(&self, car: EntityId) -> SweepMode {
51        self.mode.get(&car).copied().unwrap_or(SweepMode::Strict)
52    }
53}
54
55impl Default for ScanDispatch {
56    fn default() -> Self {
57        Self::new()
58    }
59}
60
61impl DispatchStrategy for ScanDispatch {
62    fn prepare_car(
63        &mut self,
64        car: EntityId,
65        car_position: f64,
66        group: &ElevatorGroup,
67        manifest: &DispatchManifest,
68        world: &World,
69    ) {
70        let current = self.direction_for(car);
71        if sweep::strict_demand_ahead(current, car_position, group, manifest, world) {
72            self.mode.insert(car, SweepMode::Strict);
73        } else {
74            self.direction.insert(car, current.reversed());
75            self.mode.insert(car, SweepMode::Lenient);
76        }
77    }
78
79    fn rank(&mut self, ctx: &RankContext<'_>) -> Option<f64> {
80        // Reject un-servable pairs so a full car with only
81        // over-capacity waiting demand at its own stop can't open/close
82        // doors indefinitely. SCAN's direction reversal normally lifts
83        // it out of the self-stop within one tick (strict-ahead excludes
84        // the current position), but the Lenient transition tick would
85        // still rank the self-pair at cost 0 without this guard.
86        if !pair_can_do_work(ctx) {
87            return None;
88        }
89        sweep::rank(
90            self.mode_for(ctx.car),
91            self.direction_for(ctx.car),
92            ctx.car_position,
93            ctx.stop_position,
94        )
95    }
96
97    fn notify_removed(&mut self, elevator: EntityId) {
98        self.direction.remove(&elevator);
99        self.mode.remove(&elevator);
100    }
101
102    fn builtin_id(&self) -> Option<super::BuiltinStrategy> {
103        Some(super::BuiltinStrategy::Scan)
104    }
105}
elevator_core/dispatch/scan.rs

elevator_core/dispatch/
scan.rs
