blob: 4f79fbf7c4a82d8aa01f4f85b94573dc750ed5a7 (
plain)
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
111
112
113
114
115
116
117
118
119
120
|
use v6d;
###############################################################################
=begin comment
Perl Weekly Challenge 096, Task #2: Edit Distance
Matrix class for use in implementing the Wagner–Fischer algorithm for finding
the Levenshtein distance between two strings.
=end comment
###############################################################################
#--------------------------------------#
# Copyright © 2021 PerlMonk Athanasius #
#--------------------------------------#
#==============================================================================
unit class Matrix;
#==============================================================================
#------------------------------------------------------------------------------
# Matrix attributes
#------------------------------------------------------------------------------
has UInt $.height;
has UInt $.width;
has Array[Str] @!matrix;
#------------------------------------------------------------------------------
submethod BUILD( Str:D :$S1, Str:D :$S2 )
#------------------------------------------------------------------------------
{
$!width = $S1.chars + 1;
$!height = $S2.chars + 1;
for 0 .. $!height -> UInt $row
{
@!matrix[$row ] = Array[Str].new;
@!matrix[$row; $_] = Nil for 0 .. $!width;
}
my Str $word2 = "#$S2";
my $i = 0;
for 1 .. $!height -> UInt $row
{
@!matrix[$row; 0] = $word2.substr: $i, 1;
@!matrix[$row; 1] = "$i";
++$i;
}
my Str $word1 = "#$S1";
$i = 0;
for 1 .. $!width -> UInt $col
{
@!matrix[0; $col] = $word1.substr: $i, 1;
@!matrix[1; $col] = "$i";
++$i;
}
}
#------------------------------------------------------------------------------
method element( UInt:D $row, UInt:D $col, UInt $value? --> UInt:D ) # Accessor
#------------------------------------------------------------------------------
{
if $value.defined
{
@!matrix[$row + 1; $col + 1] = "$value"; # Set
}
return @!matrix[$row + 1; $col + 1].UInt; # Get
}
#------------------------------------------------------------------------------
method display
#------------------------------------------------------------------------------
{
# Pre-compute the maximum widths of individual columns
my UInt @widths = 1;
for 1 .. $!width -> UInt $col
{
my UInt $max = 0;
for 1 .. $!height -> UInt $row
{
my Str $current = @!matrix[$row; $col];
my UInt $cur-len = $current.chars;
$max = $cur-len if $cur-len > $max;
}
@widths[ $col ] = $max;
}
# Draw a vertical separator
my Str $line = '+';
$line ~= '-%s-+'.sprintf: '-' x @widths[ $_ ] for 0 .. $!width;
$line ~= "\n";
# Draw the matrix
my Str $display = $line;
for 0 .. $!height -> UInt $row
{
$display ~= '|';
$display ~= ' %*s |'.sprintf: @widths[ $_ ], @!matrix[$row; $_] // ' '
for 0 .. $!width;
$display ~= "\n" ~ $line;
}
return $display;
}
##############################################################################
|
