// this is the benchmark for overlapping tables, 5 to 1995

extern crate rand;

use rand::Rng;
use std::cmp;

struct ESubTable {
    itablePtrs: Vec<Option<u32>>
}

// fn collapse_right(x: u32) -> u32 {
//  if x == 0 {
//      return 0
//  }
//  let mut num_shifts = 0;
//  loop {
//      let num_shifts_is_fine = ((x >> num_shifts) << num_shifts) == x;
//      let num_shifts_plus_one_is_fine =((x >> (num_shifts + 1)) << (num_shifts + 1)) == x;
//      if !num_shifts_is_fine {
//          panic!();
//      }
//      if num_shifts_is_fine && !num_shifts_plus_one_is_fine {
//          return x >> num_shifts;
//      } else {
//          num_shifts = num_shifts + 1;
//      }
//  }
// }

// fn get_span(mut x: u32) -> i32 {
//  if x == 0 {
//      return 0;
//  }
//  x = collapse_right(x);

//  for i in 0..32 {
//      if x >> i == 0 {
//          return i;
//      }
//  }
//  panic!();
// }

fn trim_array(original: &Vec<Option<u32>>) -> (Vec<Option<u32>>, u32, u32) {
    let mut trimmed_left = 0;
    let mut trimmed_right = 0;
    let mut array = original.clone();
    while array.len() > 0 && array[0] == None {
        array.remove(0);
        trimmed_left = trimmed_left + 1;
    }
    while array.len() > 0 && array[array.len() - 1] == None {
        let l = array.len();
        array.remove(l - 1);
        trimmed_right = trimmed_right + 1;
    }
    return (array, trimmed_left, trimmed_right);
}

fn compare_esubtable(a: &ESubTable, b: &ESubTable) -> std::cmp::Ordering {
    let (a_trimmed, _, _) = trim_array(&a.itablePtrs);
    let (b_trimmed, _, _) = trim_array(&b.itablePtrs);
    let a_span = a_trimmed.len();
    let b_span = b_trimmed.len();
    if a_span < b_span {
        return std::cmp::Ordering::Less;
    }
    if a_span > b_span {
        return std::cmp::Ordering::Greater;
    }
    let a_num_members = count_array_members(&a_trimmed);
    let b_num_members = count_array_members(&b_trimmed);
    if a_num_members < b_num_members {
        return std::cmp::Ordering::Less;
    }
    if a_num_members > b_num_members {
        return std::cmp::Ordering::Greater;
    }
    return std::cmp::Ordering::Equal;
}

fn merges_without_collisions(
        combined: &Vec<Option<u32>>,
        addition: &Vec<Option<u32>>,
        addition_start_index_in_combined: u32) -> bool {
    for i in 0..addition.len() {
        let i_in_combined = addition_start_index_in_combined + i as u32;
        if i_in_combined >= combined.len() as u32 {
            // no collision
        } else if combined[i_in_combined as usize] == None {
            // no collision
        } else if addition[i as usize] == None {
            // no collision
        } else {
            // collision!
            return false;
        }
    }
    return true;
}

fn merge_into(combined: &mut Vec<Option<u32>>, addition: &Vec<Option<u32>>) -> u32 {
    let mut addition_start_index_in_combined: u32 = 0;
    for i in 0..(combined.len() + 1) {
        addition_start_index_in_combined = i as u32;
        if merges_without_collisions(&combined, &addition, i as u32) {
            break;
        }
    }
    // println!("will try merge!");
    // println!("combined: ");
    // print_array(&combined);
    // println!("addition: ");
    // print_array(&addition);
    // println!("index: {}", addition_start_index_in_combined);

    let combined_num_members_before = count_array_members(&combined);

    for i in 0..addition.len() {
        if addition_start_index_in_combined + i as u32 >= combined.len() as u32 {
            combined.push(None); // will be overwritten below
        }
        if addition[i] != None {
            combined[(addition_start_index_in_combined + i as u32) as usize] = addition[i];
        }
    }

    let combined_num_members_after = count_array_members(&combined);
    if combined_num_members_after != combined_num_members_before + count_array_members(&addition) {
        panic!();
    }

    return addition_start_index_in_combined;
}

fn print_array(array: &Vec<Option<u32>>) {
    print!("(");
    for opt in array.iter() {
        match opt {
            &Some(i) => {
                print!("Some({}) ", i);
            }
            &None => {
                print!("None ");
            }
        }
    }
    println!(")");
}

fn combine_etables(etable: &Vec<ESubTable>) -> Vec<Option<u32>> {
    let mut esubtables_sorted: Vec<&ESubTable> = Vec::new();
    for esubtable in etable {
        esubtables_sorted.push(&esubtable);
    }
    esubtables_sorted.sort_by(|a, b| compare_esubtable(a, b));

    let mut combined: Vec<Option<u32>> = Vec::new();
    for i in 0..etable.len() {
        if etable[i].itablePtrs.len() > 0 {
            combined.push(Some(0xFFFFFFFF));
        } else {
            combined.push(None);
        }
    }

    // print_array(&combined);
    for esubtable in etable {
        merge_into(&mut combined, &esubtable.itablePtrs);
        // print_array(&combined);
    }
    return combined;
}

fn make_none_vec_with_size(capacity: u32) -> Vec<Option<u32>> {
    let mut vec: Vec<Option<u32>> = Vec::new();
    for _ in 0..capacity {
        vec.push(None);
    }
    return vec;
}

fn make_esubtable_with(capacity: u32) -> ESubTable {
    let esubtable = ESubTable {
        itablePtrs: make_none_vec_with_size(capacity)
    };
    return esubtable;
}

fn make_zero_etable(capacity: u32) -> Vec<ESubTable> {
    let mut etable: Vec<ESubTable> = Vec::new();
    for _ in 0..capacity {
        etable.push(make_esubtable_with(capacity));
    }
    return etable;
}

fn insert_into_esubtable(esubtable: &mut ESubTable, id: u32) {
    let esubindex = (id % esubtable.itablePtrs.len() as u32) as usize;
    esubtable.itablePtrs[esubindex] = Some(id)
}

fn bucket_into_esubtable(esubtable: &mut ESubTable, id: u32) {
    esubtable.itablePtrs.push(Some(id))
}

fn bucket_into_etable(etable: &mut Vec<ESubTable>, id: u32) {
    let etopindex = (id % (etable.len() as u32)) as usize;
    let mut esubtable = &mut etable[etopindex];
    bucket_into_esubtable(&mut esubtable, id);
}

fn hashify_esubtable(esubtable: &mut ESubTable) {
    let ids = get_array_members(&esubtable.itablePtrs);

    let mut size = ids.len() as u32;
    loop {
        esubtable.itablePtrs = make_none_vec_with_size(size);
        for id in &ids {
            insert_into_esubtable(esubtable, *id);
        }
        if get_array_members(&esubtable.itablePtrs).len() == ids.len() {
            break;
        }
        size = size + 1;
    }
}

fn get_array_members(array: &Vec<Option<u32>>) -> Vec<u32> {
    let mut members: Vec<u32> = Vec::new();
    for j in 0..array.len() {
        match array[j as usize] {
            Some(id) => {
                members.push(id);
            }
            None => {}
        }
    }
    return members;
}

fn count_array_members(esubtable: &Vec<Option<u32>>) -> u32 {
    return get_array_members(esubtable).len() as u32;
}

fn generate_etable(ids: &Vec<u32>) -> (Vec<Option<u32>>) {
    let mut capacity = ((ids.len() as f64).sqrt() / 2.0) as u32;
    // if ids.len() > 170 {
    //  capacity = ((ids.len() as f32) * 1.5f32) as u32;
    // }
    // if ids.len() > 250 {
    //  capacity = (ids.len() as u32) * 2;
    // }

    loop {
        let mut etable = make_zero_etable(capacity);

        for id in ids.iter() {
            bucket_into_etable(&mut etable, *id);
        }
        for mut esubtable in &mut etable {
            hashify_esubtable(&mut esubtable);
        }
        let combined = combine_etables(&etable);
        // return combined;
        println!("with capacity {}, end result {}", capacity, combined.len());

        capacity = capacity + 10;

        if capacity as usize >= ids.len() * 2 {
            return combined;
        }
    }
}



fn main() {
    let mut rng = rand::thread_rng();

    let increment = 1000;
    let stop = 1000;
    let mut num_elements = 0;
    loop {
        num_elements = num_elements + increment;

        let mut sum_of_sizes_for_average: u64 = 0;
        let num_trials = 10;
        let mut worst_size_option: Option<u32> = None;

        for _ in 0..num_trials {
            let mut ids: Vec<u32> = Vec::new();
            for _ in 0..num_elements {
                ids.push(rng.gen::<u32>());
            }
            let etable = generate_etable(&ids);

            let size = etable.len() as u32;

            sum_of_sizes_for_average = sum_of_sizes_for_average + size as u64;
            match worst_size_option {
                None => {
                    worst_size_option = Some(size);
                }
                Some(previously_worst_size) => {
                    worst_size_option = Some(cmp::max(previously_worst_size, size));
                }
            }
        }

        let average_size = sum_of_sizes_for_average as f64 / num_trials as f64;
        let worst_size = worst_size_option.unwrap_or(0);

        println!("For {} elements, average size {} and worst size {}", num_elements, average_size, worst_size);

        if num_elements >= stop {
            break;
        }
    }
}