/*****************************************************************************************************************
 
SAS file name: bitmap.sas
File location: 
__________________________________________________________________________________________________________________
 
Purpose: To instroduce and demonstrate the concept of bitmapping in SAS.
Author: Peter Clemmensen
Creation Date: 01Dec2019
 
This program supports the blog post "" on SASnrd.com

*****************************************************************************************************************/

/* Large data set */
proc plan seed=0;
  factors k=1e7 / noprint;
  output out=Large;
run;quit;

data Large;
   set Large;
   d=rand('integer', 1, 100);
run;

/* Small data set */
proc surveyselect data=Large out=Small seed=123 noprint
     method=srs
     sampsize=5000000;
run;

/* Binary form of power expressions 2**x for x=0, ..., 32 */
data _null_;
   array b {0 : 32};
   do x=0 to 32; 
      b[x] = 2**x; 
   end;
   put (b[*])(= binary32.);
run;

data _null_;
   a=0;
   do k=2, 7;
      a+2**(k-1);
   end;
   put a= binary10.;
run;

/* Upper Bound for bitmap */
data _null_;
   UpperBound=ceil(1e7 / 32) + 1;
   put UpperBound=;
run;

/* Bitmap search */
data bmsearch(keep=k d);
   array bm {0 : 312501} _temporary_;                           /*  1  */
   array bi {0 : 32}     _temporary_;

   do i=0 to 312500; bm[i]=0;      end;                         /*  2  */
   do j=0 to 32;     bi[j] = 2**j; end;

   do until (lr1);
      set small end=lr1;
      x = int(k / 32);                                          /*  1  */
      P = mod(k, 32);                                           /*  2  */
      bm[x] = bor(bm[x], bi[P]);                                /*  3  */
   end;

   do until (lr2);
      set large end=lr2;
      x = int(k / 32);                                          /*  1  */
      P = mod(k, 32);                                       
      if band(bm[x], bi[P]) ne 0 then output;                   /*  2  */
   end;
run;

/* Hash Object Approach */
data hash(keep=k d);
   if _N_=1 then do;
      declare hash h(dataset:'small');
      h.definekey('k');
      h.definedone();
   end;

   set large;

   if h.check()=0;
run;

/* PROC SQL Approach*/
proc sql;
   create table sql as
   select * from Large
   where k in (select k from Small);
quit;

/* Compare data sets */
proc compare base=bmsearch comp=hash;run;
proc compare base=bmsearch comp=sql;run;