solverforge_solver/heuristic/selector/
list_precedence.rs

1/* List precedence critical-path selector.
2
3Generates existing list moves around critical same-list arcs in precedence
4makespan models. The selector consumes plain list-slot hooks for node duration
5and fixed successors; it does not depend on a problem-specific model type.
6*/
7
8use std::collections::VecDeque;
9use std::fmt::Debug;
10use std::marker::PhantomData;
11
12use smallvec::{smallvec, SmallVec};
13use solverforge_core::domain::PlanningSolution;
14use solverforge_scoring::Director;
15
16use crate::heuristic::r#move::{
17    ListChangeMove, ListMoveUnion, ListMultiSwapMove, ListPermuteMove, ListReverseMove,
18    ListRuinMove, ListSwapMove, SublistChangeMove, SublistSwapMove, MAX_LIST_PERMUTE_WINDOW_SIZE,
19};
20
21use super::entity::EntitySelector;
22use super::list_support::{collect_selected_entities, ordered_index};
23use super::move_selector::{
24    CandidateId, CandidateStore, MoveCandidateRef, MoveCursor, MoveSelector, MoveStreamContext,
25};
26use super::precedence_route::{PrecedenceRouteGraph, PrecedenceRouteHooks};
27
28const CRITICAL_PERMUTE_MAX_WINDOW_SIZE: usize = 5;
29const CRITICAL_RUIN_MAX_SIZE: usize = 5;
30const CRITICAL_SUBLIST_MAX_SIZE: usize = 3;
31
32#[derive(Clone, Copy, Debug)]
33struct CriticalBlock {
34    entity: usize,
35    start: usize,
36    end: usize,
37    route_len: usize,
38}
39
40#[derive(Clone, Copy, Debug, PartialEq, Eq)]
41struct AdjacentSwap {
42    entity: usize,
43    position: usize,
44}
45
46impl AdjacentSwap {
47    fn as_tuple(self) -> (usize, usize, usize) {
48        (self.entity, self.position, self.position + 1)
49    }
50}
51
52impl CriticalBlock {
53    fn len(self) -> usize {
54        self.end - self.start + 1
55    }
56
57    fn change_move_count(self) -> usize {
58        self.len() * self.route_len.saturating_sub(1)
59    }
60
61    fn adjacent_change_move_count(self) -> usize {
62        self.len().saturating_sub(1)
63    }
64
65    fn boundary_change_move_count(self) -> usize {
66        count_boundary_change_moves(self)
67    }
68
69    fn permute_move_count(self) -> usize {
70        count_permute_moves_for_len(self.len(), CRITICAL_PERMUTE_MAX_WINDOW_SIZE)
71    }
72
73    fn swap_move_count(self) -> usize {
74        self.len().saturating_mul(self.len().saturating_sub(1)) / 2
75    }
76
77    fn reverse_move_count(self) -> usize {
78        self.len().saturating_mul(self.len().saturating_sub(1)) / 2
79    }
80
81    fn adjacent_sublist_swap_move_count(self) -> usize {
82        count_adjacent_sublist_swap_moves_for_len(self.len(), CRITICAL_SUBLIST_MAX_SIZE)
83    }
84
85    fn ruin_move_count(self) -> usize {
86        if self.len() < 2 {
87            0
88        } else {
89            let window_len = self.len().min(CRITICAL_RUIN_MAX_SIZE);
90            self.len() - window_len + 1
91        }
92    }
93
94    fn sublist_change_move_count(self) -> usize {
95        count_sublist_change_moves_for_len(self.len(), self.route_len, CRITICAL_SUBLIST_MAX_SIZE)
96    }
97
98    fn move_count(self) -> usize {
99        self.change_move_count()
100            + self.swap_move_count()
101            + self.reverse_move_count()
102            + self.adjacent_sublist_swap_move_count()
103            + self.ruin_move_count()
104            + self.sublist_change_move_count()
105            + self.permute_move_count()
106    }
107}
108
109pub struct ListPrecedenceMoveSelector<S, V, ES> {
110    entity_selector: ES,
111    element_count: fn(&S) -> usize,
112    index_to_element: fn(&S, usize) -> V,
113    node_duration: fn(&S, V) -> usize,
114    fixed_successors: fn(&S, V, &mut Vec<V>),
115    entity_count: fn(&S) -> usize,
116    list_len: fn(&S, usize) -> usize,
117    list_get: fn(&S, usize, usize) -> Option<V>,
118    list_remove: fn(&mut S, usize, usize) -> Option<V>,
119    list_insert: fn(&mut S, usize, usize, V),
120    list_set: fn(&mut S, usize, usize, V),
121    list_reverse: fn(&mut S, usize, usize, usize),
122    ruin_remove: fn(&mut S, usize, usize) -> V,
123    ruin_insert: fn(&mut S, usize, usize, V),
124    element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
125    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
126    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
127    variable_name: &'static str,
128    descriptor_index: usize,
129    _phantom: PhantomData<fn() -> V>,
130}
131
132pub struct ListPrecedenceMoveCursor<S, V>
133where
134    S: PlanningSolution,
135    V: Clone + PartialEq + Send + Sync + Debug + 'static,
136{
137    store: CandidateStore<S, ListMoveUnion<S, V>>,
138    blocks: Vec<CriticalBlock>,
139    route_graph: PrecedenceRouteGraph,
140    context: MoveStreamContext,
141    block_idx: usize,
142    move_idx: usize,
143    multi_swap_idx: usize,
144    multi_swap_count: usize,
145    multi_ruin_idx: usize,
146    multi_ruin_count: usize,
147    critical_swaps: Vec<AdjacentSwap>,
148    support_swaps: Vec<AdjacentSwap>,
149    element_count: fn(&S) -> usize,
150    index_to_element: fn(&S, usize) -> V,
151    fixed_successors: fn(&S, V, &mut Vec<V>),
152    entity_count: fn(&S) -> usize,
153    list_len: fn(&S, usize) -> usize,
154    list_get: fn(&S, usize, usize) -> Option<V>,
155    list_remove: fn(&mut S, usize, usize) -> Option<V>,
156    list_insert: fn(&mut S, usize, usize, V),
157    list_set: fn(&mut S, usize, usize, V),
158    list_reverse: fn(&mut S, usize, usize, usize),
159    ruin_remove: fn(&mut S, usize, usize) -> V,
160    ruin_insert: fn(&mut S, usize, usize, V),
161    element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
162    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
163    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
164    variable_name: &'static str,
165    descriptor_index: usize,
166}
167
168impl<S, V> ListPrecedenceMoveCursor<S, V>
169where
170    S: PlanningSolution,
171    V: Clone + PartialEq + Send + Sync + Debug + 'static,
172{
173    #[allow(clippy::too_many_arguments)]
174    fn new(
175        blocks: Vec<CriticalBlock>,
176        route_graph: PrecedenceRouteGraph,
177        context: MoveStreamContext,
178        element_count: fn(&S) -> usize,
179        index_to_element: fn(&S, usize) -> V,
180        fixed_successors: fn(&S, V, &mut Vec<V>),
181        entity_count: fn(&S) -> usize,
182        list_len: fn(&S, usize) -> usize,
183        list_get: fn(&S, usize, usize) -> Option<V>,
184        list_remove: fn(&mut S, usize, usize) -> Option<V>,
185        list_insert: fn(&mut S, usize, usize, V),
186        list_set: fn(&mut S, usize, usize, V),
187        list_reverse: fn(&mut S, usize, usize, usize),
188        ruin_remove: fn(&mut S, usize, usize) -> V,
189        ruin_insert: fn(&mut S, usize, usize, V),
190        element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
191        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
192        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
193        variable_name: &'static str,
194        descriptor_index: usize,
195    ) -> Self {
196        let critical_swaps = critical_adjacent_swaps(&blocks);
197        let support_swaps = support_adjacent_swaps(&blocks, &route_graph);
198        let multi_swap_count = multi_support_swap_count(&critical_swaps, &support_swaps);
199        let multi_ruin_count = multi_critical_ruin_count(&blocks);
200        Self {
201            store: CandidateStore::new(),
202            blocks,
203            route_graph,
204            context,
205            block_idx: 0,
206            move_idx: 0,
207            multi_swap_idx: 0,
208            multi_swap_count,
209            multi_ruin_idx: 0,
210            multi_ruin_count,
211            critical_swaps,
212            support_swaps,
213            element_count,
214            index_to_element,
215            fixed_successors,
216            entity_count,
217            list_len,
218            list_get,
219            list_remove,
220            list_insert,
221            list_set,
222            list_reverse,
223            ruin_remove,
224            ruin_insert,
225            element_owner_fn,
226            sublist_remove,
227            sublist_insert,
228            variable_name,
229            descriptor_index,
230        }
231    }
232
233    fn push_move(&mut self, block: CriticalBlock, move_idx: usize) -> CandidateId {
234        let adjacent_count = block.adjacent_change_move_count();
235        if move_idx < adjacent_count {
236            let source = block.start + move_idx;
237            let mov = ListMoveUnion::ListChange(ListChangeMove::new(
238                block.entity,
239                source,
240                block.entity,
241                source + 2,
242                self.list_len,
243                self.list_get,
244                self.list_remove,
245                self.list_insert,
246                self.variable_name,
247                self.descriptor_index,
248            ));
249            return self.store.push(mov);
250        }
251
252        let change_count = block.change_move_count();
253        if move_idx < change_count {
254            let (source, dest) = non_adjacent_change(block, move_idx - adjacent_count);
255            let mov = ListMoveUnion::ListChange(ListChangeMove::new(
256                block.entity,
257                source,
258                block.entity,
259                dest,
260                self.list_len,
261                self.list_get,
262                self.list_remove,
263                self.list_insert,
264                self.variable_name,
265                self.descriptor_index,
266            ));
267            return self.store.push(mov);
268        }
269
270        let swap_count = block.swap_move_count();
271        if move_idx < change_count + swap_count {
272            let (first, second) = critical_swap(block, move_idx - change_count);
273            let mov = ListMoveUnion::ListSwap(ListSwapMove::new(
274                block.entity,
275                first,
276                block.entity,
277                second,
278                self.list_len,
279                self.list_get,
280                self.list_set,
281                self.variable_name,
282                self.descriptor_index,
283            ));
284            return self.store.push(mov);
285        }
286
287        let reverse_count = block.reverse_move_count();
288        if move_idx < change_count + swap_count + reverse_count {
289            let (start, end) = critical_reverse(block, move_idx - change_count - swap_count);
290            let mov = ListMoveUnion::ListReverse(ListReverseMove::new(
291                block.entity,
292                start,
293                end,
294                self.list_len,
295                self.list_get,
296                self.list_reverse,
297                self.variable_name,
298                self.descriptor_index,
299            ));
300            return self.store.push(mov);
301        }
302
303        let adjacent_sublist_swap_count = block.adjacent_sublist_swap_move_count();
304        if move_idx < change_count + swap_count + reverse_count + adjacent_sublist_swap_count {
305            let (first_start, first_end, second_start, second_end) = critical_adjacent_sublist_swap(
306                block,
307                move_idx - change_count - swap_count - reverse_count,
308            );
309            let mov = ListMoveUnion::SublistSwap(SublistSwapMove::new(
310                block.entity,
311                first_start,
312                first_end,
313                block.entity,
314                second_start,
315                second_end,
316                self.list_len,
317                self.list_get,
318                self.sublist_remove,
319                self.sublist_insert,
320                self.variable_name,
321                self.descriptor_index,
322            ));
323            return self.store.push(mov);
324        }
325
326        let ruin_count = block.ruin_move_count();
327        if move_idx
328            < change_count + swap_count + reverse_count + adjacent_sublist_swap_count + ruin_count
329        {
330            let indices = critical_ruin_indices(
331                block,
332                move_idx - change_count - swap_count - reverse_count - adjacent_sublist_swap_count,
333            );
334            let mov = ListMoveUnion::ListRuin(
335                ListRuinMove::new(
336                    block.entity,
337                    &indices,
338                    self.entity_count,
339                    self.list_len,
340                    self.list_get,
341                    self.ruin_remove,
342                    self.ruin_insert,
343                    self.variable_name,
344                    self.descriptor_index,
345                )
346                .with_element_owner_fn(self.element_owner_fn)
347                .with_precedence_hooks(
348                    Some(self.element_count),
349                    Some(self.index_to_element),
350                    Some(self.fixed_successors),
351                ),
352            );
353            return self.store.push(mov);
354        }
355
356        let sublist_change_count = block.sublist_change_move_count();
357        if move_idx
358            < change_count
359                + swap_count
360                + reverse_count
361                + adjacent_sublist_swap_count
362                + ruin_count
363                + sublist_change_count
364        {
365            let (source_start, size, dest) = critical_sublist_change(
366                block.start,
367                block.len(),
368                block.route_len,
369                move_idx
370                    - change_count
371                    - swap_count
372                    - reverse_count
373                    - adjacent_sublist_swap_count
374                    - ruin_count,
375            );
376            let source_start = block.start + source_start;
377            return self
378                .store
379                .push(ListMoveUnion::SublistChange(SublistChangeMove::new(
380                    block.entity,
381                    source_start,
382                    source_start + size,
383                    block.entity,
384                    dest,
385                    self.list_len,
386                    self.list_get,
387                    self.sublist_remove,
388                    self.sublist_insert,
389                    self.variable_name,
390                    self.descriptor_index,
391                )));
392        }
393
394        let permute_idx = move_idx
395            - change_count
396            - swap_count
397            - reverse_count
398            - adjacent_sublist_swap_count
399            - ruin_count
400            - sublist_change_count;
401        let (start_offset, size, permutation) = critical_permutation(block.len(), permute_idx);
402        let start = block.start + start_offset;
403        self.store
404            .push(ListMoveUnion::ListPermute(ListPermuteMove::new(
405                block.entity,
406                start,
407                start + size,
408                permutation,
409                self.list_len,
410                self.list_get,
411                self.sublist_remove,
412                self.sublist_insert,
413                self.variable_name,
414                self.descriptor_index,
415            )))
416    }
417
418    fn push_multi_ruin_move(
419        &mut self,
420        sources: SmallVec<[(usize, SmallVec<[usize; 8]>); 4]>,
421    ) -> CandidateId {
422        let mov = ListMoveUnion::ListRuin(
423            ListRuinMove::new_multi_source(
424                &sources,
425                self.entity_count,
426                self.list_len,
427                self.list_get,
428                self.ruin_remove,
429                self.ruin_insert,
430                self.variable_name,
431                self.descriptor_index,
432            )
433            .with_element_owner_fn(self.element_owner_fn)
434            .with_precedence_hooks(
435                Some(self.element_count),
436                Some(self.index_to_element),
437                Some(self.fixed_successors),
438            ),
439        );
440        self.store.push(mov)
441    }
442
443    fn push_multi_swap_move(&mut self, swaps: &[(usize, usize, usize)]) -> CandidateId {
444        let mov = ListMoveUnion::ListMultiSwap(
445            ListMultiSwapMove::new(
446                swaps,
447                self.list_len,
448                self.list_get,
449                self.list_set,
450                self.variable_name,
451                self.descriptor_index,
452            )
453            .with_require_score_improvement(true),
454        );
455        self.store.push(mov)
456    }
457}
458
459impl<S, V> MoveCursor<S, ListMoveUnion<S, V>> for ListPrecedenceMoveCursor<S, V>
460where
461    S: PlanningSolution,
462    V: Clone + PartialEq + Send + Sync + Debug + 'static,
463{
464    fn next_candidate(&mut self) -> Option<CandidateId> {
465        loop {
466            if self.multi_swap_idx < self.multi_swap_count {
467                let move_idx = ordered_index(
468                    self.multi_swap_idx,
469                    self.multi_swap_count,
470                    self.context,
471                    0xC917_1EAF_5EED_0004 ^ self.descriptor_index as u64,
472                );
473                self.multi_swap_idx += 1;
474                let swaps =
475                    multi_support_swaps(&self.critical_swaps, &self.support_swaps, move_idx);
476                if self
477                    .route_graph
478                    .multi_intra_list_swaps_introduce_cycle(&swaps)
479                {
480                    continue;
481                }
482                return Some(self.push_multi_swap_move(&swaps));
483            }
484            if self.multi_ruin_idx < self.multi_ruin_count {
485                let move_idx = ordered_index(
486                    self.multi_ruin_idx,
487                    self.multi_ruin_count,
488                    self.context,
489                    0xC917_1EAF_5EED_0003 ^ self.descriptor_index as u64,
490                );
491                self.multi_ruin_idx += 1;
492                let sources = multi_critical_ruin_sources(&self.blocks, move_idx);
493                return Some(self.push_multi_ruin_move(sources));
494            }
495            if self.block_idx >= self.blocks.len() {
496                return None;
497            }
498            let block_index = ordered_index(
499                self.block_idx,
500                self.blocks.len(),
501                self.context,
502                0xC917_1EAF_5EED_0001 ^ self.descriptor_index as u64,
503            );
504            let block = self.blocks[block_index];
505            let move_count = block.move_count();
506            if self.move_idx < move_count {
507                let move_idx = tiered_precedence_move_index(
508                    block,
509                    self.move_idx,
510                    self.context,
511                    0xC917_1EAF_5EED_0002
512                        ^ self.descriptor_index as u64
513                        ^ block.entity as u64
514                        ^ ((block.start as u64) << 16)
515                        ^ ((block.end as u64) << 32),
516                );
517                self.move_idx += 1;
518                if move_introduces_route_cycle(block, move_idx, &self.route_graph) {
519                    continue;
520                }
521                return Some(self.push_move(block, move_idx));
522            }
523            self.block_idx += 1;
524            self.move_idx = 0;
525        }
526    }
527
528    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, ListMoveUnion<S, V>>> {
529        self.store.candidate(id)
530    }
531
532    fn take_candidate(&mut self, id: CandidateId) -> ListMoveUnion<S, V> {
533        self.store.take_candidate(id)
534    }
535}
536
537impl<S, V> Iterator for ListPrecedenceMoveCursor<S, V>
538where
539    S: PlanningSolution,
540    V: Clone + PartialEq + Send + Sync + Debug + 'static,
541{
542    type Item = ListMoveUnion<S, V>;
543
544    fn next(&mut self) -> Option<Self::Item> {
545        let id = self.next_candidate()?;
546        Some(self.take_candidate(id))
547    }
548}
549
550impl<S, V: Debug, ES: Debug> Debug for ListPrecedenceMoveSelector<S, V, ES> {
551    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
552        f.debug_struct("ListPrecedenceMoveSelector")
553            .field("entity_selector", &self.entity_selector)
554            .field("variable_name", &self.variable_name)
555            .finish()
556    }
557}
558
559impl<S, V, ES> ListPrecedenceMoveSelector<S, V, ES> {
560    #[allow(clippy::too_many_arguments)]
561    pub fn new(
562        entity_selector: ES,
563        element_count: fn(&S) -> usize,
564        index_to_element: fn(&S, usize) -> V,
565        node_duration: fn(&S, V) -> usize,
566        fixed_successors: fn(&S, V, &mut Vec<V>),
567        entity_count: fn(&S) -> usize,
568        list_len: fn(&S, usize) -> usize,
569        list_get: fn(&S, usize, usize) -> Option<V>,
570        list_remove: fn(&mut S, usize, usize) -> Option<V>,
571        list_insert: fn(&mut S, usize, usize, V),
572        list_set: fn(&mut S, usize, usize, V),
573        list_reverse: fn(&mut S, usize, usize, usize),
574        ruin_remove: fn(&mut S, usize, usize) -> V,
575        ruin_insert: fn(&mut S, usize, usize, V),
576        element_owner_fn: Option<fn(&S, &V) -> Option<usize>>,
577        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
578        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
579        variable_name: &'static str,
580        descriptor_index: usize,
581    ) -> Self {
582        Self {
583            entity_selector,
584            element_count,
585            index_to_element,
586            node_duration,
587            fixed_successors,
588            entity_count,
589            list_len,
590            list_get,
591            list_remove,
592            list_insert,
593            list_set,
594            list_reverse,
595            ruin_remove,
596            ruin_insert,
597            element_owner_fn,
598            sublist_remove,
599            sublist_insert,
600            variable_name,
601            descriptor_index,
602            _phantom: PhantomData,
603        }
604    }
605}
606
607impl<S, V, ES> MoveSelector<S, ListMoveUnion<S, V>> for ListPrecedenceMoveSelector<S, V, ES>
608where
609    S: PlanningSolution,
610    V: Clone + PartialEq + Send + Sync + Debug + 'static,
611    ES: EntitySelector<S>,
612{
613    type Cursor<'a>
614        = ListPrecedenceMoveCursor<S, V>
615    where
616        Self: 'a;
617
618    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
619        self.open_cursor_with_context(score_director, MoveStreamContext::default())
620    }
621
622    fn open_cursor_with_context<'a, D: Director<S>>(
623        &'a self,
624        score_director: &D,
625        _context: MoveStreamContext,
626    ) -> Self::Cursor<'a> {
627        let analysis = self.critical_analysis(score_director);
628        ListPrecedenceMoveCursor::new(
629            analysis.blocks,
630            analysis.route_graph,
631            _context,
632            self.element_count,
633            self.index_to_element,
634            self.fixed_successors,
635            self.entity_count,
636            self.list_len,
637            self.list_get,
638            self.list_remove,
639            self.list_insert,
640            self.list_set,
641            self.list_reverse,
642            self.ruin_remove,
643            self.ruin_insert,
644            self.element_owner_fn,
645            self.sublist_remove,
646            self.sublist_insert,
647            self.variable_name,
648            self.descriptor_index,
649        )
650    }
651
652    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
653        let analysis = self.critical_analysis(score_director);
654        let single_block_count: usize = analysis
655            .blocks
656            .iter()
657            .copied()
658            .map(|block| filtered_move_count(block, &analysis.route_graph))
659            .sum();
660        single_block_count
661            + filtered_multi_support_swap_count(&analysis.blocks, &analysis.route_graph)
662            + multi_critical_ruin_count(&analysis.blocks)
663    }
664}
665
666impl<S, V, ES> ListPrecedenceMoveSelector<S, V, ES>
667where
668    S: PlanningSolution,
669    V: Clone + PartialEq + Send + Sync + Debug + 'static,
670    ES: EntitySelector<S>,
671{
672    fn critical_analysis<D: Director<S>>(&self, score_director: &D) -> CriticalAnalysis {
673        let solution = score_director.working_solution();
674        let node_count = (self.element_count)(solution);
675        if node_count == 0 {
676            return CriticalAnalysis::default();
677        }
678
679        let elements = (0..node_count)
680            .map(|index| (self.index_to_element)(solution, index))
681            .collect::<Vec<_>>();
682        let durations = elements
683            .iter()
684            .map(|element| usize_to_i64((self.node_duration)(solution, element.clone())))
685            .collect::<Vec<_>>();
686        let route_hooks = PrecedenceRouteHooks::new(
687            self.element_count,
688            self.index_to_element,
689            self.fixed_successors,
690            self.entity_count,
691            self.list_len,
692            self.list_get,
693        );
694        let route_graph = route_hooks.build_graph_with_elements(solution, &elements);
695
696        let Some(summary) = graph_summary(
697            &durations,
698            route_graph.successors(),
699            route_graph.predecessors(),
700        ) else {
701            return CriticalAnalysis {
702                blocks: Vec::new(),
703                route_graph,
704            };
705        };
706        let selected =
707            collect_selected_entities(&self.entity_selector, score_director, self.list_len);
708        let mut blocks = Vec::new();
709        for &entity in &selected.entities {
710            let Some(nodes) = route_graph.route(entity) else {
711                continue;
712            };
713            let mut pos = 0;
714            while pos < nodes.len() {
715                let starts_critical_arc = pos + 1 < nodes.len()
716                    && is_critical_arc(
717                        nodes[pos],
718                        nodes[pos + 1],
719                        &durations,
720                        route_graph.successors(),
721                        &summary,
722                    );
723                if !starts_critical_arc {
724                    if is_critical_node(nodes[pos], &summary) {
725                        blocks.push(CriticalBlock {
726                            entity,
727                            start: pos,
728                            end: pos,
729                            route_len: nodes.len(),
730                        });
731                    }
732                    pos += 1;
733                    continue;
734                }
735
736                let start = pos;
737                pos += 1;
738                while pos + 1 < nodes.len()
739                    && is_critical_arc(
740                        nodes[pos],
741                        nodes[pos + 1],
742                        &durations,
743                        route_graph.successors(),
744                        &summary,
745                    )
746                {
747                    pos += 1;
748                }
749                blocks.push(CriticalBlock {
750                    entity,
751                    start,
752                    end: pos,
753                    route_len: nodes.len(),
754                });
755                pos += 1;
756            }
757        }
758        CriticalAnalysis {
759            blocks,
760            route_graph,
761        }
762    }
763}
764
765#[derive(Default)]
766struct CriticalAnalysis {
767    blocks: Vec<CriticalBlock>,
768    route_graph: PrecedenceRouteGraph,
769}
770
771struct GraphSummary {
772    earliest: Vec<i64>,
773    latest: Vec<i64>,
774}
775
776fn graph_summary(
777    durations: &[i64],
778    successors: &[Vec<usize>],
779    predecessors: &[Vec<usize>],
780) -> Option<GraphSummary> {
781    let node_count = durations.len();
782    let mut indegree = predecessors.iter().map(Vec::len).collect::<Vec<_>>();
783    let mut earliest = vec![0i64; node_count];
784    let mut ready = VecDeque::new();
785    for (node, &degree) in indegree.iter().enumerate() {
786        if degree == 0 {
787            ready.push_back(node);
788        }
789    }
790
791    let mut topo = Vec::with_capacity(node_count);
792    while let Some(node) = ready.pop_front() {
793        topo.push(node);
794        let finish = earliest[node].saturating_add(durations[node]);
795        for &successor in &successors[node] {
796            earliest[successor] = earliest[successor].max(finish);
797            indegree[successor] -= 1;
798            if indegree[successor] == 0 {
799                ready.push_back(successor);
800            }
801        }
802    }
803    if topo.len() != node_count {
804        return None;
805    }
806
807    let makespan = topo
808        .iter()
809        .map(|&node| earliest[node].saturating_add(durations[node]))
810        .max()
811        .unwrap_or(0);
812    let mut latest = vec![i64::MAX; node_count];
813    for &node in topo.iter().rev() {
814        latest[node] = if successors[node].is_empty() {
815            makespan.saturating_sub(durations[node])
816        } else {
817            successors[node]
818                .iter()
819                .map(|&successor| latest[successor].saturating_sub(durations[node]))
820                .min()
821                .unwrap_or_else(|| makespan.saturating_sub(durations[node]))
822        };
823    }
824
825    Some(GraphSummary { earliest, latest })
826}
827
828fn is_critical_arc(
829    from: usize,
830    to: usize,
831    durations: &[i64],
832    successors: &[Vec<usize>],
833    summary: &GraphSummary,
834) -> bool {
835    successors[from].contains(&to)
836        && summary.earliest[from] == summary.latest[from]
837        && summary.earliest[to] == summary.latest[to]
838        && summary.earliest[from].saturating_add(durations[from]) == summary.earliest[to]
839}
840
841fn is_critical_node(node: usize, summary: &GraphSummary) -> bool {
842    summary.earliest[node] == summary.latest[node]
843}
844
845fn tiered_precedence_move_index(
846    block: CriticalBlock,
847    offset: usize,
848    context: MoveStreamContext,
849    salt: u64,
850) -> usize {
851    let adjacent_count = block.adjacent_change_move_count();
852    if offset < adjacent_count {
853        return ordered_index(
854            offset,
855            adjacent_count,
856            context,
857            salt ^ 0xAD1A_CE17_0000_0001,
858        );
859    }
860
861    let boundary_count = block.boundary_change_move_count();
862    if offset < adjacent_count + boundary_count {
863        return adjacent_count
864            + ordered_index(
865                offset - adjacent_count,
866                boundary_count,
867                context,
868                salt ^ 0xAD1A_CE17_0000_0002,
869            );
870    }
871
872    let remaining_count = block.move_count() - adjacent_count - boundary_count;
873    adjacent_count
874        + boundary_count
875        + ordered_index(
876            offset - adjacent_count - boundary_count,
877            remaining_count,
878            context,
879            salt ^ 0xAD1A_CE17_0000_0003,
880        )
881}
882
883fn is_valid_non_adjacent_dest(
884    source: usize,
885    source_offset: usize,
886    dest: usize,
887    block_len: usize,
888) -> bool {
889    if dest == source || dest == source + 1 {
890        return false;
891    }
892    if source_offset + 1 < block_len && dest == source + 2 {
893        return false;
894    }
895    true
896}
897
898fn count_boundary_change_moves(block: CriticalBlock) -> usize {
899    boundary_change_offsets(block)
900        .into_iter()
901        .map(|source_offset| {
902            let source = block.start + source_offset;
903            (0..=block.route_len)
904                .filter(|&dest| {
905                    is_valid_non_adjacent_dest(source, source_offset, dest, block.len())
906                })
907                .count()
908        })
909        .sum()
910}
911
912fn boundary_change_offsets(block: CriticalBlock) -> SmallVec<[usize; 2]> {
913    if block.len() == 0 {
914        return SmallVec::new();
915    }
916    let mut offsets = SmallVec::new();
917    offsets.push(0);
918    let last = block.len() - 1;
919    if last != 0 {
920        offsets.push(last);
921    }
922    offsets
923}
924
925fn boundary_change(block: CriticalBlock, mut offset: usize) -> Option<(usize, usize)> {
926    for source_offset in boundary_change_offsets(block) {
927        let source = block.start + source_offset;
928        for dest in 0..=block.route_len {
929            if !is_valid_non_adjacent_dest(source, source_offset, dest, block.len()) {
930                continue;
931            }
932            if offset == 0 {
933                return Some((source, dest));
934            }
935            offset -= 1;
936        }
937    }
938    None
939}
940
941fn interior_change(block: CriticalBlock, mut offset: usize) -> Option<(usize, usize)> {
942    for source_offset in 0..block.len() {
943        if source_offset == 0 || source_offset + 1 == block.len() {
944            continue;
945        }
946        let source = block.start + source_offset;
947        for dest in 0..=block.route_len {
948            if !is_valid_non_adjacent_dest(source, source_offset, dest, block.len()) {
949                continue;
950            }
951            if offset == 0 {
952                return Some((source, dest));
953            }
954            offset -= 1;
955        }
956    }
957    None
958}
959
960fn non_adjacent_change(block: CriticalBlock, offset: usize) -> (usize, usize) {
961    let boundary_count = block.boundary_change_move_count();
962    if offset < boundary_count {
963        return boundary_change(block, offset)
964            .expect("critical block boundary change offset should map to a valid move");
965    }
966    if let Some(change) = interior_change(block, offset - boundary_count) {
967        return change;
968    }
969    panic!("critical block non-adjacent change offset should map to a valid move")
970}
971
972fn critical_swap(block: CriticalBlock, mut offset: usize) -> (usize, usize) {
973    for first_offset in 0..block.len() {
974        for second_offset in first_offset + 1..block.len() {
975            if offset == 0 {
976                return (block.start + first_offset, block.start + second_offset);
977            }
978            offset -= 1;
979        }
980    }
981    panic!("critical block swap offset should map to a valid move")
982}
983
984fn critical_reverse(block: CriticalBlock, mut offset: usize) -> (usize, usize) {
985    for start_offset in 0..block.len() {
986        for end_offset in start_offset + 1..block.len() {
987            if offset == 0 {
988                return (block.start + start_offset, block.start + end_offset + 1);
989            }
990            offset -= 1;
991        }
992    }
993    panic!("critical block reverse offset should map to a valid move")
994}
995
996fn count_adjacent_sublist_swap_moves_for_len(block_len: usize, max_sublist_size: usize) -> usize {
997    if block_len < 3 {
998        return 0;
999    }
1000    let max_sublist_size = max_sublist_size.min(block_len);
1001    let mut count = 0usize;
1002    for start in 0..block_len {
1003        for first_size in 1..=max_sublist_size {
1004            let second_start = start + first_size;
1005            if second_start >= block_len {
1006                break;
1007            }
1008            for second_size in 1..=max_sublist_size {
1009                if first_size == 1 && second_size == 1 {
1010                    continue;
1011                }
1012                if second_start + second_size <= block_len {
1013                    count += 1;
1014                }
1015            }
1016        }
1017    }
1018    count
1019}
1020
1021fn critical_adjacent_sublist_swap(
1022    block: CriticalBlock,
1023    mut offset: usize,
1024) -> (usize, usize, usize, usize) {
1025    let max_sublist_size = CRITICAL_SUBLIST_MAX_SIZE.min(block.len());
1026    for start_offset in 0..block.len() {
1027        for first_size in 1..=max_sublist_size {
1028            let second_start_offset = start_offset + first_size;
1029            if second_start_offset >= block.len() {
1030                break;
1031            }
1032            for second_size in 1..=max_sublist_size {
1033                if first_size == 1 && second_size == 1 {
1034                    continue;
1035                }
1036                let second_end_offset = second_start_offset + second_size;
1037                if second_end_offset > block.len() {
1038                    continue;
1039                }
1040                if offset == 0 {
1041                    return (
1042                        block.start + start_offset,
1043                        block.start + second_start_offset,
1044                        block.start + second_start_offset,
1045                        block.start + second_end_offset,
1046                    );
1047                }
1048                offset -= 1;
1049            }
1050        }
1051    }
1052    panic!("critical block adjacent sublist-swap offset should map to a valid move")
1053}
1054
1055fn critical_ruin_indices(block: CriticalBlock, offset: usize) -> SmallVec<[usize; 8]> {
1056    let window_len = block.len().min(CRITICAL_RUIN_MAX_SIZE);
1057    let max_start = block.len() - window_len;
1058    assert!(
1059        offset <= max_start,
1060        "critical block ruin offset should map to a valid move"
1061    );
1062    let start_offset = offset;
1063    (0..window_len)
1064        .map(|idx| block.start + start_offset + idx)
1065        .collect()
1066}
1067
1068fn critical_adjacent_swaps(blocks: &[CriticalBlock]) -> Vec<AdjacentSwap> {
1069    let mut swaps = Vec::new();
1070    for block in blocks {
1071        for position in block.start..block.end {
1072            push_unique_adjacent_swap(
1073                &mut swaps,
1074                AdjacentSwap {
1075                    entity: block.entity,
1076                    position,
1077                },
1078            );
1079        }
1080    }
1081    swaps
1082}
1083
1084fn support_adjacent_swaps(
1085    blocks: &[CriticalBlock],
1086    route_graph: &PrecedenceRouteGraph,
1087) -> Vec<AdjacentSwap> {
1088    let mut swaps = Vec::new();
1089    for block in blocks {
1090        let Some(route) = route_graph.route(block.entity) else {
1091            continue;
1092        };
1093        for position in block.start..=block.end {
1094            let Some(&node) = route.get(position) else {
1095                continue;
1096            };
1097            for &successor in route_graph.fixed_successors(node) {
1098                push_support_adjacent_swaps(route_graph, successor, &mut swaps);
1099            }
1100            for &predecessor in route_graph.fixed_predecessors(node) {
1101                push_support_adjacent_swaps(route_graph, predecessor, &mut swaps);
1102            }
1103        }
1104    }
1105    swaps
1106}
1107
1108fn push_support_adjacent_swaps(
1109    route_graph: &PrecedenceRouteGraph,
1110    node: usize,
1111    swaps: &mut Vec<AdjacentSwap>,
1112) {
1113    let Some((entity, position)) = route_graph.node_route_position(node) else {
1114        return;
1115    };
1116    let Some(route) = route_graph.route(entity) else {
1117        return;
1118    };
1119    if position > 0 {
1120        push_unique_adjacent_swap(
1121            swaps,
1122            AdjacentSwap {
1123                entity,
1124                position: position - 1,
1125            },
1126        );
1127    }
1128    if position + 1 < route.len() {
1129        push_unique_adjacent_swap(swaps, AdjacentSwap { entity, position });
1130    }
1131}
1132
1133fn push_unique_adjacent_swap(swaps: &mut Vec<AdjacentSwap>, swap: AdjacentSwap) {
1134    if !swaps.contains(&swap) {
1135        swaps.push(swap);
1136    }
1137}
1138
1139fn multi_support_swap_count(
1140    critical_swaps: &[AdjacentSwap],
1141    support_swaps: &[AdjacentSwap],
1142) -> usize {
1143    let mut count = 0usize;
1144    for first_idx in 0..critical_swaps.len() {
1145        let first = critical_swaps[first_idx];
1146        for &second in &critical_swaps[first_idx + 1..] {
1147            if first.entity == second.entity {
1148                continue;
1149            }
1150            count += support_swaps
1151                .iter()
1152                .filter(|&&support| {
1153                    support.entity != first.entity && support.entity != second.entity
1154                })
1155                .count();
1156        }
1157    }
1158    count
1159}
1160
1161fn multi_support_swaps(
1162    critical_swaps: &[AdjacentSwap],
1163    support_swaps: &[AdjacentSwap],
1164    mut offset: usize,
1165) -> SmallVec<[(usize, usize, usize); 4]> {
1166    for first_idx in 0..critical_swaps.len() {
1167        let first = critical_swaps[first_idx];
1168        for &second in &critical_swaps[first_idx + 1..] {
1169            if first.entity == second.entity {
1170                continue;
1171            }
1172            for &support in support_swaps {
1173                if support.entity == first.entity || support.entity == second.entity {
1174                    continue;
1175                }
1176                if offset == 0 {
1177                    return smallvec![first.as_tuple(), second.as_tuple(), support.as_tuple()];
1178                }
1179                offset -= 1;
1180            }
1181        }
1182    }
1183    SmallVec::new()
1184}
1185
1186fn filtered_multi_support_swap_count(
1187    blocks: &[CriticalBlock],
1188    route_graph: &PrecedenceRouteGraph,
1189) -> usize {
1190    let critical_swaps = critical_adjacent_swaps(blocks);
1191    let support_swaps = support_adjacent_swaps(blocks, route_graph);
1192    let count = multi_support_swap_count(&critical_swaps, &support_swaps);
1193    (0..count)
1194        .filter(|&offset| {
1195            let swaps = multi_support_swaps(&critical_swaps, &support_swaps, offset);
1196            !route_graph.multi_intra_list_swaps_introduce_cycle(&swaps)
1197        })
1198        .count()
1199}
1200
1201fn multi_critical_ruin_count(blocks: &[CriticalBlock]) -> usize {
1202    let mut count = 0usize;
1203    for first_idx in 0..blocks.len() {
1204        let first_count = blocks[first_idx].len();
1205        if first_count == 0 {
1206            continue;
1207        }
1208        for second in &blocks[first_idx + 1..] {
1209            count += first_count * second.len();
1210        }
1211    }
1212    count
1213}
1214
1215fn multi_critical_ruin_sources(
1216    blocks: &[CriticalBlock],
1217    mut offset: usize,
1218) -> SmallVec<[(usize, SmallVec<[usize; 8]>); 4]> {
1219    for first_idx in 0..blocks.len() {
1220        let first = blocks[first_idx];
1221        let first_count = first.len();
1222        if first_count == 0 {
1223            continue;
1224        }
1225        for second in &blocks[first_idx + 1..] {
1226            let second_count = second.len();
1227            let pair_count = first_count * second_count;
1228            if offset >= pair_count {
1229                offset -= pair_count;
1230                continue;
1231            }
1232            let first_offset = offset / second_count;
1233            let second_offset = offset % second_count;
1234            return smallvec![
1235                (first.entity, smallvec![first.start + first_offset]),
1236                (second.entity, smallvec![second.start + second_offset])
1237            ];
1238        }
1239    }
1240    SmallVec::new()
1241}
1242
1243fn count_permute_moves_for_len(block_len: usize, max_window_size: usize) -> usize {
1244    if block_len < 2 {
1245        return 0;
1246    }
1247    let max_window_size = max_window_size
1248        .min(MAX_LIST_PERMUTE_WINDOW_SIZE)
1249        .min(block_len);
1250    let mut count = 0;
1251    for start in 0..block_len {
1252        let max_valid = max_window_size.min(block_len - start);
1253        for size in 2..=max_valid {
1254            count += factorial(size).saturating_sub(1);
1255        }
1256    }
1257    count
1258}
1259
1260fn count_sublist_change_moves_for_len(
1261    block_len: usize,
1262    route_len: usize,
1263    max_sublist_size: usize,
1264) -> usize {
1265    if block_len < 2 || route_len < 2 {
1266        return 0;
1267    }
1268    let max_sublist_size = max_sublist_size.min(block_len).min(route_len);
1269    let mut count = 0usize;
1270    for size in 2..=max_sublist_size {
1271        let source_count = block_len - size + 1;
1272        let dest_count = route_len.saturating_sub(size);
1273        count += source_count * dest_count;
1274    }
1275    count
1276}
1277
1278fn critical_sublist_change(
1279    block_start: usize,
1280    block_len: usize,
1281    route_len: usize,
1282    mut offset: usize,
1283) -> (usize, usize, usize) {
1284    let max_sublist_size = CRITICAL_SUBLIST_MAX_SIZE.min(block_len).min(route_len);
1285    for size in 2..=max_sublist_size {
1286        for source_start in 0..=block_len - size {
1287            for dest in 0..=route_len - size {
1288                if dest == block_start + source_start {
1289                    continue;
1290                }
1291                if offset == 0 {
1292                    return (source_start, size, dest);
1293                }
1294                offset -= 1;
1295            }
1296        }
1297    }
1298    panic!("critical sublist-change offset should map to a valid move")
1299}
1300
1301fn critical_permutation(
1302    block_len: usize,
1303    mut offset: usize,
1304) -> (
1305    usize,
1306    usize,
1307    SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]>,
1308) {
1309    let max_window_size = CRITICAL_PERMUTE_MAX_WINDOW_SIZE
1310        .min(MAX_LIST_PERMUTE_WINDOW_SIZE)
1311        .min(block_len);
1312    for start in 0..block_len {
1313        let max_valid = max_window_size.min(block_len - start);
1314        for size in 2..=max_valid {
1315            let permutation_count = factorial(size).saturating_sub(1);
1316            if offset < permutation_count {
1317                return (start, size, nth_permutation(size, offset + 1));
1318            }
1319            offset -= permutation_count;
1320        }
1321    }
1322    panic!("critical permutation offset should map to a valid window")
1323}
1324
1325fn filtered_move_count(block: CriticalBlock, route_graph: &PrecedenceRouteGraph) -> usize {
1326    (0..block.move_count())
1327        .filter(|&move_idx| !move_introduces_route_cycle(block, move_idx, route_graph))
1328        .count()
1329}
1330
1331fn move_introduces_route_cycle(
1332    block: CriticalBlock,
1333    move_idx: usize,
1334    route_graph: &PrecedenceRouteGraph,
1335) -> bool {
1336    let Some(route) = route_graph.route(block.entity) else {
1337        return false;
1338    };
1339    if route.len() != block.route_len {
1340        return false;
1341    }
1342    let change_count = block.change_move_count();
1343    if move_idx < change_count {
1344        let (source, dest) = if move_idx < block.adjacent_change_move_count() {
1345            (block.start + move_idx, block.start + move_idx + 2)
1346        } else {
1347            non_adjacent_change(block, move_idx - block.adjacent_change_move_count())
1348        };
1349        return route_graph.intra_list_change_introduces_cycle(block.entity, source, dest);
1350    }
1351
1352    let swap_count = block.swap_move_count();
1353    if move_idx < change_count + swap_count {
1354        let (first, second) = critical_swap(block, move_idx - change_count);
1355        return route_graph.intra_list_swap_introduces_cycle(block.entity, first, second);
1356    }
1357
1358    let reverse_count = block.reverse_move_count();
1359    if move_idx < change_count + swap_count + reverse_count {
1360        let (start, end) = critical_reverse(block, move_idx - change_count - swap_count);
1361        return route_graph.intra_list_reverse_introduces_cycle(block.entity, start, end);
1362    }
1363
1364    let adjacent_sublist_swap_count = block.adjacent_sublist_swap_move_count();
1365    if move_idx < change_count + swap_count + reverse_count + adjacent_sublist_swap_count {
1366        let (first_start, first_end, second_start, second_end) = critical_adjacent_sublist_swap(
1367            block,
1368            move_idx - change_count - swap_count - reverse_count,
1369        );
1370        return route_graph.intra_sublist_swap_introduces_cycle(
1371            block.entity,
1372            first_start,
1373            first_end,
1374            second_start,
1375            second_end,
1376        );
1377    }
1378
1379    let ruin_count = block.ruin_move_count();
1380    if move_idx
1381        < change_count + swap_count + reverse_count + adjacent_sublist_swap_count + ruin_count
1382    {
1383        return false;
1384    }
1385
1386    let sublist_change_count = block.sublist_change_move_count();
1387    if move_idx
1388        < change_count
1389            + swap_count
1390            + reverse_count
1391            + adjacent_sublist_swap_count
1392            + ruin_count
1393            + sublist_change_count
1394    {
1395        let (source_start, size, dest) = critical_sublist_change(
1396            block.start,
1397            block.len(),
1398            block.route_len,
1399            move_idx
1400                - change_count
1401                - swap_count
1402                - reverse_count
1403                - adjacent_sublist_swap_count
1404                - ruin_count,
1405        );
1406        return route_graph.intra_sublist_change_introduces_cycle(
1407            block.entity,
1408            block.start + source_start,
1409            block.start + source_start + size,
1410            dest,
1411        );
1412    }
1413
1414    let (start_offset, size, permutation) = critical_permutation(
1415        block.len(),
1416        move_idx
1417            - change_count
1418            - swap_count
1419            - reverse_count
1420            - adjacent_sublist_swap_count
1421            - ruin_count
1422            - sublist_change_count,
1423    );
1424    let start = block.start + start_offset;
1425    route_graph.intra_list_permutation_introduces_cycle(
1426        block.entity,
1427        start,
1428        start + size,
1429        &permutation,
1430    )
1431}
1432
1433fn factorial(value: usize) -> usize {
1434    (2..=value).product()
1435}
1436
1437fn nth_permutation(len: usize, mut rank: usize) -> SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]> {
1438    let mut remaining: SmallVec<[usize; MAX_LIST_PERMUTE_WINDOW_SIZE]> = (0..len).collect();
1439    let mut permutation = smallvec![];
1440    for pos in 0..len {
1441        let suffix = len - pos - 1;
1442        let step = factorial(suffix);
1443        let index = rank / step;
1444        rank %= step;
1445        permutation.push(remaining.remove(index));
1446    }
1447    permutation
1448}
1449
1450fn usize_to_i64(value: usize) -> i64 {
1451    i64::try_from(value).unwrap_or(i64::MAX)
1452}
solverforge_solver/heuristic/selector/list_precedence.rs

solverforge_solver/heuristic/selector/
list_precedence.rs
