givp 1.0.0

// SPDX-FileCopyrightText: 2026 Arnaldo Mendes Pires Junior
// SPDX-License-Identifier: MIT

use crate::cache::EvaluationCache;
use crate::helpers::{clamp, normalize_integer_tail, safe_evaluate};
use rand::Rng;
use rand_chacha::ChaCha8Rng;
use std::time::Instant;

use std::sync::atomic::{AtomicBool, Ordering};

static FORCE_POOL_BUILD_FAIL: AtomicBool = AtomicBool::new(false);

fn build_local_pool(n_workers: usize) -> Option<rayon::ThreadPool> {
    if FORCE_POOL_BUILD_FAIL.load(Ordering::Relaxed) {
        return None;
    }

    rayon::ThreadPoolBuilder::new()
        .num_threads(n_workers)
        .build()
        .ok()
}

#[cfg(test)]
fn set_force_pool_build_fail(value: bool) {
    FORCE_POOL_BUILD_FAIL.store(value, Ordering::Relaxed);
}

/// Compute adaptive alpha via linear interpolation.
pub(crate) fn get_current_alpha(
    iter_idx: usize,
    max_iterations: usize,
    alpha_min: f64,
    alpha_max: f64,
    adaptive: bool,
    alpha: f64,
) -> f64 {
    if !adaptive {
        return alpha;
    }
    let progress = iter_idx as f64 / max_iterations.max(1) as f64;
    alpha_min + (alpha_max - alpha_min) * progress
}

/// Evaluate with optional cache.
pub(crate) fn evaluate_with_cache<F>(
    candidate: &[f64],
    func: &F,
    cache: &mut Option<EvaluationCache>,
    half: usize,
) -> f64
where
    F: Fn(&[f64]) -> f64,
{
    if let Some(ref mut c) = cache {
        if let Some(v) = c.get(candidate, half) {
            return v;
        }
        let cost = safe_evaluate(func, candidate);
        c.put(candidate, half, cost);
        cost
    } else {
        safe_evaluate(func, candidate)
    }
}

/// Select an index from the Restricted Candidate List.
fn select_from_rcl(costs: &[f64], alpha: f64, rng: &mut ChaCha8Rng) -> Option<usize> {
    if costs.is_empty() {
        return None;
    }
    let min_cost = costs.iter().cloned().fold(f64::INFINITY, f64::min);
    let max_cost = costs.iter().cloned().fold(f64::NEG_INFINITY, f64::max);
    let threshold = min_cost + alpha * (max_cost - min_cost);

    let candidates: Vec<usize> = costs
        .iter()
        .enumerate()
        .filter(|(_, &c)| c <= threshold)
        .map(|(i, _)| i)
        .collect();

    if candidates.is_empty() {
        return Some(0);
    }
    let idx = rng.random_range(0..candidates.len());
    Some(candidates[idx])
}

/// Sample an integer uniformly from bounds.
fn sample_integer_from_bounds(lo: f64, hi: f64, rng: &mut ChaCha8Rng) -> f64 {
    let lo_i = lo.ceil() as i64;
    let hi_i = hi.floor() as i64;
    if lo_i > hi_i {
        return ((lo + hi) / 2.0).round();
    }
    rng.random_range(lo_i..=hi_i) as f64
}

/// Build a purely random candidate.
fn build_random_candidate(
    num_vars: usize,
    half: usize,
    lower: &[f64],
    upper: &[f64],
    rng: &mut ChaCha8Rng,
) -> Vec<f64> {
    let mut sol = vec![0.0; num_vars];
    for i in 0..half {
        sol[i] = rng.random_range(lower[i]..=upper[i]);
    }
    for i in half..num_vars {
        sol[i] = sample_integer_from_bounds(lower[i], upper[i], rng);
    }
    sol
}

/// Build a heuristic candidate (mid ± 15% noise).
fn build_heuristic_candidate(
    num_vars: usize,
    half: usize,
    lower: &[f64],
    upper: &[f64],
    rng: &mut ChaCha8Rng,
) -> Vec<f64> {
    let mut sol = vec![0.0; num_vars];
    for i in 0..half {
        let mid = (lower[i] + upper[i]) / 2.0;
        let span = upper[i] - lower[i];
        let noise = rng.random_range(-0.15..=0.15) * span;
        sol[i] = clamp(mid + noise, lower[i], upper[i]);
    }
    for i in half..num_vars {
        sol[i] = sample_integer_from_bounds(lower[i], upper[i], rng);
    }
    sol
}

/// GRASP construction phase.
///
/// When `n_workers > 1` and `cache` is `None`, candidate evaluation is
/// parallelised using **rayon**.  The cache cannot be shared across threads
/// (single `&mut` reference), so the parallel path always calls
/// `safe_evaluate` directly — semantically equivalent to
/// `evaluate_with_cache` when no cache is active.
#[allow(clippy::too_many_arguments)]
pub(crate) fn construct_grasp<F>(
    num_vars: usize,
    lower: &[f64],
    upper: &[f64],
    func: &F,
    initial_guess: Option<&[f64]>,
    alpha: f64,
    half: usize,
    num_candidates: usize,
    cache: &mut Option<EvaluationCache>,
    rng: &mut ChaCha8Rng,
    deadline: Option<Instant>,
    n_workers: usize,
) -> (Vec<f64>, f64)
where
    F: Fn(&[f64]) -> f64 + Sync,
{
    let mut candidates: Vec<Vec<f64>> = Vec::with_capacity(num_candidates);

    // ── Build candidates (all serial — RNG is not Sync) ──────────────────────
    if let Some(ig) = initial_guess {
        let mut sol = ig.to_vec();
        normalize_integer_tail(&mut sol, half);
        candidates.push(sol);
    }

    if candidates.len() < num_candidates {
        let mut sol = build_heuristic_candidate(num_vars, half, lower, upper, rng);
        normalize_integer_tail(&mut sol, half);
        candidates.push(sol);
    }

    while candidates.len() < num_candidates {
        if crate::helpers::expired(deadline) {
            break;
        }
        let mut sol = build_random_candidate(num_vars, half, lower, upper, rng);
        normalize_integer_tail(&mut sol, half);
        candidates.push(sol);
    }

    // ── Evaluate candidates ──────────────────────────────────────────────────
    let costs: Vec<f64> = if n_workers > 1 && candidates.len() > 1 && cache.is_none() {
        use rayon::prelude::*;
        match build_local_pool(n_workers) {
            Some(pool) => pool.install(|| {
                candidates
                    .par_iter()
                    .map(|s| safe_evaluate(func, s))
                    .collect()
            }),
            None => candidates.iter().map(|s| safe_evaluate(func, s)).collect(),
        }
    } else {
        candidates
            .iter()
            .map(|s| evaluate_with_cache(s, func, cache, half))
            .collect()
    };

    // ── RCL selection ────────────────────────────────────────────────────────
    let idx = select_from_rcl(&costs, alpha, rng).expect("costs should not be empty");
    (candidates.swap_remove(idx), costs[idx])
}

#[cfg(test)]
mod tests {
    use super::*;
    use rand::SeedableRng;
    use rand_chacha::ChaCha8Rng;
    use std::time::{Duration, Instant};

    #[test]
    fn test_select_from_rcl_empty_returns_none() {
        let mut rng = ChaCha8Rng::seed_from_u64(0);
        assert!(select_from_rcl(&[], 0.5, &mut rng).is_none());
    }

    #[test]
    fn test_construct_grasp_expired_deadline_breaks_fill_loop() {
        // An already-expired deadline triggers the break in the fill-random loop.
        // The heuristic candidate is still returned because it was added before the loop.
        let mut rng = ChaCha8Rng::seed_from_u64(42);
        let mut cache = None;
        let lower = [-5.0f64, -5.0];
        let upper = [5.0f64, 5.0];
        let func = |x: &[f64]| x.iter().map(|&xi| xi * xi).sum::<f64>();
        let deadline = Some(Instant::now() - Duration::from_secs(1));
        let (sol, cost) = construct_grasp(
            2, &lower, &upper, &func, None, 0.5, 2, 100, &mut cache, &mut rng, deadline, 1,
        );
        assert_eq!(sol.len(), 2);
        assert!(cost.is_finite());
    }
    #[test]
    fn test_construct_grasp_parallel_fallback_when_pool_build_fails() {
        let mut rng = ChaCha8Rng::seed_from_u64(7);
        let mut cache = None;
        let lower = [-5.0f64, -5.0];
        let upper = [5.0f64, 5.0];
        let func = |x: &[f64]| x.iter().map(|&xi| xi * xi).sum::<f64>();

        set_force_pool_build_fail(true);
        let (sol, cost) = construct_grasp(
            2, &lower, &upper, &func, None, 0.3, 2, 8, &mut cache, &mut rng, None, 4,
        );
        set_force_pool_build_fail(false);
        assert_eq!(sol.len(), 2);
        assert!(cost.is_finite());
    }

    #[test]
    fn test_construct_grasp_initial_guess_fills_single_candidate_slot() {
        // When initial_guess is provided and num_candidates==1, the heuristic
        // block (if candidates.len() < num_candidates) is skipped, covering its false branch.
        let mut rng = ChaCha8Rng::seed_from_u64(0);
        let mut cache = None;
        let lower = [-5.0f64, -5.0];
        let upper = [5.0f64, 5.0];
        let func = |x: &[f64]| x.iter().map(|&xi| xi * xi).sum::<f64>();
        let ig = vec![1.0f64, 2.0f64];
        let (sol, cost) = construct_grasp(
            2,
            &lower,
            &upper,
            &func,
            Some(&ig),
            0.5,
            2,
            1,
            &mut cache,
            &mut rng,
            None,
            1,
        );
        assert_eq!(sol.len(), 2);
        assert!(cost.is_finite());
    }

    #[test]
    fn test_construct_grasp_parallel_pool_success_path() {
        let mut rng = ChaCha8Rng::seed_from_u64(11);
        let mut cache = None;
        let lower = [-5.0f64, -5.0];
        let upper = [5.0f64, 5.0];
        let func = |x: &[f64]| x.iter().map(|&xi| xi * xi).sum::<f64>();

        set_force_pool_build_fail(false);
        let (sol, cost) = construct_grasp(
            2, &lower, &upper, &func, None, 0.4, 2, 16, &mut cache, &mut rng, None, 2,
        );
        assert_eq!(sol.len(), 2);
        assert!(cost.is_finite());
    }
}