blib/lib/Binary/Heap/Search.pm

filter: Statementstmt 94.7% 91 / 96 Branchbran 84.2% 32 / 38 Conditioncond 52.9% 9 / 17 MC/DCmcdc 37.5% 3 / 8 Subroutinesub 94.4% 17 / 18 Podpod 0.0% 0 / 12 totaltotal 80.4% 152 / 189 CC 29 SCAR 16.2
CC
29
Cov
87%
mergeAdjacentArrays
9.4
binarySearch
8.0
add
6.0
CRAP 5.1
↑ Summary
1 #!/usr/bin/perl
2 #-------------------------------------------------------------------------------
3 # Binary search-able heap in 100% Pure Perl
4 # Philip R Brenan at gmail dot com, Appa Apps Ltd, 2017
5 #-------------------------------------------------------------------------------
6  
7 package Binary::Heap::Search;
8 1 require v5.16.0;
9 1 ▶use warnings FATAL => qw(all);
Subroutine BEGIN: called CC=1 SCAR=0.0
10 1 ▶use strict;
Subroutine BEGIN: called CC=1 SCAR=0.0
11 1 ▶use Carp;
Subroutine BEGIN: called CC=1 SCAR=0.0
12 1 ▶use Data::Dump qw(dump);
Subroutine BEGIN: called CC=1 SCAR=0.0
13 1 our $VERSION = 2017.117;
14  
15 1 if (0) # Save to S3:- this will not work, unless you're me, or you happen, to know the key
16 {my $z = 'BinaryHeapSearch.zip';
17 print for qx(zip $z $0 && aws s3 cp $z s3://AppaAppsSourceVersions/$z && rm $z);
18 }
19  
20 #1 Methods
21 sub new($) # Create a new Binary Search-able Heap
22 23 ▶ {my ($compare) = @_; # Sub to perform <=> on two elements of the heap
Subroutine new: called CC=1 SCAR=0.0
Pod undocumented
23 23 return bless {compare=>$compare};
24 }
25  
26 288 ▶sub arrays {$_[0]{arrays} //= []} ## Each array in the heap is in the order created by compare
Subroutine arrays: called CC=2 SCAR=6.9
Pod undocumented
Condition100%2/2
$_[0]{"arrays"} //= []
l!l
26523
MC/DC100%1/1
$_[0]{"arrays"} //= []
$_[0]{"arrays"}
Truth table100%2/2
A
A= $_[0]{"arrays"}
Aresult
11
00
27 265 ▶sub compare {$_[0]{compare}} ## A sub that performs <=>/cmp on any two elements on the heap
Subroutine compare: called CC=1 SCAR=0.0
Pod undocumented
28 0 ▶sub size {scalar @{$_[0]->heaps}} ## Number of arrays in the heap
Subroutine size: not called CC=1 SCAR=6.9
Pod undocumented
29  
30 sub mergeArrays($$$) ## Merge two ordered arrays to make a new ordered array
31 87 ▶ {my ($compare, $b, $c) = @_; # Sub to order elements, first array of elements to be merged, second array of elements to be merged
Subroutine mergeArrays: called CC=5 SCAR=16.3
Pod undocumented
32 87 my @a;
33 87 ▶ while(@$b and @$c) # Sequentially merge the two arrays
Branch: 1 branch
BranchTrueFalseTotal
if (@$b and @$c) 256 87 343
Condition66%2/3
@$b and @$c
!ll&&!rl&&r
087256
MC/DC50%1/2
@$b and @$c
@$b @$c
Truth table66%2/3
A and B
A= @$bB= @$c
ABresult
0X0
100
111
34 256 {my $k = $compare->($$b[0], $$c[0]); # Compare the smallest elements in each array
35 256 ▶ if ($k < 0) {push @a, shift @$b} # Save smallest element
Branch: 2 branches
BranchTrueFalseTotal
if ($k < 0) { } 82 174 256
elsif ($k > 0) { } 174 0 174
36 174 elsif ($k > 0) {push @a, shift @$c}
37 0 else {confess "Duplicate entry ", dump($$b[0])}
38 }
39 87 @a, @$b, @$c # Add remaining un-merged elements, the order does not matter because one of the arrays will be emptied by the preceding merge
40 }
41  
42 sub mergeAdjacentArrays($$$) ## Merge adjacent arrays
43 122 ▶ {my ($arrays, $compare, $start) = @_; # Index of first array to be merged
Subroutine mergeAdjacentArrays: called CC=8 SCAR=22.4
Pod undocumented
44  
45 122 for my $small(reverse 1..$start) # Each array that might be merge-able
46 169 {my $b = $arrays->[$small-1]; # Larger array
47 169 my $c = $arrays->[$small-0]; # Smaller array
48 169 ▶ if ($b and @$b and $c and @$c and @$b <= @$c * 2) # Adjacent arrays are close enough in size to warrant merging
Branch: 1 branch
BranchTrueFalseTotal
if ($b and @$b and $c and @$c and @$b <= @$c * 2) { } 87 82 169
Condition41%5/12
$b and @$b and $c and @$c and @$b <= @$c * 2
!ll&&!rl&&r
08287
$b and @$b and $c and @$c
!ll&&!rl&&r
00169
$b and @$b and $c
!ll&&!rl&&r
00169
$b and @$b
!ll&&!rl&&r
00169
MC/DC20%1/5
$b and @$b and $c and @$c and @$b <= @$c * 2
$b @$b $c @$c @$b <= @$c * 2
Truth table33%2/6
A and B and C and D and E
A= $bB= @$bC= $cD= @$cE= @$b <= @$c * 2
ABCDEresult
0XXXX0
10XXX0
110XX0
1110X0
111100
111111
49 87 {$arrays->[$small-1] = [mergeArrays($compare, $b, $c)];
50 }
51 else # Adjacent arrays are to different in size to be worth merging
52 82 ▶ {splice @$arrays, $small+1, $start-$small if $small != $start; # Remove previously merged arrays - this inefficient operation is done just once on a small array
Branch: 1 branch
BranchTrueFalseTotal
if $small != $start 24 58 82
53 return
54 82 }
55 }
56 40 $#$arrays = 0; # All the arrays have been merged into just one array
57 }
58  
59 sub add($$) # Add an element to the heap of ordered arrays
60 203 ▶ {my ($heap, $element) = @_; # Heap, element (that can be ordered by compare)
Subroutine add: called CC=6 SCAR=18.0
Pod undocumented
61 203 my $compare = $heap->compare;
62 203 my $arrays = $heap->arrays;
63  
64 203 for my $arrayIndex(0..$#$arrays) # Try to put the element on top of one of the existing arrays starting at the largest one. We could of course just add the new element as a single array at the end and then merge up through all the arrays, doing so would avoid the splice operation in merge() but seems to produce longer sequences of arrays than the technique used which is to find the first viable array.
65 276 {my $array = $arrays->[$arrayIndex];
66 276 my $c = $compare->($element, $array->[-1]); # Compare the element to be added to the topmost element of the current array
67 276 ▶ if ($c == 1) # The element to be added is greater than the largest element in the current array
Branch: 2 branches
BranchTrueFalseTotal
if ($c == 1) { } 85 191 276
elsif ($c == 0) { } 0 191 191
68 85 {push @$array, $element; # Add the element to the top of this array
69 85 ▶ mergeAdjacentArrays($arrays, $compare, $arrayIndex) if $arrayIndex; # Merge two adjacent arrays if they are close enough in size
Branch: 1 branch
BranchTrueFalseTotal
if $arrayIndex 27 58 85
70 85 return;
71 }
72 elsif ($c == 0) # Duplicate element detected
73 0 {confess "Duplicate element ", dump($element);
74 }
75 }
76 118 push @$arrays, [$element]; # Cannot put element on top of any array in the heap so create a new array
77 118 ▶ mergeAdjacentArrays($arrays, $compare, $#$arrays) if $#$arrays; # Try to merge the newest array if there is an existing array into which to merge it
Branch: 1 branch
BranchTrueFalseTotal
if $arrays->$#* 95 23 118
78 }
79  
80 sub binarySearch($$$) ## Find an element in an array using binary search
81 67 ▶ {my ($array, $compare, $element) = @_; # Array, element
Subroutine binarySearch: called CC=8 SCAR=20.8
Pod undocumented
82 67 my $m = 0; # Check the lower bound of the array
83 67 my $e = $array->[$m]; # Lowest element in the array
84 67 my $c = $compare->($element, $e); # Compare with lowest element in the array
85 67 ▶ return $e if $c == 0; # Equal to the lowest element
Branch: 1 branch
BranchTrueFalseTotal
if $c == 0 2 65 67
86 65 ▶ return undef unless $c == 1; # Lower than any element in the array
Branch: 1 branch
BranchTrueFalseTotal
unless $c == 1 0 65 65
87 65 my $M = $#$array; # Check the upper bound of the array
88 65 my $E = $array->[$M]; # Highest element in the array
89 65 my $C = $compare->($element, $E); # Compare with highest element in the array
90 65 ▶ return $E if $C == 0; # Equal to the highest element
Branch: 1 branch
BranchTrueFalseTotal
if $C == 0 2 63 65
91 63 ▶ return undef if $C == 1; # Lower than any element in the array
Branch: 1 branch
BranchTrueFalseTotal
if $C == 1 0 63 63
92  
93 63 ▶ while($m+1 < $M) # Narrow the zone
Branch: 1 branch
BranchTrueFalseTotal
if ($m + 1 < $M) 308 5 313
94 308 {my $i = int(($m+$M)/2); # Index of a point halfway between
95 308 my $e = $array->[$i]; # Element at mid point
96 308 my $c = $compare->($element, $e); # Compare
97 308 ▶ return $e if $c == 0; # Found
Branch: 1 branch
BranchTrueFalseTotal
if $c == 0 58 250 308
98 250 ▶ ($c == 1 ? $m : $M) = $i;
Branch: 1 branch
BranchTrueFalseTotal
$c == 1 ? : 128 122 250
99 } # Continue to narrow the range
100 undef # Not found
101 5 }
102  
103 sub find($$) # Find an element in the heap
104 62 ▶ {my ($heap, $element) = @_; # Heap, element (that can be ordered by compare)
Subroutine find: called CC=3 SCAR=11.0
Pod undocumented
105 62 my $compare = $heap->compare;
106 62 my $arrays = $heap->arrays;
107  
108 62 for my $array(@$arrays) # Use a binary search on each array in the heap
109 67 {my $e = binarySearch($array, $compare, $element);
110 67 ▶ return $e if defined $e # Return matching element
Branch: 1 branch
BranchTrueFalseTotal
if defined $e 62 5 67
111 }
112 undef # Element not found
113 0 }
114  
115 # Test
116 1 ▶sub test{eval join('', <Binary::Heap::Search::DATA>) or die $@}
Subroutine BEGIN: called CC=1 SCAR=0.0
Subroutine BEGIN: called CC=1 SCAR=0.0
Subroutine dumpHeap: called CC=1 SCAR=0.0
Subroutine newHeap: called CC=2 SCAR=6.9
Subroutine test: called CC=2 SCAR=6.9
Pod undocumented
Pod undocumented
Pod undocumented
Branch: 1 branch
BranchTrueFalseTotal
eval join("", readline DATA) or die $@ 1 0 1
117  
118 1 ▶test unless caller;
Branch: 1 branch
BranchTrueFalseTotal
unless caller 0 1 1
119  
120 # Documentation
121 #extractDocumentation() unless caller; # Extract the documentation
122  
123 1 1;
124  
125 =encoding utf-8
126  
127 =head1 Name
128  
129 Binary::Heap::Search - Binary search-able heap in 100% Pure Perl
130  
131 =head1 Synopsis
132  
133 =head1 Installation
134  
135 This module is written in 100% Pure Perl and is thus easy to read, modify and
136 install.
137  
138 Standard Module::Build process for building and installing modules:
139  
140 perl Build.PL
141 ./Build
142 ./Build test
143 ./Build install
144  
145 =head1 Author
146  
147 philiprbrenan@gmail.com
148  
149 http://www.appaapps.com
150  
151 =head1 Copyright
152  
153 Copyright (c) 2017 Philip R Brenan.
154  
155 This module is free software. It may be used, redistributed and/or modified
156 under the same terms as Perl itself.
157  
158 =cut
159  
160 __DATA__
↑ Summary