use std::collections::HashSet;
use {Vertex, Edge};

#[derive(Copy, Clone)]
struct Task {
  vertex: Vertex,
  duration: u32
}

static ASCII: [char; 26] = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',
                            'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',
                            'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];

fn vertex_to_duration(v: &Vertex) -> u32 {
  let index = ASCII.iter().position(|a| a == v).expect("Vertex not in list");
  (index + 60 + 1) as u32
}

fn print_vertices(msg: &str, vertices: &Vec<Vertex>) {
  println!("{}", msg);
  print!("[");
  for v in vertices {
    print!("{}, ", &v);
  }
  print!("]\n");
}

fn print_tasks(msg: &str, tasks: &Vec<Task>) {
  println!("{}", msg);
  print!("[");
  for t in tasks {
    print!("({}, {}), ", &t.vertex, &t.duration);
  }
  print!("]\n");
}

pub fn find(V: &HashSet<Vertex>, E: &HashSet<Edge>, V_sources: &HashSet<Vertex>, worker_count: u32) -> u32 {
  let mut done: Vec<Vertex> = Vec::new();
  let mut ready: Vec<Task> = V_sources.iter()
    .map(|&vertex| Task {vertex, duration: vertex_to_duration(&vertex) })
    .collect();
  let mut worked_on: Vec<Task> = Vec::new();

  ready.sort_by(|t1, t2| t1.vertex.cmp(&t2.vertex));
  let mut time: u32 = 0;

  let n = V.len();
  while done.len() != n {
    print_vertices("done: ", &done);
    print_tasks("worked_on: ", &worked_on);
    print_tasks("ready: ", &ready);
    while worked_on.len() < worker_count as usize && ready.len() > 0 {
      let task = ready[0];
      worked_on.push(task);
      ready.remove(0);
    }

    let mut done_on_tick: Vec<Vertex> = Vec::new();
    let mut new_worked_on: Vec<Task> = Vec::new();
    for task in &worked_on {
      let new_duration = task.duration - 1;
      if new_duration == 0 {
        done_on_tick.push(task.vertex);
        done.push(task.vertex);
      } else {
        new_worked_on.push(Task { vertex: task.vertex, duration: new_duration });
      }
    }
    worked_on = new_worked_on;

    for vertex in &done_on_tick {
      let destinations: Vec<Vertex> = E.iter()
        .filter(|&(v1, _v2)| v1 == vertex)
        .map(|&(_v1, v2)| v2)
        .collect();

      for dest_v in &destinations {
        let sources: Vec<Vertex> = E.iter()
          .filter(|&(_v1, v2)| *v2 == *dest_v)
          .map(|&(v1, _v2)| v1)
          .collect();

        let mut ok = true;
        for s in &sources {
          if !done.contains(&s) {
            ok = false;
            break;
          }
        }

        if ok {
          ready.push(Task { vertex: *dest_v, duration: vertex_to_duration(&dest_v) });
        }
      }
    }

    ready.sort_by(|t1, t2| t1.vertex.cmp(&t2.vertex));
    time += 1;
  }

  time
}