#[cfg(test)]
mod tests {
    #[test]
    fn it_works() {
        assert_eq!(2 + 2, 4);
    }
}

use std::cmp::{max, min};
use std::mem::take;

pub struct Muto {
	jobs: Vec<Job>,
	vehicles: Vec<Vehicle>,
	cost_matrix: CostMatrix,
}

impl Muto {
	pub fn new() -> Muto {
		Muto {
			jobs: vec!(),
			vehicles: vec!(),
			cost_matrix: CostMatrix {
				elements: vec![],
			},
		}
	}

	pub fn add_job(&mut self, job: Job) {
		self.jobs.push(job);
	}

	pub fn set_cost_matrix(&mut self, cost_matrix: CostMatrix) {
		self.cost_matrix = cost_matrix;
	}

	pub fn start(&self) {
		println!("Hello, World!");
	}

	pub fn add_vehicle(&mut self, vehicle: Vehicle) {
		self.vehicles.push(vehicle);
	}

	pub fn solve(&mut self) -> Vec<Solution> {

		let mut routes: Vec<Route> = vec![];

		let mut unassigned_jobs: Vec<Job> = vec![];

		for job in self.jobs.iter() {
			unassigned_jobs.push(*job);
		}

		let mut cost: i64 = 0;

		// Just do a really simple greedy algorithm at the moment.
		for vehicle in self.vehicles.iter() {

			if unassigned_jobs.len() == 0 {
				break;
			}

			let mut route: Route = Route::new(vehicle.id);

			route.tasks.push(Task {
				start_time: vehicle.time_window.start,
				end_time: vehicle.time_window.start,
				location: vehicle.start_location,
				task_type: TaskType::START(),
			});

			route.tasks.push(Task {
				start_time: vehicle.time_window.end,
				end_time: vehicle.time_window.end,
				location: vehicle.end_location,
				task_type: TaskType::END(),
			});

			// Find the job that costs the least to insert next in the route.
			// Get all the jobs to try

			let mut attempt_jobs: Vec<Job> = vec![];

			for job in unassigned_jobs.iter() {
				attempt_jobs.push(*job);
			}

			unassigned_jobs.clear();

			// Go through each job to attempt.
			// If it can be inserted, store how much that will cost
			// If it can't be inserted, discard it
			// Find the least cost job and insert it into the tasks
			// Clear and insert all viable jobs back into the attempt list
			// Repeat until we end up with zero viable jobs to attempt again with

			while attempt_jobs.len() > 0 {

				let mut re_insert: Vec<Job> = vec![];

				let mut best_insertion: Option<InsertionData> = None;

				for job in attempt_jobs.iter() {

					if job.time_window.end < vehicle.time_window.start ||
						job.time_window.start > vehicle.time_window.end {
						unassigned_jobs.push(*job);
						continue;
					}

					let insertion_data = self.attempt_insert(job, &vehicle, &route);

					match insertion_data {

						None => {
							unassigned_jobs.push(*job);
						}

						Some(insertion_data) => {
							if let Some(current_best) = best_insertion {

								if insertion_data.cost < current_best.cost {
									best_insertion = Some(insertion_data);
									re_insert.push(current_best.job);

								} else {
									re_insert.push(insertion_data.job);
								}

							} else {
								best_insertion = Some(insertion_data);
							}
						}
					}

				}

				if let Some(best_insert) = best_insertion {

					cost += best_insert.cost;

					route.tasks.push(Task{
						start_time: best_insert.insertion_time,
						end_time: best_insert.insertion_time + best_insert.job.service_time,
						location: best_insert.job.location,
						task_type: TaskType::JOB(JobTaskData{
							job_id: best_insert.job.id,
						})
					});

					route.tasks.sort_by(|a, b| a.start_time.cmp(&b.start_time));
				}

				attempt_jobs.clear();
				for job in re_insert.iter() {
					attempt_jobs.push(*job);
				}
			}

			routes.push(route);
		}

		vec!(Solution {
			cost,
			routes,
		})
	}

	fn attempt_insert(&self, job: &Job, vehicle: &Vehicle, route: &Route) -> Option<InsertionData> {

		let start_bound = max(job.time_window.start, vehicle.time_window.start);
		let end_bound = min(job.time_window.end, vehicle.time_window.end);

		let mut insert_time = start_bound;
		let mut insert_end_time = insert_time + job.service_time;

		let mut prev_task: &Task = route.tasks.get(0).unwrap();
		let mut next_task: &Task = route.tasks.get(1).unwrap();
		let mut task_counter = 1;

		while insert_end_time <= end_bound {

			let travel_time_from_prev = self.cost_matrix.get_time(prev_task.location, job.location);
			let travel_time_to_next = self.cost_matrix.get_time(job.location, next_task.location);

			if prev_task.end_time + travel_time_from_prev <= insert_time &&
				next_task.start_time - travel_time_to_next >= insert_end_time {
				return Some(InsertionData{
					prev_task: *prev_task,
					next_task: *next_task,
					job: *job,
					cost: travel_time_from_prev,
					insertion_time: insert_time,
				});
			}

			insert_time = prev_task.end_time + travel_time_from_prev;
			insert_end_time = insert_time + job.service_time;

			task_counter += 1;

			if let Some(task) = route.tasks.get(task_counter) {
				prev_task = next_task;
				next_task = task;
			}
		}

		return None;
	}
}

pub struct Solution {
	pub cost: i64,
	pub routes: Vec<Route>,
}

pub struct Route {
	pub vehicle_id: i64,
	pub tasks: Vec<Task>,
}

impl Route {

	pub fn new(vehicle_id: i64) -> Route {
		Route {
			vehicle_id,
			tasks: vec![],
		}
	}

}

#[derive(Debug, Copy, Clone)]
struct InsertionData {
	prev_task: Task,
	next_task: Task,
	job: Job,
	cost: i64,
	insertion_time: i64,
}

#[derive(Debug, Copy, Clone)]
pub struct Task {
	pub start_time: i64,
	pub end_time: i64,
	pub location: usize,
	pub task_type: TaskType,
}

#[derive(Debug, Copy, Clone)]
pub enum TaskType {
	JOB(JobTaskData),
	START(),
	END(),
}

#[derive(Debug, Copy, Clone)]
pub struct JobTaskData {
	pub job_id: i64,
}

#[derive(Debug, Copy, Clone)]
pub struct Job {
	id: i64,
	location: usize,
	time_window: TimeWindow,
	service_time: i64,
}

#[derive(Debug, Copy, Clone)]
pub struct TimeWindow {
	start: i64,
	end: i64
}

impl Job {
	pub fn new(id: i64, location: usize, time_window: (i64, i64), service_time: i64) -> Job {
		Job {
			id,
			location,
			time_window: TimeWindow {
				start: time_window.0,
				end: time_window.1,
			},
			service_time
		}
	}
}

pub struct Vehicle {
	id: i64,
	start_location: usize,
	end_location: usize,
	time_window: TimeWindow,
}

impl Vehicle {
	pub fn new(id: i64, start_location: usize, end_location: usize, time_window: (i64, i64)) -> Vehicle {
		Vehicle {
			id,
			start_location,
			end_location,
			time_window: TimeWindow {
				start: time_window.0,
				end: time_window.1,
			}
		}
	}
}

pub struct CostMatrix {
	elements: Vec<Vec<i64>>,
}

impl CostMatrix {
	pub fn new() -> CostMatrix {
		let mut matrix: Vec<Vec<i64>> = vec!();

		for i in 0..100 {
			let mut row = vec!();
			for j in 0..100 {
				if i == j {
					row.push(0);
				} else {
					row.push(j);
				}
			}
			matrix.push(row);
		}

		CostMatrix{
			elements: matrix,
		}
	}

	pub fn get_time(&self, i: usize, j: usize) -> i64 {
		self.elements[i][j]
	}
}