//! Windowing primitives for LOWESS smoothing.
//!
//! ## Purpose
//!
//! This module provides low-level data structures and algorithms used to
//! construct and manage sliding windows over sorted input data. These
//! windows are used by the core LOWESS algorithms to perform localized
//! regression.
//!
//! ## Design notes
//!
//! * Assumes input data is pre-sorted by the independent variable.
//! * Window sizes are derived from the user-supplied fraction parameter.
//! * Boundary behavior is handled explicitly to avoid bias near edges.
//! * Windows are dynamically recentered to maintain optimal positioning
//!   around the current point being fitted.
//! * All operations are designed for performance in tight inner loops.
//!
//! ## Key concepts
//!
//! ### Window Structure
//! A window is defined by inclusive bounds `[left, right]` that specify
//! the indices of points used for local regression at a given target point.
//!
//! ### Window Initialization
//! Windows are initially centered around the target point with a size
//! determined by the fraction parameter. Boundary adjustments ensure the
//! window fits within array bounds.
//!
//! ### Window Recentering
//! As processing moves through the data, windows are dynamically adjusted
//! to maintain optimal centering around the current point, ensuring the
//! window contains the nearest neighbors.
//!
//! ## Invariants
//!
//! * Windows always contain at least one point (size ≥ 1).
//! * Indices are guaranteed to remain within input bounds.
//! * Window size remains constant during recentering (slides, doesn't grow/shrink).
//! * The window contains the nearest neighbors to the current point.
//!
//! ## Non-goals
//!
//! * This module does not perform regression.
//! * This module does not validate user input.
//! * This module does not handle sorting of input data.
//!
//! ## Visibility
//!
//! This module is an internal implementation detail and is not part of the
//! public API. It may change without notice.

use num_traits::Float;

// ============================================================================
// Data Structures
// ============================================================================

/// Inclusive window bounds for a local fit.
///
/// Defines the neighborhood `[left, right]` of points used for fitting a
/// target point in LOWESS regression. Both bounds are inclusive indices
/// into the sorted data arrays.
///
/// # Fields
///
/// * `left` - Left boundary index (inclusive)
/// * `right` - Right boundary index (inclusive)
///
/// # Invariants
///
/// A valid window satisfies `left <= right`. Invalid windows (where
/// `left > right`) have zero length and are considered empty.
#[derive(Copy, Clone, Debug)]
pub struct Window {
    /// Left boundary index (inclusive).
    pub left: usize,

    /// Right boundary index (inclusive).
    pub right: usize,
}

impl Window {
    /// Create a new window with the specified bounds.
    ///
    /// # Parameters
    ///
    /// * `left` - Left boundary index (inclusive)
    /// * `right` - Right boundary index (inclusive)
    ///
    /// # Returns
    ///
    /// `Some(Window)` if `left <= right`, otherwise `None`.
    #[inline]
    pub fn new(left: usize, right: usize) -> Option<Self> {
        if left <= right {
            Some(Self { left, right })
        } else {
            None
        }
    }

    /// Check if the window is valid.
    ///
    /// A window is valid if `left <= right`.
    ///
    /// # Returns
    ///
    /// `true` if the window is valid, `false` otherwise.
    #[inline]
    fn is_valid(&self) -> bool {
        self.left <= self.right
    }

    /// Get the number of points in the window.
    ///
    /// # Returns
    ///
    /// The number of points in the window (`right - left + 1`),
    /// or `0` if the window is invalid.
    #[inline]
    pub fn len(&self) -> usize {
        if self.is_valid() {
            // Safe: left <= right guaranteed by is_valid()
            self.right - self.left + 1
        } else {
            0
        }
    }

    /// Returns `true` if the window contains no points.
    ///
    /// # Returns
    ///
    /// `true` if the window is empty (invalid), `false` otherwise.
    #[inline]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    // ========================================================================
    // Window Management
    // ========================================================================

    /// Initialize window boundaries for a given point.
    ///
    /// Creates an initial window of the specified size, attempting to center
    /// it around the target index. If the window would extend beyond array
    /// bounds, it is adjusted to fit within `[0, n-1]`.
    ///
    /// # Parameters
    ///
    /// * `idx` - Index of the point to center the window around
    /// * `window_size` - Desired size of the window (must be ≥ 1)
    /// * `n` - Total number of points in the array
    ///
    /// # Returns
    ///
    /// A new `Window` instance centered around `idx` with the requested size.
    ///
    /// # Algorithm
    ///
    /// 1. If `window_size >= n`, return the full range `[0, n-1]`
    /// 2. Otherwise, center the window around `idx`:
    ///    - Start with `left = idx - window_size/2`
    ///    - Clamp `left` to ensure the window fits in `[0, n-1]`
    ///    - Set `right = left + window_size - 1`
    ///
    /// # Panics
    ///
    /// Debug builds assert that `window_size >= 1`.
    pub fn initialize(idx: usize, window_size: usize, n: usize) -> Self {
        debug_assert!(
            window_size >= 1,
            "initialize_window: window_size must be at least 1"
        );

        // If requested window covers (or exceeds) the whole array, return full range
        if window_size >= n {
            return Self {
                left: 0,
                right: n.saturating_sub(1),
            };
        }

        let half = window_size / 2;
        // Start by centering the window around idx
        let mut left = idx.saturating_sub(half);

        // Clamp left so the window fits in [0, n-1] with the requested size
        // Since window_size < n here, n - window_size is well-defined
        let max_left = n - window_size;
        if left > max_left {
            left = max_left;
        }

        let right = left + window_size.saturating_sub(1);

        debug_assert_eq!(
            right - left + 1,
            window_size,
            "initialize_window produced wrong size"
        );

        Self { left, right }
    }

    /// Update window boundaries to maintain optimal centering around current point.
    ///
    /// This function adjusts the window to keep it centered around the current
    /// point while maintaining the desired window size. It slides the window
    /// to ensure the current point is surrounded by the nearest neighbors.
    ///
    /// # Parameters
    ///
    /// * `x` - Sorted array of x-coordinates
    /// * `current` - Index of the current point being fitted
    /// * `n` - Total number of points in the array
    ///
    /// # Algorithm
    ///
    /// While the right boundary can expand without exceeding array bounds:
    /// 1. Compute `d_left = x[current] - x[left]` (distance to left boundary)
    /// 2. Compute `d_right = x[right+1] - x[current]` (distance to next right point)
    /// 3. If `d_left <= d_right`, the window is optimally centered (stop)
    /// 4. Otherwise, slide window right by incrementing both boundaries
    ///
    /// This ensures the window contains the `window_size` nearest neighbors to
    /// the current point.
    ///
    /// # Safety
    ///
    /// Caller must ensure `current < n`. The function includes defensive checks:
    /// - Debug builds assert `current < n`
    /// - Release builds no-op if bounds are invalid (prevents panics)
    /// - Clamps `left` and `right` to valid indices to prevent out-of-bounds access
    pub fn recenter<T: Float>(&mut self, x: &[T], current: usize, n: usize) {
        // Safety: caller is expected to pass current < n
        debug_assert!(current < n, "recenter: current index out of bounds");

        if current >= n || n == 0 {
            // Defensive check for release builds: no-op if current is invalid
            return;
        }

        // Clamp left/right to valid indices to prevent accidental out-of-bounds access
        self.left = self.left.min(n - 1);
        self.right = self.right.min(n - 1);

        let x_current = x[current];

        // Slide window right while maintaining balance around current point
        // Loop invariant: left < n and right < n (maintained by clamping above)
        while self.right < n - 1 {
            let d_left = x_current - x[self.left];
            let d_right = x[self.right + 1] - x_current;

            // If distance to left boundary <= distance to next right point,
            // the window is optimally centered
            if d_left <= d_right {
                break;
            }

            // Slide window right
            self.left += 1;
            self.right += 1;
        }
    }

    // ========================================================================
    // Utility Methods
    // ========================================================================

    /// Compute the window radius for a given point.
    ///
    /// The radius is defined as the maximum distance from the current point
    /// to the boundaries of the window. This is used for computing kernel
    /// weights in LOWESS.
    ///
    /// # Parameters
    ///
    /// * `x` - Sorted array of x-coordinates
    /// * `x_current` - The x-coordinate of the current point
    ///
    /// # Returns
    ///
    /// The maximum distance from `x_current` to either window boundary.
    ///
    /// # Panics
    ///
    /// Panics if `self.left` or `self.right` are out of bounds for `x`.
    /// This indicates a contract violation (window constructed incorrectly).
    pub fn max_distance<T: Float>(&self, x: &[T], x_current: T) -> T {
        // Safe: self.left and self.right are valid indices within x
        // (assuming the window was constructed correctly relative to x)
        T::max(x_current - x[self.left], x[self.right] - x_current)
    }

    /// Calculate window size from fraction and number of points.
    ///
    /// Converts a fraction parameter (proportion of data to use) into an
    /// integer window size suitable for LOWESS smoothing.
    ///
    /// # Parameters
    ///
    /// * `n` - Number of data points
    /// * `frac` - Fraction of data to use (typically in range 0.0 to 1.0)
    ///
    /// # Returns
    ///
    /// Window size clamped to the range `[2, n]`. The minimum size of 2
    /// ensures at least two points are available for fitting.
    ///
    /// # Algorithm
    ///
    /// 1. Compute `window_size = frac * n`
    /// 2. Clamp to `[2, n]`
    #[inline]
    pub fn calculate_span<T: Float>(n: usize, frac: T) -> usize {
        let frac_n = frac * T::from(n).unwrap();
        let frac_n_int = frac_n.to_usize().unwrap_or(0);
        usize::max(2, usize::min(n, frac_n_int))
    }
}
