solverforge_solver/heuristic/selector/
pillar.rs

1//! Pillar selector for selecting groups of entities with the same variable value.
2//!
3//! A pillar is a group of entities that share the same planning variable value.
4//! Pillar moves operate on entire pillars, changing or swapping all entities
5//! in the pillar atomically.
6
7use std::collections::HashMap;
8use std::fmt::Debug;
9use std::hash::Hash;
10use std::marker::PhantomData;
11
12use solverforge_core::domain::PlanningSolution;
13use solverforge_scoring::ScoreDirector;
14
15use super::entity::{EntityReference, EntitySelector};
16
17/// A pillar is a group of entity references that share the same variable value.
18///
19/// All entities in a pillar have the same value for a specific planning variable,
20/// which allows them to be moved together atomically.
21#[derive(Debug, Clone, PartialEq, Eq)]
22pub struct Pillar {
23    /// The entity references in this pillar.
24    pub entities: Vec<EntityReference>,
25}
26
27impl Pillar {
28    /// Creates a new pillar with the given entities.
29    pub fn new(entities: Vec<EntityReference>) -> Self {
30        Self { entities }
31    }
32
33    /// Returns the number of entities in this pillar.
34    pub fn size(&self) -> usize {
35        self.entities.len()
36    }
37
38    /// Returns true if this pillar is empty.
39    pub fn is_empty(&self) -> bool {
40        self.entities.is_empty()
41    }
42
43    /// Returns the first entity reference in this pillar.
44    pub fn first(&self) -> Option<&EntityReference> {
45        self.entities.first()
46    }
47
48    /// Returns an iterator over the entity references.
49    pub fn iter(&self) -> impl Iterator<Item = &EntityReference> {
50        self.entities.iter()
51    }
52}
53
54/// Trait for selecting pillars of entities.
55///
56/// A pillar selector groups entities by their variable values and returns
57/// groups (pillars) that can be moved together.
58///
59/// # Type Parameters
60/// * `S` - The planning solution type
61pub trait PillarSelector<S: PlanningSolution>: Send + Debug {
62    /// Returns an iterator over pillars.
63    ///
64    /// Each pillar contains entity references for entities that share
65    /// the same variable value.
66    fn iter<'a, D: ScoreDirector<S>>(
67        &'a self,
68        score_director: &'a D,
69    ) -> impl Iterator<Item = Pillar> + 'a;
70
71    /// Returns the approximate number of pillars.
72    fn size<D: ScoreDirector<S>>(&self, score_director: &D) -> usize;
73
74    /// Returns true if this selector may return the same pillar multiple times.
75    fn is_never_ending(&self) -> bool {
76        false
77    }
78
79    /// Returns the descriptor index this selector operates on.
80    fn descriptor_index(&self) -> usize;
81}
82
83/// Configuration for sub-pillar selection.
84#[derive(Debug, Clone)]
85pub struct SubPillarConfig {
86    /// Whether sub-pillar selection is enabled.
87    pub enabled: bool,
88    /// Minimum size of a sub-pillar (default: 1).
89    pub minimum_size: usize,
90    /// Maximum size of a sub-pillar (default: usize::MAX).
91    pub maximum_size: usize,
92}
93
94impl Default for SubPillarConfig {
95    fn default() -> Self {
96        Self {
97            enabled: false,
98            minimum_size: 1,
99            maximum_size: usize::MAX,
100        }
101    }
102}
103
104impl SubPillarConfig {
105    /// Creates a new sub-pillar config with sub-pillars disabled.
106    pub fn none() -> Self {
107        Self::default()
108    }
109
110    /// Creates a new sub-pillar config with sub-pillars enabled.
111    pub fn all() -> Self {
112        Self {
113            enabled: true,
114            minimum_size: 1,
115            maximum_size: usize::MAX,
116        }
117    }
118
119    /// Sets the minimum sub-pillar size.
120    pub fn with_minimum_size(mut self, size: usize) -> Self {
121        self.minimum_size = size.max(1);
122        self
123    }
124
125    /// Sets the maximum sub-pillar size.
126    pub fn with_maximum_size(mut self, size: usize) -> Self {
127        self.maximum_size = size;
128        self
129    }
130}
131
132/// A pillar selector that groups entities by their variable value.
133///
134/// This selector uses an entity selector to get entities, then groups them
135/// by the value of a specified variable using a value extractor function.
136///
137/// # Zero-Erasure Design
138///
139/// Both the entity selector `ES` and the extractor function `E` are stored as
140/// concrete generic type parameters, eliminating all virtual dispatch overhead.
141///
142/// **Note**: The value extractor closure uses `&dyn ScoreDirector<S>` intentionally.
143/// This is a scorer-agnostic boundary - the closure doesn't need the concrete `D` type.
144pub struct DefaultPillarSelector<S, V, ES, E>
145where
146    S: PlanningSolution,
147    V: Clone + Eq + Hash + Send + Sync + 'static,
148    ES: EntitySelector<S>,
149    E: Fn(&dyn ScoreDirector<S>, usize, usize) -> Option<V> + Send + Sync,
150{
151    /// The underlying entity selector (zero-erasure).
152    entity_selector: ES,
153    /// The descriptor index.
154    descriptor_index: usize,
155    /// The variable name for grouping.
156    variable_name: &'static str,
157    /// Function to extract the value from an entity for grouping (zero-erasure).
158    value_extractor: E,
159    /// Sub-pillar configuration.
160    sub_pillar_config: SubPillarConfig,
161    /// Marker for solution and value types.
162    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
163}
164
165impl<S, V, ES, E> Debug for DefaultPillarSelector<S, V, ES, E>
166where
167    S: PlanningSolution,
168    V: Clone + Eq + Hash + Send + Sync + 'static,
169    ES: EntitySelector<S> + Debug,
170    E: Fn(&dyn ScoreDirector<S>, usize, usize) -> Option<V> + Send + Sync,
171{
172    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
173        f.debug_struct("DefaultPillarSelector")
174            .field("entity_selector", &self.entity_selector)
175            .field("descriptor_index", &self.descriptor_index)
176            .field("variable_name", &self.variable_name)
177            .field("sub_pillar_config", &self.sub_pillar_config)
178            .finish()
179    }
180}
181
182impl<S, V, ES, E> DefaultPillarSelector<S, V, ES, E>
183where
184    S: PlanningSolution,
185    V: Clone + Eq + Hash + Send + Sync + 'static,
186    ES: EntitySelector<S>,
187    E: Fn(&dyn ScoreDirector<S>, usize, usize) -> Option<V> + Send + Sync,
188{
189    /// Creates a new default pillar selector.
190    ///
191    /// # Arguments
192    ///
193    /// * `entity_selector` - The entity selector to get entities from
194    /// * `descriptor_index` - The entity descriptor index
195    /// * `variable_name` - The variable name for grouping
196    /// * `value_extractor` - Function to extract the grouping value from an entity
197    pub fn new(
198        entity_selector: ES,
199        descriptor_index: usize,
200        variable_name: &'static str,
201        value_extractor: E,
202    ) -> Self {
203        Self {
204            entity_selector,
205            descriptor_index,
206            variable_name,
207            value_extractor,
208            sub_pillar_config: SubPillarConfig::default(),
209            _phantom: PhantomData,
210        }
211    }
212
213    /// Sets the sub-pillar configuration.
214    pub fn with_sub_pillar_config(mut self, config: SubPillarConfig) -> Self {
215        self.sub_pillar_config = config;
216        self
217    }
218
219    /// Returns the variable name.
220    pub fn variable_name(&self) -> &str {
221        self.variable_name
222    }
223
224    /// Builds the pillar list from the current solution state.
225    fn build_pillars<D: ScoreDirector<S>>(&self, score_director: &D) -> Vec<Pillar> {
226        // Group entities by their value
227        let mut value_to_entities: HashMap<Option<V>, Vec<EntityReference>> = HashMap::new();
228
229        for entity_ref in self.entity_selector.iter(score_director) {
230            // Use dyn ScoreDirector for the extractor (intentional type-erasure boundary)
231            let value = (self.value_extractor)(
232                score_director,
233                entity_ref.descriptor_index,
234                entity_ref.entity_index,
235            );
236            value_to_entities.entry(value).or_default().push(entity_ref);
237        }
238
239        // Filter by minimum size and create pillars
240        let min_size = self.sub_pillar_config.minimum_size;
241        value_to_entities
242            .into_values()
243            .filter(|entities| entities.len() >= min_size)
244            .map(Pillar::new)
245            .collect()
246    }
247}
248
249impl<S, V, ES, E> PillarSelector<S> for DefaultPillarSelector<S, V, ES, E>
250where
251    S: PlanningSolution,
252    V: Clone + Eq + Hash + Send + Sync + 'static,
253    ES: EntitySelector<S>,
254    E: Fn(&dyn ScoreDirector<S>, usize, usize) -> Option<V> + Send + Sync,
255{
256    fn iter<'a, D: ScoreDirector<S>>(
257        &'a self,
258        score_director: &'a D,
259    ) -> impl Iterator<Item = Pillar> + 'a {
260        let pillars = self.build_pillars(score_director);
261        pillars.into_iter()
262    }
263
264    fn size<D: ScoreDirector<S>>(&self, score_director: &D) -> usize {
265        self.build_pillars(score_director).len()
266    }
267
268    fn descriptor_index(&self) -> usize {
269        self.descriptor_index
270    }
271}
272
273#[cfg(test)]
274#[path = "pillar_tests.rs"]
275mod tests;
solverforge_solver/heuristic/selector/pillar.rs

solverforge_solver/heuristic/selector/
pillar.rs
