Algorithm-BinarySearch-Vec

 view release on metacpan or  search on metacpan

Vec.pm  view on Meta::CPAN

boolean scalar C<$Algorithm::BinarySearch::Vec::HAVE_XS>.

=cut

##======================================================================
## Data Conventions
=pod

=head2 Data Conventions

All API functions provided by this module assume that the elements of the vec()-style vector arguments
are sorted in strictly ascending order.  The user is responsible for assuring that this is the case,
since no additional checking is done by this module.

=cut

##======================================================================
## Exports
=pod

=head2 Exports

Vec.pm  view on Meta::CPAN

##======================================================================
## API: Search: element-wise
=pod

=head2 Search: element-wise

=over 4

=item 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 (C<vec($v,$i,$nbits)==$key>,
with ($ilo E<lt>= $i E<lt> $ihi)),
or $KEY_NOT_FOUND if no such element exists.

=item 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 L<vbsearch()|vbsearch>.

Returns the maximum index $i such that
C<vec($v,$i,$nbits) E<lt>= $key>
and
C<vec($v,$j,$nbits) E<lt> $key> for all $j with $ilo E<lt>= $j E<lt> $i,
or $KEY_NOT_FOUND if no such $i exists (i.e. if C<vec($v,$ilo,$nbits) E<gt> $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,

Vec.pm  view on Meta::CPAN

   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().


=item 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 L<vbsearch()|vbsearch>.

Returns the minimum index $i such that
C<vec($v,$i,$nbits) E<gt>= $key>
and
C<vec($v,$j,$nbits) E<gt> $key> for all $j with $i E<lt> $j E<lt> $ihi,
or $KEY_NOT_FOUND if no such $i exists (i.e. if C<vec($v,$ihi-1,$nbits) E<lt> $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,

Vec.pm  view on Meta::CPAN

##======================================================================
## API: Search: array-wise
=pod

=head2 Search: array-wise

=over 4

=item 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 L<vbsearch()|vbsearch>.
Returns an ARRAY-ref of indices.
This is equivalent to (but usually much faster than):

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


=item 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 L<vbsearch()|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];

=item 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 L<vbsearch()|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];

=back

=cut

Vec.pm  view on Meta::CPAN

=back

=cut

##======================================================================
## API: Set Opterations
=pod

=head2 Set Operations

The set operations supported by this module assume that the vec()-style vector sets
are sorted in ascending order, contain no duplicates, and are encoded with
C<$nbits E<gt>= 8>; i.e. every element-boundary must lie on a byte-boundary.
The vector-sets returned by these API functions should also conform to these
conventions whenever the parameters do.

=over 4

=item vunion($av,$bv,$nbits)

Computes the union of two sorted vec()-style sets C<$av> and C<$bv>
and returns the result as a sorted vector-set.  Complexity is I<O>(C<$a> + C<$b>)>.

=item vintersect($av,$bv,$nbits)

Computes the intersection of two sorted vec()-style sets C<$av> and C<$bv>
and returns the result as a sorted vector-set.  Complexity is I<O>(C<$A> * log C<$B>),
where C<$A> is the shorter and C<$B> the longer of the argument vectors C<$a> and C<$b>.

=item vsetdiff($av,$bv,$nbits)

Computes the difference of two sorted vec()-style sets C<$av> and C<$bv>
and returns the result as a sorted vector-set.  Complexity is I<O>(C<$A> * log C<$B>),
where C<$A> is the shorter and C<$B> the longer of the argument vectors C<$a> and C<$b>.

=back

=cut

##======================================================================
## Debugging
=pod