#include <math.h>#include <stdlib.h>#include <signal.h>#include <time.h>//////////////////////////////////////////////////////////////////////////////// defines//////////////////////////////////////////////////////////////////////////////#ifndef TRUE#define TRUE 1#define FALSE 0#endif#define BLK_SIZE   4096#define MAXLONGINT 32768 #define NUM_TRIES 10#define ZAEHLER#include "blk_file.h"#include "linlist.h"#include "x_tree.h"//////////////////////////////////////////////////////////////////////////////// DATA//////////////////////////////////////////////////////////////////////////////class DATA{    int dimension;public:    float *data;                       // Vector    float distanz;                     // anything    float *get_mbr();                  // returns MBR of the object    float get_area()                   // returns the area of the MBR    { return 0.0; }                    // for vectors always 0.0    void read_from_buffer(char *buffer);                                          // reads data from buffer    void write_to_buffer(char *buffer);                                          // writes data to buffer    int get_size();                    // returns amount of needed space    void print();    virtual DATA & operator = (DATA &_d);    virtual bool operator < (DATA &_d);    virtual bool operator > (DATA &_d);    DATA(int *dimension = &XTDataNode__dimension);    virtual ~DATA();};DATA::DATA(int *_dimension){    dimension = *((int *)_dimension);    data = new float[dimension];}DATA::~DATA(){    delete [] data;}DATA & DATA::operator = (DATA &_d){    dimension = _d.dimension;    distanz = _d.distanz;    memcpy(data, _d.data, sizeof(float) * dimension);    return *this;}bool DATA::operator < (DATA &_d){    return (distanz < _d.distanz);}bool DATA::operator > (DATA &_d){    return (distanz > _d.distanz);}void DATA::read_from_buffer(char *buffer){    int i;    i = dimension*sizeof(float);    memcpy(data, buffer, i);    memcpy(&distanz, &buffer[i], sizeof(int));}void DATA::write_to_buffer(char *buffer){    int i;    i = dimension*sizeof(float);    memcpy(buffer, data, i);    memcpy(&buffer[i], &distanz, sizeof(int));}int DATA::get_size(){    return dimension * sizeof(float) + sizeof(int);}void DATA::print(){ int i; printf("( "); for(i = 0; i < dimension; i++)   printf("%7.5f ",data[i]); printf(")\n");}float *DATA::get_mbr()// fuer Punktdaten trivial: untere_grenze == obere_grenze{    int i;    float *f;    f = new float[2*dimension];    for (i = 0; i < dimension; i++)	f[2*i] = f[2*i+1] = data[i];    return f;}////////////////////////////////////////////////////////////////// main()///////////////////////////////////////////////////////////////bool abort_flag;void abort(int signal){    abort_flag = TRUE;}void error(char *t, bool ex){    fprintf(stderr, t);    if (ex)	exit(0);}void pm(float *mbr){    int i;    for (i = 0; i < 8; i++)	printf("%f..%f ", mbr[2*i], mbr[2*i+1]);    printf("\n");}float page_access;class Timer{    float dist_time_cpu;     float dist_time;     clock_t clock_start, clock_end;    time_t time_start, time_end;public:    void start();    void end();};void Timer::start(){    clock_start = clock();    time (&time_start);}void Timer::end(){    time (&time_end);    clock_end = clock ();    dist_time_cpu = (float) (clock_end - clock_start) / 	(float) CLOCKS_PER_SEC;    dist_time = difftime(time_end, time_start);        printf("%f sec cpu,   %f sec real\n", 	   dist_time_cpu, dist_time);}void usage(){    printf("X-tree usage:\n");    printf("x-tree [command] [parameter]\n");    printf("Available commands are:\n");    printf("c  [dim]                             create X-tree of dimension dim\n");    printf("re [dim] [filename] [dim_data] [num] insert num vectors from file filename of dimension dim\n");    printf("fu [dim] [num]                       insert num uniformlly distributed vectors of dimension dim\n");    printf("w  [dim]                             \n");}XTree<DATA> * create_tree(char *filename, int dimension)// neuen Baum erzeugen{    return new XTree<DATA>(filename, BLK_SIZE, 4, dimension);}XTree<DATA> * open_tree(char *filename)// Baum 鰂fnen{    return new XTree<DATA>("test.xt", 4);}void read_data(XTree<DATA> *xt, char *filename, int dim_data, int anz, int dim)  // liest Daten aus einer Datei in den Baum ein{    Timer t;    FILE *fp;    int j, wie_oft;    DATA *d;	    // Baum fuellen	    wie_oft = dim_data / dim;    if (wie_oft == 0)	error("cannot read vectors larger than dim_data from filename",	      TRUE);        fp = fopen(filename, "rb");        printf("reading %d vectors into index of dimension %d\n",	   anz, dim);        if (fp == NULL)	error("error opening founew.dump", TRUE);    t.start();    for (j = 0; j < anz && !abort_flag; j++ )    {	d = new DATA(&dim);	fread(d->data, sizeof(float), dim, fp);		xt->insert(d);		if (j % 500 == 0)	    printf("did %d\n",j);	delete d;    }    t.end();    fclose(fp);} void fill_uniform(XTree<DATA> *xt, int dim, int anz)// fuellt den Baum mit gleichverteilten Vektoren auf{    int j, l;    Timer t;    DATA *d;    // Baum fuellen	    t.start();    for (j = 0; j < anz && !abort_flag; j++ )    {	d = new DATA(&dim);	for(l = 0; l < dim; l++)	    d->data[l] = drand48();		xt->insert(d);	delete d;		if (j % 50 == 0)	    printf("did %d\n",j);    }    t.end();}void overlap(XTree<DATA> *xt, int dim)// berechnet Ueberlappung im Directory des Baums{    int i, j, l, all, num;    int nodes_b[20];   // Anzahl der Knoten pro Tiefe    int nodes_t[20];       int nodes_s[20];       int nodes_a[20];       float *mbr;    float mi[30], ma[30], ex[30];    DATA *d;        for (i = 0; i < 20; i++)	nodes_t[i] = nodes_s[i] = nodes_b[i] = nodes_a[i] = 0;        // bestimme Anzahl der Knoten pro level    xt->nodes(nodes_a);        // bestimme 1 % Anfragepunkte    all = xt->get_num();    num = all / 100;        printf("querying %d of %d data\n", num, all);    xt->load_root();    mbr = xt->root_ptr->get_mbr();        for (i = 0; i < dim; i++)    {	ma[i] = -MAXREAL;	mi[i] = MAXREAL;    }        for (i = 0; i < dim; i++)    {	ma[i] = max(mbr[2*i+1], ma[i]);	mi[i] = min(mbr[2*i], mi[i]);    }        for (i = 0; i < dim; i++)	ex[i] = ma[i] - mi[i];        for (i = 0; i < num; i++)    {	d = xt->get(rand()/10);	// d = new DATA(&dim);	// for(l = 0; l < dim; l++)	   //  d->data[l] = ma[l] - ex[l] * drand48();		for (j = 0; j < 20; j++)	    nodes_b[j] = 0;      		xt->overlapping(d->data, nodes_b);		for (j = 0; j < 20; j++)	{	    nodes_s[j] += nodes_b[j];	    if (nodes_b[j] > 1)		nodes_t[j]++;	}	delete d;    }        for (i = 0; i < 5; i++)    {	printf("nodes accessed on level %d: %f,  %f of %d\n", i, 	       (float)nodes_t[i]/(float)num, 	       (float)nodes_s[i]/(float)num, nodes_a[i]);    }}void nearest_neighbour(XTree<DATA> *xt, int dim)// stellt gleichverteilte Nearest Neighbour queries{    int z, l;    DATA *d, *p;        // alten Baum laden    srand(12345);        printf("tree is filled now --> nearest neighbour search von (0.05)^5 \n");    for(z = 0; z < 1; z++)    {	page_access = 0.0;	d = new DATA(&dim);	for(l = 0; l < dim; l++)	    d->data[l] = drand48();		printf("Query-Point :");	d->print();		p = new DATA(&dim);	for(l = 0; l < dim; l++)  	    p->data[ l ] = 2.0;		xt->nearest_neighbour_search( d, p);		printf("\nNearest:");	p->print(); 	delete p;	delete d;		printf("\nQuery-Nummer: %d Plattenzugriffe: %f \n\n",	       z, page_access);	    }}void point_query(XTree<DATA> *xt, int dim)// stellt gleichverteilte point queries{    float all_page;    int nn, k, l;    Timer t;    DATA *d;        // alten Baum laden    srand(2314);        t.start();    all_page = 0.0;    for (nn = 0; nn < NUM_TRIES; nn++)    {	page_access = 0.0;		l = rand()/10;	printf("/%d/\n", l);	d = xt->get(l);		xt->point_query(d->data);		delete d;		all_page += page_access;	printf(".");	fflush(stdout);    }    printf("average (%d) page_accesses: %f \n\n", 	   NUM_TRIES, all_page / NUM_TRIES);    t.end();}void k_nearest_neighbour(XTree<DATA> *xt, int dim, int k)// stellt gleichverteilte Nearest-Neighbour queries{    SortedLinList<DATA> *res;    float all_page;    int nn, l, cache_size;    Timer t;    DATA *d;        // alten Baum laden     srand(907932);        // berechne Gewichte fuer Cache    cache_size = (int) ((12 * dim * 			 (xt->num_of_dnodes+xt->num_of_inodes)) / BLK_SIZE);    xt->set_node_weight(cache_size);        t.start();    all_page = 0.0;    for(nn = 0; nn < 10; nn++)    {	page_access = 0.0;		d = new DATA(&dim);	for(l = 0; l < dim; l++)	    d->data[l] = drand48();	d->distanz = MAXREAL;	//	    printf("Query-Point :");//	    d->print();		res = new SortedLinList<DATA>;	xt->k_nearest_neighbour_search(d, k, res);	// 	    printf("\n%d Nearest:\n",k);// 	    for(n = 0; n < k; n++)// 	    {//         	printf("%1d.Nearest: Distanz: %f Point: ",n,// 		       res->get(n)->distanz);// 		res->get(n)->print();// 	    } 		delete d;	delete res;		all_page += page_access;	printf(".");	fflush(stdout);    }    printf("average (10) page_accesses (%d NN): %f \n\n", 	   k, all_page / 10.0);    t.end();}main(int argc, char *argv[]){    XTree<DATA> *xt;    char filename[255];     int dim;    abort_flag = FALSE;    signal(SIGTERM, abort);        if (argc < 2)    {	usage();	exit(1);    }    dim = atoi(argv[2]);    if (dim < 1)    {	usage();	exit(1);    }    strcpy(filename, "test.xt");    if (!strcmp(argv[1], "c"))	xt = create_tree(filename, dim);    else if (!strcmp(argv[1], "re"))    {	// alten Baum laden	xt = open_tree(filename);		// Daten einlesen	read_data(xt, argv[4], atoi(argv[5]), atoi(argv[5]), atoi(argv[5]));    }    else if (!strcmp(argv[1], "fu"))    {	// alten Baum laden	xt = open_tree(filename);		fill_uniform(xt, dim, atoi(argv[3]));     }    else if (!strcmp(argv[1], "overlap"))    {	xt = open_tree(filename);	// Ueberlappung ausgeben	overlap(xt, dim);    }    else if (!strcmp(argv[1], "w"))    {	FILE *f;	xt = open_tree(filename);	f = fopen("mbr","w");	xt->write_info(f);	fclose(f);    }    else if (!strcmp(argv[1], "pq"))    {	xt = open_tree(filename);	point_query(xt, dim);    }    else if (!strcmp(argv[1], "nn"))    {	xt = open_tree(filename);	nearest_neighbour(xt, dim);    }    else if (!strcmp(argv[1], "knn"))    {	xt = open_tree(filename);	k_nearest_neighbour(xt, dim, atoi(argv[3]));    }    else     {	usage();	exit(1);    }    delete xt;    return 0;}