Algorithm-BinarySearch-Vec

 view release on metacpan or  search on metacpan

Vec.xs  view on Meta::CPAN

vget(SV *vec, ABSV_UINT i, ABSV_UINT nbits)
PREINIT:
  uchar *vp;
  STRLEN len;
CODE:
 vp = (uchar *)SvPVbyte(vec, len);
 if (len > i*nbits/8)
   RETVAL = absv_vget(vp, i, nbits);
 else
   RETVAL = 0;
OUTPUT:
  RETVAL

 ##--------------------------------------------------------------
void
vset(SV *vec, ABSV_UINT i, ABSV_UINT nbits, ABSV_UINT val)
PREINIT:
  uchar *vp;
  STRLEN len;
CODE:
 vp = (uchar *)SvPVbyte(vec,len);

Vec.xs  view on Meta::CPAN

##--------------------------------------------------------------
ABSV_UINT
HAVE_QUAD()
CODE:
#ifdef ABSV_HAVE_QUAD
 RETVAL = 1;
#else
 RETVAL = 0;
#endif
OUTPUT:
 RETVAL

##--------------------------------------------------------------
ABSV_UINT
KEY_NOT_FOUND()
CODE:
 RETVAL = KEY_NOT_FOUND;
OUTPUT:
 RETVAL

##=====================================================================
## BINARY SEARCH, element-wise

##--------------------------------------------------------------
ABSV_UINT
vbsearch(SV *vec, ABSV_UINT key, ABSV_UINT nbits, ...)
PREINIT:
  const uchar *v;
  STRLEN vlen;
  ABSV_UINT ilo, ihi;
CODE:
 v = SvPV(vec,vlen);
 ilo = items > 3 ? SvUV(ST(3)) : 0;
 ihi = items > 4 ? SvUV(ST(4)) : (vlen*8/nbits);
 RETVAL = absv_bsearch(v,key,ilo,ihi,nbits);
OUTPUT:
 RETVAL

##--------------------------------------------------------------
ABSV_UINT
vbsearch_lb(SV *vec, ABSV_UINT key, ABSV_UINT nbits, ...)
PREINIT:
  const uchar *v;
  STRLEN vlen;
  ABSV_UINT ilo, ihi;
CODE:
 v = SvPV(vec,vlen);
 ilo = items > 3 ? SvUV(ST(3)) : 0;
 ihi = items > 4 ? SvUV(ST(4)) : (vlen*8/nbits);
 RETVAL = absv_bsearch_lb(v,key,ilo,ihi,nbits);
OUTPUT:
 RETVAL

##--------------------------------------------------------------
ABSV_UINT
vbsearch_ub(SV *vec, ABSV_UINT key, ABSV_UINT nbits, ...)
PREINIT:
  const uchar *v;
  STRLEN vlen;
  ABSV_UINT ilo, ihi;
CODE:
 v = SvPV(vec,vlen);
 ilo = items > 3 ? SvUV(ST(3)) : 0;
 ihi = items > 4 ? SvUV(ST(4)) : (vlen*8/nbits);
 RETVAL = absv_bsearch_ub(v,key,ilo,ihi,nbits);
OUTPUT:
 RETVAL


##=====================================================================
## BINARY SEARCH, array-wise

##--------------------------------------------------------------
AV*
vabsearch(SV *vec, AV *keys, ABSV_UINT nbits, ...)
PREINIT:

Vec.xs  view on Meta::CPAN

 ilo = items > 3 ? SvUV(ST(3)) : 0;
 ihi = items > 4 ? SvUV(ST(4)) : (vlen*8/nbits);
 n = av_len(keys);
 RETVAL = newAV();
 av_extend(RETVAL, n);
 for (i=0; i<=n; ++i) {
   SV   **key  = av_fetch(keys, i, 0);
   ABSV_UINT   found = absv_bsearch(v,SvUV(*key),ilo,ihi,nbits);
   av_store(RETVAL, i, newSVuv(found));
 }
OUTPUT:
 RETVAL

##--------------------------------------------------------------
AV*
vabsearch_lb(SV *vec, AV *keys, ABSV_UINT nbits, ...)
PREINIT:
  const uchar *v;
  STRLEN vlen;
  ABSV_UINT ilo, ihi;
  I32 i,n;

Vec.xs  view on Meta::CPAN

 ilo = items > 3 ? SvUV(ST(3)) : 0;
 ihi = items > 4 ? SvUV(ST(4)) : (vlen*8/nbits);
 n = av_len(keys);
 RETVAL = newAV();
 av_extend(RETVAL, n);
 for (i=0; i<=n; ++i) {
   SV   **key  = av_fetch(keys, i, 0);
   ABSV_UINT   found = absv_bsearch_lb(v,SvUV(*key),ilo,ihi,nbits);
   av_store(RETVAL, i, newSVuv(found));
 }
OUTPUT:
 RETVAL

##--------------------------------------------------------------
AV*
vabsearch_ub(SV *vec, AV *keys, ABSV_UINT nbits, ...)
PREINIT:
  const uchar *v;
  STRLEN vlen;
  ABSV_UINT ilo, ihi;
  I32 i,n;

Vec.xs  view on Meta::CPAN

 ilo = items > 3 ? SvUV(ST(3)) : 0;
 ihi = items > 4 ? SvUV(ST(4)) : (vlen*8/nbits);
 n = av_len(keys);
 RETVAL = newAV();
 av_extend(RETVAL, n);
 for (i=0; i<=n; ++i) {
   SV   **key  = av_fetch(keys, i, 0);
   ABSV_UINT   found = absv_bsearch_ub(v,SvUV(*key),ilo,ihi,nbits);
   av_store(RETVAL, i, newSVuv(found));
 }
OUTPUT:
 RETVAL

##=====================================================================
## BINARY SEARCH, vec-wise

##--------------------------------------------------------------
SV*
vvbsearch(SV *vec, SV *vkeys, ABSV_UINT nbits, ...)
PREINIT:
  const uchar *v, *k;

Vec.xs  view on Meta::CPAN

 n   = klen*8/nbits;
 RETVAL = newSVpv("",0);
 SvGROW(RETVAL, n*4);	       //-- always use 32-bit keys
 SvCUR_set(RETVAL, n*4);
 rv = SvPV_nolen(RETVAL);
 for (i=0; i<n; ++i) {
   ABSV_UINT key   = absv_vget(k,i,nbits);
   ABSV_UINT found = absv_bsearch(v,key,ilo,ihi,nbits);
   absv_vset(rv,i,32,found);
 }
OUTPUT:
 RETVAL

##--------------------------------------------------------------
SV*
vvbsearch_lb(SV *vec, SV *vkeys, ABSV_UINT nbits, ...)
PREINIT:
  const uchar *v, *k;
  uchar *rv;
  STRLEN vlen, klen;
  ABSV_UINT i,n, ilo, ihi;

Vec.xs  view on Meta::CPAN

 n   = klen*8/nbits;
 RETVAL = newSVpv("",0);
 SvGROW(RETVAL, n*4);	 	//-- always use 32-bit keys
 SvCUR_set(RETVAL, n*4);
 rv = SvPV_nolen(RETVAL);
 for (i=0; i<n; ++i) {
   ABSV_UINT key   = absv_vget(k,i,nbits);
   ABSV_UINT found = absv_bsearch_lb(v,key,ilo,ihi,nbits);
   absv_vset(rv,i,32,found);
 }
OUTPUT:
 RETVAL

##--------------------------------------------------------------
SV*
vvbsearch_ub(SV *vec, SV *vkeys, ABSV_UINT nbits, ...)
PREINIT:
  const uchar *v, *k;
  uchar *rv;
  STRLEN vlen, klen;
  ABSV_UINT i,n, ilo, ihi;

Vec.xs  view on Meta::CPAN

 n   = klen*8/nbits;
 RETVAL = newSVpv("",0);
 SvGROW(RETVAL, n*4);		//-- always use 32-bit keys
 SvCUR_set(RETVAL, n*4);
 rv = SvPV_nolen(RETVAL);
 for (i=0; i<n; ++i) {
   ABSV_UINT key   = absv_vget(k,i,nbits);
   ABSV_UINT found = absv_bsearch_ub(v,key,ilo,ihi,nbits);
   absv_vset(rv,i,32,found);
 }
OUTPUT:
 RETVAL

##=====================================================================
## SET OPERATIONS

##--------------------------------------------------------------
SV*
vunion(SV *avec, SV *bvec, ABSV_UINT nbits)
PREINIT:
  const uchar *a, *b;

Vec.xs  view on Meta::CPAN

   } else { //-- aval > bval
     absv_vset(c,ci,nbits,bval);
     ++bi;
   }
 }
 for (; ai < na; ++ai, ++ci)
   absv_vset(c,ci,nbits,absv_vget(a,ai,nbits));
 for (; bi < nb; ++bi, ++ci)
   absv_vset(c,ci,nbits,absv_vget(b,bi,nbits));
 SvCUR_set(RETVAL, ci*nbits/8);
OUTPUT:
 RETVAL

##--------------------------------------------------------------
SV*
vintersect(SV *avec, SV *bvec, ABSV_UINT nbits)
PREINIT:
  const uchar *a, *b;
  uchar *c;
  STRLEN alen,blen;
  ABSV_UINT na,nb,nc, ai,blo,bi,ci, aval,bval;

Vec.xs  view on Meta::CPAN

 for (ai=0,blo=0,ci=0; ai < na; ++ai) {
   aval = absv_vget(a,ai,nbits);
   bi   = absv_bsearch_ub(b,aval,blo,nb,nbits);
   if (bi   == KEY_NOT_FOUND) break;
   if (aval == absv_vget(b,bi,nbits)) {
     absv_vset(c,ci++,nbits,aval);
   }
   blo = bi;
 }
 SvCUR_set(RETVAL, ci*nbits/8);
OUTPUT:
 RETVAL

##--------------------------------------------------------------
SV*
vsetdiff(SV *avec, SV *bvec, ABSV_UINT nbits)
PREINIT:
  const uchar *a, *b;
  uchar *c;
  STRLEN alen,blen;
  ABSV_UINT na,nb,nc, ai,blo,bi,ci, aval,bval;

Vec.xs  view on Meta::CPAN

   bi   = absv_bsearch_ub(b,aval,blo,nb,nbits);
   if (bi   == KEY_NOT_FOUND) break;
   if (aval != absv_vget(b,bi,nbits)) {
     absv_vset(c,ci++,nbits,aval);
   }
   blo = bi;
 }
 for ( ; ai < na; ++ai)
   absv_vset(c,ci++,nbits,absv_vget(a,ai,nbits));
 SvCUR_set(RETVAL, ci*nbits/8);
OUTPUT:
 RETVAL

typemap  view on Meta::CPAN

# -*- Mode: Perl -*-

ABSV_UINT     T_UINT

######################################################################
# perl->C
INPUT

T_INT
  {
      $var = SvIV($arg);
  }

T_UINT
  {
      $var = SvUV($arg);
  }

T_FLOAT
  {
      $var = SvNV($arg);
  }

######################################################################
# C->perl
OUTPUT

T_CHAR
  {
      sv_setpvn($arg,&$var,1);
  }

T_INT
  {
      sv_setiv($arg,$var);
  }