solverforge_solver/heuristic/selector/k_opt/
nearby.rs

1//! Public static adapter for the canonical nearby 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::{NativeKOptEmitter, NearbyKOptCursor};
14
15use super::super::entity::EntitySelector;
16use super::super::move_selector::{
17    CandidateId, MoveCandidateRef, MoveCursor, MoveSelector, MoveStreamContext,
18};
19use super::config::KOptConfig;
20use super::distance_meter::ListPositionDistanceMeter;
21
22pub struct NearbyKOptMoveSelector<S, V, D: ListPositionDistanceMeter<S>, ES> {
23    entity_selector: ES,
24    distance_meter: D,
25    max_nearby: usize,
26    config: KOptConfig,
27    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 NearbyKOptMoveCursor<'a, S, V, D>
38where
39    S: PlanningSolution,
40    V: Clone + Send + Sync + Debug + 'static,
41    D: ListPositionDistanceMeter<S>,
42{
43    inner: NearbyKOptCursor<'a, S, NativeKOptEmitter<S, V>, &'a D>,
44}
45
46impl<'a, S, V, D> NearbyKOptMoveCursor<'a, S, V, D>
47where
48    S: PlanningSolution,
49    V: Clone + Send + Sync + Debug + 'static,
50    D: ListPositionDistanceMeter<S>,
51{
52    fn new(inner: NearbyKOptCursor<'a, S, NativeKOptEmitter<S, V>, &'a D>) -> Self {
53        Self { inner }
54    }
55}
56
57impl<S, V, D> MoveCursor<S, KOptMove<S, V>> for NearbyKOptMoveCursor<'_, S, V, D>
58where
59    S: PlanningSolution,
60    V: Clone + Send + Sync + Debug + 'static,
61    D: ListPositionDistanceMeter<S>,
62{
63    fn next_candidate(&mut self) -> Option<CandidateId> {
64        self.inner.next_candidate()
65    }
66    fn candidate(&self, id: CandidateId) -> Option<MoveCandidateRef<'_, S, KOptMove<S, V>>> {
67        self.inner.candidate(id)
68    }
69    fn take_candidate(&mut self, id: CandidateId) -> KOptMove<S, V> {
70        self.inner.take_candidate(id)
71    }
72    fn next_owned_candidate(&mut self) -> Option<KOptMove<S, V>> {
73        self.inner.next_owned_candidate()
74    }
75    fn next_owned_candidate_matching(
76        &mut self,
77        predicate: for<'b> fn(MoveCandidateRef<'b, S, KOptMove<S, V>>) -> bool,
78    ) -> Option<KOptMove<S, V>> {
79        self.inner.next_owned_candidate_matching(predicate)
80    }
81    fn release_candidate(&mut self, id: CandidateId) -> bool {
82        self.inner.release_candidate(id)
83    }
84}
85
86impl<S, V, D> Iterator for NearbyKOptMoveCursor<'_, S, V, D>
87where
88    S: PlanningSolution,
89    V: Clone + Send + Sync + Debug + 'static,
90    D: ListPositionDistanceMeter<S>,
91{
92    type Item = KOptMove<S, V>;
93    fn next(&mut self) -> Option<Self::Item> {
94        self.next_owned_candidate()
95    }
96}
97
98impl<S, V: Debug, D: ListPositionDistanceMeter<S>, ES: Debug> Debug
99    for NearbyKOptMoveSelector<S, V, D, ES>
100{
101    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
102        f.debug_struct("NearbyKOptMoveSelector")
103            .field("entity_selector", &self.entity_selector)
104            .field("max_nearby", &self.max_nearby)
105            .field("config", &self.config)
106            .field("pattern_count", &self.patterns.len())
107            .finish()
108    }
109}
110
111impl<S: PlanningSolution, V, D: ListPositionDistanceMeter<S>, ES>
112    NearbyKOptMoveSelector<S, V, D, ES>
113{
114    #[allow(clippy::too_many_arguments)]
115    pub fn new(
116        entity_selector: ES,
117        distance_meter: D,
118        max_nearby: usize,
119        config: KOptConfig,
120        list_len: fn(&S, usize) -> usize,
121        list_get: fn(&S, usize, usize) -> Option<V>,
122        sublist_remove: fn(&mut S, usize, usize, usize) -> Vec<V>,
123        sublist_insert: fn(&mut S, usize, usize, Vec<V>),
124        variable_name: &'static str,
125        descriptor_index: usize,
126    ) -> Self {
127        let patterns = if config.k == 3 {
128            THREE_OPT_RECONNECTIONS.to_vec()
129        } else {
130            enumerate_reconnections(config.k)
131        };
132        Self {
133            entity_selector,
134            distance_meter,
135            max_nearby,
136            config,
137            patterns,
138            list_len,
139            list_get,
140            sublist_remove,
141            sublist_insert,
142            variable_name,
143            descriptor_index,
144            _phantom: PhantomData,
145        }
146    }
147}
148
149impl<S, V, DM, ES> MoveSelector<S, KOptMove<S, V>> for NearbyKOptMoveSelector<S, V, DM, ES>
150where
151    S: PlanningSolution,
152    V: Clone + Send + Sync + Debug + 'static,
153    DM: ListPositionDistanceMeter<S> + 'static,
154    ES: EntitySelector<S>,
155{
156    type Cursor<'a>
157        = NearbyKOptMoveCursor<'a, S, V, DM>
158    where
159        Self: 'a;
160
161    fn open_cursor<'a, SD: Director<S>>(&'a self, score_director: &SD) -> Self::Cursor<'a> {
162        self.open_cursor_with_context(score_director, MoveStreamContext::default())
163    }
164
165    fn open_cursor_with_context<'a, SD: Director<S>>(
166        &'a self,
167        score_director: &SD,
168        context: MoveStreamContext,
169    ) -> Self::Cursor<'a> {
170        let solution = score_director.working_solution();
171        let entities = self
172            .entity_selector
173            .iter(score_director)
174            .map(|reference| reference.entity_index)
175            .collect();
176        NearbyKOptMoveCursor::new(NearbyKOptCursor::new(
177            NativeKOptEmitter::new(
178                self.list_len,
179                self.list_get,
180                self.sublist_remove,
181                self.sublist_insert,
182                self.variable_name,
183                self.descriptor_index,
184            ),
185            solution.clone(),
186            &self.distance_meter,
187            entities,
188            self.config.k,
189            self.config.min_segment_len,
190            self.max_nearby,
191            &self.patterns,
192            self.list_len,
193            context,
194            self.descriptor_index,
195        ))
196    }
197
198    fn size<SD: Director<S>>(&self, score_director: &SD) -> usize {
199        self.entity_selector
200            .iter(score_director)
201            .map(|reference| {
202                let len =
203                    (self.list_len)(score_director.working_solution(), reference.entity_index);
204                if len < (self.config.k + 1) * self.config.min_segment_len {
205                    0
206                } else {
207                    len.saturating_sub(self.config.k)
208                        * self.max_nearby.pow((self.config.k - 1) as u32)
209                        * self.patterns.len()
210                }
211            })
212            .sum()
213    }
214}
solverforge_solver/heuristic/selector/k_opt/nearby.rs

solverforge_solver/heuristic/selector/k_opt/
nearby.rs
