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

SAS file name: avl_distribution
File location: 
_________________________________________________________________________________________________________________

Purpose: To demonstrate the AVL bucket distribution that takes place when a SAS hash object is filled with data.
Author: Peter Clemmensen
Creation Date: 03/02/2019

This program supports the example page "AVL Tree Distribution in SAS Hash Objects Explained" on SASnrd.com

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

/* Example data */
data MyData;
   array first_names{20} $20 _temporary_ ("Paul", "Allan", "Thomas", "Michael", "Chris", "David", "John", "Jerry", "James", "Robert",
                                          "William", "Richard", "Bob", "Daniel", "Paul", "George", "Larry", "Eric", "Charles", "Stephen");
   array last_names{20}$20 _temporary_ ("Smith", "Johnson", "Williams", "Jones", "Brown", "Miller", "Wilson", "Moore", "Taylor", "Hall",
                                        "Anderson", "Jackson", "White", "Harris", "Martin", "Thompson", "Robinson", "Lewis", "Walker", "Allen");
   call streaminit(123);
   do ID=1 to 1e6;
      first_name=first_names[ceil(rand("Uniform")*20)];
      last_name=last_names[ceil(rand("Uniform")*20)];
      output;
   end;

   format ID z7.;
run;

/* Simulate AVL tree distribution */
data AVL(keep=num:);
   set MyData end=eof;
   Tree=1+mod(rank(md5(ID)), 256);
   array num{256} (256*0);
   num[Tree]+1;
   if eof then do;
      diff=(max(of num:)-min(of num:))/1e6;
      output;
      put diff;
   end;
run;

/* Key values are sorte within each tree to make binary search posible */
data _null_;
   declare hash h(hashexp:2);
   h.definekey('k');
   h.definedone();
   do k=1 to 100;
      h.add();
   end;
   h.output(dataset:'test');
run;