elevator_core/dispatch/
scan.rs

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

elevator_core/dispatch/
scan.rs
