Algorithm-BinarySearch-Vec

 view release on metacpan or  search on metacpan

Vec.pm  view on Meta::CPAN

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

##--------------------------------------------------------------
## $index = vbsearch($v,$key,$nbits)
## $index = vbsearch($v,$key,$nbits,$ilo,$ihi)
sub _vbsearch {
  my ($vr,$key,$nbits,$ilo,$ihi) = (\$_[0],@_[1..$#_]);
  $ilo = 0 if (!defined($ilo));
  $ihi = 8*length($$vr)/$nbits if (!defined($ihi));
  my ($imid);
  while ($ilo < $ihi) {
    $imid = ($ihi+$ilo) >> 1;
    if (vec($$vr,$imid,$nbits) < $key) {
      $ilo = $imid + 1;
    } else {
      $ihi = $imid;
    }
  }
  return ($ilo==$ihi) && vec($$vr,$ilo,$nbits)==$key ? $ilo : $KEY_NOT_FOUND;
}

##--------------------------------------------------------------
## $index = vbsearch_lb($v,$key,$nbits)
## $index = vbsearch_lb($v,$key,$nbits,$ilo,$ihi)
sub _vbsearch_lb {
  my ($vr,$key,$nbits,$ilo,$ihi) = (\$_[0],@_[1..$#_]);
  $ilo = 0 if (!defined($ilo));
  $ihi = 8*length($$vr)/$nbits if (!defined($ihi));
  my ($imin,$imax,$imid) = ($ilo,$ihi);
  while ($ihi-$ilo > 1) {
    $imid = ($ihi+$ilo) >> 1;
    if (vec($$vr,$imid,$nbits) < $key) {
      $ilo = $imid;
    } else {
      $ihi = $imid;
    }
  }
  return $ilo if (                vec($$vr,$ilo,$nbits)==$key);

Vec.pm  view on Meta::CPAN

  return $ilo if ($ilo > $imin || vec($$vr,$ilo,$nbits) <$key);
  return $KEY_NOT_FOUND;
}

##--------------------------------------------------------------
## $index = vbsearch_ub($v,$key,$nbits)
## $index = vbsearch_ub($v,$key,$nbits,$ilo,$ihi)
sub _vbsearch_ub {
  my ($vr,$key,$nbits,$ilo,$ihi) = (\$_[0],@_[1..$#_]);
  $ilo = 0 if (!defined($ilo));
  $ihi = 8*length($$vr)/$nbits if (!defined($ihi));
  my ($imin,$imax,$imid) = ($ilo,$ihi);
  while ($ihi-$ilo > 1) {
    $imid = ($ihi+$ilo) >> 1;
    if (vec($$vr,$imid,$nbits) > $key) {
      $ihi = $imid;
    } else {
      $ilo = $imid;
    }
  }
  return $ihi if ($ihi < $imax && vec($$vr,$ihi,$nbits)==$key);

Vec.pm  view on Meta::CPAN

## \@indices = vabsearch_ub($v,\@keys,$nbits,$ilo,$ihi)
sub _vabsearch_ub {
  return [map {vbsearch_ub($_[0],$_,@_[2..$#_])} @{$_[1]}];
}

##======================================================================
## API: Search: vec-wise

## \@a = vec2array($vec,$nbits)
sub vec2array {
  return [map {vec($_[0],$_,$_[1])} (0..(length($_[0])*8/$_[1]-1))];
}

##--------------------------------------------------------------
## $indices = vvbsearch($v,$keys,$nbits)
## $indices = vvbsearch($v,$keys,$nbits,$ilo,$ihi)
sub _vvbsearch {
  return pack('N*', @{vabsearch($_[0],vec2array(@_[1,2]),@_[2..$#_])});
}

##--------------------------------------------------------------

Vec.pm  view on Meta::CPAN

}

##======================================================================
## API: set operations

##--------------------------------------------------------------
## $vunion = vunion($av,$bv,$nbits)
sub _vunion {
  my ($avr,$bvr,$nbits) = (\$_[0],\$_[1],$_[2]);
  die(__PACKAGE__ , "::_vunion(): cannot handle nbits < 8, but you requested $nbits") if ($nbits < 8);
  my $na = length($$avr)*8/$nbits;
  my $nb = length($$bvr)*8/$nbits;
  my $cv = '';
  my ($ai,$bi,$ci, $aval,$bval);
  for ($ai=0,$bi=0,$ci=0; $ai < $na && $bi < $nb; ++$ci) {
    $aval = vec($$avr,$ai,$nbits);
    $bval = vec($$bvr,$bi,$nbits);
    if ($aval <= $bval) {
      vec($cv,$ci,$nbits) = $aval;
      ++$ai;
      ++$bi if ($aval == $bval);
    } else { ##-- $aval == $bval

Vec.pm  view on Meta::CPAN

  return $cv;
}

##--------------------------------------------------------------
## $vintersect = vintersect($av,$bv,$nbits)
sub _vintersect {
  my ($avr,$bvr,$nbits) = (\$_[0],\$_[1],$_[2]);
  die(__PACKAGE__ , "::_vintersect(): cannot handle nbits < 8, but you requested $nbits") if ($nbits < 8);

  ##-- ensure smaller set is "a"
  ($$avr,$$bvr) = ($$bvr,$$avr) if (length($$bvr) < length($$avr));

  my $na = length($$avr)*8/$nbits;
  my $nb = length($$bvr)*8/$nbits;
  my $cv = '';
  my ($ai,$bi,$ci, $blo,$aval,$bval);
  for ($ai=0,$blo=0,$ci=0; $ai < $na; ++$ai) {
    $aval = vec($$avr,$ai,$nbits);
    $bi   = _vbsearch_ub($$bvr,$aval,$nbits,$blo,$nb);
    last if ($bi == $KEY_NOT_FOUND);
    vec($cv,$ci++,$nbits) = $aval if ($aval == vec($$bvr,$bi,$nbits));
    $blo = $bi;
  }
  return $cv;
}

##--------------------------------------------------------------
## $vsetdiff = vsetdiff($av,$bv,$nbits)
sub _vsetdiff {
  my ($avr,$bvr,$nbits) = (\$_[0],\$_[1],$_[2]);
  die(__PACKAGE__ , "::_vintersect(): cannot handle nbits < 8, but you requested $nbits") if ($nbits < 8);

  my $na = length($$avr)*8/$nbits;
  my $nb = length($$bvr)*8/$nbits;
  my $cv = '';
  my ($ai,$bi,$ci, $blo,$aval,$bval);
  for ($ai=0,$blo=0,$ci=0; $ai < $na; ++$ai) {
    $aval = vec($$avr,$ai,$nbits);
    $bi   = _vbsearch_ub($$bvr,$aval,$nbits,$blo,$nb);
    last if ($bi == $KEY_NOT_FOUND);
    vec($cv,$ci++,$nbits) = $aval if ($aval != vec($$bvr,$bi,$nbits));
    $blo = $bi;
  }
  $cv .= substr($$avr, $ai*$nbits/8);

Vec.pm  view on Meta::CPAN

=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>.

Vec.pm  view on Meta::CPAN

Debugging XS-wrapper equivalent to C<vec($vec,$i,$nbits)>.

=item vset($vec,$i,$nbits,$newval)

Debugging XS-wrapper equivalent to C<vec($vec,$i,$nbits)=$newval>.

=item vec2array($vec,$nbits)

Debugging utility, equivalent to

 [map {vec($vec,$_,$nbits)} (0..(length($vec)*8/$nbits-1))]

=back

=cut

##======================================================================
## Footer
=pod

=head1 SEE ALSO

Vec.xs  view on Meta::CPAN

  uchar *vp;
  STRLEN len;
CODE:
 vp = (uchar *)SvPVbyte(vec,len);
 if (len <= i*nbits/8) {
#if 0
   //-- doesn't propagate to perl sv?
   vp = (uchar *)SvGROW(vec, (i+1)*nbits/8);
   SvCUR_set(vec, (i+1)*nbits/8);
#endif //-- re-allocate
   croak("vset(): index " ABSV_PRI " exceeds vector length = " ABSV_PRI " element(s)", i, i*nbits/8);
 }
 absv_vset(vp, i, nbits, val);

##=====================================================================
## CONSTANTS

##--------------------------------------------------------------
ABSV_UINT
HAVE_QUAD()
CODE:

t/04_search.t  view on Meta::CPAN

  my ($nbits,$vals) = @_;
  my $vec   = '';
  vec($vec,$_,$nbits)=$vals->[$_] foreach (0..$#$vals);
  return $vec;
}

## \@l = vec2list($vec,$nbits)
sub vec2list {
  use bytes;
  my ($vec,$nbits) = @_;
  return [map {vec($vec,$_,$nbits)} (0..(length($vec)*8/$nbits-1))];
}

## $str = n2str($n)
sub n2str {
  return !defined($_[0]) ? 'undef' : ($_[0]==$NOKEY ? 'NOKEY' : ($_[0]+0));
}

## $str = l2str(\@vlist)
sub l2str {
  return join(' ', map {n2str($_)} @{$_[0]});

t/05_setops.t  view on Meta::CPAN

  my ($nbits,$vals) = @_;
  my $vec   = '';
  vec($vec,$_,$nbits)=$vals->[$_] foreach (0..$#$vals);
  return $vec;
}

## \@l = vec2list($vec,$nbits)
sub vec2list {
  use bytes;
  my ($vec,$nbits) = @_;
  return [map {vec($vec,$_,$nbits)} (0..(length($vec)*8/$nbits-1))];
}

## $str = l2str(\@vlist)
sub l2str {
  return join(' ', @{$_[0]});
}

## $str = v2str($vec,$nbits)
sub v2str {
  return l2str(vec2list(@_));