Algorithm::BinarySearch::Vec - binary search functions for vec()-vectors with fast XS implementations
use Algorithm::BinarySearch::Vec; ##------------------------------------------------------------- ## Constants my $NOKEY = $Algorithm::BinarySearch::Vec::KEY_NOT_FOUND; my $is_fast = $Algorithm::BinarySearch::Vec::HAVE_XS; ##------------------------------------------------------------- ## Search: element-wise $index = vbsearch ($v,$key,$nbits,$lo,$hi); ##-- match only $index = vbsearch_lb($v,$key,$nbits,$lo,$hi); ##-- lower bound $index = vbsearch_ub($v,$key,$nbits,$lo,$hi); ##-- upper bound ##------------------------------------------------------------- ## Search: array-wise $indices = vabsearch ($v,\@keys,$nbits,$lo,$hi); ##-- match only $indices = vabsearch_lb($v,\@keys,$nbits,$lo,$hi); ##-- lower bound $indices = vabsearch_ub($v,\@keys,$nbits,$lo,$hi); ##-- upper bound ##------------------------------------------------------------- ## Search: vector-wise $ixvec = vvbsearch ($v,$keyvec,$nbits,$lo,$hi); ##-- match only $ixvec = vvbsearch_lb($v,$keyvec,$nbits,$lo,$hi); ##-- lower bound $ixvec = vvbsearch_ub($v,$keyvec,$nbits,$lo,$hi); ##-- upper bound ##------------------------------------------------------------- ## Debugging $val = vget($vec,$i,$nbits); undef = vset($vec,$i,$nbits, $newval); $vals = vec2array($vec,$nbits);
The Algorithm::BinarySearch::Vec perl module provides binary search functions for vec()-vectors, including fast XS implementations in the package Algorithm::BinarySearch::Vec::XS. The XS implementations are used by default if available, otherwise pure-perl fallbacks are provided. You can check whether the XS implementations are available on your system by examining the boolean scalar $Algorithm::BinarySearch::Vec::HAVE_XS.
This module support the following export tags:
Exports all API functions (default).
Exports the following constant(s):
Constant returned by search functions indicating that the requested key was not found, or the requested bound is not within the data vector.
Exports debugging subs for the XS module (vget(), vset()).
Exports everything available.
Binary search for $key in the vec()-style vector $v, which contains elements of $nbits bits each, sorted in ascending order. $ilo and $ihi if specified are indices to limit the search. $ilo defaults to 0, $ihi defaults to (8*$nbits/bytes::length($v)), i.e. the entire vector is to be searched. Returns the index $i of an element in $v matching $key (vec($v,$i,$nbits)==$key, with ($ilo <= $i < $ihi)), or $KEY_NOT_FOUND if no such element exists.
vec($v,$i,$nbits)==$key
Binary search for the lower-bound of $key in the vec()-style vector $v. Arguments are as for vbsearch().
Returns the maximum index $i such that vec($v,$i,$nbits) <= $key and vec($v,$j,$nbits) < $key for all $j with $ilo <= $j < $i, or $KEY_NOT_FOUND if no such $i exists (i.e. if vec($v,$ilo,$nbits) > $key). In other words, returns the least index of a match for $key in $v whenever a match exists, otherwise the greatest index whose value in $v is strictly less than $key if that exists, and $KEY_NOT_FOUND if all values in $v are strictly greater than $key.
vec($v,$i,$nbits) <= $key
vec($v,$j,$nbits) < $key
vec($v,$ilo,$nbits) > $key
This is equivalent to (but usually much faster than):
return $KEY_NOT_FOUND if (vec($v,$ilo,$nbits) > $key); for (my $i=$ilo; $i < $ihi; $i++) { return $i if (vec($v,$i,$nbits) == $key); return $i-1 if (vec($v,$i,$nbits) > $key); } return ($ihi-1);
Note that the semantics of this function differ substantially from the C++ STL function lower_bound().
Binary search for the upper-bound of $key in the vec()-style vector $v. Arguments are as for vbsearch().
Returns the minimum index $i such that vec($v,$i,$nbits) >= $key and vec($v,$j,$nbits) > $key for all $j with $i < $j < $ihi, or $KEY_NOT_FOUND if no such $i exists (i.e. if vec($v,$ihi-1,$nbits) < $key). In other words, returns the greatest index of a match for $key in $v whenever a match exists, otherwise the least index whose value in $v is strictly greater than $key if that exists, and $KEY_NOT_FOUND if all values in $v are strictly less than $key.
vec($v,$i,$nbits) >= $key
vec($v,$j,$nbits) > $key
vec($v,$ihi-1,$nbits) < $key
return $KEY_NOT_FOUND if (vec($v,$ihi-1,$nbits) < $key); for ($i=$ihi-1; $i >= 0; $i--) { return $i if (vec($v,$i,$nbits) == $key) return $i+1 if (vec($v,$i,$nbits) < $key) } return $ilo;
Note that the semantics of this function differ substantially from the C++ STL function upper_bound().
Binary search for each value in the ARRAY-ref \@keys in the vec()-style vector $v. Other arguments are as for vbsearch(). Returns an ARRAY-ref of indices. This is equivalent to (but usually much faster than):
$indices = [map {vbsearch($v,$_,$nbits,$ilo,$ihi)} @keys];
Binary search for the lower-bound of each value in the ARRAY-ref \@keys in the vec()-style vector $v. Other arguments are as for vbsearch(). Returns an ARRAY-ref of indices. This is equivalent to (but usually much faster than):
$indices = [map {vbsearch_lb($v,$_,$nbits,$ilo,$ihi)} @keys];
Binary search for the upper-bound of each value in the ARRAY-ref \@keys in the vec()-style vector $v. Other arguments are as for vbsearch(). Returns an ARRAY-ref of indices. This is equivalent to (but usually much faster than):
$indices = [map {vbsearch_ub($v,$_,$nbits,$ilo,$ihi)} @keys];
Binary search for each key in the key-vector $keyvec in the "haystack"-vector $v. Other arguments are as for vbsearch(). Returns a vec()-vector of 32-bit indices. This is equivalent to (but usually faster than):
$ixvec = pack('N*', @{vabsearch($v,vec2array($keyvec,$nbits),$nbits,$ilo,$ihi)});
Binary lower-bound search for each key in the key-vector $keyvec in the "haystack"-vector $v. Other arguments are as for vbsearch(). Returns a vec()-vector of 32-bit indices. This is equivalent to (but usually faster than):
$ixvec = pack('N*', @{vabsearch_lb($v,vec2array($keyvec,$nbits),$nbits,$ilo,$ihi)});
Binary upper-bound search for each key in the key-vector $keyvec in the "haystack"-vector $v. Other arguments are as for vbsearch(). Returns a vec()-vector of 32-bit indices. This is equivalent to (but usually faster than):
$ixvec = pack('N*', @{vabsearch_ub($v,vec2array($keyvec,$nbits),$nbits,$ilo,$ihi)});
Debugging XS-wrapper equivalent to vec($vec,$i,$nbits).
vec($vec,$i,$nbits)
Debugging XS-wrapper equivalent to vec($vec,$i,$nbits)=$newval.
vec($vec,$i,$nbits)=$newval
Debugging utility, equivalent to
[map {vec($vec,$_,$nbits)} (0..(length($vec)*8/$nbits-1))]
vec() in perlfunc(1), PDL(3perl), perl(1).
Bryan Jurish <moocow@cpan.org>
Copyright (C) 2012 by Bryan Jurish
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.10.1 or, at your option, any later version of Perl 5 you may have available.
To install Algorithm::BinarySearch::Vec, copy and paste the appropriate command in to your terminal.
cpanm
cpanm Algorithm::BinarySearch::Vec
CPAN shell
perl -MCPAN -e shell install Algorithm::BinarySearch::Vec
For more information on module installation, please visit the detailed CPAN module installation guide.