#include <stdio.h> 
#include <assert.h> 
#include "minwise.h"

/* generate a approx min-wise permutation for [2^n] within 2^-e
   and with restriction 2^k */

mwPermutation::mwPermutation(int n_, int k_, int e_){

	n=n_;
	k=k_;
	e=e_;

	/* construct a series of kwhashfunctions */
	ki=new int[k];
	ri=new int[k];
	
	int r=0;

	for(d=0;(d<k)&&(r<n);d++){
		ki[d]=k-d;	
		ri[d]=2+(( 2*(1+e+LOG2C(k)) )>>ki[d]); 
		if(ri[d]==2) 
			ri[d]++;
		r+=ri[d];
	}

	for(int i=0;r<n;i++){
		i=i%k; 
		ri[k-i]++;
		r++;
	}
	
	buf=new char[r+1];

	/* construct hash functions... */
#ifdef DEBUG 
	printf("  creating %d hashfucntions with buf size %d\n",d, r);
#endif

	h=new kwHashFunctionPtr[d];
	for(int i=0;i<d;i++){
#ifdef DEBUG 
	printf("  creating hash 2^%d->2^%d (k=2^%d,e=2^-%d)\n",n,ri[i],ki[i],e+1+k);
#endif
		h[i]=new kwHashFunction(n , ri[i] , ki[i], e+1+k);
	}
#ifdef DEBUG 
	printf("2^%d mwPermutation(k=2^%d,e=2^-%d) constructed.\n",n,k,e);
#endif
}

mwPermutation::~mwPermutation(){
	for(int i=0;i<d;i++)
		delete h[i];
	delete [] h; 
	delete [] ri;
	delete [] ki;
	delete [] buf;
#ifdef DEBUG 
	printf("mwPermutation Destroyed.\n");
#endif
}


INTTYPE mwPermutation::map(INTTYPE k){
	INTTYPE result=0;
	int r=0;
	for(int i=0;i<d;i++){
		h[i]->hash(k,buf+r);
		r+=ri[i];
	}
	for(int i=0;i<n;i++){
		result=result<<1;
		result|=buf[i];
	}
#ifdef DEBUG
	for(int i=0;i<n;i++){
		if(buf[i]!=0 && buf[i]!=1){
		printf("%llX ",result);
		for(int i=0;i<n;i++){
			printf(" %1d ", buf[i]);
		}
		printf("\n");
		break;
		}
	}
#endif

	return result;
}

RNG *global_rng=NULL;