sort-steps 0.2.4

use std::{cmp::Ordering, iter::from_generator};
/// Sorts a slice of data using the pancake sort algorithm with a custom comparator.
///
/// # Examples
///
/// ```
/// # use sort_steps::{pancake_sort};
/// let numbers = [5, 9, 3, 6, 8, 2, 1, 7, 4];
/// println!("Heap Sort Steps:");
/// for (i, v) in pancake_sort(&numbers).enumerate() {
///     println!("#{:02}: {:?}", i, v);
/// }
/// ```
pub fn pancake_sort<T>(v: &[T]) -> impl Iterator<Item = Vec<T>>
where
    T: Clone + PartialOrd,
{
    pancake_sort_by(v, |a, b| a.partial_cmp(b))
}

/// Sorts a slice of data using the pancake sort algorithm with a custom comparator.
///
/// # Examples
///
/// ```
/// # use sort_steps::{pancake_sort_by};
/// let numbers = [5, 9, 3, 6, 8, 2, 1, 7, 4];
/// println!("Heap Sort Steps:");
/// for (i, v) in pancake_sort_by(&numbers, |a, b| a.partial_cmp(b)).enumerate() {
///     println!("#{:02}: {:?}", i, v);
/// }
/// ```
pub fn pancake_sort_by<T, F>(v: &[T], compare: F) -> impl Iterator<Item = Vec<T>>
where
    F: Fn(&T, &T) -> Option<Ordering> + Copy,
    T: Clone,
{
    let mut state = v.to_vec();

    from_generator(move || {
        yield state.to_vec();
        for i in (1..=state.len()).rev() {
            let max_index = find_max_index(&state[..i], compare);
            if max_index != i - 1 {
                if max_index != 0 {
                    flip(&mut state, max_index);
                    yield state.to_vec();
                }
                flip(&mut state, i - 1);
                yield state.to_vec();
            }
        }
    })
}

// Helper function to reverse the elements in the slice from 0 to index
fn flip<T>(v: &mut [T], index: usize)
where
    T: Clone,
{
    v[..=index].reverse();
}

// Find the index of the maximum element in the slice
fn find_max_index<T, F>(v: &[T], compare: F) -> usize
where
    F: Fn(&T, &T) -> Option<Ordering> + Copy,
{
    let mut max_index = 0;
    for i in 1..v.len() {
        if compare(&v[max_index], &v[i]) == Some(Ordering::Less) {
            max_index = i;
        }
    }
    max_index
}