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 smallvec::SmallVec;
11
12use crate::entity::EntityId;
13use crate::world::World;
14
15use super::{DispatchDecision, DispatchManifest, DispatchStrategy, ElevatorGroup};
16
17/// Tolerance for floating-point position comparisons.
18const EPSILON: f64 = 1e-9;
19
20/// Direction of travel for the SCAN algorithm.
21#[derive(Debug, Clone, Copy, PartialEq, Eq)]
22#[non_exhaustive]
23pub(crate) enum ScanDirection {
24    /// Traveling upward (increasing position).
25    Up,
26    /// Traveling downward (decreasing position).
27    Down,
28}
29
30/// Elevator dispatch using the SCAN (elevator) algorithm.
31///
32/// Serves all requests in the current direction of travel before reversing.
33pub struct ScanDispatch {
34    /// Per-elevator sweep direction.
35    direction: HashMap<EntityId, ScanDirection>,
36}
37
38impl ScanDispatch {
39    /// Create a new `ScanDispatch` with no initial direction state.
40    #[must_use]
41    pub fn new() -> Self {
42        Self {
43            direction: HashMap::new(),
44        }
45    }
46}
47
48impl Default for ScanDispatch {
49    fn default() -> Self {
50        Self::new()
51    }
52}
53
54impl DispatchStrategy for ScanDispatch {
55    fn decide(
56        &mut self,
57        elevator: EntityId,
58        elevator_position: f64,
59        group: &ElevatorGroup,
60        manifest: &DispatchManifest,
61        world: &World,
62    ) -> DispatchDecision {
63        let direction = self
64            .direction
65            .get(&elevator)
66            .copied()
67            .unwrap_or(ScanDirection::Up);
68
69        // Collect "interesting" stops: stops with demand or rider destinations.
70        let mut interesting: SmallVec<[(EntityId, f64); 32]> = SmallVec::new();
71
72        for &stop_eid in group.stop_entities() {
73            if manifest.has_demand(stop_eid)
74                && let Some(pos) = world.stop_position(stop_eid)
75            {
76                interesting.push((stop_eid, pos));
77            }
78        }
79
80        if interesting.is_empty() {
81            return DispatchDecision::Idle;
82        }
83
84        let pos = elevator_position;
85
86        // Partition into ahead and behind based on current direction.
87        let (ahead, behind): (SmallVec<[_; 32]>, SmallVec<[_; 32]>) = match direction {
88            ScanDirection::Up => interesting.iter().partition(|(_, p)| *p > pos + EPSILON),
89            ScanDirection::Down => interesting.iter().partition(|(_, p)| *p < pos - EPSILON),
90        };
91
92        if !ahead.is_empty() {
93            let nearest = match direction {
94                ScanDirection::Up => ahead
95                    .iter()
96                    .min_by(|a: &&&(EntityId, f64), b: &&&(EntityId, f64)| a.1.total_cmp(&b.1)),
97                ScanDirection::Down => ahead
98                    .iter()
99                    .max_by(|a: &&&(EntityId, f64), b: &&&(EntityId, f64)| a.1.total_cmp(&b.1)),
100            };
101            // ahead is non-empty, so nearest is always Some.
102            if let Some(stop) = nearest {
103                return DispatchDecision::GoToStop(stop.0);
104            }
105        }
106
107        // Nothing ahead — reverse direction.
108        let new_dir = match direction {
109            ScanDirection::Up => ScanDirection::Down,
110            ScanDirection::Down => ScanDirection::Up,
111        };
112        self.direction.insert(elevator, new_dir);
113
114        if behind.is_empty() {
115            // All interesting stops at current position (handled above).
116            return interesting
117                .first()
118                .map_or(DispatchDecision::Idle, |(sid, _)| {
119                    DispatchDecision::GoToStop(*sid)
120                });
121        }
122
123        let nearest = match new_dir {
124            ScanDirection::Up => behind
125                .iter()
126                .min_by(|a: &&&(EntityId, f64), b: &&&(EntityId, f64)| a.1.total_cmp(&b.1)),
127            ScanDirection::Down => behind
128                .iter()
129                .max_by(|a: &&&(EntityId, f64), b: &&&(EntityId, f64)| a.1.total_cmp(&b.1)),
130        };
131
132        // behind is non-empty, so nearest is always Some.
133        nearest.map_or(DispatchDecision::Idle, |stop| {
134            DispatchDecision::GoToStop(stop.0)
135        })
136    }
137
138    fn notify_removed(&mut self, elevator: EntityId) {
139        self.direction.remove(&elevator);
140    }
141}
elevator_core/dispatch/scan.rs

elevator_core/dispatch/
scan.rs
