1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
|
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
}
|
