# include <math.h>
# include <stdlib.h>
# include <stdio.h>

# define elementsof(x) (sizeof (x) / sizeof (*(x)))

// # define TEST_FALSEDROPS
# define QUERY_FROM_DS

/*****
int db_sizes []        = {1000, 3000, 10000, 30000, 100000, 300000, 1000000, 3000000} ;
int dimensions []      = {8, 16, 32, 64, 128, 256, 512} ;
float selectivities [] = {1e-6, 3e-6, 1e-5, 3e-5, 1e-4, 3e-4, 1e-3, 3e-3, 1e-2, 3e-2} ;
*****/

int db_sizes []        = {10000, 100000, 1000000} ;
int dimensions []      = {16, 32} ;
float selectivities [] = {1e-6, 3e-6, 1e-5, 3e-5, 1e-4, 3e-4, 1e-3, 3e-3, 1e-2, 3e-2} ;

typedef struct {
    int    quadrno ;
    float  height ;
} datacrip ;

typedef int cmpfunc (const void *, const void *) ;

int cmpintfloat (datacrip *p1, datacrip *p2) {
    if (p1->quadrno == p2->quadrno)
	return p1->height > p2->height ? -1 : 1 ;
    else
	return p1->quadrno > p2->quadrno ? -1 : 1 ;
}

void test (int dimension, int N, int pg_size, char * filename) {

    typedef struct {
	int    quadrno ;
	float  height ;
	float  vector [dimension] ;
    } datarec ;

    datarec * database = (datarec *) malloc (N * sizeof (datarec) ) ;
    FILE * fp = fopen (filename, "rb") ;

    int datapp = pg_size / sizeof (datarec) ;
    int numpg = N/datapp + 1 ;

    int pghits, eno ;
    int num_exp = 100 ;
    float * q = (float *) malloc (dimension * sizeof (float) ) ;
    float qside ;

    int i, j, i2, i3, quadrno ;
    float h, minh ;

    for (i=0 ; i<N ; i++) {
	minh = MAXFLOAT ;
	for (j=0 ; j<dimension ; j++) {
	    if (fp) {
	        fread (&h, sizeof (float), 1, fp) ;
	        database [i] . vector [j] = h ;
	    } else
	        h = database [i] . vector [j] = drand48 () ;
	    if (h < minh) {
		minh = h ;
		quadrno = j ;
	    }
	    if (1-h < minh) {
		minh = 1-h ;
		quadrno = dimension + j ;
	    }
	}
	database [i] . quadrno = quadrno ;
	database [i] . height = minh ;
    }

    qsort (database, N, sizeof (datarec), (cmpfunc *) cmpintfloat) ;

    for (j=0 ; j < elementsof (selectivities) ; j++) {
	pghits = 0 ;
	qside = pow (selectivities [j], 1.0 / (float) dimension) ;
	for (eno=0 ; eno<num_exp ; eno++) {
	    for (i=0 ; i<dimension ; i++)
# ifdef QUERY_FROM_DS
		q [i] = drand48 () * (1-qside) ;
# else
		q [i] = drand48 () - qside/2 ; 
# endif
	    for (i=0 ; i<N-datapp ; i+=datapp)
		if (database [i] . quadrno != database [i+datapp-1] . quadrno)
		    pghits ++ ;
		else {
		    quadrno = database [i] . quadrno ;
		    if (quadrno < dimension) {
			if (q [quadrno] < database [i] . height)
			    pghits ++ ;
# ifdef TEST_FALSEDROPS
			else {
			    for (i2=i ; i2<i+datapp ; i2++)
				for (i3=0 ; i3<dimension ; i3++) {
				    if (database [i2] . vector [i3] <= q [i3] || database [i2] . vector [i3] >= q [i3] + qside)
					break ;
				    if (i3>=dimension-1)
					printf ("WARNING ! FALSE DROP (1)\n") ;
				}
			}
# endif
		    } else
			if (q [quadrno - dimension] + qside > 1 - database [i] . height)
			    pghits ++ ;
# ifdef TEST_FALSEDROPS
			else {
			    for (i2=i ; i2<i+datapp ; i2++)
				for (i3=0 ; i3<dimension ; i3++) {
				    if (database [i2] . vector [i3] <= q [i3] || database [i2] . vector [i3] >= q [i3] + qside)
					break ;
				    if (i3>=dimension-1)
					printf ("WARNING ! FALSE DROP (2)\n") ;
				}
			}
# endif
		}
	}

	printf ("%4d %9d %8d %8d %11.1e %9.3f %12.3f %10.5f\n", 
		dimension, N, pg_size, numpg, selectivities [j], qside, 
		(float) pghits / num_exp, (float) pghits / num_exp / numpg) ;
    }
    printf ("\n") ;
    free (q) ;
    free (database) ;
    if (fp) 
        fclose (fp) ;
}

int main (int argc, char ** argv) {
    int i, j ;
    if (argc == 4)
	test (atoi (argv[1]), atoi (argv[2]), atoi (argv [3]), "") ;
    else {
	printf (" dim         N  pg-size  num-pgs selectivity   sidelen  pg_accesses proportion\n"
		"------------------------------------------------------------------------------\n\n") ;
	for (i=0 ; i < elementsof (db_sizes) ; i++)
	    for (j=0 ; j < elementsof (dimensions) ; j++)
		test (dimensions [j], db_sizes [i], 4096, argc == 2 ? argv [1] : "") ;
    }
    return 0 ;
}