slice-reduce 0.1.0

//! # 切片工具库/Slice Utilities
//! 
//! 提供高效的切片操作函数/Provides efficient slice operations
//! 
//! ## 功能/Features
//! - 分块/Chunking
//! - 搜索/Searching
//! - 统计/Counting
//! - 排序相关/Sorting utilities

use std::{cmp::{max, min, Ordering}, collections::HashMap};
use rand::Rng;

/// 将数组分块/Chunk an array into smaller arrays
/// 
/// # 参数/Arguments
/// * `arr` - 要分块的数组/The array to chunk
/// * `chunk_size` - 每个块的大小/The size of each chunk
/// 
/// # 返回值/Returns
/// 包含分块结果的 `Vec<Vec<T>>`/A vector of vectors containing the chunks
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::chunk;
/// let arr = vec![1, 2, 3, 4, 5];
/// let chunks = chunk(&arr, 2);
/// assert_eq!(chunks, vec![vec![1, 2], vec![3, 4], vec![5]]);
/// ```
/// 
/// # 注意/Notes
/// - 如果 `chunk_size` 为 0，返回空向量/If `chunk_size` is 0, returns empty vector
/// - 最后一个块可能小于 `chunk_size`/Last chunk may be smaller than `chunk_size`
pub fn chunk<T>(arr: &[T], chunk_size: usize) -> Vec<Vec<T>>
where
    T: Clone,
{
    let mut chunks: Vec<Vec<T>> = vec![];
    if chunk_size == 0 {
        chunks
    } else {
        for i in (0..arr.len()).step_by(chunk_size) {
            let end = min(i + chunk_size, arr.len());
            chunks.push(arr[i..end].to_vec());
        }
        chunks
    }
}

/// 按指定键函数统计元素出现次数/Count elements by key function
/// 
/// # 参数/Arguments
/// * `items` - 要统计的数组/The array to count
/// * `key_of` - 生成统计键的函数/Function to generate key
/// 
/// # 返回值/Returns
/// `HashMap<K, usize>` 键为统计键，值为出现次数/Key is the grouping key, value is count
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::count_by;
/// let words = ["hello", "world"];
/// let counts = count_by(&words, |s| s.len());
/// assert_eq!(counts[&5], 2);
/// ```
pub fn count_by<T, K, F>(items: &[T], key_of: F) -> HashMap<K, usize>
where
    K: std::hash::Hash + Eq,
    F: Fn(&T) -> K,
{
    let mut result = HashMap::<K, usize>::new();
    for item in items {
        let key = key_of(item);
        let count = result.entry(key).or_insert(0);
        *count += 1;
    }
    result
}

/// 统计元素出现次数/Count element occurrences
/// 
/// # 参数/Arguments
/// * `items` - 要统计的数组/The array to count
/// 
/// # 返回值/Returns
/// `HashMap<T, usize>` 键为元素，值为出现次数/Key is element, value is count
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::count;
/// let nums = [1, 2, 2, 3];
/// let counts = count(&nums);
/// assert_eq!(counts[&2], 2);
/// ```
pub fn count<T>(items: &[T]) -> HashMap<T, usize>
where
    T: std::hash::Hash + Eq + Clone,
{
    count_by(items, Clone::clone)
}

/// 反转数组/Reverse an array
/// 
/// # 参数/Arguments
/// * `arr` - 要反转的数组/The array to reverse
/// 
/// # 返回值/Returns
/// 反转后的新数组/New array with elements reversed
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::reverse;
/// let arr = [1, 2, 3];
/// assert_eq!(reverse(&arr), [3, 2, 1]);
/// ```
pub fn reverse<T>(arr: &[T]) -> Vec<T>
where
    T: Clone,
{
    let mut result = arr.to_vec();
    result.reverse();
    result
}

/// 线性搜索/Linear search
/// 
/// # 参数/Arguments
/// * `arr` - 要搜索的数组/The array to search
/// * `target` - 要查找的目标/The target to find
/// 
/// # 返回值/Returns
/// 目标索引（如果找到）/Index of target if found
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::linear_search;
/// let arr = [10, 20, 30];
/// assert_eq!(linear_search(&arr, &20), Some(1));
/// assert_eq!(linear_search(&arr, &40), None);
/// ```
pub fn linear_search<T>(arr: &[T], target: &T) -> Option<usize>
where
    T: PartialEq,
{
    for (i, item) in arr.iter().enumerate() {
        if item == target {
            return Some(i);
        }
    }
    None
}

/// 二分查找/Binary search (要求数组已排序/Array must be sorted)
/// 
/// # 参数/Arguments
/// * `arr` - 已排序的数组/Sorted array to search
/// * `target` - 要查找的目标/Target to find
/// 
/// # 返回值/Returns
/// 目标索引（如果找到）/Index of target if found
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::binary_search;
/// let arr = [10, 20, 30, 40];
/// assert_eq!(binary_search(&arr, &20), Some(1));
/// assert_eq!(binary_search(&arr, &25), None);
/// ```
pub fn binary_search<T>(arr: &[T], target: &T) -> Option<usize>
where
    T: Ord,
{
    let mut left = 0;
    let mut right = arr.len() - 1;
    while left <= right {
        let mid = left + (right - left) / 2;
        match arr[mid].cmp(target) {
            std::cmp::Ordering::Less => left = mid + 1,
            std::cmp::Ordering::Greater => right = mid - 1,
            std::cmp::Ordering::Equal => return Some(mid),
        }
    }
    None
}

/// 滑动窗口最大值/Sliding window maximum
/// 
/// # 参数/Arguments
/// * `slice` - 输入数组/Input array
/// * `window_size` - 窗口大小/Window size
/// 
/// # 返回值/Returns
/// 每个窗口的最大值组成的数组/Array of each window's maximum
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::sliding_window_max;
/// let arr = [1, 3, -1, -3, 5, 3];
/// assert_eq!(sliding_window_max(&arr, 3), vec![3, 3, 5, 5]);
/// ```
/// 
/// # 注意/Notes
/// - 窗口大小必须 ≤ 数组长度/Window size must ≤ array length
pub fn sliding_window_max(slice: &[i32], window_size: usize) -> Vec<i32> {
    let mut result = vec![];
    for i in 0..=slice.len() - window_size {
        let window = &slice[i..i + window_size];
        let max = window.iter().max().unwrap();
        result.push(*max);
    }
    result
}

/// 合并两个已排序数组合并保持顺序/Merge two sorted arrays
/// 
/// # 参数/Arguments
/// * `a` - 第一个已排序数组/First sorted array
/// * `b` - 第二个已排序数组/Second sorted array
/// 
/// # 返回值/Returns
/// 合并后的新数组/New merged array
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::merge_sorted;
/// let a = [1, 3, 5];
/// let b = [2, 4, 6];
/// assert_eq!(merge_sorted(&a, &b), vec![1, 2, 3, 4, 5, 6]);
/// ```
pub fn merge_sorted<T: Ord + Clone>(a: &[T], b: &[T]) -> Vec<T> {
    let mut merged = vec![];
    let mut i = 0;
    let mut j = 0;
    while i < a.len() && j < b.len() {
        if a[i] <= b[j] {
            merged.push(a[i].clone());
            i += 1;
        } else {
            merged.push(b[j].clone());
            j += 1;
        }
    }
    while i < a.len() {
        merged.push(a[i].clone());
        i += 1;
    }
    while j < b.len() {
        merged.push(b[j].clone());
        j += 1;
    }
    merged
}

/// 查找字符串数组的最长公共前缀/Longest common prefix of strings
/// 
/// # 参数/Arguments
/// * `strs` - 字符串数组/String array
/// 
/// # 返回值/Returns
/// 最长公共前缀字符串/Longest common prefix string
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::longest_common_prefix;
/// let strs = ["flower", "flow", "flight"];
/// assert_eq!(longest_common_prefix(&strs), "fl");
/// ```
pub fn longest_common_prefix(strs: &[&str]) -> String {
    if strs.is_empty() {
        return "".to_string();
    }
    let mut prefix = strs[0].to_string();
    for s in strs.iter().skip(1) {
        while !s.starts_with(&prefix) {
            prefix.pop();
            if prefix.is_empty() {
                return "".to_string();
            }
        }
    }
    prefix
}

/// 最大子数组和（Kadane算法）/Maximum subarray sum (Kadane's algorithm)
/// 
/// # 参数/Arguments
/// * `slice` - 输入数组/Input array
/// 
/// # 返回值/Returns
/// 最大子数组和/Maximum subarray sum
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::max_subarray_sum;
/// let arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
/// assert_eq!(max_subarray_sum(&arr), 6);  // [4, -1, 2, 1]
/// ```
pub fn max_subarray_sum(slice: &[i32]) -> i32 {
    let mut max_sum = slice[0];
    let mut current_sum = slice[0];
    for item in slice.iter().skip(1) {
        current_sum = max(*item, current_sum + *item);
        max_sum = max(max_sum, current_sum);
    }
    max_sum
}

/// 随机打乱数组/Randomly shuffle array (Fisher-Yates算法/Fisher-Yates algorithm)
/// 
/// # 参数/Arguments
/// * `slice` - 要打乱的数组/Array to shuffle
/// * `rng` - 随机数生成器实例/Random number generator instance
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::shuffle;
/// use rand::thread_rng;
/// 
/// let mut arr = [1, 2, 3, 4, 5];
/// let mut rng = thread_rng();
/// shuffle(&mut arr, &mut rng);
/// println!("{:?}", arr);  // 随机顺序/Random order
/// ```
/// 
/// # 高级用法/Advanced usage
/// ```
/// // 使用确定性随机源测试（需rand::rngs::mock）
/// # #[cfg(feature = "rand")]
/// use rand::rngs::mock::StepRng;
/// # #[cfg(feature = "rand")]
/// let mut test_arr = [1, 2, 3];
/// # #[cfg(feature = "rand")]
/// shuffle(&mut test_arr, &mut StepRng::new(0, 1));
/// # #[cfg(feature = "rand")]
/// assert_eq!(test_arr, [2, 1, 3]);
/// ```
pub fn shuffle<T, R: Rng>(slice: &mut [T], rng: &mut R) {
    for i in (1..slice.len()).rev() {
        let j = rng.random_range(0..=i);
        slice.swap(i, j);
    }
}

/// 已排序数组去重/Remove duplicates from sorted array
/// 
/// # 参数/Arguments
/// * `slice` - 要处理的数组（必须已排序）/Array to process (must be sorted)
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::dedup_sorted;
/// let mut arr = vec![1, 1, 2, 3, 3, 3];
/// dedup_sorted(&mut arr);
/// assert_eq!(arr, [1, 2, 3]);
/// ```
pub fn dedup_sorted<T>(slice: &mut Vec<T>)
where
    T: PartialEq + Copy,
{
    if slice.is_empty() {
        return;
    }

    let mut write_index = 1;
    for read_index in 1..slice.len() {
        if slice[read_index] != slice[write_index - 1] {
            slice[write_index] = slice[read_index];
            write_index += 1;
        }
    }
    slice.truncate(write_index);
}

/// 切片比较（类似字典序）/Slice comparison (lexicographical order)
/// 
/// # 参数/Arguments
/// * `a` - 第一个切片/First slice
/// * `b` - 第二个切片/Second slice
/// 
/// # 返回值/Returns
/// 比较结果（Ordering）/Comparison result (Ordering)
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::slice_cmp;
/// use std::cmp::Ordering;
/// let a = [1, 2, 3];
/// let b = [1, 2, 4];
/// assert_eq!(slice_cmp(&a, &b), Ordering::Less);
/// ```
pub fn slice_cmp<T>(a: &[T], b: &[T]) -> Ordering
where T: Ord
{
    let min_len = min(a.len(), b.len());
    for i in 0..min_len {
        match a[i].cmp(&b[i]) {
            Ordering::Less => return Ordering::Less,
            Ordering::Greater => return Ordering::Greater,
            Ordering::Equal => continue,
        }
    }
    a.len().cmp(&b.len())
}

/// 用模式重复填充数组/Repeat pattern to fill array
/// 
/// # 参数/Arguments
/// * `slice` - 要填充的数组/Array to fill
/// * `pattern` - 重复模式/Pattern to repeat
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::repeat_fill;
/// let mut arr = [0; 5];
/// repeat_fill(&mut arr, &[1, 2]);
/// assert_eq!(arr, [1, 2, 1, 2, 1]);
/// ```
pub fn repeat_fill<T>(slice: &mut [T], pattern: &[T])
where T: Copy
{
    if pattern.is_empty() {
        return;
    }
    for i in (0..slice.len()).step_by(pattern.len()) {
        let end = min(i + pattern.len(), slice.len());
        slice[i..end].copy_from_slice(pattern);
    }
}

/// 安全的分割切片/Safely split slice at index
/// 
/// # 参数/Arguments
/// * `slice` - 要分割的切片/Slice to split
/// * `mid` - 分割位置/Split position
/// 
/// # 返回值/Returns
/// `Some((left, right))` 如果分割成功，否则 `None`/`Some((left, right))` if valid, else `None`
/// 
/// # 示例/Examples
/// ```
/// use slice_reducer::split_at_checked;
/// let arr = [1, 2, 3, 4];
/// assert!(split_at_checked(&arr, 2).is_some());
/// assert!(split_at_checked(&arr, 5).is_none());
/// ```
pub fn split_at_checked<T> (slice: &[T], mid: usize) -> Option<(&[T], &[T])> { 
    if mid > slice.len() {
        return None;
    }
    Some(slice.split_at(mid))
}