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
|
#!/bin/env perl6
class task {
has UInt $.priority;
has Str $.id;
}
class PriorityQueue {
has UInt @!priorities; # keep sorted
has %!queue{ UInt }; # UInt => task array
submethod BUILD() {
@!priorities = ();
%!queue = %();
}
method is_empty(--> Bool) { %!queue.elems == 0 }
method add-new-task(UInt:D $priority, task:D $task) {
my UInt $start = 0;
my UInt $end = max(0, @!priorities.elems - 1);
while ($end - $start > 1) {
my UInt $index = ($start + $end) / 2;
if $priority < @!priorities[$index] {
$start = $index;
} elsif $priority > @!priorities[$index] {
$end = $index;
} else { # $priority == @!priorities[$index]
%!queue{ $priority }.push($task);
}
}
put("end - start should be 0 or 1: { $end - $start }");
@!priorities.splice($start, 0, [$priority]);
%!queue{ $priority } = [$task];
}
method insert-with-priority(UInt:D $priority, Str:D $task-id) {
my $new-task = task.new(priority => $priority, id => $task-id);
self.add-new-task($priority, $new-task);
}
method pull-highest-priority-element() {
return Nil if %!queue.elems == 0;
my $t = %!queue{ @!priorities[0] }.pop;
if %!queue{ @!priorities[0] }.elems == 0 {
%!queue{ @!priorities[0] }:delete;
@!priorities.pop;
}
return $t;
}
method elems { [@!priorities.elems, %!queue.elems] }
}
use Test;
plan 5;
my PriorityQueue $que = PriorityQueue.new;
is True, $que.is_empty, 'default queue is empty';
$que.insert-with-priority(3, 'task one');
is [1, 1], $que.elems, 'task queue length is 1 after 1 insertion';
my $t = $que.pull-highest-priority-element;
is 3, $t.priority, 'task priority is 3';
is 'task one', $t.id, 'task is correct';
is [0, 0], $que.elems, 'task queue length is 0 after element is pulled';
|
