use std::path::Path;

use time;

use assert;
use reader;

pub const ID:   i32 = 10;
pub const DIR: &str = "array/mergein";

//-------------------------------------------------------------------------------
// O(m+n) time, O(1) extra space
//-------------------------------------------------------------------------------

pub fn first(data_path: &Path) -> Box<Fn() -> u64> {
  // Reading input
  let mut data = reader::read_all_lines(data_path);

  let first_count:  usize    = reader::first_usize(&mut data);
  let first:        Vec<i64> = reader::all_i64(&mut data, first_count);
  let second_count: usize    = reader::first_usize(&mut data);
  let second:       Vec<i64> = reader::all_i64(&mut data, second_count);

  reader::skip_empty_line(&mut data);

  // Reading desired output
  let expected: Vec<i64> = reader::all_i64(&mut data, first_count);

  Box::new(move || -> u64 {
    // Setup
    let mut first = first.clone();

    // Measure
    let start = time::precise_time_ns();
    first_algorithm(&mut first, &second);
    let end   = time::precise_time_ns();

    // Validate
    assert::eq_vec_i64(&first, &expected, "Result differes from expected!");

    // Result
    end - start
  })
}

fn first_algorithm(mut first: &mut Vec<i64>, second: &Vec<i64>) {
  rearrange(&mut first);

  merge(&mut first, &second);
}

fn rearrange(elements: &mut Vec<i64>) {
  let mut index    = 0;
  let mut position = 0;
  let     total    = elements.len() - 1;

  loop {
    let current = elements[index];

    if current != 0 {
      elements[position] = current;

      position += 1;
    }

    if index < total { index += 1; }
    else             { break;      }
  }
}

fn merge(mut first: &mut Vec<i64>, second: &Vec<i64>) {
  let mut  first_index =  first.len() - second.len() - 1;
  let mut second_index = second.len() - 1;
  let mut  final_index =  first.len() - 1;

  loop {
    let current_first  = first[first_index];
    let current_second = second[second_index];

    if current_first > current_second {
      first[final_index] = current_first;

      if first_index == 0 {
        for index in 0..(second_index + 1) {
          first[index] = second[index];
        }
      } else {
        first_index -= 1;
      }
    } else {
      first[final_index] = current_second;

      if second_index != 0 {
        second_index -= 1;
      }
    }

    if final_index == 0 { break;            }
    else                { final_index -= 1; }
  }
}
