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, solution: &S) -> Option<CandidateId> {
64        self.inner.next_candidate(solution)
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, solution: &S) -> Option<KOptMove<S, V>> {
73        self.inner.next_owned_candidate(solution)
74    }
75    fn next_owned_candidate_matching(
76        &mut self,
77        solution: &S,
78        predicate: for<'b> fn(MoveCandidateRef<'b, S, KOptMove<S, V>>) -> bool,
79    ) -> Option<KOptMove<S, V>> {
80        self.inner
81            .next_owned_candidate_matching(solution, predicate)
82    }
83    fn release_candidate(&mut self, id: CandidateId) -> bool {
84        self.inner.release_candidate(id)
85    }
86}
87
88impl<S, V: Debug, D: ListPositionDistanceMeter<S>, ES: Debug> Debug
89    for NearbyKOptMoveSelector<S, V, D, ES>
90{
91    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
92        f.debug_struct("NearbyKOptMoveSelector")
93            .field("entity_selector", &self.entity_selector)
94            .field("max_nearby", &self.max_nearby)
95            .field("config", &self.config)
96            .field("pattern_count", &self.patterns.len())
97            .finish()
98    }
99}
100
101impl<S: PlanningSolution, V, D: ListPositionDistanceMeter<S>, ES>
102    NearbyKOptMoveSelector<S, V, D, ES>
103{
104    #[allow(clippy::too_many_arguments)]
105    pub fn new(
106        entity_selector: ES,
107        distance_meter: D,
108        max_nearby: usize,
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 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            distance_meter,
125            max_nearby,
126            config,
127            patterns,
128            list_len,
129            list_get,
130            sublist_remove,
131            sublist_insert,
132            variable_name,
133            descriptor_index,
134            _phantom: PhantomData,
135        }
136    }
137}
138
139impl<S, V, DM, ES> MoveSelector<S, KOptMove<S, V>> for NearbyKOptMoveSelector<S, V, DM, ES>
140where
141    S: PlanningSolution,
142    V: Clone + Send + Sync + Debug + 'static,
143    DM: ListPositionDistanceMeter<S> + 'static,
144    ES: EntitySelector<S>,
145{
146    type Cursor<'a>
147        = NearbyKOptMoveCursor<'a, S, V, DM>
148    where
149        Self: 'a;
150
151    fn open_cursor<'a, SD: Director<S>>(&'a self, score_director: &SD) -> Self::Cursor<'a> {
152        self.open_cursor_with_context(score_director, MoveStreamContext::default())
153    }
154
155    fn open_cursor_with_context<'a, SD: Director<S>>(
156        &'a self,
157        score_director: &SD,
158        context: MoveStreamContext,
159    ) -> Self::Cursor<'a> {
160        let solution = score_director.working_solution();
161        let entities = self
162            .entity_selector
163            .iter(score_director)
164            .map(|reference| {
165                let entity = reference.entity_index;
166                (entity, (self.list_len)(solution, entity))
167            })
168            .collect();
169        NearbyKOptMoveCursor::new(NearbyKOptCursor::new(
170            NativeKOptEmitter::new(
171                self.list_len,
172                self.list_get,
173                self.sublist_remove,
174                self.sublist_insert,
175                self.variable_name,
176                self.descriptor_index,
177            ),
178            &self.distance_meter,
179            entities,
180            self.config.k,
181            self.config.min_segment_len,
182            self.max_nearby,
183            &self.patterns,
184            context,
185            self.descriptor_index,
186        ))
187    }
188
189    fn size<SD: Director<S>>(&self, score_director: &SD) -> usize {
190        self.entity_selector
191            .iter(score_director)
192            .map(|reference| {
193                let len =
194                    (self.list_len)(score_director.working_solution(), reference.entity_index);
195                if len < (self.config.k + 1) * self.config.min_segment_len {
196                    0
197                } else {
198                    len.saturating_sub(self.config.k)
199                        * self.max_nearby.pow((self.config.k - 1) as u32)
200                        * self.patterns.len()
201                }
202            })
203            .sum()
204    }
205}
solverforge_solver/heuristic/selector/k_opt/nearby.rs

solverforge_solver/heuristic/selector/k_opt/
nearby.rs
