#![allow(unused_variables)]

extern crate rand;

use rand::Rng;
use std::time::Instant;

const MAX_LENGTH: i32 = 25;
const SIZE:       i32 = 200000;
const TEST_TIMES: u32 = 100;

fn verify(vec1: &Vec::<String>) -> bool {
    for x in 0..(SIZE - 1) as usize {
        match (&vec1[x], &vec1[x+1]) {
            (x, y) if x.chars().count() > y.chars().count()           => { println!("definate: {} > {}", x, y); return false },
            (x, y) if x > y && x.chars().count() == y.chars().count() => { println!("definate: {} > {}", x, y); return false },
            (x, y) if y > x                                           => continue,
            _                                                         => continue
        }
    }
    true
}

fn gen_random_vector_data(value: &mut Vec::<String>) {
    let mut rng = rand::thread_rng();

    for _ in 0..SIZE {
        value.push((0..rng.gen_range(1, MAX_LENGTH + 1)).map(|_| {
            rng.gen_range::<u8>(97, 123) as char
        }).collect());
    }
}

fn counting_sort(value: &Vec::<String>, result: &mut Vec::<String>, i: usize) {
    let mut table = vec![0 as usize; 27]; //reset table at start of loop

    for item in value.iter() {
        let index: usize = match item.chars().rev().nth(i) {
            Some(x) => x as usize - 96,
            None    => 0
        };

        table[index] += 1;
    }

    for x in 0..26 {
        table[x+1] += table[x];
    }
    for x in (0..26).rev() {
        table[x+1] = table[x];
    }
    table[0] = 0;

    for item in value.iter() {
        let index: usize = match item.chars().rev().nth(i) {
            Some(x) => x as usize - 96,
            None    => 0
        };

        result[table[index]] = item.to_string();
        table[index] += 1;
    }
}

fn radix_sort(mut value: Vec::<String>, mut result: &mut Vec::<String>) {
    for i in 0 .. (MAX_LENGTH) as usize {
        if i % 2 == 0 {
            counting_sort(&value, &mut result, i);
        } else {
            counting_sort(&result, &mut value, i);
        }
    }

    if MAX_LENGTH % 2 == 0 {
        *result = value;
    }
}

fn main() {
    //vars for timiming individual parts of functions
    let mut total_time_sort:   _ = std::time::Duration::new(0, 0);
    let mut total_time_verify: _ = std::time::Duration::new(0, 0);
    let mut total_time_gen:    _ = std::time::Duration::new(0, 0);
    let mut result = vec!["".to_string(); SIZE as usize]; //vec for our results

    for x in 0..TEST_TIMES {
        let mut value: Vec<String> = Vec::<String>::with_capacity(SIZE as usize); //vec for our random values

        let start_gen = Instant::now();
        gen_random_vector_data(&mut value);
        total_time_gen += Instant::now().duration_since(start_gen);

        let start_sort = Instant::now();
        radix_sort(value, &mut result);
        total_time_sort += Instant::now().duration_since(start_sort);

        //println!("({}) sorted data: {:?}", x, result);
        let start_verify = Instant::now();
        if !verify(&result) { break; } //verify if data is correct
        total_time_verify += Instant::now().duration_since(start_verify);
    }
    println!("average time to generate data: {:?}", total_time_gen / TEST_TIMES);
    println!("average time to sort data:     {:?}", total_time_sort / TEST_TIMES);
    println!("average time to verify data:   {:?}", total_time_verify / TEST_TIMES);
}