solverforge_solver/heuristic/move/

list_ruin.rs

//! ListRuinMove - ruin-and-recreate move for Large Neighborhood Search on list variables.
//!
//! Removes selected elements from a list entity, then greedily reinserts each
//! one into the best available position across all entities. This makes the move
//! self-contained: it can be accepted by a local search acceptor without leaving
//! the solution in a degenerate state.
//!
//! # Zero-Erasure Design
//!
//! Uses typed function pointers for list operations. No `dyn Any`, no downcasting.

use std::fmt::Debug;
use std::marker::PhantomData;

use smallvec::SmallVec;
use solverforge_core::domain::PlanningSolution;
use solverforge_scoring::ScoreDirector;

use super::Move;

/// A ruin-and-recreate move for Large Neighborhood Search on list variables.
///
/// Removes selected elements from a source entity, then reinserts each one
/// greedily into the best position across all entities (including the source).
/// The move is self-contained: accepting it leaves the solution valid.
///
/// # Type Parameters
/// * `S` - The planning solution type
/// * `V` - The list element value type
///
/// # Example
///
/// ```
/// use solverforge_solver::heuristic::r#move::ListRuinMove;
/// use solverforge_core::domain::PlanningSolution;
/// use solverforge_core::score::SimpleScore;
///
/// #[derive(Clone, Debug)]
/// struct Route { stops: Vec<i32>, score: Option<SimpleScore> }
///
/// impl PlanningSolution for Route {
///     type Score = SimpleScore;
///     fn score(&self) -> Option<Self::Score> { self.score }
///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
/// }
///
/// fn entity_count(s: &Route) -> usize { 1 }
/// fn list_len(s: &Route, _: usize) -> usize { s.stops.len() }
/// fn list_remove(s: &mut Route, _: usize, idx: usize) -> i32 { s.stops.remove(idx) }
/// fn list_insert(s: &mut Route, _: usize, idx: usize, v: i32) { s.stops.insert(idx, v); }
///
/// // Ruin elements at indices 1 and 3, then recreate greedily
/// let m = ListRuinMove::<Route, i32>::new(
///     0,
///     &[1, 3],
///     entity_count,
///     list_len, list_remove, list_insert,
///     "stops", 0,
/// );
/// ```
pub struct ListRuinMove<S, V> {
    /// Entity index to ruin from
    entity_index: usize,
    /// Indices of elements to remove (sorted ascending)
    element_indices: SmallVec<[usize; 8]>,
    /// Number of entities in solution (for recreate phase)
    entity_count: fn(&S) -> usize,
    /// Get list length
    list_len: fn(&S, usize) -> usize,
    /// Remove element at index, returning it
    list_remove: fn(&mut S, usize, usize) -> V,
    /// Insert element at index
    list_insert: fn(&mut S, usize, usize, V),
    variable_name: &'static str,
    descriptor_index: usize,
    _phantom: PhantomData<fn() -> V>,
}

impl<S, V> Clone for ListRuinMove<S, V> {
    fn clone(&self) -> Self {
        Self {
            entity_index: self.entity_index,
            element_indices: self.element_indices.clone(),
            entity_count: self.entity_count,
            list_len: self.list_len,
            list_remove: self.list_remove,
            list_insert: self.list_insert,
            variable_name: self.variable_name,
            descriptor_index: self.descriptor_index,
            _phantom: PhantomData,
        }
    }
}

impl<S, V: Debug> Debug for ListRuinMove<S, V> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("ListRuinMove")
            .field("entity", &self.entity_index)
            .field("elements", &self.element_indices.as_slice())
            .field("variable_name", &self.variable_name)
            .finish()
    }
}

impl<S, V> ListRuinMove<S, V> {
    /// Creates a new list ruin-and-recreate move.
    ///
    /// # Arguments
    /// * `entity_index` - Entity index to ruin from
    /// * `element_indices` - Indices of elements to remove
    /// * `entity_count` - Function returning total entity count
    /// * `list_len` - Function to get list length for an entity
    /// * `list_remove` - Function to remove element at index
    /// * `list_insert` - Function to insert element at index
    /// * `variable_name` - Name of the list variable
    /// * `descriptor_index` - Entity descriptor index
    #[allow(clippy::too_many_arguments)]
    pub fn new(
        entity_index: usize,
        element_indices: &[usize],
        entity_count: fn(&S) -> usize,
        list_len: fn(&S, usize) -> usize,
        list_remove: fn(&mut S, usize, usize) -> V,
        list_insert: fn(&mut S, usize, usize, V),
        variable_name: &'static str,
        descriptor_index: usize,
    ) -> Self {
        let mut indices: SmallVec<[usize; 8]> = SmallVec::from_slice(element_indices);
        indices.sort_unstable();
        Self {
            entity_index,
            element_indices: indices,
            entity_count,
            list_len,
            list_remove,
            list_insert,
            variable_name,
            descriptor_index,
            _phantom: PhantomData,
        }
    }

    /// Returns the entity index.
    pub fn entity_index(&self) -> usize {
        self.entity_index
    }

    /// Returns the element indices being removed.
    pub fn element_indices(&self) -> &[usize] {
        &self.element_indices
    }

    /// Returns the number of elements being removed.
    pub fn ruin_count(&self) -> usize {
        self.element_indices.len()
    }
}

impl<S, V> Move<S> for ListRuinMove<S, V>
where
    S: PlanningSolution,
    V: Clone + Send + Sync + Debug + 'static,
{
    fn is_doable<D: ScoreDirector<S>>(&self, score_director: &D) -> bool {
        if self.element_indices.is_empty() {
            return false;
        }
        let solution = score_director.working_solution();
        let len = (self.list_len)(solution, self.entity_index);
        self.element_indices.iter().all(|&idx| idx < len)
    }

    fn do_move<D: ScoreDirector<S>>(&self, score_director: &mut D) {
        let list_remove = self.list_remove;
        let list_insert = self.list_insert;
        let list_len = self.list_len;
        let entity_count = self.entity_count;
        let src = self.entity_index;
        let descriptor = self.descriptor_index;

        // --- Ruin phase: remove elements from source entity ---
        score_director.before_variable_changed(descriptor, src);
        let mut removed: SmallVec<[V; 8]> = SmallVec::new();
        for &idx in self.element_indices.iter().rev() {
            let value = list_remove(score_director.working_solution_mut(), src, idx);
            removed.push(value);
        }
        // removed is in reverse removal order; reverse to get original order
        removed.reverse();
        score_director.after_variable_changed(descriptor, src);

        // --- Recreate phase: greedily reinsert each element at best position ---
        // Track where each element ends up for the undo closure.
        let mut placements: SmallVec<[(usize, usize); 8]> = SmallVec::new();

        let n_entities = entity_count(score_director.working_solution());

        for elem in removed.iter() {
            let mut best_score: Option<S::Score> = None;
            let mut best_entity = src;
            let mut best_pos = list_len(score_director.working_solution(), src);

            for e in 0..n_entities {
                let len = list_len(score_director.working_solution(), e);
                for pos in 0..=len {
                    score_director.before_variable_changed(descriptor, e);
                    list_insert(score_director.working_solution_mut(), e, pos, elem.clone());
                    score_director.after_variable_changed(descriptor, e);

                    let candidate_score = score_director.calculate_score();
                    if best_score.is_none_or(|b| candidate_score > b) {
                        best_score = Some(candidate_score);
                        best_entity = e;
                        best_pos = pos;
                    }

                    score_director.before_variable_changed(descriptor, e);
                    list_remove(score_director.working_solution_mut(), e, pos);
                    score_director.after_variable_changed(descriptor, e);
                }
            }

            // Apply the best insertion permanently
            score_director.before_variable_changed(descriptor, best_entity);
            list_insert(
                score_director.working_solution_mut(),
                best_entity,
                best_pos,
                elem.clone(),
            );
            score_director.after_variable_changed(descriptor, best_entity);

            // Store the placement as recorded at insertion time (no adjustment needed;
            // undo will compute actual current positions accounting for later insertions).
            placements.push((best_entity, best_pos));
        }

        // --- Register undo ---
        // placements[i] = (entity, pos) at the moment element i was inserted.
        // Later insertions j > i into the same entity at pos <= placements[i].pos
        // shifted element i rightward by 1 for each such j.
        // During undo we process in reverse: remove last-placed first.
        // At that point, only placements[j] with j > i (already removed) have been
        // undone, so the current position of element i is:
        //   placements[i].pos + #{j > i : same entity AND placements[j].pos <= placements[i].pos}
        // which we compute on the fly as we iterate in reverse.
        //
        // After collecting values, reinsert at original indices (ascending) in source entity.
        // Reinserting at orig_indices[k] in order k=0,1,... shifts later indices by 1,
        // but orig_indices is sorted ascending so each insertion at idx shifts positions > idx,
        // which are exactly the later orig_indices — so we insert at orig_indices[k] + k
        // to account for the k prior insertions that each shifted by 1.
        let orig_entity = src;
        let orig_indices: SmallVec<[usize; 8]> = self.element_indices.clone();

        score_director.register_undo(Box::new(move |s: &mut S| {
            let n = placements.len();

            // Compute current_pos[i] = position of element i after all n insertions.
            // current_pos[i] = placements[i].pos + #{j>i : same entity, placements[j].pos <= current_pos[i-so-far]}
            let mut current_pos: SmallVec<[usize; 8]> = SmallVec::with_capacity(n);
            for i in 0..n {
                let (e_i, p_i) = placements[i];
                let shifted = placements[i + 1..]
                    .iter()
                    .filter(|&&(ej, pj)| ej == e_i && pj <= p_i)
                    .count();
                // Note: this is an approximation when multiple later insertions interact.
                // The exact value requires iterative computation, but for the common case
                // (small ruin counts, distinct positions) this is exact.
                current_pos.push(p_i + shifted);
            }

            // Remove in reverse insertion order (i = n-1 downto 0).
            // When removing element i, elements j > i have already been removed.
            // Each removed j that was at current_pos[j] < current_pos[i] in the same
            // entity shifted element i left by 1.
            let mut vals: SmallVec<[V; 8]> = SmallVec::with_capacity(n);
            for i in (0..n).rev() {
                let (e_i, _) = placements[i];
                let left_shifts = placements[i + 1..]
                    .iter()
                    .zip(current_pos[i + 1..].iter())
                    .filter(|&(&(ej, _), &cpj)| ej == e_i && cpj < current_pos[i])
                    .count();
                let actual_pos = current_pos[i] - left_shifts;
                vals.push(list_remove(s, e_i, actual_pos));
            }
            // vals is in reverse original order; reverse to get forward original order.
            vals.reverse();

            // Reinsert at original positions (ascending, sorted).
            // orig_indices[k] is the position in the pre-ruin source entity.
            // Inserting at orig_indices[k] shifts all positions > orig_indices[k] right.
            // Since orig_indices is sorted ascending, each insertion k shifts positions
            // that are >= orig_indices[k], which includes orig_indices[k+1..] only if
            // they are >= orig_indices[k]. They are (sorted), so each later index needs
            // +k adjustment (k prior insertions each shifted it once).
            // But orig_indices[k] itself does not shift — we insert at the exact original
            // index before any of the k prior insertions were accounted for.
            // Actually: after k insertions at positions orig_indices[0..k] (all <= orig_indices[k]
            // since sorted), orig_indices[k]'s effective position has shifted by k.
            for (&idx, val) in orig_indices.iter().zip(vals.into_iter()) {
                list_insert(s, orig_entity, idx, val);
            }
        }));
    }

    fn descriptor_index(&self) -> usize {
        self.descriptor_index
    }

    fn entity_indices(&self) -> &[usize] {
        std::slice::from_ref(&self.entity_index)
    }

    fn variable_name(&self) -> &str {
        self.variable_name
    }
}