//! This module holds all the different sorting algorithms described in chapter 2 of the book.
//!
//! ## Examples
//!
//! Sort an array :)
//! ```
//! use algorithms4::MergeSort;
//!
//! let mut vec = vec![4, 1, 8, 10, 47, 2];
//! # let mut og_sorted_vec = vec.clone();
//! # og_sorted_vec.sort();
//! MergeSort::bottom_up_sort(&mut vec);
//! # assert_eq!(vec, og_sorted_vec);
//! ```

/// Test if array is actually sorted
fn is_sorted<T: Ord>(arr: &[T]) -> bool {
    if arr.len() <= 1 {
        return true;
    }

    for i in 1..arr.len() {
        if arr[i] < arr[i - 1] {
            return false;
        }
    }
    true
}

#[cfg(test)]
macro_rules! test_sort {
    ($($name:ident),*) => ($(
        pastey::paste! {
            #[test]
            fn [<$name _works>]() {
                let mut arr = vec![4, 5, 2, 6, 3, 1];
                $name(&mut arr);
                assert!(is_sorted(&arr));
                assert_eq!(arr, vec![1, 2, 3, 4, 5, 6]);
            }

            #[test]
            fn [<$name _big_works>]() {
                let mut rand = rand::rng();

                let mut arr = vec![0; 100];
                for item in arr.iter_mut() {
                    *item = rand.random_range(0..1000);
                }

                let mut clone = arr.to_vec();
                clone.sort(); // assume rust's sorting works

                $name(&mut arr);

                assert!(is_sorted(&arr));
                assert_eq!(arr, clone);
            }

            #[test]
            fn [<$name _really_big_works>]() {
                let mut rand = rand::rng();

                let mut arr = vec![0; 10_000];
                for item in arr.iter_mut() {
                    *item = rand.random_range(0..1000);
                }

                let mut clone = arr.to_vec();
                clone.sort(); // assume rust's sorting works

                $name(&mut arr);

                assert!(is_sorted(&arr));
                assert_eq!(arr, clone);
            }

            #[test]
            fn [<$name _single>]() {
                let mut arr = vec![1];
                $name(&mut arr);
                assert!(is_sorted(&arr));
                assert_eq!(arr, vec![1]);
            }

            #[test]
            fn [<$name _pre_sorted>]() {
                let mut arr = vec![1, 4, 5, 9, 14, 42];
                $name(&mut arr);
                assert!(is_sorted(&arr));
                assert_eq!(arr, vec![1, 4, 5, 9, 14, 42]);
            }
        }
    )*);
}

mod elementary;
mod merge;
pub mod priority_queue;
mod quick;

pub use elementary::*;
pub use merge::MergeSort;
pub use priority_queue::{
    HeapSort, IndexPriorityQueue, IndexPriorityQueueErrors, PriorityQueue,
};
pub use quick::QuickSort;
