/* Richard A. DeVenezia, 3/27/04
 * http://www.devenezia.com
 *
 * Based on original SAS-L posting 3/27/04, "SQL: All, every"
 */

/*
 * Bars sell beer
 * Drinkers like beer
 * Which bars sells the beers a drinker likes ?
 */

%let SEED = 2;
%let N_BEERS = 100;
%let N_BARS = 1000;
%let N_DRINKERS = 10000;
%let MIN_BEERS_PER_BAR = 3 ;
%let MAX_BEERS_PER_BAR = 20;
%let MAX_BEERS_PER_DRINKER = 9;

/**/
%let N_BEERS = 50;
%let N_BARS = 100;
%let N_DRINKERS = 1000;
%let MIN_BEERS_PER_BAR = 20;
%let MAX_BEERS_PER_BAR = 30;
%let MAX_BEERS_PER_DRINKER = 4;
/**/


%let ranChar  = byte(rank('A')+26*ranuni(&SEED));
%let ranDigit = byte(rank('0')+10*ranuni(&SEED));

%*-------------------------------------------------------------------;

data allBeers;
  do beer_id = 1 to &N_BEERS;
    beer_name = &ranChar. || &ranChar. || &ranChar.
             || &ranDigit.|| &ranDigit.|| &ranDigit.
    ;
    output;
  end;
run;

%*-------------------------------------------------------------------;

* each bar stocks a random sampling from all beers;

data barStock (keep=bar_id beer_id beer_id_seq);

  do bar_id = 1 to &N_BARS;

    k = &MIN_BEERS_PER_BAR + int((&MAX_BEERS_PER_BAR-&MIN_BEERS_PER_BAR) * ranuni(&SEED));
    n = &N_BEERS;

    _n_ = 0;
    do while (k > 0);
      _n_ + 1;
      if (ranuni(&SEED) <= k/n) then do;
        beer_id_seq + 1;
        k = k - 1;
        beer_id = _n_;
*       set allBeers(keep=beer_id) point = _n_;
        output;
      end;
      n = n - 1;
    end;
  end;

  stop;
run;

%*-------------------------------------------------------------------;

* each drinker likes a random sampling from all beers;

data drinkerSurvey (keep=drinker_id beer_id);

  do drinker_id = 1 to &N_DRINKERS;

    k = 1 + int(&MAX_BEERS_PER_DRINKER * ranuni(&SEED));
    n = &N_BEERS;

    _n_ = 0;
    do while (k > 0);
      _n_ + 1;
      if (ranuni(&SEED) <= k/n) then do;
        beer_id_seq + 1;
        k = k - 1;
        beer_id = _n_;
*       set allBeers(keep=beer_id) point = _n_;
        output;
      end;
      n = n - 1;
    end;
  end;

  stop;
run;


%*-------------------------------------------------------------------;

* find which bars could satisfy every like of which drinkers;

proc sql;
* this is commented out, faster response using bit-coding (see below);
* create table barList as
  select barLikes.bar_id
       , drinkerLikes.drinker_id
  from
    ( select
             drinker_id
           , count (beer_id) as beerCount
      from
             drinkerSurvey
      group
         by  drinker_id
    ) as drinkerLikes
    ,
    ( select
             bar_id
           , drinker_id
           , count(drinkerSurvey.beer_id) as surveyBeerCount
      from
             barStock
          , drinkerSurvey
      where
            barStock.beer_id = drinkerSurvey.beer_id
      group
         by bar_id
          , drinker_id
    )
    as barLikes
  where
    drinkerLikes.drinker_id = barLikes.drinker_id
    and
    drinkerLikes.beerCount = barLikes.surveyBeerCount
  ;
quit;


%*-------------------------------------------------------------------;

* bitcoding;
* since beer_id is 1 based, one bit (bit 0 of byte 0) will be squandered;

%let N_BYTES = %eval (&N_BEERS / 32);

data barBeerBits;

  retain bar_id; * just for setting as 1st column;

  array beerbits [0:&N_BYTES] 8;
  do byte_no = lbound(beerbits) to hbound(beerbits);
    beerbits[byte_no] = 0;;
  end;

  do until (last.bar_id);
    set barStock;
    by bar_id;

    byte_no = int(beer_id / 32);
    bit_no  = mod(beer_id , 32);

    x = beerbits[byte_no];
    x = bor (x, blshift(1,bit_no));
    beerbits[byte_no] = x;

*   put beer_id= (beerbits:)(=binary8.);
  end;

  keep bar_id byte_no beer_bits ;

  do byte_no = lbound(beerbits) to hbound(beerbits);
    beer_bits = beerbits[byte_no];
    output;
  end;

  format beer_bits binary32.;
run;

%*-------------------------------------------------------------------;

data drinkerBeerBits;

  retain drinker_id; * just for setting as 1st column;

  array beerbits [0:&N_BYTES] 8;
  do byte_no = lbound(beerbits) to hbound(beerbits);
    beerbits[byte_no] = 0;;
  end;

  do until (last.drinker_id);
    set drinkerSurvey;
    by drinker_id;

    byte_no = int(beer_id / 32);
    bit_no  = mod(beer_id , 32);

    x = beerbits[byte_no];
    x = bor (x, blshift(1,bit_no));
    beerbits[byte_no] = x;

*   put beer_id= (beerbits:)(=binary8.);
  end;

  keep drinker_id byte_no beer_bits ;

  do byte_no = lbound(beerbits) to hbound(beerbits);
    beer_bits = beerbits[byte_no];
    output;
  end;

  format beer_bits binary32.;
run;

%*-------------------------------------------------------------------;

proc sql;
  create table barDrinker as
  select bar.bar_id
       , drinker.drinker_id
  from   barBeerBits as bar
       , drinkerBeerBits as drinker
  where
         bar.byte_no = drinker.byte_no
  group by
         bar_id
       , drinker_id
  having
         sum (  band (bar.beer_bits, drinker.beer_bits) = drinker.beer_bits ) = %eval(&N_BYTES+1)
  order by
         bar_id, drinker_id
  ;
quit;




%*-------------- tabulation ------------;

proc sql;
  create table barDrinkerBeers as
  select bar.bar_id
       , drinker.drinker_id
       , bar.byte_no
       , bar.beer_bits as bar_bits
       , drinker.beer_bits as drinker_bits
  from   barBeerBits as bar
       , drinkerBeerBits as drinker
  where
         bar.byte_no = drinker.byte_no
  group by
         bar_id
       , drinker_id
  having
         sum (  band (bar.beer_bits, drinker.beer_bits) = drinker.beer_bits ) = %eval(&N_BYTES+1)
  order by
         bar_id, drinker_id, byte_no
  ;
quit;


data barDrinkerBeersList;
  set barDrinkerBeers end=end;
  by bar_id drinker_id byte_no;

  if first.bar_id then bd_seq = 0;
  if first.drinker_id then bd_seq + 1;

  if first.drinker_id then
    beer_id = -1;

  mask = 1;
  do i = 0 to 31;
    beer_id + 1;
    if band (drinker_bits, mask) then output;
    mask = blshift (mask, 1);
  end;

  if bd_seq = 1 then do;
    beer_id = beer_id - 32;
    drinker_id = 0; * indicates bar beers;
    mask = 1;
    do i = 0 to 31;
      beer_id + 1;
      if band (bar_bits, mask) then output;
      mask = blshift (mask, 1);
    end;
  end;

  keep bar_id drinker_id beer_id ;
run;


%macro who(bar_id=);
  proc format; value drinker 0='Bar Serves'; run;

  proc tabulate data=barDrinkerBeersList;
    class bar_id drinker_id beer_id;
    table bar_id,drinker_id,beer_id;
    where bar_id = &bar_id;
    title "Drinkers the bar should solicit";
    format drinker_id drinker.;
  run;
%mend;

%macro where(drinker_id=);

  proc sql;
    create table report as
    select
           bar.bar_id
         , bar.beer_id
         , drinker.drinker_id
         , &drinker_id as id
    from
         (select *
          from barDrinkerBeersList
          where drinker_id = &drinker_id
         ) as drinker
    right join
         (select bar_id, beer_id
          from barStock
         ) as bar
    on
         bar.bar_id  = drinker.bar_id
    and  bar.beer_id = drinker.beer_id
    group by bar.bar_id
    having count(drinker_id) > 0

    UNION

    select
           0 as bar_id
         , x.beer_id
         , x.drinker_id
         , &drinker_id as id
    from barDrinkerBeersList as x
    where x.drinker_id = &drinker_id
    ;
  quit;

  proc format; value bar 0='Drinker Likes'; run;

  proc tabulate data=report ;
    class id bar_id beer_id;
    var drinker_id;
    table id,bar_id,beer_id;
    title "Bars the drinker should visit";
    format bar_id bar.;
  run;
%mend;

ods listing close;
ods html path="%sysfunc(pathname(WORK))" file="matchups.html";

%who   (bar_id=2)
%where (drinker_id=2)

ods html close;