solverforge_solver/builder/selector/
grouped_scalar.rs

1use std::cell::Cell;
2
3pub struct GroupedScalarSelector<S> {
4    group: crate::builder::context::ScalarGroupBinding<S>,
5    value_candidate_limit: Option<usize>,
6    max_moves_per_step: Option<usize>,
7    require_hard_improvement: bool,
8    next_entity_offset: Cell<usize>,
9}
10
11impl<S> GroupedScalarSelector<S> {
12    pub fn new(
13        group: crate::builder::context::ScalarGroupBinding<S>,
14        value_candidate_limit: Option<usize>,
15        max_moves_per_step: Option<usize>,
16        require_hard_improvement: bool,
17    ) -> Self {
18        let effective_value_candidate_limit =
19            value_candidate_limit.or(group.limits.value_candidate_limit);
20        let effective_max_moves_per_step = max_moves_per_step.or(group.limits.max_moves_per_step);
21        Self {
22            group,
23            value_candidate_limit: effective_value_candidate_limit,
24            max_moves_per_step: effective_max_moves_per_step,
25            require_hard_improvement,
26            next_entity_offset: Cell::new(0),
27        }
28    }
29
30    fn next_entity_offset(&self) -> usize {
31        let offset = self.next_entity_offset.get();
32        self.next_entity_offset.set(offset.wrapping_add(1));
33        offset
34    }
35
36    fn effective_max_moves_per_step(&self, solution: &S) -> usize {
37        if let Some(max_moves_per_step) = self.max_moves_per_step {
38            return max_moves_per_step;
39        }
40        match self.group.kind {
41            crate::builder::ScalarGroupBindingKind::Assignment(assignment) => {
42                let max_rematch_size = self.group.limits.max_rematch_size.unwrap_or(4).max(2);
43                assignment
44                    .entity_count(solution)
45                    .saturating_mul(max_rematch_size)
46                    .clamp(256, 4096)
47            }
48            crate::builder::ScalarGroupBindingKind::Candidates { .. } => 256,
49        }
50    }
51
52    fn limits(&self, max_moves_per_step: usize) -> crate::builder::context::ScalarGroupLimits {
53        crate::builder::context::ScalarGroupLimits {
54            value_candidate_limit: self.value_candidate_limit,
55            group_candidate_limit: Some(max_moves_per_step),
56            max_moves_per_step: Some(max_moves_per_step),
57            max_augmenting_depth: self.group.limits.max_augmenting_depth,
58            max_rematch_size: self.group.limits.max_rematch_size,
59        }
60    }
61}
62
63impl<S> std::fmt::Debug for GroupedScalarSelector<S> {
64    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
65        f.debug_struct("GroupedScalarSelector")
66            .field("group_name", &self.group.group_name)
67            .field("value_candidate_limit", &self.value_candidate_limit)
68            .field("max_moves_per_step", &self.max_moves_per_step)
69            .field("require_hard_improvement", &self.require_hard_improvement)
70            .finish()
71    }
72}
73
74pub struct GroupedScalarCursor<S>
75where
76    S: PlanningSolution + 'static,
77{
78    store: CandidateStore<S, ScalarMoveUnion<S, usize>>,
79    next_index: usize,
80    assignment_cursor:
81        Option<crate::phase::construction::grouped_scalar::ScalarAssignmentMoveCursor<S>>,
82    require_hard_improvement: bool,
83}
84
85impl<S> GroupedScalarCursor<S>
86where
87    S: PlanningSolution + 'static,
88{
89    fn new(store: CandidateStore<S, ScalarMoveUnion<S, usize>>) -> Self {
90        Self {
91            store,
92            next_index: 0,
93            assignment_cursor: None,
94            require_hard_improvement: false,
95        }
96    }
97
98    fn assignment(
99        assignment_cursor: crate::phase::construction::grouped_scalar::ScalarAssignmentMoveCursor<S>,
100        require_hard_improvement: bool,
101        capacity: usize,
102    ) -> Self {
103        Self {
104            store: CandidateStore::with_capacity(capacity),
105            next_index: 0,
106            assignment_cursor: Some(assignment_cursor),
107            require_hard_improvement,
108        }
109    }
110}
111
112impl<S> MoveCursor<S, ScalarMoveUnion<S, usize>> for GroupedScalarCursor<S>
113where
114    S: PlanningSolution + 'static,
115{
116    fn next_candidate(&mut self) -> Option<CandidateId> {
117        if self.next_index < self.store.len() {
118            let id = CandidateId::new(self.next_index);
119            self.next_index += 1;
120            return Some(id);
121        }
122        let assignment_cursor = self.assignment_cursor.as_mut()?;
123        let mov = assignment_cursor
124            .next_move()?
125            .with_require_hard_improvement(self.require_hard_improvement);
126        let id = self.store.push(ScalarMoveUnion::CompoundScalar(mov));
127        self.next_index = id.index() + 1;
128        Some(id)
129    }
130
131    fn candidate(
132        &self,
133        id: CandidateId,
134    ) -> Option<MoveCandidateRef<'_, S, ScalarMoveUnion<S, usize>>> {
135        self.store.candidate(id)
136    }
137
138    fn take_candidate(&mut self, id: CandidateId) -> ScalarMoveUnion<S, usize> {
139        self.store.take_candidate(id)
140    }
141}
142
143impl<S> MoveSelector<S, ScalarMoveUnion<S, usize>> for GroupedScalarSelector<S>
144where
145    S: PlanningSolution + 'static,
146{
147    type Cursor<'a>
148        = GroupedScalarCursor<S>
149    where
150        Self: 'a;
151
152    fn open_cursor<'a, D: solverforge_scoring::Director<S>>(
153        &'a self,
154        score_director: &D,
155    ) -> Self::Cursor<'a> {
156        self.open_cursor_with_context(score_director, MoveStreamContext::default())
157    }
158
159    fn open_cursor_with_context<'a, D: solverforge_scoring::Director<S>>(
160        &'a self,
161        score_director: &D,
162        context: MoveStreamContext,
163    ) -> Self::Cursor<'a> {
164        let solution = score_director.working_solution();
165        let max_moves_per_step = self.effective_max_moves_per_step(solution);
166        if max_moves_per_step == 0 {
167            return GroupedScalarCursor::new(CandidateStore::new());
168        }
169
170        let candidate_provider = match self.group.kind {
171            crate::builder::ScalarGroupBindingKind::Candidates { candidate_provider } => {
172                candidate_provider
173            }
174            crate::builder::ScalarGroupBindingKind::Assignment(assignment) => {
175                return self.open_assignment_cursor(
176                    score_director,
177                    assignment,
178                    context,
179                    max_moves_per_step,
180                );
181            }
182        };
183        let mut store = CandidateStore::with_capacity(max_moves_per_step);
184        let mut seen_candidates = Vec::new();
185        let mut targets = std::collections::HashSet::new();
186
187        let mut candidates = candidate_provider(solution, self.limits(max_moves_per_step));
188        let offset = context.start_offset(
189            candidates.len(),
190            0xC0A1_E5CE_AAA0_0001 ^ self.group.group_name.len() as u64,
191        );
192        candidates.rotate_left(offset);
193        for candidate in candidates {
194            if store.len() >= max_moves_per_step {
195                break;
196            }
197            if candidate.edits().is_empty()
198                || seen_candidates
199                    .iter()
200                    .any(|seen_candidate| seen_candidate == &candidate)
201            {
202                continue;
203            }
204            targets.clear();
205            if candidate.edits().iter().any(|edit| {
206                !targets.insert((
207                    edit.descriptor_index(),
208                    edit.entity_index(),
209                    edit.variable_name(),
210                ))
211            }) {
212                continue;
213            }
214
215            let Some(mov) =
216                crate::phase::construction::grouped_scalar::compound_move_for_group_candidate(
217                    &self.group,
218                    solution,
219                    &candidate,
220                )
221            else {
222                continue;
223            };
224            let mov = mov.with_require_hard_improvement(self.require_hard_improvement);
225            if mov.is_doable(score_director) {
226                store.push(ScalarMoveUnion::CompoundScalar(mov));
227                seen_candidates.push(candidate);
228            }
229        }
230
231        GroupedScalarCursor::new(store)
232    }
233
234    fn size<D: solverforge_scoring::Director<S>>(&self, score_director: &D) -> usize {
235        self.effective_max_moves_per_step(score_director.working_solution())
236    }
237}
238
239impl<S> GroupedScalarSelector<S>
240where
241    S: PlanningSolution + 'static,
242{
243    fn open_assignment_cursor<D: solverforge_scoring::Director<S>>(
244        &self,
245        score_director: &D,
246        assignment: crate::builder::ScalarAssignmentBinding<S>,
247        context: MoveStreamContext,
248        max_moves_per_step: usize,
249    ) -> GroupedScalarCursor<S> {
250        if max_moves_per_step == 0 {
251            return GroupedScalarCursor::new(CandidateStore::new());
252        }
253
254        let solution = score_director.working_solution();
255        let entity_offset = self.next_entity_offset().wrapping_add(context.offset_seed(
256            0xC0A1_E5CE_AAA0_0002 ^ self.group.group_name.len() as u64,
257        ));
258        let options = crate::phase::construction::grouped_scalar::ScalarAssignmentMoveOptions::for_selector(
259            self.group.limits,
260            self.value_candidate_limit,
261            max_moves_per_step,
262            entity_offset,
263        );
264        let assignment_cursor =
265            crate::phase::construction::grouped_scalar::ScalarAssignmentMoveCursor::new(
266                assignment,
267                solution.clone(),
268                options,
269            );
270        GroupedScalarCursor::assignment(
271            assignment_cursor,
272            self.require_hard_improvement,
273            max_moves_per_step,
274        )
275    }
276}
solverforge_solver/builder/selector/grouped_scalar.rs

solverforge_solver/builder/selector/
grouped_scalar.rs
