// initialize mbr of R1 	    for (s = 0; s < 2*dimension; s += 2)	    {		rxmbr[s] =    MAXREAL;		rxmbr[s+1] = -MAXREAL;	    }            for (l = 0; l < m1+k; l++)            {                // calculate mbr of R1 		for (s = 0; s < 2*dimension; s += 2)	        {	            rxmbr[s] =   min(rxmbr[s],   sml[l].mbr[s]);	            rxmbr[s+1] = max(rxmbr[s+1], sml[l].mbr[s+1]);                }            }	    marg += margin(dimension, rxmbr);             // now calculate margin of R2	    // initialize mbr of R2 	    for (s = 0; s < 2*dimension; s += 2)	    {		rxmbr[s] =    MAXREAL;		rxmbr[s+1] = -MAXREAL;	    }            for ( ; l < n; l++)            {                // calculate mbr of R1 		for (s = 0; s < 2*dimension; s += 2)	        {	            rxmbr[s] =   min(rxmbr[s],   sml[l].mbr[s]);	            rxmbr[s+1] = max(rxmbr[s+1], sml[l].mbr[s+1]);                }            }	    marg += margin(dimension, rxmbr);         }        // for all possible distributions of smu       	for (k = 0; k < n - 2*m1 + 1; k++)        {            // now calculate margin of R1	    // initialize mbr of R1 	    for (s = 0; s < 2*dimension; s += 2)	    {		rxmbr[s] =    MAXREAL;		rxmbr[s+1] = -MAXREAL;	    }            for (l = 0; l < m1+k; l++)            {                // calculate mbr of R1 		for (s = 0; s < 2*dimension; s += 2)	        {	            rxmbr[s] =   min(rxmbr[s],   smu[l].mbr[s]);	            rxmbr[s+1] = max(rxmbr[s+1], smu[l].mbr[s+1]);                }            }	    marg += margin(dimension, rxmbr);             // now calculate margin of R2	    // initialize mbr of R2 	    for (s = 0; s < 2*dimension; s += 2)	    {		rxmbr[s] =    MAXREAL;		rxmbr[s+1] = -MAXREAL;	    }            for ( ; l < n; l++)            {                // calculate mbr of R1 		for (s = 0; s < 2*dimension; s += 2)	        {	            rxmbr[s] =   min(rxmbr[s],   smu[l].mbr[s]);	            rxmbr[s+1] = max(rxmbr[s+1], smu[l].mbr[s+1]);                }            }	    marg += margin(dimension, rxmbr);         }        // actual margin better than optimum?        if (marg < minmarg)        {            split_axis = i;            minmarg = marg;        }    }    /* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!! */    *dim = split_axis;        // choose best distribution for split axis    for (j = 0; j < n; j++)    {	sml[j].index = smu[j].index = j;	sml[j].dimension = smu[j].dimension = split_axis;	sml[j].mbr = smu[j].mbr = mbr[j];    }	           // Sort by lower and upper value perpendicular split axis    qsort(sml, n, sizeof(SortMbr), sort_lower_mbr);    qsort(smu, n, sizeof(SortMbr), sort_upper_mbr);        minover = MAXREAL;    mindead = MAXREAL;    // for all possible distributions of sml and snu    for (k = 0; k < n - 2*m1 + 1; k++)    {        // lower sort	// now calculate margin of R1	// initialize mbr of R1         dead = 0.0;	for (s = 0; s < 2*dimension; s += 2)	{	    rxmbr[s] =    MAXREAL;	    rxmbr[s+1] = -MAXREAL;	}	for (l = 0; l < m1+k; l++)	{	    // calculate mbr of R1 	    for (s = 0; s < 2*dimension; s += 2)	    {		rxmbr[s] =   min(rxmbr[s],   sml[l].mbr[s]);		rxmbr[s+1] = max(rxmbr[s+1], sml[l].mbr[s+1]);	    }            dead -= area(dimension, sml[l].mbr);	}        dead += area(dimension, rxmbr);		// now calculate margin of R2	// initialize mbr of R2 	for (s = 0; s < 2*dimension; s += 2)	{	    rymbr[s] =    MAXREAL;       	    rymbr[s+1] = -MAXREAL;	}	for ( ; l < n; l++)	{	    // calculate mbr of R1 	    for (s = 0; s < 2*dimension; s += 2)	    {		rymbr[s] =   min(rymbr[s],   sml[l].mbr[s]);		rymbr[s+1] = max(rymbr[s+1], sml[l].mbr[s+1]);	    }            dead -= area(dimension, sml[l].mbr);	}        dead += area(dimension, rymbr);	over = overlap(dimension, rxmbr, rymbr);         if ((over < minover) ||	    (over == minover) && dead < mindead)        {            minover = over;            mindead = dead;            dist = m1+k;            lu = TRUE;        }        // upper sort	// now calculate margin of R1	// initialize mbr of R1         dead = 0.0;	for (s = 0; s < 2*dimension; s += 2)	{	    rxmbr[s] =    MAXREAL;	    rxmbr[s+1] = -MAXREAL;	}	for (l = 0; l < m1+k; l++)	{	    // calculate mbr of R1 	    for (s = 0; s < 2*dimension; s += 2)	    {		rxmbr[s] =   min(rxmbr[s],   smu[l].mbr[s]);		rxmbr[s+1] = max(rxmbr[s+1], smu[l].mbr[s+1]);	    }            dead -= area(dimension, smu[l].mbr);	}        dead += area(dimension, rxmbr);		// now calculate margin of R2	// initialize mbr of R2 	for (s = 0; s < 2*dimension; s += 2)	{	    rymbr[s] =    MAXREAL;	    rymbr[s+1] = -MAXREAL;	}	for ( ; l < n; l++)	{	    // calculate mbr of R1 	    for (s = 0; s < 2*dimension; s += 2)	    {		rymbr[s] =   min(rymbr[s],   smu[l].mbr[s]);		rymbr[s+1] = max(rymbr[s+1], smu[l].mbr[s+1]);	    }            dead -= area(dimension, smu[l].mbr);	}        dead += area(dimension, rxmbr);	over = overlap(dimension, rxmbr, rymbr);         if ((over < minover) ||	    (over == minover) && dead < mindead)        {            minover = over;            mindead = dead;            dist = m1+k;            lu = FALSE;        }    }    // calculate best distribution    *distribution = new int[n];        for (i = 0; i < n; i++)    {        if (lu)            (*distribution)[i] = sml[i].index;        else            (*distribution)[i] = smu[i].index;    }    delete [] sml;    delete [] smu;    delete [] rxmbr;    delete [] rymbr;    return dist;}    //////////////////////////////////////////////////////////////////////////////// XTDirNode//////////////////////////////////////////////////////////////////////////////template <class DATA> XTDirNode<DATA>::XTDirNode(int _nodesize, XTree<DATA> *rt)    : XTNode<DATA>(rt)// according block does not yet exist// _nodesize is the size of the new node{    int header_size, i;    DirEntry<DATA> * d;    nodesize = _nodesize;    // allocate one more intern blocks than necessary to avoid memory conflicts in    // read_from_buffer and write_to_buffer    intern_block = new int[nodesize+1];    // mal kurz einen Dateneintrag erzeugen und schauen, wie gross der wird..    d = new DirEntry<DATA>(dimension, rt);    // von der Blocklaenge geht die Headergroesse ab    header_size = sizeof(bool) + sizeof(char) + sizeof(int) + sizeof(int) + sizeof(int);    block_capacity = (rt->file->get_blocklength() - header_size) / d->get_size();    capacity = block_capacity * nodesize;    delete d;    // Eintraege erzeugen, das geht mit einem Trick, da C++ beim     // Initialisieren von Objektarrays nur Defaultkonstruktoren kapiert.    // Daher wird ueber globale Variablen die Information uebergeben.    XTDirNode__dimension = dimension;    XTDirNode__my_tree = my_tree;    entries = new DirEntry<DATA>[capacity];    // neue Plattenbloecke an File anhaengen    for (i = 0; i < nodesize; i++)    {	intern_block[i] = rt->file->append_block(rt->block_buffer);    }    block = intern_block[0];    rt->num_of_inodes ++;    // Plattenblock muss auf jeden Fall neu geschrieben werden    dirty = TRUE;}template <class DATA> XTDirNode<DATA>::XTDirNode(XTree<DATA> *rt, int _block)    : XTNode<DATA>(rt)// zugehoeriger Plattenblock existiert schon{    int header_size;    int l;    DirEntry<DATA> * d;    // mal kurz einen Dateneintrag erzeugen und schauen, wie gross der wird..    d = new DirEntry<DATA>(dimension, rt);    // von der Blocklaenge geht die Headergroesse ab    header_size = sizeof(bool) + sizeof(char) + sizeof(int) + sizeof(int) + sizeof(int);    block_capacity = (rt->file->get_blocklength() - header_size) / d->get_size();    delete d;    // first reading the header of the first block, to know how many blocks exist    block = _block;        rt->file->read_block(rt->block_buffer, block);    read_header(rt->block_buffer);    capacity = nodesize * block_capacity;    // allocate one more intern blocks than necessary to avoid memory conflicts in    // read_from_buffer and write_to_buffer    intern_block = new int[nodesize+1];    intern_block[0] = block;        // Eintraege erzeugen, das geht mit einem Trick, da C++ beim    // Initialisieren von Objektarrays nur Defaultkonstruktoren kapiert.    // Daher wird ueber globale Variablen die Information uebergeben.    XTDirNode__dimension = dimension;    XTDirNode__my_tree = my_tree;    entries = new DirEntry<DATA>[capacity];    // zugehoerigen Plattenblock holen und Daten einlesen    // dies kann nicht in XTNode::XTNode(..) passieren, weil    // beim Aufruf des Basisklassenkonstruktors XTDirNode noch    // gar nicht konstruiert ist, also auch keine Daten aufnehmen kann    for (l = 0; l < nodesize; l++)    {	rt->file->read_block(rt->block_buffer, intern_block[l]);	read_from_buffer(rt->block_buffer, l);    }        // Plattenblock muss vorerst nicht geschrieben werden    dirty = FALSE;}template <class DATA> XTDirNode<DATA>::~XTDirNode(){    int l;    if (dirty)    {	// writing data to the according physical blocks	for (l = 0; l < nodesize; l++)        {	    write_to_buffer(my_tree->block_buffer, l);	    my_tree->file->write_block(my_tree->block_buffer, intern_block[l]);	}        }    delete [] entries;}template <class DATA> void XTDirNode<DATA>::read_header(char *buffer){    int j;    // Lesen, ob Sohnknoten eine Datenseite ist    memcpy(&son_is_data, buffer, sizeof(bool));    j = sizeof(bool);    // Level des Knotens lesen    memcpy(&level, &buffer[j], sizeof(char));    j += sizeof(char);    // Anzahl der belegten Eintraege lesen    memcpy(&num_entries, &buffer[j], sizeof(int));    j += sizeof(int);    // Groesse des DirNodes    memcpy(&nodesize, &buffer[j], sizeof(int));    j += sizeof(int);}template <class DATA> void XTDirNode<DATA>::read_from_buffer(char *buffer, int offset)// reads the data from buffer// offset specifies the position of the entries and the block numbers of supernodes// in entries[] respectively intern_block[]{    int i, j, s;    // Lesen, ob Sohnknoten eine Datenseite ist    memcpy(&son_is_data, buffer, sizeof(bool));    j = sizeof(bool);    // Level des Knotens lesen    memcpy(&level, &buffer[j], sizeof(char));    j += sizeof(char);    // Anzahl der belegten Eintraege lesen    memcpy(&num_entries, &buffer[j], sizeof(int));    j += sizeof(int);    // Groesse des DirNodes    memcpy(&nodesize, &buffer[j], sizeof(int));    j += sizeof(int);    // Zeiger auf naechsten Block    memcpy(&intern_block[offset+1], &buffer[j], sizeof(int));    j += sizeof(int);       s = entries[0].get_size();    for (i = 0; i < block_capacity; i++)    {	entries[i + offset*block_capacity].read_from_buffer(&buffer[j]);	entries[i + offset*block_capacity].son_is_data = son_is_data;	j += s;    }}template <class DATA> void XTDirNode<DATA>::write_to_buffer(char *buffer, int offset)// writes the data to buffer// offset has the same function as in read_from_buffer{    int i, j, s;    // Schreiben, ob Sohnknoten eine Datenseite ist    memcpy(buffer, &son_is_data, sizeof(bool));    j = sizeof(bool);    // Level des Knotens schreiben    memcpy(&buffer[j], &level, sizeof(char));    j += sizeof(char);    // Anzahl der belegten Eintraege schreiben    memcpy(&buffer[j], &num_entries, sizeof(int));    j += sizeof(int);    // Groesse des DirNodes    memcpy(&buffer[j], &nodesize, sizeof(int));    j += sizeof(int);    // Zeiger auf naechsten Block (bei supernodes)    memcpy(&buffer[j], &intern_block[offset+1], sizeof(int));    j += sizeof(int);       s = entries[0].get_size();    for (i = 0; i < block_capacity; i++)    {	entries[i + offset*block_capacity].write_to_buffer(&buffer[j]);	j += s;    }}template <class DATA> void XTDirNode<DATA>::print(){    int i, n;    n = get_num();    for (i = 0; i < n ; i++)    {         printf("(%4.1lf, %4.1lf, %4.1lf, %4.1lf)\n", 	       entries[i].bounces[0],	       entries[i].bounces[1],	       entries[i].bounces[2],	       entries[i].bounces[3]);    }    printf("level %d\n", level);}template <class DATA> int XTDirNode<DATA>::get_num_of_data(){    int i, n, sum;    n = get_num();    sum = 0;    for (i = 0; i < n ; i++)        sum += entries[i].num_of_data;    return sum;}template <class DATA> float * XTDirNode<DATA>::get_mbr()// liefert mbr des Directoryknotens{    int i, j, n;    float *mbr;    mbr = new float[2*dimension];    for (i = 0; i < 2*dimension; i ++ )