//! Sorting utilities for LOWESS input data.
//!
//! ## Purpose
//!
//! This module provides utilities for sorting input data by x-coordinates
//! and mapping results back to the original order. LOWESS requires sorted
//! input for efficient window-based processing, but users expect results
//! in their original data order. This module handles the sort-process-unsort
//! workflow transparently.
//!
//! ## Design notes
//!
//! * Uses stable sorting to ensure deterministic results when x-values are equal.
//! * Handles non-finite values (NaN, Inf) by placing them at the end of the
//!   sorted sequence, preventing them from interfering with normal processing.
//! * Maintains an index mapping to efficiently restore original order without
//!   re-sorting.
//! * All operations are generic over `Float` types to support both `f32` and
//!   `f64` precision.
//!
//! ## Key concepts
//!
//! ### Sort-Process-Unsort Pattern
//! 1. **Sort**: Input data is sorted by x-coordinates, creating an index mapping
//! 2. **Process**: LOWESS smoothing operates on sorted data
//! 3. **Unsort**: Results are mapped back to original order using the index mapping
//!
//! ### Index Mapping
//! The `indices` array stores the original position for each sorted position:
//! - `indices[sorted_position] = original_position`
//! - This allows O(n) restoration of original order
//!
//! ### Non-finite Handling
//! - Finite values are sorted normally in ascending order
//! - NaN and Inf values are placed at the end
//! - Original order is preserved among non-finite values
//!
//! ## Invariants
//!
//! * Sorted x-values are in ascending order (finite values only).
//! * Index mapping is a valid permutation (bijection from sorted to original).
//! * Unsorted results have the same length as the original input.
//! * Non-finite values maintain their relative order from the input.
//!
//! ## Non-goals
//!
//! * This module does not validate input data.
//! * This module does not perform LOWESS smoothing.
//! * This module does not handle missing data or sparse arrays.
//!
//! ## Visibility
//!
//! This module is an internal implementation detail used by all adapters.
//! The [`SortedData`] struct and sorting functions are public but primarily
//! intended for internal use by the LOWESS engine.

#[cfg(not(feature = "std"))]
extern crate alloc;

#[cfg(not(feature = "std"))]
use alloc::vec;
#[cfg(not(feature = "std"))]
use alloc::vec::Vec;

use core::cmp::Ordering;
use num_traits::Float;

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

/// Result of sorting input data by x-coordinates.
///
/// Contains sorted data arrays and an index mapping that allows results
/// to be restored to the original input order after processing.
///
/// # Fields
///
/// * `x` - X-coordinates sorted in ascending order (finite values first)
/// * `y` - Y-coordinates reordered to match sorted x-coordinates
/// * `indices` - Index mapping where `indices[sorted_pos] = original_pos`
pub struct SortedData<T> {
    /// Sorted x-coordinates (finite values in ascending order, then non-finite).
    pub x: Vec<T>,

    /// Y-coordinates reordered to match the sorted x-coordinates.
    pub y: Vec<T>,

    /// Index mapping from sorted position to original position.
    ///
    /// For each sorted position `i`, `indices[i]` gives the original
    /// position of that element before sorting.
    pub indices: Vec<usize>,
}

impl<T> SortedData<T> {
    /// Returns the number of points in the sorted data.
    pub fn len(&self) -> usize {
        self.x.len()
    }

    /// Returns `true` if the sorted data contains no points.
    pub fn is_empty(&self) -> bool {
        self.x.is_empty()
    }
}

// ============================================================================
// Sorting Functions
// ============================================================================

/// Sort input data by x-coordinates in ascending order.
///
/// Creates a sorted copy of the input data along with an index mapping
/// that allows results to be restored to the original order. This is the
/// first step in the sort-process-unsort pattern used by LOWESS.
///
/// # Algorithm
///
/// 1. Pair each (x, y) with its original index
/// 2. Stable sort by x-coordinate:
///    - Finite values in ascending order
///    - Non-finite values (NaN, Inf) at the end
///    - Equal values maintain original order (stable sort)
/// 3. Extract sorted arrays and index mapping
///
/// # Parameters
///
/// * `x` - X-coordinates (independent variable)
/// * `y` - Y-coordinates (dependent variable)
///
/// # Returns
///
/// [`SortedData`] containing:
/// - Sorted x and y arrays
/// - Index mapping for later restoration of original order
///
/// # Complexity
///
/// * Time: O(n log n) for the stable sort
/// * Space: O(n) for the sorted arrays and index mapping
///
/// # Implementation notes
///
/// * Uses stable sort to ensure deterministic results
/// * Non-finite values are handled specially to prevent comparison issues
/// * The index mapping enables O(n) restoration of original order
pub fn sort_by_x<T: Float>(x: &[T], y: &[T]) -> SortedData<T> {
    // Create tuples of (x_value, y_value, original_index)
    let mut pairs: Vec<(T, T, usize)> = x
        .iter()
        .zip(y.iter())
        .enumerate()
        .map(|(i, (&xi, &yi))| (xi, yi, i))
        .collect();

    // Stable sort to preserve order of equal x values for determinism
    pairs.sort_by(|a, b| {
        match (a.0.is_finite(), b.0.is_finite()) {
            (true, true) => {
                // Both finite: normal comparison
                a.0.partial_cmp(&b.0).unwrap_or(Ordering::Equal)
            }
            (true, false) => Ordering::Less, // Finite values come first
            (false, true) => Ordering::Greater, // Non-finite values at end
            (false, false) => {
                // Both non-finite: preserve original order
                a.2.cmp(&b.2)
            }
        }
    });

    // Extract sorted components
    SortedData {
        x: pairs.iter().map(|p| p.0).collect(),
        y: pairs.iter().map(|p| p.1).collect(),
        indices: pairs.iter().map(|p| p.2).collect(),
    }
}

/// Map sorted results back to the original input order.
///
/// Restores the original order of data after processing sorted values.
/// This is the final step in the sort-process-unsort pattern.
///
/// # Parameters
///
/// * `sorted_values` - Values in sorted order (e.g., smoothed y-values)
/// * `indices` - Index mapping from [`sort_by_x`] (sorted → original)
///
/// # Returns
///
/// Values reordered to match the original input order.
///
/// # Complexity
///
/// * Time: O(n)
/// * Space: O(n) for the output vector
///
/// # Panics
///
/// Does not panic. Assumes `indices` is a valid permutation.
pub fn unsort<T: Float>(sorted_values: &[T], indices: &[usize]) -> Vec<T> {
    let n = indices.len();
    let mut result = vec![T::zero(); n];

    // Map each sorted position back to its original position
    for (sorted_idx, &orig_idx) in indices.iter().enumerate() {
        result[orig_idx] = sorted_values[sorted_idx];
    }

    result
}
