solverforge_solver/heuristic/selector/k_opt/
selector.rs

1//! Public static adapter for the canonical exhaustive K-opt cursor.
2
3use std::fmt::Debug;
4use std::marker::PhantomData;
5
6use solverforge_core::domain::PlanningSolution;
7use solverforge_scoring::Director;
8
9use crate::heuristic::r#move::k_opt_reconnection::{
10    enumerate_reconnections, KOptReconnection, THREE_OPT_RECONNECTIONS,
11};
12use crate::heuristic::r#move::KOptMove;
13use crate::heuristic::selector::list_kernel::{KOptCursor, NativeKOptEmitter};
14
15use super::super::entity::EntitySelector;
16use super::super::move_selector::{
17    CandidateId, MoveCandidateRef, MoveCursor, MoveSelector, MoveStreamContext,
18};
19use super::config::KOptConfig;
20use super::iterators::count_cut_combinations;
21
22/// Static K-opt selector.  It preserves its public move/cursor types while
23/// common cut and reconnection enumeration is owned by the shared list kernel.
24pub struct KOptMoveSelector<S, V, ES> {
25    entity_selector: ES,
26    config: KOptConfig,
27    owned_patterns: Vec<KOptReconnection>,
28    list_len: fn(&S, usize) -> usize,
29    list_get: fn(&S, usize, usize) -> Option<V>,
30    sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
31    sublist_insert: fn(&mut S, usize, usize, Vec<V>),
32    variable_name: &'static str,
33    descriptor_index: usize,
34    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
35}
36
37pub struct KOptMoveCursor<'a, S, V>
38where
39    S: PlanningSolution,
40    V: Clone + Send + Sync + Debug + 'static,
41{
42    inner: KOptCursor<'a, S, NativeKOptEmitter<S, V>>,
43}
44
45impl<'a, S, V> KOptMoveCursor<'a, S, V>
46where
47    S: PlanningSolution,
48    V: Clone + Send + Sync + Debug + 'static,
49{
50    fn new(inner: KOptCursor<'a, S, NativeKOptEmitter<S, V>>) -> Self {
51        Self { inner }
52    }
53}
54
55impl<S, V> MoveCursor<S, KOptMove<S, V>> for KOptMoveCursor<'_, S, V>
56where
57    S: PlanningSolution,
58    V: Clone + Send + Sync + Debug + 'static,
59{
60    fn next_candidate(&mut self) -> Option<CandidateId> {
61        self.inner.next_candidate()
62    }
63    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, KOptMove<S, V>>> {
64        self.inner.candidate(id)
65    }
66    fn take_candidate(&mut self, id: CandidateId) -> KOptMove<S, V> {
67        self.inner.take_candidate(id)
68    }
69    fn next_owned_candidate(&mut self) -> Option<KOptMove<S, V>> {
70        self.inner.next_owned_candidate()
71    }
72    fn next_owned_candidate_matching(
73        &mut self,
74        predicate: for<'b> fn(MoveCandidateRef<'b, S, KOptMove<S, V>>) -> bool,
75    ) -> Option<KOptMove<S, V>> {
76        self.inner.next_owned_candidate_matching(predicate)
77    }
78    fn release_candidate(&mut self, id: CandidateId) -> bool {
79        self.inner.release_candidate(id)
80    }
81}
82
83impl<S, V> Iterator for KOptMoveCursor<'_, S, V>
84where
85    S: PlanningSolution,
86    V: Clone + Send + Sync + Debug + 'static,
87{
88    type Item = KOptMove<S, V>;
89    fn next(&mut self) -> Option<Self::Item> {
90        self.next_owned_candidate()
91    }
92}
93
94impl<S, V: Debug, ES: Debug> Debug for KOptMoveSelector<S, V, ES> {
95    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
96        f.debug_struct("KOptMoveSelector")
97            .field("entity_selector", &self.entity_selector)
98            .field("config", &self.config)
99            .field("pattern_count", &self.owned_patterns.len())
100            .field("variable_name", &self.variable_name)
101            .finish()
102    }
103}
104
105impl<S: PlanningSolution, V, ES> KOptMoveSelector<S, V, ES> {
106    #[allow(clippy::too_many_arguments)]
107    pub fn new(
108        entity_selector: ES,
109        config: KOptConfig,
110        list_len: fn(&S, usize) -> usize,
111        list_get: fn(&S, usize, usize) -> Option<V>,
112        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
113        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
114        variable_name: &'static str,
115        descriptor_index: usize,
116    ) -> Self {
117        let owned_patterns = if config.k == 3 {
118            THREE_OPT_RECONNECTIONS.to_vec()
119        } else {
120            enumerate_reconnections(config.k)
121        };
122        Self {
123            entity_selector,
124            config,
125            owned_patterns,
126            list_len,
127            list_get,
128            sublist_remove,
129            sublist_insert,
130            variable_name,
131            descriptor_index,
132            _phantom: PhantomData,
133        }
134    }
135}
136
137impl<S, V, ES> MoveSelector<S, KOptMove<S, V>> for KOptMoveSelector<S, V, ES>
138where
139    S: PlanningSolution,
140    ES: EntitySelector<S>,
141    V: Clone + Send + Sync + Debug + 'static,
142{
143    type Cursor<'a>
144        = KOptMoveCursor<'a, S, V>
145    where
146        Self: 'a;
147
148    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
149        self.open_cursor_with_context(score_director, MoveStreamContext::default())
150    }
151
152    fn open_cursor_with_context<'a, D: Director<S>>(
153        &'a self,
154        score_director: &D,
155        context: MoveStreamContext,
156    ) -> Self::Cursor<'a> {
157        let entity_lens = self
158            .entity_selector
159            .iter(score_director)
160            .map(|reference| {
161                let entity = reference.entity_index;
162                (
163                    entity,
164                    (self.list_len)(score_director.working_solution(), entity),
165                )
166            })
167            .collect();
168        KOptMoveCursor::new(KOptCursor::new(
169            NativeKOptEmitter::new(
170                self.list_len,
171                self.list_get,
172                self.sublist_remove,
173                self.sublist_insert,
174                self.variable_name,
175                self.descriptor_index,
176            ),
177            entity_lens,
178            self.config.k,
179            self.config.min_segment_len,
180            &self.owned_patterns,
181            context,
182            self.descriptor_index,
183        ))
184    }
185
186    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
187        self.entity_selector
188            .iter(score_director)
189            .map(|reference| {
190                let len =
191                    (self.list_len)(score_director.working_solution(), reference.entity_index);
192                count_cut_combinations(self.config.k, len, self.config.min_segment_len)
193                    * self.owned_patterns.len()
194            })
195            .sum()
196    }
197}
solverforge_solver/heuristic/selector/k_opt/selector.rs

solverforge_solver/heuristic/selector/k_opt/
selector.rs
