-
Notifications
You must be signed in to change notification settings - Fork 1
/
move_to_front_mtf2.pl
114 lines (89 loc) · 1.98 KB
/
move_to_front_mtf2.pl
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
103
104
105
106
107
108
109
110
#!/usr/bin/env perl
# MTF-1
use strict;
use warnings;
use Perl6::Say;
use constant UCHAR_MAX => 0x100;
sub del (\@$) {
my ($array, $i) = @_;
if ($i > @$array - 1) {
return;
}
my $value = $array->[$i];
my $len = @$array;
for (my $j = $i; $j < $len; $j++) {
$array->[$j] = $array->[$j + 1];
}
pop @$array;
return $value;
}
sub index_of (\@$) {
my ($array, $c) = @_;
for (my $i = 0; $i < @$array; $i++) {
if ($array->[$i] == $c) {
return $i;
}
}
}
sub insert_to_2nd (\@$) {
my ($array, $c) = @_;
my $first = pop @$array;
unshift @$array, $first, $c;
}
sub mtf_encode ($) {
my $str = shift;
my @in = unpack('C*', $str);
my $prev = 1;
my @table;
for (my $i = 0; $i < UCHAR_MAX; $i++) {
$table[$i] = $i;
}
for (my $x = 0; $x < @in; $x++) {
my $c = $in[$x];
my $i = index_of @table, $c;
if ($i == 1) {
if ($prev != 0) {
$table[1] = $table[0];
$table[0] = $c;
}
} elsif ($i > 1) {
del @table, $i;
insert_to_2nd @table, $c;
}
$in[$x] = $i;
$prev = $i;
}
return \@in;
}
sub mtf_decode ($) {
my $in = shift;
my $prev = 1;
my @table;
for (my $i = 0; $i < UCHAR_MAX; $i++) {
$table[$i] = $i;
}
for (my $x = 0; $x < @$in; $x++) {
my $i = $in->[$x];
my $c = $table[$i];
if ($i == 1) {
if ($prev != 0) {
$table[1] = $table[0];
$table[0] = $c;
}
} elsif ($i > 1) {
del @table, $i;
insert_to_2nd @table, $c;
}
$in->[$x] = $c;
$prev = $i;
}
return join '', map { chr } @$in;
}
package main;
# my $str = shift or die "usage: $0 <string>";
while (<>) {
my $enc = mtf_encode $_;
say join ' ', @$enc;
say "in : ", $_;
say "out: ", mtf_decode $enc;
}