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
35impl<S, V, ES, VS> QueuedEntityPlacer<S, V, ES, VS>
36where
37    S: PlanningSolution,
38    ES: EntitySelector<S>,
39    VS: ValueSelector<S, V>,
40{
41    pub fn new(
42        entity_selector: ES,
43        value_selector: VS,
44        getter: fn(&S, usize, usize) -> Option<V>,
45        setter: fn(&mut S, usize, usize, Option<V>),
46        descriptor_index: usize,
47        variable_index: usize,
48        variable_name: &'static str,
49    ) -> Self {
50        Self {
51            entity_selector,
52            value_selector,
53            getter,
54            setter,
55            variable_index,
56            variable_name,
57            descriptor_index,
58            allows_unassigned: false,
59            _phantom: PhantomData,
60        }
61    }
62
63    pub fn with_allows_unassigned(mut self, allows_unassigned: bool) -> Self {
64        self.allows_unassigned = allows_unassigned;
65        self
66    }
67}
68
69impl<S, V, ES, VS> Debug for QueuedEntityPlacer<S, V, ES, VS>
70where
71    S: PlanningSolution,
72    ES: EntitySelector<S> + Debug,
73    VS: ValueSelector<S, V> + Debug,
74{
75    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
76        f.debug_struct("QueuedEntityPlacer")
77            .field("entity_selector", &self.entity_selector)
78            .field("value_selector", &self.value_selector)
79            .field("variable_name", &self.variable_name)
80            .field("allows_unassigned", &self.allows_unassigned)
81            .finish()
82    }
83}
84
85struct QueuedLiveCandidateStore<S, V>
86where
87    S: PlanningSolution,
88    V: Clone + PartialEq + Send + Sync + Debug + 'static,
89{
90    primary: Option<(CandidateId, ChangeMove<S, V>)>,
91    overflow: Vec<(CandidateId, ChangeMove<S, V>)>,
92    next_id: usize,
93}
94
95impl<S, V> QueuedLiveCandidateStore<S, V>
96where
97    S: PlanningSolution,
98    V: Clone + PartialEq + Send + Sync + Debug + 'static,
99{
100    fn new() -> Self {
101        Self {
102            primary: None,
103            overflow: Vec::new(),
104            next_id: 0,
105        }
106    }
107
108    fn push(&mut self, mov: ChangeMove<S, V>) -> CandidateId {
109        let id = CandidateId::new(self.next_id);
110        self.next_id += 1;
111        if self.primary.is_none() {
112            self.primary = Some((id, mov));
113        } else {
114            self.overflow.push((id, mov));
115        }
116        id
117    }
118
119    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ChangeMove<S, V>>> {
120        self.primary
121            .as_ref()
122            .filter(|(candidate_id, _)| *candidate_id == id)
123            .map(|(_, mov)| MoveCandidateRef::Borrowed(mov))
124            .or_else(|| {
125                self.overflow
126                    .iter()
127                    .find(|(candidate_id, _)| *candidate_id == id)
128                    .map(|(_, mov)| MoveCandidateRef::Borrowed(mov))
129            })
130    }
131
132    fn take_candidate(&mut self, id: CandidateId) -> ChangeMove<S, V> {
133        if self
134            .primary
135            .as_ref()
136            .is_some_and(|(candidate_id, _)| *candidate_id == id)
137        {
138            let (_, mov) = self
139                .primary
140                .take()
141                .expect("checked queued construction candidate must remain live");
142            self.primary = self.overflow.pop();
143            return mov;
144        }
145        let index = self
146            .overflow
147            .iter()
148            .position(|(candidate_id, _)| *candidate_id == id)
149            .expect("queued construction candidate id must remain live");
150        self.overflow.swap_remove(index).1
151    }
152
153    fn release_candidate(&mut self, id: CandidateId) -> bool {
154        if self.candidate(id).is_none() {
155            return false;
156        }
157        drop(self.take_candidate(id));
158        true
159    }
160}
161
162pub struct QueuedPlacementCandidateCursor<S, V>
163where
164    S: PlanningSolution,
165    V: Clone + PartialEq + Send + Sync + Debug + 'static,
166{
167    store: QueuedLiveCandidateStore<S, V>,
168    values: std::vec::IntoIter<V>,
169    entity_index: usize,
170    getter: fn(&S, usize, usize) -> Option<V>,
171    setter: fn(&mut S, usize, usize, Option<V>),
172    variable_index: usize,
173    variable_name: &'static str,
174    descriptor_index: usize,
175}
176
177impl<S, V> MoveCursor<S, ChangeMove<S, V>> for QueuedPlacementCandidateCursor<S, V>
178where
179    S: PlanningSolution,
180    V: Clone + PartialEq + Send + Sync + Debug + 'static,
181{
182    fn next_candidate(&mut self) -> Option<CandidateId> {
183        let value = self.values.next()?;
184        Some(self.store.push(ChangeMove::new(
185            self.entity_index,
186            Some(value),
187            self.getter,
188            self.setter,
189            self.variable_index,
190            self.variable_name,
191            self.descriptor_index,
192        )))
193    }
194
195    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ChangeMove<S, V>>> {
196        self.store.candidate(id)
197    }
198
199    fn take_candidate(&mut self, id: CandidateId) -> ChangeMove<S, V> {
200        self.store.take_candidate(id)
201    }
202
203    #[inline(always)]
204    fn next_owned_candidate(&mut self) -> Option<ChangeMove<S, V>> {
205        let value = self.values.next()?;
206        Some(ChangeMove::new(
207            self.entity_index,
208            Some(value),
209            self.getter,
210            self.setter,
211            self.variable_index,
212            self.variable_name,
213            self.descriptor_index,
214        ))
215    }
216
217    fn release_candidate(&mut self, id: CandidateId) -> bool {
218        self.store.release_candidate(id)
219    }
220}
221
222pub struct QueuedEntityPlacerCursor<'a, S, V, ES, VS>
223where
224    S: PlanningSolution,
225    ES: EntitySelector<S>,
226    VS: ValueSelector<S, V>,
227{
228    placer: &'a QueuedEntityPlacer<S, V, ES, VS>,
229    entities: std::vec::IntoIter<EntityReference>,
230}
231
232impl<S, V, ES, VS> EntityPlacerCursor<S, ChangeMove<S, V>>
233    for QueuedEntityPlacerCursor<'_, S, V, ES, VS>
234where
235    S: PlanningSolution,
236    V: Clone + PartialEq + Send + Sync + Debug + 'static,
237    ES: EntitySelector<S>,
238    VS: ValueSelector<S, V>,
239{
240    type CandidateCursor = QueuedPlacementCandidateCursor<S, V>;
241
242    fn next_placement<D, IsCompleted, ShouldStop>(
243        &mut self,
244        score_director: &D,
245        mut is_completed: IsCompleted,
246        mut should_stop: ShouldStop,
247    ) -> Option<Placement<S, ChangeMove<S, V>, Self::CandidateCursor>>
248    where
249        D: Director<S>,
250        IsCompleted: FnMut(&Placement<S, ChangeMove<S, V>, Self::CandidateCursor>) -> bool,
251        ShouldStop: FnMut() -> bool,
252    {
253        while !should_stop() {
254            let entity_ref = self.entities.next()?;
255            if (self.placer.getter)(
256                score_director.working_solution(),
257                entity_ref.entity_index,
258                self.placer.variable_index,
259            )
260            .is_some()
261            {
262                continue;
263            }
264            let values = self
265                .placer
266                .value_selector
267                .iter(
268                    score_director,
269                    entity_ref.descriptor_index,
270                    entity_ref.entity_index,
271                )
272                .collect::<Vec<_>>();
273            if values.is_empty() {
274                continue;
275            }
276            let placement = Placement::new(
277                entity_ref,
278                QueuedPlacementCandidateCursor {
279                    store: QueuedLiveCandidateStore::new(),
280                    values: values.into_iter(),
281                    entity_index: entity_ref.entity_index,
282                    getter: self.placer.getter,
283                    setter: self.placer.setter,
284                    variable_index: self.placer.variable_index,
285                    variable_name: self.placer.variable_name,
286                    descriptor_index: self.placer.descriptor_index,
287                },
288            )
289            .with_keep_current_legal(self.placer.allows_unassigned);
290            if !is_completed(&placement) {
291                return Some(placement);
292            }
293        }
294        None
295    }
296}
297
298impl<S, V, ES, VS> EntityPlacer<S, ChangeMove<S, V>> for QueuedEntityPlacer<S, V, ES, VS>
299where
300    S: PlanningSolution,
301    V: Clone + PartialEq + Send + Sync + Debug + 'static,
302    ES: EntitySelector<S>,
303    VS: ValueSelector<S, V>,
304{
305    type Cursor<'a>
306        = QueuedEntityPlacerCursor<'a, S, V, ES, VS>
307    where
308        Self: 'a;
309
310    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
311        QueuedEntityPlacerCursor {
312            placer: self,
313            entities: self
314                .entity_selector
315                .iter(score_director)
316                .collect::<Vec<_>>()
317                .into_iter(),
318        }
319    }
320}
solverforge_solver/phase/construction/placer/queued.rs

solverforge_solver/phase/construction/placer/
queued.rs
