-
Notifications
You must be signed in to change notification settings - Fork 131
/
Hash.nqp
65 lines (58 loc) · 1.85 KB
/
Hash.nqp
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
sub hash(*%new) {
%new
}
# Usually only a small number of keys are seen,
# so a bubble sort would be fine. However, the
# number can get much larger (e.g., when profiling
# a build of the Rakudo settings), so use a heapsort
# instead. Note that this sorts in **reverse** order.
sub sorted_keys($hash) {
my @keys := nqp::list_s();
my $iter := nqp::iterator($hash);
nqp::while(
$iter,
nqp::push_s(@keys,nqp::iterkey_s(nqp::shift($iter)))
);
sub sift_down(@a, int $start, int $end) {
my int $root := $start;
my int $child;
my int $swap;
while 2*$root + 1 <= $end {
$child := 2*$root + 1;
$swap := $root;
if nqp::atpos_s(@a, $swap) gt nqp::atpos_s(@a, $child) {
$swap := $child;
}
if $child + 1 <= $end && nqp::atpos_s(@a, $swap) ge nqp::atpos_s(@a, $child + 1) {
$swap := $child + 1;
}
if $swap == $root {
return;
} else {
my str $tmp := nqp::atpos_s(@a, $root);
nqp::bindpos_s(@a, $root, nqp::atpos_s(@a, $swap));
nqp::bindpos_s(@a, $swap, $tmp);
$root := $swap;
}
}
}
my int $count := +@keys;
if $count > 2 {
my int $start := $count / 2;
my int $end := $count - 1;
while --$start >= 0 {
sift_down(@keys, $start, $end);
}
while $end > 0 {
my str $swap := nqp::atpos_s(@keys, $end);
nqp::bindpos_s(@keys, $end, nqp::atpos_s(@keys, 0));
nqp::bindpos_s(@keys, 0, $swap);
$end := $end - 1;
sift_down(@keys, 0, $end);
}
}
elsif $count == 2 && nqp::atpos_s(@keys, 0) lt nqp::atpos_s(@keys, 1) {
nqp::push_s(@keys, nqp::shift_s(@keys));
}
@keys
}