solverforge_solver/phase/construction/placer/
queued.rs

1/// A queued entity placer that processes entities in order.
2///
3/// For each uninitialized entity, generates change moves for all possible values.
4/// Uses concrete function pointers for zero-erasure access.
5///
6/// # Type Parameters
7/// * `S` - The planning solution type
8/// * `V` - The value type
9/// * `ES` - The entity selector type
10/// * `VS` - The value selector type
11pub struct QueuedEntityPlacer<S, V, ES, VS>
12where
13    S: PlanningSolution,
14    ES: EntitySelector<S>,
15    VS: ValueSelector<S, V>,
16{
17    // The entity selector.
18    entity_selector: ES,
19    // The value selector.
20    value_selector: VS,
21    // Concrete getter function pointer.
22    getter: fn(&S, usize, usize) -> Option<V>,
23    // Concrete setter function pointer.
24    setter: fn(&mut S, usize, usize, Option<V>),
25    variable_index: usize,
26    // The variable name.
27    variable_name: &'static str,
28    // The descriptor index.
29    descriptor_index: usize,
30    // Whether the variable can remain unassigned during construction.
31    allows_unassigned: bool,
32    _phantom: PhantomData<fn() -> V>,
33}
34
35// Entity visits between wall-clock stop checks inside one placement scan.
36const STOP_POLL_INTERVAL: u64 = 64;
37
38impl<S, V, ES, VS> QueuedEntityPlacer<S, V, ES, VS>
39where
40    S: PlanningSolution,
41    ES: EntitySelector<S>,
42    VS: ValueSelector<S, V>,
43{
44    pub fn new(
45        entity_selector: ES,
46        value_selector: VS,
47        getter: fn(&S, usize, usize) -> Option<V>,
48        setter: fn(&mut S, usize, usize, Option<V>),
49        descriptor_index: usize,
50        variable_index: usize,
51        variable_name: &'static str,
52    ) -> Self {
53        Self {
54            entity_selector,
55            value_selector,
56            getter,
57            setter,
58            variable_index,
59            variable_name,
60            descriptor_index,
61            allows_unassigned: false,
62            _phantom: PhantomData,
63        }
64    }
65
66    pub fn with_allows_unassigned(mut self, allows_unassigned: bool) -> Self {
67        self.allows_unassigned = allows_unassigned;
68        self
69    }
70}
71
72impl<S, V, ES, VS> Debug for QueuedEntityPlacer<S, V, ES, VS>
73where
74    S: PlanningSolution,
75    ES: EntitySelector<S> + Debug,
76    VS: ValueSelector<S, V> + Debug,
77{
78    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
79        f.debug_struct("QueuedEntityPlacer")
80            .field("entity_selector", &self.entity_selector)
81            .field("value_selector", &self.value_selector)
82            .field("variable_name", &self.variable_name)
83            .field("allows_unassigned", &self.allows_unassigned)
84            .finish()
85    }
86}
87
88struct QueuedLiveCandidateStore<S, V>
89where
90    S: PlanningSolution,
91    V: Clone + PartialEq + Send + Sync + Debug + 'static,
92{
93    primary: Option<(CandidateId, ChangeMove<S, V>)>,
94    overflow: Vec<(CandidateId, ChangeMove<S, V>)>,
95    next_id: usize,
96}
97
98impl<S, V> QueuedLiveCandidateStore<S, V>
99where
100    S: PlanningSolution,
101    V: Clone + PartialEq + Send + Sync + Debug + 'static,
102{
103    fn new() -> Self {
104        Self {
105            primary: None,
106            overflow: Vec::new(),
107            next_id: 0,
108        }
109    }
110
111    fn push(&mut self, mov: ChangeMove<S, V>) -> CandidateId {
112        let id = CandidateId::new(self.next_id);
113        self.next_id += 1;
114        if self.primary.is_none() {
115            self.primary = Some((id, mov));
116        } else {
117            self.overflow.push((id, mov));
118        }
119        id
120    }
121
122    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ChangeMove<S, V>>> {
123        self.primary
124            .as_ref()
125            .filter(|(candidate_id, _)| *candidate_id == id)
126            .map(|(_, mov)| MoveCandidateRef::Borrowed(mov))
127            .or_else(|| {
128                self.overflow
129                    .iter()
130                    .find(|(candidate_id, _)| *candidate_id == id)
131                    .map(|(_, mov)| MoveCandidateRef::Borrowed(mov))
132            })
133    }
134
135    fn take_candidate(&mut self, id: CandidateId) -> ChangeMove<S, V> {
136        if self
137            .primary
138            .as_ref()
139            .is_some_and(|(candidate_id, _)| *candidate_id == id)
140        {
141            let (_, mov) = self
142                .primary
143                .take()
144                .expect("checked queued construction candidate must remain live");
145            self.primary = self.overflow.pop();
146            return mov;
147        }
148        let index = self
149            .overflow
150            .iter()
151            .position(|(candidate_id, _)| *candidate_id == id)
152            .expect("queued construction candidate id must remain live");
153        self.overflow.swap_remove(index).1
154    }
155
156    fn release_candidate(&mut self, id: CandidateId) -> bool {
157        if self.candidate(id).is_none() {
158            return false;
159        }
160        drop(self.take_candidate(id));
161        true
162    }
163}
164
165pub struct QueuedPlacementCandidateCursor<S, V>
166where
167    S: PlanningSolution,
168    V: Clone + PartialEq + Send + Sync + Debug + 'static,
169{
170    store: QueuedLiveCandidateStore<S, V>,
171    values: std::vec::IntoIter<V>,
172    entity_index: usize,
173    getter: fn(&S, usize, usize) -> Option<V>,
174    setter: fn(&mut S, usize, usize, Option<V>),
175    variable_index: usize,
176    variable_name: &'static str,
177    descriptor_index: usize,
178}
179
180impl<S, V> MoveCursor<S, ChangeMove<S, V>> for QueuedPlacementCandidateCursor<S, V>
181where
182    S: PlanningSolution,
183    V: Clone + PartialEq + Send + Sync + Debug + 'static,
184{
185    fn next_candidate(&mut self) -> Option<CandidateId> {
186        let value = self.values.next()?;
187        Some(self.store.push(ChangeMove::new(
188            self.entity_index,
189            Some(value),
190            self.getter,
191            self.setter,
192            self.variable_index,
193            self.variable_name,
194            self.descriptor_index,
195        )))
196    }
197
198    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ChangeMove<S, V>>> {
199        self.store.candidate(id)
200    }
201
202    fn take_candidate(&mut self, id: CandidateId) -> ChangeMove<S, V> {
203        self.store.take_candidate(id)
204    }
205
206    #[inline(always)]
207    fn next_owned_candidate(&mut self) -> Option<ChangeMove<S, V>> {
208        let value = self.values.next()?;
209        Some(ChangeMove::new(
210            self.entity_index,
211            Some(value),
212            self.getter,
213            self.setter,
214            self.variable_index,
215            self.variable_name,
216            self.descriptor_index,
217        ))
218    }
219
220    fn release_candidate(&mut self, id: CandidateId) -> bool {
221        self.store.release_candidate(id)
222    }
223}
224
225pub struct QueuedEntityPlacerCursor<'a, S, V, ES, VS>
226where
227    S: PlanningSolution,
228    ES: EntitySelector<S>,
229    VS: ValueSelector<S, V>,
230{
231    placer: &'a QueuedEntityPlacer<S, V, ES, VS>,
232    entities: std::vec::IntoIter<EntityReference>,
233}
234
235impl<S, V, ES, VS> EntityPlacerCursor<S, ChangeMove<S, V>>
236    for QueuedEntityPlacerCursor<'_, S, V, ES, VS>
237where
238    S: PlanningSolution,
239    V: Clone + PartialEq + Send + Sync + Debug + 'static,
240    ES: EntitySelector<S>,
241    VS: ValueSelector<S, V>,
242{
243    type CandidateCursor = QueuedPlacementCandidateCursor<S, V>;
244
245    fn next_placement<D, IsCompleted, ShouldStop>(
246        &mut self,
247        score_director: &D,
248        mut is_completed: IsCompleted,
249        mut should_stop: ShouldStop,
250    ) -> Option<Placement<S, ChangeMove<S, V>, Self::CandidateCursor>>
251    where
252        D: Director<S>,
253        IsCompleted: FnMut(&Placement<S, ChangeMove<S, V>, Self::CandidateCursor>) -> bool,
254        ShouldStop: FnMut() -> bool,
255    {
256        // The wall-clock stop check reads the solver clock; iterating every
257        // assigned-away entity through it costs real throughput at scale.
258        // The per-placement poll in the construction phase still enforces
259        // the limit, so this loop batches its own stop checks.
260        let mut visited = 0u64;
261        loop {
262            visited += 1;
263            if visited.is_multiple_of(STOP_POLL_INTERVAL) && should_stop() {
264                return None;
265            }
266            let entity_ref = self.entities.next()?;
267            if (self.placer.getter)(
268                score_director.working_solution(),
269                entity_ref.entity_index,
270                self.placer.variable_index,
271            )
272            .is_some()
273            {
274                continue;
275            }
276            let values = self
277                .placer
278                .value_selector
279                .iter(
280                    score_director,
281                    entity_ref.descriptor_index,
282                    entity_ref.entity_index,
283                )
284                .collect::<Vec<_>>();
285            if values.is_empty() {
286                continue;
287            }
288            let placement = Placement::new(
289                entity_ref,
290                QueuedPlacementCandidateCursor {
291                    store: QueuedLiveCandidateStore::new(),
292                    values: values.into_iter(),
293                    entity_index: entity_ref.entity_index,
294                    getter: self.placer.getter,
295                    setter: self.placer.setter,
296                    variable_index: self.placer.variable_index,
297                    variable_name: self.placer.variable_name,
298                    descriptor_index: self.placer.descriptor_index,
299                },
300            )
301            .with_keep_current_legal(self.placer.allows_unassigned);
302            if !is_completed(&placement) {
303                return Some(placement);
304            }
305        }
306    }
307}
308
309impl<S, V, ES, VS> EntityPlacer<S, ChangeMove<S, V>> for QueuedEntityPlacer<S, V, ES, VS>
310where
311    S: PlanningSolution,
312    V: Clone + PartialEq + Send + Sync + Debug + 'static,
313    ES: EntitySelector<S>,
314    VS: ValueSelector<S, V>,
315{
316    type Cursor<'a>
317        = QueuedEntityPlacerCursor<'a, S, V, ES, VS>
318    where
319        Self: 'a;
320
321    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
322        QueuedEntityPlacerCursor {
323            placer: self,
324            entities: self
325                .entity_selector
326                .iter(score_director)
327                .collect::<Vec<_>>()
328                .into_iter(),
329        }
330    }
331}
solverforge_solver/phase/construction/placer/queued.rs

solverforge_solver/phase/construction/placer/
queued.rs
