elevator_core/dispatch/
look.rs

1//! LOOK dispatch algorithm — reverses at the last request, not the shaft end.
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.
16#[derive(Debug, Clone, Copy, PartialEq, Eq)]
17#[non_exhaustive]
18pub(crate) enum Direction {
19    /// Traveling upward (increasing position).
20    Up,
21    /// Traveling downward (decreasing position).
22    Down,
23}
24
25/// Elevator dispatch using the LOOK algorithm.
26///
27/// Like SCAN, but reverses at the last request in the current direction
28/// instead of traveling to the end of the shaft. More efficient than
29/// pure SCAN for sparse request distributions.
30///
31/// This is the standard "elevator algorithm" used in real buildings.
32pub struct LookDispatch {
33    /// Per-elevator sweep direction.
34    direction: HashMap<EntityId, Direction>,
35}
36
37impl LookDispatch {
38    /// Create a new `LookDispatch` with no initial direction state.
39    #[must_use]
40    pub fn new() -> Self {
41        Self {
42            direction: HashMap::new(),
43        }
44    }
45}
46
47impl Default for LookDispatch {
48    fn default() -> Self {
49        Self::new()
50    }
51}
52
53impl DispatchStrategy for LookDispatch {
54    fn decide(
55        &mut self,
56        elevator: EntityId,
57        elevator_position: f64,
58        group: &ElevatorGroup,
59        manifest: &DispatchManifest,
60        world: &World,
61    ) -> DispatchDecision {
62        let direction = self
63            .direction
64            .get(&elevator)
65            .copied()
66            .unwrap_or(Direction::Up);
67
68        // Collect stops with demand or rider destinations.
69        let mut interesting: SmallVec<[(EntityId, f64); 32]> = SmallVec::new();
70
71        for &stop_eid in group.stop_entities() {
72            if manifest.has_demand(stop_eid)
73                && let Some(pos) = world.stop_position(stop_eid)
74            {
75                interesting.push((stop_eid, pos));
76            }
77        }
78
79        if interesting.is_empty() {
80            return DispatchDecision::Idle;
81        }
82
83        let pos = elevator_position;
84
85        // Partition into ahead (in current direction) and behind.
86        let (ahead, behind): (SmallVec<[_; 32]>, SmallVec<[_; 32]>) = match direction {
87            Direction::Up => interesting.iter().partition(|(_, p)| *p > pos + EPSILON),
88            Direction::Down => interesting.iter().partition(|(_, p)| *p < pos - EPSILON),
89        };
90
91        if !ahead.is_empty() {
92            // Continue in current direction — pick nearest ahead.
93            let nearest = match direction {
94                Direction::Up => ahead
95                    .iter()
96                    .min_by(|a: &&&(EntityId, f64), b: &&&(EntityId, f64)| a.1.total_cmp(&b.1)),
97                Direction::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        // No requests ahead — reverse direction (LOOK behavior).
108        let new_dir = match direction {
109            Direction::Up => Direction::Down,
110            Direction::Down => Direction::Up,
111        };
112        self.direction.insert(elevator, new_dir);
113
114        if behind.is_empty() {
115            // All interesting stops at current position.
116            return interesting
117                .first()
118                .map_or(DispatchDecision::Idle, |(sid, _)| {
119                    DispatchDecision::GoToStop(*sid)
120                });
121        }
122
123        // Pick nearest in new direction.
124        let nearest = match new_dir {
125            Direction::Up => behind
126                .iter()
127                .min_by(|a: &&&(EntityId, f64), b: &&&(EntityId, f64)| a.1.total_cmp(&b.1)),
128            Direction::Down => behind
129                .iter()
130                .max_by(|a: &&&(EntityId, f64), b: &&&(EntityId, f64)| a.1.total_cmp(&b.1)),
131        };
132
133        // behind is non-empty, so nearest is always Some.
134        nearest.map_or(DispatchDecision::Idle, |stop| {
135            DispatchDecision::GoToStop(stop.0)
136        })
137    }
138
139    fn notify_removed(&mut self, elevator: EntityId) {
140        self.direction.remove(&elevator);
141    }
142}
elevator_core/dispatch/look.rs

elevator_core/dispatch/
look.rs
