/ 
Algorithm-BinarySearch-Vec-0.01
River stage one • 2 direct dependents • 4 total dependents
/ Algorithm::BinarySearch::Vec

NAME

Algorithm::BinarySearch::Vec - binary search functions for vec()-vectors with fast XS implementations

SYNOPSIS

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

DESCRIPTION

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.

Exports

This module support the following export tags:

:api

Exports all API functions (default).

:const

Exports constant(s):

$KEY_NOT_FOUND

Constant returned by search functions indicating that the requested key was not found, or the requested bound is not within the data vector.

:debug

Exports debugging subs for the XS module (vget(), vset()).

:all

Exports everything available.

Search: element-wise

vbsearch($v,$key,$nbits,?$ilo,?$ihi)

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.

vbsearch_lb($v,$key,$nbits,?$ilo,?$ihi)

Binary search for the lower-bound of $key in the vec()-style vector $v. Arguments are as for vbsearch().

Returns the least index $i with vec($v,$i,$nbits) == $key if it exists, otherwise returns the greatest index $i with vec($v,$i,$nbits) < $key, or $KEY_NOT_FOUND if no such $i exists (i.e. if vec($v,0,$nbits) > $key).

This is equivalent to (but usually much faster than):

return $KEY_NOT_FOUND if (vec($v,0,$nbits)>$key);
for (my $i=0; $i < $ihi; $i++) {
  return $i-1 if (vec($v,$i,$nbits) >  $key)
  return $i   if (vec($v,$i,$nbits) == $key)
}
return ($ihi-1);

Note that the semantics of this function differ somewhat from the C++ STL function lower_bound().

vbsearch_ub($v,$key,$nbits,?$ilo,?$ihi)

Binary search for the upper-bound of $key in the vec()-style vector $v. Arguments are as for vbsearch().

Returns the greatest index $i with vec($v,$i,$nbits) == $key if it exists, otherwise returns the least index $i with vec($v,$i,$nbits) > $key, or $ihi if no such $i exists (i.e. if vec($v,$ihi-1,$nbits) < $key).

This is equivalent to (but usually much faster than):

for ($i=$ihi-1; $i >= 0; $i--) {
  return $i+1 if (vec($v,$i,$nbits) <  $key)
  return $i   if (vec($v,$i,$nbits) == $key)
}
return $ihi;

Note that the semantics of this function differ somewhat from the C++ STL function upper_bound().

Search: array-wise

vabsearch($v,\@keys,$nbits,?$ilo,?$ihi)

Binary search for each value in the ARRAY-ref \@keys in the vec()-style vector $v. Other arguments are as for vbsearch(). This is equivalent to (but usually much faster than):

$indices = [map {vbsearch($v,$_,$nbits,$ilo,$ihi)} @keys];

vabsearch_lb($v,\@keys,$nbits,?$ilo,?$ihi)

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(). This is equivalent to (but usually much faster than):

$indices = [map {vbsearch_lb($v,$_,$nbits,$ilo,$ihi)} @keys];

vabsearch_ub($v,\@keys,$nbits,?$ilo,?$ihi)

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(). This is equivalent to (but usually much faster than):

$indices = [map {vbsearch_ub($v,$_,$nbits,$ilo,$ihi)} @keys];

SEE ALSO

vec() in perlfunc(1), PDL(3perl), perl(1).

AUTHOR

Bryan Jurish <moocow@cpan.org>

COPYRIGHT AND LICENSE

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.