File Coverage

blib/lib/GenOO/Module/Search/Binary.pm
Criterion Covered Total %
statement 25 25 100.0
branch 9 10 90.0
condition 4 6 66.6
subroutine 2 2 100.0
pod 0 1 0.0
total 40 44 90.9


line stmt bran cond sub pod time code
1             # POD documentation - main docs before the code
2              
3             =head1 NAME
4              
5             GenOO::Module::Search::Binary - Module that offers methods for searching in an array using binary search
6              
7             =head1 SYNOPSIS
8              
9             use GenOO::Module::Search::Binary
10             my $pos = GenOO::Module::Search::Binary->binary_search_for_value_greater_or_equal(3.2, [0,1,2,3,4,4,4,5,6], sub {return $_[0]});
11              
12              
13             =head1 DESCRIPTION
14              
15             Implements binary search algorithms for scanning an array.
16            
17             =cut
18              
19             # Let the code begin...
20              
21             package GenOO::Module::Search::Binary;
22             $GenOO::Module::Search::Binary::VERSION = '1.5.1';
23              
24             #######################################################################
25             ####################### Load External modules #####################
26             #######################################################################
27 1     1   5 use Modern::Perl;
  1         2  
  1         8  
28              
29              
30             #######################################################################
31             ####################### Interface Functions #######################
32             #######################################################################
33             =head2 binary_search_for_value_greater_or_equal
34             Arg [1] : number. The target value
35             Arg [2] : array reference. Array in which the target value is searched.
36             No assumption is made about the entries in the array and how to extract the actual values from them.
37             The array must be sorted by value though.
38             Arg [3] : code reference. Code that extracts the actual value given an entry of the array
39             Example : binary_search_for_value_greater_or_equal(3.2, [0,1,2,3,4,4,4,5,6], sub {return $_[0]})
40             Description: Implements a binary search algorithm returning the I<position> of the first I<entry>
41             whose I<value> is greater than or equal to C<target value>. The search routine does
42             not make any assumption about the entries in the array, but leaves the implementation
43             to the user supplied code function.
44             During the search the user supplied code function will be called with a single arguments:
45             an entry of the array and should return the value that corresponds to this entry.
46             Return : Integer index of the first entry whose value is greater or equal to the target value
47             =cut
48             sub binary_search_for_value_greater_or_equal {
49 30     30 0 7852 my ($class, $target_value, $sorted_array, $code) = @_;
50            
51 30         31 my $index;
52 30         34 my $low_index = 0;
53 30         31 my $up_index = $#{$sorted_array};
  30         39  
54            
55 30         85 while ($low_index <= $up_index) {
56            
57 65         109 $index = int(($low_index + $up_index) / 2);
58            
59 65 100       138 if ($code->($sorted_array->[$index]) < $target_value) {
    100          
60 26         116 $low_index = $index+1; # move to the up half
61             }
62             elsif ($code->($sorted_array->[$index]) > $target_value) {
63 25         203 $up_index = $index-1; # move to the low half
64             }
65             else {
66             # exact match found -> search upstream for the first of the exact matches
67 14   100     113 while (($index-1 >= 0) and ($code->($sorted_array->[$index-1]) == $target_value)) {
68 3         26 $index--;
69             }
70 14         42 last;
71             }
72            
73             }
74            
75             # check if got outside the array without finding a bigger value than the one requested
76 30 100       32 if ($low_index > $#{$sorted_array}) {
  30         73  
77 5         32 return undef;
78             }
79            
80             # under certain conditions index might point to the value immediatelly preceding the greater value
81 25 100       52 if ($code->($sorted_array->[$index]) < $target_value) {
82 3 50 33     15 if (($index+1 <= $#{$sorted_array}) and ($code->($sorted_array->[$index+1]) > $target_value)) {
  3         23  
83 3         19 $index++;
84             }
85 3         17 return $index;
86             }
87            
88 22         163 return $index;
89             }
90              
91             1;