elevator_core/dispatch/
look.rs

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

elevator_core/dispatch/
look.rs
