use rand::RngCore;

#[derive(Copy, Clone)]
enum PivotChoice {
    Random,
    Last,
}

fn main() {
    let mut numbers = [10, 8, 3, 6, 1, 4, 2, 5, 9, 7];
    let length = numbers.len();
    println!("{:?}", numbers);
    quick_sort(&mut numbers, 0, length, PivotChoice::Last);
}

fn quick_sort(mut array: &mut [i32], from: usize, to: usize, pc: PivotChoice) {
    fn partition(array: &mut [i32], from: usize, pivot_idx: usize, to: usize)
            -> usize {
        let pivot = array[pivot_idx];
        let num_left = array[from..to].iter().filter(|n| **n <= pivot).count()-1;
        let new_pivot_idx = from + num_left;
        array.swap(pivot_idx, new_pivot_idx);

        // l and r are indices for the left and right side respectively
        let mut r = to - 1;
        for l in from..new_pivot_idx {
            if array[l] > pivot {
                while array[r] > pivot {
                    r -= 1;
                }
                array.swap(l, r);
            }
        }

        new_pivot_idx
    }

    if array[from..to].len() >= 2 {
        let pivot = match pc {
            PivotChoice::Random => rand::thread_rng().next_u32() as usize
                                   % (to - from) + from,
            PivotChoice::Last => to - 1,
        };
        let middle = partition(&mut array, from, pivot, to);
        print_progress(array, from, to);
        quick_sort(&mut array, from, middle, pc);
        quick_sort(&mut array, middle + 1, to, pc);
    }
}

fn print_progress(array: &mut [i32], from: usize, to: usize) {
    print!("[");
    for i in 0..from {
        print!("{}, ", array[i]);
    }
    print!("\\highlight{{");
    for i in from..to {
        print!("{}, ", array[i]);
    }
    print!("}}");
    for i in to..array.len() {
        print!("{}, ", array[i]);
    }
    println!("]");
}