solverforge_solver/heuristic/selector/

nearby.rs

/* Nearby selection for distance-based filtering of candidates.

Nearby selection improves move quality by preferring destinations that are
geographically or otherwise "close" to an origin. This is critical for
vehicle routing problems (VRP) where swapping with nearby customers
is more likely to improve the solution than swapping with distant ones.

# Architecture

- [`NearbyDistanceMeter`]: User-defined function to measure distance between elements
- [`NearbySelectionConfig`]: Configuration for nearby selection behavior
- [`NearbyEntitySelector`]: Selects entities nearby to a reference entity
*/

use std::cmp::Ordering;
use std::fmt::Debug;

use solverforge_core::domain::PlanningSolution;
use solverforge_scoring::Director;

use super::entity::{EntityReference, EntitySelector};
use super::mimic::MimicRecorder;

/// Trait for measuring distance between an origin and a destination.
///
/// Implementations should be stateless. The solver may reuse instances.
///
/// # Type Parameters
///
/// - `Origin`: The type of the origin element (usually an entity or value)
/// - `Destination`: The type of the destination element (usually an entity or value)
///
/// # Example
///
/// ```
/// use solverforge_solver::heuristic::selector::NearbyDistanceMeter;
///
/// #[derive(Debug)]
/// struct Location { x: f64, y: f64 }
///
/// #[derive(Debug)]
/// struct EuclideanMeter;
///
/// impl NearbyDistanceMeter<Location, Location> for EuclideanMeter {
///     fn distance(&self, origin: &Location, dest: &Location) -> f64 {
///         let dx = origin.x - dest.x;
///         let dy = origin.y - dest.y;
///         (dx * dx + dy * dy).sqrt()
///     }
/// }
/// ```
pub trait NearbyDistanceMeter<Origin, Destination>: Send + Sync + Debug {
    /* Measures the distance from the origin to the destination.

    The distance can be in any unit (meters, seconds, cost, etc.).
    Distances can be asymmetrical: the distance from A to B may differ
    from the distance from B to A.

    Returns a value >= 0.0. If origin == destination, typically returns 0.0.
    */
    fn distance(&self, origin: &Origin, destination: &Destination) -> f64;
}

// Distribution type for nearby selection.
#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
pub enum NearbyDistributionType {
    // Select all candidates sorted by distance (up to a maximum).
    #[default]
    Linear,
    // Select candidates with probability proportional to distance (closer = more likely).
    Parabolic,
    // Use a block distribution for k-opt style moves.
    Block,
}

// Configuration for nearby selection.
#[derive(Debug, Clone)]
pub struct NearbySelectionConfig {
    // The distribution type to use.
    pub distribution_type: NearbyDistributionType,
    // Maximum number of nearby candidates to consider.
    // If None, considers all candidates (sorted by distance).
    pub max_nearby_size: Option<usize>,
    // Minimum distance to include a candidate (exclusive of origin).
    pub min_distance: f64,
}

impl Default for NearbySelectionConfig {
    fn default() -> Self {
        Self {
            distribution_type: NearbyDistributionType::Linear,
            max_nearby_size: None,
            min_distance: 0.0,
        }
    }
}

impl NearbySelectionConfig {
    pub fn new() -> Self {
        Self::default()
    }

    pub fn with_distribution_type(mut self, distribution_type: NearbyDistributionType) -> Self {
        self.distribution_type = distribution_type;
        self
    }

    pub fn with_max_nearby_size(mut self, max_size: usize) -> Self {
        self.max_nearby_size = Some(max_size);
        self
    }

    pub fn with_min_distance(mut self, min_distance: f64) -> Self {
        self.min_distance = min_distance;
        self
    }
}

/// Type-erased distance meter for dynamic dispatch.
pub trait DynDistanceMeter: Send + Sync + Debug {
    // Measures distance between two entity references.
    fn distance_between<S: PlanningSolution>(
        &self,
        score_director: &dyn Director<S>,
        origin: EntityReference,
        destination: EntityReference,
    ) -> f64;
}

/// An entity selector that returns entities nearby to an origin entity.
///
/// The origin entity is obtained from a mimic recorder, allowing this selector
/// to be synchronized with another selector that picks the "current" entity.
///
/// # Zero-Erasure Design
///
/// The child entity selector `ES` is stored as a concrete generic type parameter,
/// eliminating virtual dispatch overhead when iterating over candidate entities.
pub struct NearbyEntitySelector<S, M, ES> {
    // The child selector providing all candidate entities (zero-erasure).
    child: ES,
    // The recorder providing the origin entity.
    origin_recorder: MimicRecorder,
    // The distance meter for measuring nearness.
    distance_meter: M,
    // Configuration for nearby selection.
    config: NearbySelectionConfig,
    // Marker for solution type.
    _phantom: std::marker::PhantomData<fn() -> S>,
}

impl<S, M, ES> NearbyEntitySelector<S, M, ES> {
    pub fn new(
        child: ES,
        origin_recorder: MimicRecorder,
        distance_meter: M,
        config: NearbySelectionConfig,
    ) -> Self {
        Self {
            child,
            origin_recorder,
            distance_meter,
            config,
            _phantom: std::marker::PhantomData,
        }
    }
}

impl<S: PlanningSolution, M: DynDistanceMeter, ES: Debug> Debug for NearbyEntitySelector<S, M, ES> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("NearbyEntitySelector")
            .field("child", &self.child)
            .field("origin_recorder_id", &self.origin_recorder.id())
            .field("distance_meter", &self.distance_meter)
            .field("config", &self.config)
            .finish()
    }
}

impl<S, M, ES> EntitySelector<S> for NearbyEntitySelector<S, M, ES>
where
    S: PlanningSolution,
    M: DynDistanceMeter + 'static,
    ES: EntitySelector<S>,
{
    fn iter<'a, D: Director<S>>(
        &'a self,
        score_director: &'a D,
    ) -> impl Iterator<Item = EntityReference> + 'a {
        // Get the origin entity from the recorder
        let origin = self.origin_recorder.get_recorded_entity();

        // Collect all candidate entities with their distances (empty if no origin)
        let mut candidates: Vec<(EntityReference, f64)> = match origin {
            Some(origin) => self
                .child
                .iter(score_director)
                .filter(move |&dest| dest != origin) // Exclude the origin itself
                .map(move |dest| {
                    let dist = self
                        .distance_meter
                        .distance_between(score_director, origin, dest);
                    (dest, dist)
                })
                .filter(|(_, dist)| *dist >= self.config.min_distance)
                .collect(),
            None => Vec::new(),
        };

        // Sort by distance (closest first)
        candidates.sort_by(|a, b| a.1.partial_cmp(&b.1).unwrap_or(Ordering::Equal));

        // Apply max size limit
        if let Some(max_size) = self.config.max_nearby_size {
            candidates.truncate(max_size);
        }

        candidates.into_iter().map(|(entity, _)| entity)
    }

    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
        // This is an estimate; the actual size depends on the origin
        let child_size = self.child.size(score_director);
        match self.config.max_nearby_size {
            Some(max) => child_size.min(max),
            None => child_size,
        }
    }
}