1use std::fmt::Debug;
4use std::marker::PhantomData;
5
6use smallvec::{smallvec, SmallVec};
7use solverforge_core::domain::PlanningSolution;
8use solverforge_scoring::Director;
9
10use crate::heuristic::r#move::{ListPermuteMove, MAX_LIST_PERMUTE_WINDOW_SIZE};
11use crate::list_placement::{selected_segment_allows, OwnerRestriction, SelectedOwnerRestrictions};
12
13use super::entity::EntitySelector;
14use super::list_support::{collect_selected_entities, ordered_index};
15use super::move_selector::{
16 CandidateId, CandidateStore, MoveCandidateRef, MoveCursor, MoveSelector, MoveStreamContext,
17};
18use super::precedence_route::{PrecedenceRouteGraph, PrecedenceRouteHooks};
19
20pub struct ListPermuteMoveSelector<S, V, ES> {
21 entity_selector: ES,
22 min_window_size: usize,
23 max_window_size: usize,
24 list_len: fn(&S, usize) -> usize,
25 list_get: fn(&S, usize, usize) -> Option<V>,
26 sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
27 sublist_insert: fn(&mut S, usize, usize, Vec<V>),
28 element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
29 precedence_route_hooks: Option<PrecedenceRouteHooks<S, V>>,
30 variable_name: &'static str,
31 descriptor_index: usize,
32 _phantom: PhantomData<(fn() -> S, fn() -> V)>,
33}
34
35pub struct ListPermuteMoveCursor<S, V>
36where
37 S: PlanningSolution,
38 V: Clone + Send + Sync + Debug + 'static,
39{
40 store: CandidateStore<S, ListPermuteMove<S, V>>,
41 entities: Vec<usize>,
42 route_lens: Vec<usize>,
43 context: MoveStreamContext,
44 element_owners: Option<Vec<Vec<OwnerRestriction>>>,
45 fixed_to_current_entity: bool,
46 precedence_route_graph: Option<PrecedenceRouteGraph>,
47 entity_idx: usize,
48 start_offset: usize,
49 size_offset: usize,
50 permutation_offset: usize,
51 current_window: Option<(usize, usize)>,
52 list_len: fn(&S, usize) -> usize,
53 list_get: fn(&S, usize, usize) -> Option<V>,
54 sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
55 sublist_insert: fn(&mut S, usize, usize, Vec<V>),
56 min_window_size: usize,
57 max_window_size: usize,
58 variable_name: &'static str,
59 descriptor_index: usize,
60}
61
62impl<S, V> ListPermuteMoveCursor<S, V>
63where
64 S: PlanningSolution,
65 V: Clone + Send + Sync + Debug + 'static,
66{
67 #[allow(clippy::too_many_arguments)]
68 fn new(
69 entities: Vec<usize>,
70 route_lens: Vec<usize>,
71 context: MoveStreamContext,
72 element_owners: Option<Vec<Vec<OwnerRestriction>>>,
73 fixed_to_current_entity: bool,
74 precedence_route_graph: Option<PrecedenceRouteGraph>,
75 min_window_size: usize,
76 max_window_size: usize,
77 list_len: fn(&S, usize) -> usize,
78 list_get: fn(&S, usize, usize) -> Option<V>,
79 sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
80 sublist_insert: fn(&mut S, usize, usize, Vec<V>),
81 variable_name: &'static str,
82 descriptor_index: usize,
83 ) -> Self {
84 Self {
85 store: CandidateStore::new(),
86 entities,
87 route_lens,
88 context,
89 element_owners,
90 fixed_to_current_entity,
91 precedence_route_graph,
92 entity_idx: 0,
93 start_offset: 0,
94 size_offset: 0,
95 permutation_offset: 0,
96 current_window: None,
97 list_len,
98 list_get,
99 sublist_remove,
100 sublist_insert,
101 min_window_size,
102 max_window_size,
103 variable_name,
104 descriptor_index,
105 }
106 }
107
108 pub(crate) fn with_precedence_route_graph(
109 mut self,
110 precedence_route_graph: Option<PrecedenceRouteGraph>,
111 ) -> Self {
112 self.precedence_route_graph = precedence_route_graph;
113 self
114 }
115
116 fn advance_entity(&mut self) {
117 self.entity_idx += 1;
118 self.start_offset = 0;
119 self.size_offset = 0;
120 self.permutation_offset = 0;
121 self.current_window = None;
122 }
123
124 fn advance_start(&mut self) {
125 self.start_offset += 1;
126 self.size_offset = 0;
127 self.permutation_offset = 0;
128 self.current_window = None;
129 }
130
131 fn window_owner_allows(&self, start: usize, end: usize) -> bool {
132 if self.fixed_to_current_entity {
133 return true;
134 }
135 let Some(element_owners) = &self.element_owners else {
136 return true;
137 };
138 selected_segment_allows(
139 element_owners,
140 self.entity_idx,
141 start,
142 end,
143 self.entities[self.entity_idx],
144 )
145 }
146
147 fn push_move(
148 &mut self,
149 entity: usize,
150 start: usize,
151 end: usize,
152 permutation: SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]>,
153 ) -> CandidateId {
154 self.store.push(ListPermuteMove::new(
155 entity,
156 start,
157 end,
158 permutation,
159 self.list_len,
160 self.list_get,
161 self.sublist_remove,
162 self.sublist_insert,
163 self.variable_name,
164 self.descriptor_index,
165 ))
166 }
167}
168
169impl<S, V> MoveCursor<S, ListPermuteMove<S, V>> for ListPermuteMoveCursor<S, V>
170where
171 S: PlanningSolution,
172 V: Clone + Send + Sync + Debug + 'static,
173{
174 fn next_candidate(&mut self) -> Option<CandidateId> {
175 loop {
176 if self.entity_idx >= self.entities.len() {
177 return None;
178 }
179 let entity = self.entities[self.entity_idx];
180 let route_len = self.route_lens[self.entity_idx];
181 if route_len < self.min_window_size {
182 self.advance_entity();
183 continue;
184 }
185
186 if let Some((start, size)) = self.current_window {
187 let permutation_count = factorial(size).saturating_sub(1);
188 if self.permutation_offset < permutation_count {
189 let rank = ordered_index(
190 self.permutation_offset,
191 permutation_count,
192 self.context,
193 0x91D7_9E8A_0000_0004
194 ^ entity as u64
195 ^ start as u64
196 ^ size as u64
197 ^ self.descriptor_index as u64,
198 ) + 1;
199 self.permutation_offset += 1;
200 let permutation = nth_permutation(size, rank);
201 if self.precedence_route_graph.as_ref().is_some_and(|graph| {
202 graph.intra_list_permutation_introduces_cycle(
203 entity,
204 start,
205 start + size,
206 &permutation,
207 )
208 }) {
209 continue;
210 }
211 return Some(self.push_move(entity, start, start + size, permutation));
212 }
213 self.current_window = None;
214 self.size_offset += 1;
215 self.permutation_offset = 0;
216 }
217
218 if self.start_offset >= route_len {
219 self.advance_entity();
220 continue;
221 }
222
223 let start = ordered_index(
224 self.start_offset,
225 route_len,
226 self.context,
227 0x91D7_9E8A_0000_0002 ^ entity as u64 ^ self.descriptor_index as u64,
228 );
229 let max_valid = self.max_window_size.min(route_len - start);
230 if max_valid < self.min_window_size {
231 self.advance_start();
232 continue;
233 }
234 let size_count = max_valid - self.min_window_size + 1;
235 if self.size_offset >= size_count {
236 self.advance_start();
237 continue;
238 }
239 let size = self.min_window_size
240 + ordered_index(
241 self.size_offset,
242 size_count,
243 self.context,
244 0x91D7_9E8A_0000_0003 ^ entity as u64 ^ start as u64,
245 );
246 if !self.window_owner_allows(start, start + size) {
247 self.size_offset += 1;
248 continue;
249 }
250 self.current_window = Some((start, size));
251 }
252 }
253
254 fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ListPermuteMove<S, V>>> {
255 self.store.candidate(id)
256 }
257
258 fn take_candidate(&mut self, id: CandidateId) -> ListPermuteMove<S, V> {
259 self.store.take_candidate(id)
260 }
261}
262
263impl<S, V> Iterator for ListPermuteMoveCursor<S, V>
264where
265 S: PlanningSolution,
266 V: Clone + Send + Sync + Debug + 'static,
267{
268 type Item = ListPermuteMove<S, V>;
269
270 fn next(&mut self) -> Option<Self::Item> {
271 let id = self.next_candidate()?;
272 Some(self.take_candidate(id))
273 }
274}
275
276impl<S, V: Debug, ES: Debug> Debug for ListPermuteMoveSelector<S, V, ES> {
277 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
278 f.debug_struct("ListPermuteMoveSelector")
279 .field("entity_selector", &self.entity_selector)
280 .field("min_window_size", &self.min_window_size)
281 .field("max_window_size", &self.max_window_size)
282 .field("variable_name", &self.variable_name)
283 .finish()
284 }
285}
286
287impl<S, V, ES> ListPermuteMoveSelector<S, V, ES> {
288 #[allow(clippy::too_many_arguments)]
289 pub fn new(
290 entity_selector: ES,
291 min_window_size: usize,
292 max_window_size: usize,
293 list_len: fn(&S, usize) -> usize,
294 list_get: fn(&S, usize, usize) -> Option<V>,
295 sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
296 sublist_insert: fn(&mut S, usize, usize, Vec<V>),
297 variable_name: &'static str,
298 descriptor_index: usize,
299 ) -> Self {
300 assert!(
301 min_window_size >= 2,
302 "list permute min_window_size must be at least 2",
303 );
304 assert!(
305 min_window_size <= max_window_size,
306 "list permute min_window_size must be <= max_window_size",
307 );
308 assert!(
309 max_window_size <= MAX_LIST_PERMUTE_WINDOW_SIZE,
310 "list permute max_window_size must be <= {MAX_LIST_PERMUTE_WINDOW_SIZE}",
311 );
312 Self {
313 entity_selector,
314 min_window_size,
315 max_window_size,
316 list_len,
317 list_get,
318 sublist_remove,
319 sublist_insert,
320 element_owner_fn: None,
321 precedence_route_hooks: None,
322 variable_name,
323 descriptor_index,
324 _phantom: PhantomData,
325 }
326 }
327
328 pub fn with_element_owner_fn(mut self, owner_fn: Option<fn(&S, &V) -> Option<usize>>) -> Self {
329 self.element_owner_fn = owner_fn;
330 self
331 }
332
333 pub(crate) fn with_precedence_route_hooks(
334 mut self,
335 precedence_route_hooks: Option<PrecedenceRouteHooks<S, V>>,
336 ) -> Self {
337 self.precedence_route_hooks = precedence_route_hooks;
338 self
339 }
340
341 pub(crate) fn precedence_route_hooks(&self) -> Option<PrecedenceRouteHooks<S, V>> {
342 self.precedence_route_hooks
343 }
344}
345
346impl<S, V, ES> MoveSelector<S, ListPermuteMove<S, V>> for ListPermuteMoveSelector<S, V, ES>
347where
348 S: PlanningSolution,
349 V: Clone + Send + Sync + Debug + 'static,
350 ES: EntitySelector<S>,
351{
352 type Cursor<'a>
353 = ListPermuteMoveCursor<S, V>
354 where
355 Self: 'a;
356
357 fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
358 self.open_cursor_with_context(score_director, MoveStreamContext::default())
359 }
360
361 fn open_cursor_with_context<'a, D: Director<S>>(
362 &'a self,
363 score_director: &D,
364 context: MoveStreamContext,
365 ) -> Self::Cursor<'a> {
366 let selected =
367 collect_selected_entities(&self.entity_selector, score_director, self.list_len);
368 let owner_restrictions = crate::list_placement::selected_owner_restrictions(
369 self.element_owner_fn,
370 score_director.working_solution(),
371 score_director
372 .entity_count(self.descriptor_index)
373 .unwrap_or(0),
374 &selected.entities,
375 &selected.route_lens,
376 self.list_get,
377 );
378 let fixed_to_current_entity = owner_restrictions
379 .as_ref()
380 .is_some_and(SelectedOwnerRestrictions::is_fixed_to_current);
381 let element_owners = owner_restrictions.and_then(SelectedOwnerRestrictions::into_mixed);
382
383 ListPermuteMoveCursor::new(
384 selected.entities,
385 selected.route_lens,
386 context,
387 element_owners,
388 fixed_to_current_entity,
389 None,
390 self.min_window_size,
391 self.max_window_size,
392 self.list_len,
393 self.list_get,
394 self.sublist_remove,
395 self.sublist_insert,
396 self.variable_name,
397 self.descriptor_index,
398 )
399 }
400
401 fn size<D: Director<S>>(&self, score_director: &D) -> usize {
402 let selected =
403 collect_selected_entities(&self.entity_selector, score_director, self.list_len);
404 let Some(owner_restrictions) = crate::list_placement::selected_owner_restrictions(
405 self.element_owner_fn,
406 score_director.working_solution(),
407 score_director
408 .entity_count(self.descriptor_index)
409 .unwrap_or(0),
410 &selected.entities,
411 &selected.route_lens,
412 self.list_get,
413 ) else {
414 return selected
415 .route_lens
416 .iter()
417 .map(|&route_len| {
418 count_list_permute_moves_for_len(
419 route_len,
420 self.min_window_size,
421 self.max_window_size,
422 )
423 })
424 .sum();
425 };
426
427 if owner_restrictions.is_fixed_to_current() {
428 return selected
429 .route_lens
430 .iter()
431 .map(|&route_len| {
432 count_list_permute_moves_for_len(
433 route_len,
434 self.min_window_size,
435 self.max_window_size,
436 )
437 })
438 .sum();
439 }
440 let element_owners = owner_restrictions
441 .mixed()
442 .expect("non-fixed owner restrictions must retain mixed owner matrix");
443
444 let mut count = 0;
445 for (entity_idx, &route_len) in selected.route_lens.iter().enumerate() {
446 for start in 0..route_len {
447 let max_valid = self.max_window_size.min(route_len - start);
448 for size in self.min_window_size..=max_valid {
449 if selected_segment_allows(
450 element_owners,
451 entity_idx,
452 start,
453 start + size,
454 selected.entities[entity_idx],
455 ) {
456 count += factorial(size).saturating_sub(1);
457 }
458 }
459 }
460 }
461 count
462 }
463}
464
465fn count_list_permute_moves_for_len(
466 route_len: usize,
467 min_window_size: usize,
468 max_window_size: usize,
469) -> usize {
470 if route_len < min_window_size {
471 return 0;
472 }
473 let mut count = 0;
474 for start in 0..route_len {
475 let max_valid = max_window_size.min(route_len - start);
476 for size in min_window_size..=max_valid {
477 count += factorial(size).saturating_sub(1);
478 }
479 }
480 count
481}
482
483fn factorial(value: usize) -> usize {
484 (2..=value).product()
485}
486
487fn nth_permutation(len: usize, mut rank: usize) -> SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]> {
488 let mut remaining: SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]> = (0..len).collect();
489 let mut permutation = smallvec![];
490 for pos in 0..len {
491 let suffix = len - pos - 1;
492 let step = factorial(suffix);
493 let index = rank / step;
494 rank %= step;
495 permutation.push(remaining.remove(index));
496 }
497 permutation
498}