pub fn bubble_sort<T: Ord>(data: &mut [T])
{
    for offset in 0 .. data.len()
    {
        for index in 1 .. data.len() - offset
        {
            if data[index - 1] > data[index]
            {
                data.swap(index, index - 1);
            }
        }
    }
}

pub fn selection_sort<T: Ord>(data: &mut [T])
{
    for offset in 0 .. data.len()
    {
        let mut min_index = offset;
        for index in 0 + offset .. data.len()
        {
            if data[index] < data[min_index]
            {
                min_index = index;
            }
        }
        data.swap(min_index, offset);
    }
}

pub fn insertion_sort<T: Ord>(data: &mut [T])
{
    for mut index in 1 .. data.len()
    {
        while index > 0 && data[index] < data[index - 1]
        {
            data.swap(index, index - 1);
            index -= 1;
        }
    }
}

pub fn merge_sort<T: Copy + Ord>(data: &mut [T]) 
{
	let mid = (data.len() as f32 / 2.0).round() as usize;
 
	if data.len() > 1 
    {
        merge_sort(&mut data[.. mid]);
        merge_sort(&mut data[mid ..]);
     
        let mut result: Vec<T> = data.to_vec();
 
        merge(&data[.. mid], &data[mid ..], &mut result[..]);
     
        data.copy_from_slice(&result);
    }
}

fn merge<T: Copy + Ord>(left: &[T], right: &[T], result: &mut [T])
{
    let mut index_left = 0;
    let mut index_right = 0;
    let mut index_data = 0;
    while index_left < left.len() && index_right < right.len()
    {
        if left[index_left] < right[index_right] 
        {
            result[index_data] = left[index_left];
            index_data += 1;
            index_left += 1;
        } 
        else 
        {
            result[index_data] = right[index_right];
            index_data += 1;
            index_right += 1;
        }
    }

    if index_left < left.len()
    {
        result[index_data ..].copy_from_slice(&left[index_left ..]);
    }
    if index_right < right.len()
    {
        result[index_data ..].copy_from_slice(&right[index_right ..]);
    }
}

pub fn quick_sort<T: Clone + Ord>(data: &mut [T])
{
    if data.len() > 2
    {
        let pivot_index = data.len() / 2;
        let pivot = data[pivot_index].clone();
        let mut last_left_index = 0;
        let mut last_right_index = data.len() - 1;

        loop
        {
            if data[last_left_index] >= pivot
            {
                let mut is_searching = true;
                while (last_left_index != last_right_index) && is_searching
                {
                    if data[last_right_index] <= pivot
                    {
                        data.swap(last_left_index, last_right_index);
                        is_searching = false;
                    }
                    last_right_index -= 1;
                }
            }

            if last_left_index == last_right_index
            {
                break;
            }
            last_left_index += 1;
        }

        let factor = if data[last_right_index] <= pivot {1} else {0};
        quick_sort(&mut data[.. last_right_index + factor]);
        quick_sort(&mut data[last_right_index + factor ..]);
    }
    else if data.len() == 2
    {
        if data[0] > data[1]
        {
            data.swap(0, 1);
        }
    }
}

pub fn radix_sort<T: Clone + Ord + ToString>(data: &mut [T])
{
    let mut is_searching = true;
    let mut actual_digit = 1;
    while is_searching
    {
        let mut binding: Vec<Vec<usize>> = vec![vec![]; 10];
        is_searching = false;
        for (index, number) in data.iter().map(|x| x.to_string()).enumerate()
        {
            if number.len() >= actual_digit
            {
                let mut number_chars = number.chars().rev().skip(actual_digit - 1);
                let digit = number_chars.next().unwrap().to_digit(10).unwrap() as usize;
                binding[digit].push(index);
                is_searching = true;
            }
            else
            {
                binding[0].push(index);
            }
        }

        if is_searching
        {
            let mut index_data = 0;
            let tmp = data.to_vec();
            for index in binding
            {
                for item in index
                {
                    data[index_data] = tmp[item].clone();
                    index_data += 1;
                }
            }
            actual_digit += 1;
        }
    }
}

#[cfg(test)]
mod tests
{
    use super::*;

    #[test]
    fn test_bubble_sort()
    {
        let mut data = vec![5, 2, 12, 7, 1, 5, 11, 5];
        let expected = vec![1, 2, 5, 5, 5, 7, 11, 12];
        bubble_sort(&mut data);

        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_selection_sort()
    {
        let mut data = vec![5, 2, 12, 14, 7, 1, 5, 11, 5];
        let expected = vec![1, 2, 5, 5, 5, 7, 11, 12, 14];
        selection_sort(&mut data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_insertion_sort()
    {
        let mut data = vec![5, 2, 12, 14, 7, 1, 5, 11, 5];
        let expected = vec![1, 2, 5, 5, 5, 7, 11, 12, 14];
        insertion_sort(&mut data);
        println!("{:?}", data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_merge_sort()
    {
        let mut data = vec![5, 2, 12, 14, 7, 1, 5, 11, 5];
        let expected = vec![1, 2, 5, 5, 5, 7, 11, 12, 14];
        merge_sort(&mut data);
        println!("{:?}", data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_quick_sort()
    {
        let mut data = vec![5, 2, 12, 14, 7, 1, 5, 11, 5, 99, 25, 0, 9];
        let expected = vec![0, 1, 2, 5, 5, 5, 7, 9, 11, 12, 14, 25, 99];
        quick_sort(&mut data);
        println!("{:?}", data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_quick_sort_zero_args()
    {
        let mut data = Vec::<u32>::new();
        quick_sort(&mut data);
        assert_eq!(0, data.len());
    }

    #[test]
    fn test_quick_sort_one_arg()
    {
        let mut data = vec![5];
        let expected = vec![5];
        quick_sort(&mut data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_quick_sort_two_args_sorted()
    {
        let mut data = vec![2, 5];
        let expected = vec![2, 5];
        quick_sort(&mut data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    
    #[test]
    fn test_quick_sort_two_args()
    {
        let mut data = vec![5, 2];
        let expected = vec![2, 5];
        quick_sort(&mut data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_quick_sort_biggest_pivot()
    {
        let mut data = vec![4, 1, 6, 2, 77, 34, 52, 8, 12];
        let expected = vec![1, 2, 4, 6, 8, 12, 34, 52, 77];
        quick_sort(&mut data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_quick_sort_smallest_pivot()
    {
        let mut data = vec![4, 77, 6, 2, 1, 34, 52, 8, 12];
        let expected = vec![1, 2, 4, 6, 8, 12, 34, 52, 77];
        quick_sort(&mut data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_radix_sort_dozens()
    {
        let mut data = vec![77, 1, 34, 52, 8, 12];
        let expected = vec![1, 8, 12, 34, 52, 77];
        radix_sort(&mut data);
        println!("{:?}", data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_radix_sort_hundreds()
    {
        let mut data = vec![77, 1, 120, 34, 52, 8, 12, 754, 22];
        let expected = vec![1, 8, 12, 22, 34, 52, 77, 120, 754];
        radix_sort(&mut data);
        println!("{:?}", data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }

    #[test]
    fn test_radix_sort_simple()
    {
        let mut data = vec![3, 0, 9, 2, 5, 1, 2, 2, 6, 4];
        let expected = vec![0, 1, 2, 2, 2, 3, 4, 5, 6, 9];
        radix_sort(&mut data);
        println!("{:?}", data);
        for index in 0 .. data.len()
        {
            assert_eq!(expected[index], data[index]);
        }
    }
}