| 1 | ########################################### | ||||||||||||||||||||||||||||
| 2 | package Path::Ancestor; | ||||||||||||||||||||||||||||
| 3 | ########################################### | ||||||||||||||||||||||||||||
| 4 | 1 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 5 | 1 | ▶ | use warnings; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 6 | 1 | ▶ | use List::Util qw(min max); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 7 | |||||||||||||||||||||||||||||
| 8 | 1 | require Exporter; | |||||||||||||||||||||||||||
| 9 | 1 | our @ISA = qw(Exporter); | |||||||||||||||||||||||||||
| 10 | 1 | our @EXPORT_OK = qw(longest_common_ancestor); | |||||||||||||||||||||||||||
| 11 | |||||||||||||||||||||||||||||
| 12 | 1 | our $VERSION = "0.01"; | |||||||||||||||||||||||||||
| 13 | |||||||||||||||||||||||||||||
| 14 | ########################################### | ||||||||||||||||||||||||||||
| 15 | 33 | ▶ | sub longest_common_ancestor { | ||||||||||||||||||||||||||
|
Subroutine
longest_common_ancestor: called CC=17 SCAR=28.3
Pod
undocumented
| |||||||||||||||||||||||||||||
| 16 | ########################################### | ||||||||||||||||||||||||||||
| 17 | 33 | my $paths = []; | |||||||||||||||||||||||||||
| 18 | |||||||||||||||||||||||||||||
| 19 | # Just one path? Simply return it. | ||||||||||||||||||||||||||||
| 20 | 33 | ▶ | return $_[0] if @_ == 1; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||
| 22 | # Transform all paths to arrays | ||||||||||||||||||||||||||||
| 23 | 31 | for ( @_ ) { | |||||||||||||||||||||||||||
| 24 | 71 | push @$paths, [split //, $_]; | |||||||||||||||||||||||||||
| 25 | } | ||||||||||||||||||||||||||||
| 26 | |||||||||||||||||||||||||||||
| 27 | 31 | my $minlen = min map { scalar @$_ } @$paths; | |||||||||||||||||||||||||||
| 28 | 31 | my $maxlen = max map { scalar @$_ } @$paths; | |||||||||||||||||||||||||||
| 29 | 31 | my $last_match = -1; | |||||||||||||||||||||||||||
| 30 | 31 | my $last_slash_idx = -1; | |||||||||||||||||||||||||||
| 31 | |||||||||||||||||||||||||||||
| 32 | # Examine all characters left-to-right | ||||||||||||||||||||||||||||
| 33 | 31 | MATCH: for my $i (0..$minlen-1) { | |||||||||||||||||||||||||||
| 34 | |||||||||||||||||||||||||||||
| 35 | # Get the Nth character of the first path | ||||||||||||||||||||||||||||
| 36 | 154 | my $ref = $paths->[0]->[ $i ]; | |||||||||||||||||||||||||||
| 37 | 154 | ▶ | if( $ref eq "/" ){ | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 38 | 40 | $last_slash_idx = $i; | |||||||||||||||||||||||||||
| 39 | } | ||||||||||||||||||||||||||||
| 40 | |||||||||||||||||||||||||||||
| 41 | # ... and compare what all other paths have at this location | ||||||||||||||||||||||||||||
| 42 | 154 | for my $path_idx ( 1 .. $#$paths ) { | |||||||||||||||||||||||||||
| 43 | 204 | ▶ | if( $paths->[ $path_idx ]->[ $i ] ne $ref ) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 44 | 9 | last MATCH; | |||||||||||||||||||||||||||
| 45 | } | ||||||||||||||||||||||||||||
| 46 | 195 | $last_match = $i; | |||||||||||||||||||||||||||
| 47 | } | ||||||||||||||||||||||||||||
| 48 | } | ||||||||||||||||||||||||||||
| 49 | |||||||||||||||||||||||||||||
| 50 | # Here's an edge case: If we have "/foo", "/foo/bar", "/foo/moo/moo", | ||||||||||||||||||||||||||||
| 51 | # we need to verify that "/foo" is a *complete* path with all other | ||||||||||||||||||||||||||||
| 52 | # paths. | ||||||||||||||||||||||||||||
| 53 | 31 | my $is_complete_path = 1; | |||||||||||||||||||||||||||
| 54 | 31 | for ( @$paths ) { | |||||||||||||||||||||||||||
| 55 | 50 | ▶ | if(exists $_->[ $last_match+1 ] and | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
exists $$_[$last_match + 1] and $$_[$last_match + 1] ne "/"
MC/DC100%2/2
exists $$_[$last_match + 1] and $$_[$last_match + 1] ne "/"
exists $$_[$last_match + 1]
$$_[$last_match + 1] ne "/"
Truth table100%3/3
A and B
A= exists $$_[$last_match + 1]B= $$_[$last_match + 1] ne "/"
| |||||||||||||||||||||||||||||
| 56 | $_->[ $last_match+1 ] ne "/") { | ||||||||||||||||||||||||||||
| 57 | 20 | $is_complete_path = 0; | |||||||||||||||||||||||||||
| 58 | 20 | last; | |||||||||||||||||||||||||||
| 59 | } | ||||||||||||||||||||||||||||
| 60 | } | ||||||||||||||||||||||||||||
| 61 | |||||||||||||||||||||||||||||
| 62 | # Remove only trailing slashes | ||||||||||||||||||||||||||||
| 63 | 31 | ▶ | while($last_match > 0 and | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$last_match > 0 and $paths->[0][$last_match] eq "/"
MC/DC100%2/2
$last_match > 0 and $paths->[0][$last_match] eq "/"
$last_match > 0
$paths->[0][$last_match] eq "/"
Truth table100%3/3
A and B
A= $last_match > 0B= $paths->[0][$last_match] eq "/"
| |||||||||||||||||||||||||||||
| 64 | $paths->[0]->[ $last_match ] eq "/") { | ||||||||||||||||||||||||||||
| 65 | 5 | $last_match--; | |||||||||||||||||||||||||||
| 66 | } | ||||||||||||||||||||||||||||
| 67 | |||||||||||||||||||||||||||||
| 68 | # What if we didn't match all the way to the end? | ||||||||||||||||||||||||||||
| 69 | 31 | ▶ | if( $last_match+1 ne $maxlen and !$is_complete_path) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition100%3/3
$last_match + 1 ne $maxlen and not $is_complete_path
MC/DC100%2/2
$last_match + 1 ne $maxlen and not $is_complete_path
$last_match + 1 ne $maxlen
not $is_complete_path
Truth table100%3/3
A and not(B)
A= $last_match + 1 ne $maxlenB= not $is_complete_path
| |||||||||||||||||||||||||||||
| 70 | # Not a complete path, go back | ||||||||||||||||||||||||||||
| 71 | |||||||||||||||||||||||||||||
| 72 | 20 | ▶ | if($last_slash_idx < 0) { | ||||||||||||||||||||||||||
|
Branch: 2 branches
| |||||||||||||||||||||||||||||
| 73 | # We don't have a slash to go back to => empty match | ||||||||||||||||||||||||||||
| 74 | 5 | $last_match = -1; | |||||||||||||||||||||||||||
| 75 | ▶ | } elsif($last_slash_idx == 0 and $paths->[0]->[0] eq "/") { | |||||||||||||||||||||||||||
|
Condition66%2/3
$last_slash_idx == 0 and $paths->[0][0] eq "/"
MC/DC50%1/2
$last_slash_idx == 0 and $paths->[0][0] eq "/"
$last_slash_idx == 0
$paths->[0][0] eq "/"
Truth table66%2/3
A and B
A= $last_slash_idx == 0B= $paths->[0][0] eq "/"
| |||||||||||||||||||||||||||||
| 76 | # leave the slash in if "/" is the longest common path | ||||||||||||||||||||||||||||
| 77 | 4 | $last_match = 0; | |||||||||||||||||||||||||||
| 78 | } else { | ||||||||||||||||||||||||||||
| 79 | # up until (excluding) the last matching slash | ||||||||||||||||||||||||||||
| 80 | 11 | $last_match = $last_slash_idx - 1; | |||||||||||||||||||||||||||
| 81 | } | ||||||||||||||||||||||||||||
| 82 | } | ||||||||||||||||||||||||||||
| 83 | |||||||||||||||||||||||||||||
| 84 | 31 | return substr $_[0], 0, $last_match+1; | |||||||||||||||||||||||||||
| 85 | } | ||||||||||||||||||||||||||||
| 86 | |||||||||||||||||||||||||||||
| 87 | 1 | 1; | |||||||||||||||||||||||||||
| 88 | |||||||||||||||||||||||||||||
| 89 | __END__ | ||||||||||||||||||||||||||||