selen 0.15.5

//! Trail-based backtracking system for efficient search without cloning.
//!
//! This module implements a trail-based backtracking system that eliminates the need
//! to clone the entire search space on every branch. Instead, we record only the
//! changes (deltas) made to variable domains, allowing O(k) backtracking where k is
//! the number of changes, rather than O(n×m) where n=variables and m=propagators.
//!
//! ## Performance Impact
//!
//! Traditional approach (cloning):
//! - Memory: O(n×m) per branch point (all variables + all propagators)
//! - Time: O(n×m) to clone entire space
//!
//! Trail-based approach:
//! - Memory: O(k) per branch point (only changed domains)
//! - Time: O(k) to save/restore state
//!
//! For typical CSP problems, k << n×m, resulting in 5-10x speedup.

use crate::variables::{VarId, core::Var};
use crate::variables::domain::{
    sparse_set::SparseSetState,
    // float_interval::FloatInterval is not needed here
};

/// Snapshot of a single variable's domain state.
#[derive(Clone, Debug)]
pub enum DomainSnapshot {
    /// Integer variable (SparseSet) snapshot
    IntDomain(SparseSetState),
    /// Float variable (FloatInterval) snapshot
    FloatDomain(FloatDomainState),
}

/// State snapshot for FloatInterval backtracking
#[derive(Clone, Debug)]
pub struct FloatDomainState {
    pub min: f64,
    pub max: f64,
    // step is immutable, no need to save
}

/// A single change to a variable domain recorded on the trail.
#[derive(Clone, Debug)]
pub struct TrailEntry {
    /// Which variable was modified
    pub var_id: VarId,
    /// Previous state of the variable domain
    pub old_state: DomainSnapshot,
}

/// Trail records all domain changes for efficient backtracking.
///
/// The trail is a stack of changes. When we branch, we save a checkpoint
/// (the current trail length). To backtrack, we undo all changes after
/// the checkpoint and pop them from the trail.
#[derive(Clone, Debug)]
pub struct Trail {
    /// Stack of domain changes
    entries: Vec<TrailEntry>,
    /// Stack of checkpoint positions for nested backtracking
    checkpoints: Vec<usize>,
}

impl Trail {
    /// Create a new empty trail.
    pub fn new() -> Self {
        Trail {
            entries: Vec::with_capacity(1024), // Pre-allocate for typical search
            checkpoints: Vec::with_capacity(64), // Typical search depth
        }
    }

    /// Create a trail with specified capacity.
    pub fn with_capacity(entries_capacity: usize, checkpoints_capacity: usize) -> Self {
        Trail {
            entries: Vec::with_capacity(entries_capacity),
            checkpoints: Vec::with_capacity(checkpoints_capacity),
        }
    }

    /// Save a checkpoint (current position in the trail).
    /// Returns the checkpoint level for reference.
    #[inline]
    pub fn push_checkpoint(&mut self) -> usize {
        let checkpoint = self.entries.len();
        self.checkpoints.push(checkpoint);
        checkpoint
    }

    /// Record a domain change on the trail.
    #[inline]
    pub fn push_change(&mut self, var_id: VarId, old_state: DomainSnapshot) {
        self.entries.push(TrailEntry { var_id, old_state });
    }

    /// Get the current trail level (number of entries).
    #[inline]
    pub fn level(&self) -> usize {
        self.entries.len()
    }

    /// Get the number of active checkpoints.
    #[inline]
    pub fn checkpoint_depth(&self) -> usize {
        self.checkpoints.len()
    }

    /// Backtrack to the most recent checkpoint, returning the changes to undo.
    ///
    /// This pops the checkpoint and returns an iterator over changes to undo,
    /// in reverse order (most recent first).
    pub fn pop_checkpoint(&mut self) -> Option<impl Iterator<Item = TrailEntry> + '_> {
        let checkpoint = self.checkpoints.pop()?;

        // Drain entries after the checkpoint in reverse order
        let drain_start = checkpoint;
        let drain_end = self.entries.len();

        // We need to reverse and collect because drain returns in forward order
        // but we need to restore in reverse order
        Some(self.entries.drain(drain_start..drain_end).rev())
    }

    /// Clear the entire trail (for starting fresh search).
    pub fn clear(&mut self) {
        self.entries.clear();
        self.checkpoints.clear();
    }

    /// Get current memory usage estimate in bytes.
    pub fn memory_bytes(&self) -> usize {
        // Each TrailEntry is approximately 24-32 bytes (VarId + enum with states)
        let entries_capacity = self.entries.capacity() * 32;

        // Each checkpoint is usize (8 bytes on 64-bit)
        let checkpoints_capacity = self.checkpoints.capacity() * 8;

        entries_capacity + checkpoints_capacity + 16 // +16 for struct overhead
    }
}

impl Default for Trail {
    fn default() -> Self {
        Self::new()
    }
}

/// Extension trait for Var to support trail-based backtracking.
pub trait VarTrail {
    /// Save the current domain state as a snapshot.
    fn save_snapshot(&self) -> DomainSnapshot;

    /// Restore domain from a snapshot.
    fn restore_snapshot(&mut self, snapshot: &DomainSnapshot);
}

impl VarTrail for Var {
    fn save_snapshot(&self) -> DomainSnapshot {
        match self {
            Var::VarI(sparse_set) => {
                DomainSnapshot::IntDomain(sparse_set.save_state())
            }
            Var::VarF(interval) => {
                DomainSnapshot::FloatDomain(FloatDomainState {
                    min: interval.min,
                    max: interval.max,
                })
            }
        }
    }

    fn restore_snapshot(&mut self, snapshot: &DomainSnapshot) {
        match (self, snapshot) {
            (Var::VarI(sparse_set), DomainSnapshot::IntDomain(state)) => {
                sparse_set.restore_state(state);
            }
            (Var::VarF(interval), DomainSnapshot::FloatDomain(state)) => {
                interval.min = state.min;
                interval.max = state.max;
            }
            _ => {
                // Type mismatch - should not happen
                debug_assert!(false, "Domain snapshot type mismatch");
            }
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::variables::core::Vars;
    use crate::variables::Val;

    #[test]
    fn test_trail_basic() {
        let mut trail = Trail::new();

        // Initially empty
        assert_eq!(trail.level(), 0);
        assert_eq!(trail.checkpoint_depth(), 0);

        // Push a checkpoint
        trail.push_checkpoint();
        assert_eq!(trail.checkpoint_depth(), 1);

        // Add some changes (mock data)
        let var_id = VarId::from_index(0);
        let snapshot = DomainSnapshot::FloatDomain(FloatDomainState {
            min: 0.0,
            max: 10.0,
        });

        trail.push_change(var_id, snapshot.clone());
        assert_eq!(trail.level(), 1);

        // Backtrack
        let changes: Vec<_> = trail.pop_checkpoint().unwrap().collect();
        assert_eq!(changes.len(), 1);
        assert_eq!(trail.level(), 0);
        assert_eq!(trail.checkpoint_depth(), 0);
    }

    #[test]
    fn test_trail_nested_checkpoints() {
        let mut trail = Trail::new();

        // Level 0: checkpoint
        trail.push_checkpoint();
        let var0 = VarId::from_index(0);
        trail.push_change(var0, DomainSnapshot::FloatDomain(FloatDomainState {
            min: 0.0,
            max: 10.0,
        }));

        // Level 1: checkpoint
        trail.push_checkpoint();
        let var1 = VarId::from_index(1);
        trail.push_change(var1, DomainSnapshot::FloatDomain(FloatDomainState {
            min: 0.0,
            max: 5.0,
        }));

        assert_eq!(trail.level(), 2);
        assert_eq!(trail.checkpoint_depth(), 2);

        // Backtrack to level 1
        let changes: Vec<_> = trail.pop_checkpoint().unwrap().collect();
        assert_eq!(changes.len(), 1);
        assert_eq!(trail.level(), 1);

        // Backtrack to level 0
        let changes: Vec<_> = trail.pop_checkpoint().unwrap().collect();
        assert_eq!(changes.len(), 1);
        assert_eq!(trail.level(), 0);
    }

    #[test]
    fn test_var_snapshot_restore() {
        let mut vars = Vars::new();
        let var_id = vars.new_var_with_bounds(Val::ValI(0), Val::ValI(10));

        // Get mutable access to variable
        let var = &mut vars[var_id];

        // Save initial state
        let snapshot = var.save_snapshot();

        // Modify the domain (simulate constraint propagation)
        if let Var::VarI(sparse_set) = var {
            sparse_set.remove(5);
            sparse_set.remove(6);
            assert_eq!(sparse_set.size(), 9);
        }

        // Restore original state
        var.restore_snapshot(&snapshot);

        // Verify restoration
        if let Var::VarI(sparse_set) = var {
            assert_eq!(sparse_set.size(), 11);
            assert!(sparse_set.contains(5));
            assert!(sparse_set.contains(6));
        }
    }

    #[test]
    fn test_trail_memory_estimate() {
        let trail = Trail::with_capacity(100, 10);
        let mem = trail.memory_bytes();

        // Should be approximately: 100*32 + 10*8 + 16 = 3296 bytes
        assert!(mem >= 3000 && mem <= 4000);
    }
}