if (v[i] < bounces[2*i] ||     // untere Grenze	    v[i] > bounces[2*i + 1])   // obere Grenze	    return FALSE;    }    return TRUE;}template <class DATA> SECTION DirEntry<DATA>::section(float *mbr)// testet, ob mbr den Eintrag irgendwo ueberlappt// Uberlappung kann nur dann nicht auf, wenn ////    ttttt eeeee////      oder////    eeeee ttttt//// diese beiden Faelle werden fuer jede Dimension getestet{    bool inside;    bool overlap;    int i;    overlap = TRUE;    inside = TRUE;    for (i = 0; i < dimension; i++)    {	if (mbr[2*i]     > bounces[2*i + 1] ||	    mbr[2*i + 1] < bounces[2*i]) 	    overlap = FALSE;	if (mbr[2*i]     < bounces[2*i] ||	    mbr[2*i + 1] > bounces[2*i + 1]) 	    inside = FALSE;    }    if (inside)	return INSIDE;    else if (overlap)	return OVERLAP;    else	return S_NONE;}template <class DATA> void DirEntry<DATA>::read_from_buffer(char *buffer){    int i;    i = 2*dimension*sizeof(float);    memcpy(bounces, buffer, i);    memcpy(&son, &buffer[i], sizeof(int));    i += sizeof(int);    memcpy(&num_of_data, &buffer[i], sizeof(int));    i += sizeof(int);    memcpy(&history, &buffer[i], sizeof(int));}template <class DATA> void DirEntry<DATA>::write_to_buffer(char *buffer){    int i;    i = 2*dimension*sizeof(float);    memcpy(buffer, bounces, i);    memcpy(&buffer[i], &son, sizeof(int));    i += sizeof(int);    memcpy(&buffer[i], &num_of_data, sizeof(int));    i += sizeof(int);    memcpy(&buffer[i], &history, sizeof(int));}template <class DATA> int DirEntry<DATA>::get_size(){    return 2*dimension * sizeof(float) + sizeof(int) + sizeof(int) + sizeof(int);}template <class DATA> XTNode<DATA>* DirEntry<DATA>::get_son(){    if (son_ptr == NULL)    {	if (son_is_data)	    son_ptr = new XTDataNode<DATA>(my_tree, son);	else	    son_ptr = new XTDirNode<DATA>(my_tree, son);    }    return son_ptr;}template <class DATA>bool DirEntry<DATA>::section_circle(DATA *center, float radius){ float r2; r2 = radius * radius; if ( (r2 - MINDIST(center,bounces )) < 1.0e-8)	return TRUE; else	return FALSE;} //////////////////////////////////////////////////////////////////////////////// XTNode//////////////////////////////////////////////////////////////////////////////template <class DATA> XTNode<DATA>::~XTNode(){}template <class DATA> XTNode<DATA>::XTNode(XTree<DATA> *rt){    my_tree = rt;     dimension = rt->dimension;     num_entries = 0;     block = -1;}template <class DATA> int XTNode<DATA>::topological_split(float **mbr, int **distribution, int *dim)// teilt ein Array von mbrs in zwei Haelften und liefert in distribution// zurueck, welche *m Eintraege in die neue Seite verschoben werden muessen// hierfuer wird der R*-Baum Split Algorithmus benutzt{#ifdef SHOWMBR	split_000++;#endif    bool lu;    int i, j, k, l, s, n, m1, dist, split_axis;    SortMbr *sml, *smu;    float minmarg, marg, minover, mindead, dead, over, 	*rxmbr, *rymbr;    // how many nodes are used?    n = get_num();    // nodes have to be filled at least 40%    m1 = (int) ((float)n * 0.40);     // sort by lower value of their rectangles    // Indexarray aufbauen und initialisieren    sml = new SortMbr[n];        smu = new SortMbr[n];        rxmbr = new float[2*dimension];    rymbr = new float[2*dimension];    // choose split axis    minmarg = MAXREAL;    for (i = 0; i < dimension; i++)    // for each axis    {        for (j = 0; j < n; j++)        {            sml[j].index = smu[j].index = j;            sml[j].dimension = smu[j].dimension = i;            sml[j].mbr = smu[j].mbr = mbr[j];        }        // Sort by lower and upper value perpendicular axis_i      	qsort(sml, n, sizeof(SortMbr), sort_lower_mbr);        qsort(smu, n, sizeof(SortMbr), sort_upper_mbr);        marg = 0.0;        // for all possible distributions of sml        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],   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;}template <class DATA> int XTNode<DATA>::overlap_free_split(float **mbr, int *split_history, int **distribution, int *dim)// teilt ein Array von mbrs in zwei Haelften und liefert in distribution// zurueck, welche *m Eintraege in die neue Seite verschoben werden muessen// hierfuer wird der X-Baum Split Algorithmus benutzt{#ifdef SHOWMBR	split_000++;#endif    bool lu;    int i, j, k, l, s, n, m1, dist, split_axis;    int split_vector, num_axis, a;    int axis[dimension];    SortMbr *sml, *smu;    float minmarg, marg, minover, mindead, dead, over, 	*rxmbr, *rymbr;    // how many nodes are used?    n = get_num();    // check split-history    split_vector = split_history[0];    for (i = 1; i < n; i++)        split_vector = split_vector & split_history[i];    if (split_vector == 0)       return 0;    // nodes have to be filled with at least one entry    m1 = 1;     // sort by lower value of their rectangles    // Indexarray aufbauen und initialisieren    sml = new SortMbr[n];        smu = new SortMbr[n];        rxmbr = new float[2*dimension];    rymbr = new float[2*dimension];        num_axis = 0;    for (i = 0; i < dimension; i++)    {        if ((split_vector & 1) == 1) {            axis[num_axis] = i;            num_axis++;        }        split_vector = split_vector >> 1;    }    // choose split axis from the above pre-selection    minmarg = MAXREAL;    for (a = 0; a < num_axis; a++)    // for each axis    {        i = axis[a];        for (j = 0; j < n; j++)        {            sml[j].index = smu[j].index = j;            sml[j].dimension = smu[j].dimension = i;            sml[j].mbr = smu[j].mbr = mbr[j];        }        // Sort by lower and upper value perpendicular axis_i      	qsort(sml, n, sizeof(SortMbr), sort_lower_mbr);        qsort(smu, n, sizeof(SortMbr), sort_upper_mbr);        marg = 0.0;        // for all possible distributions of sml        for (k = 0; k < n - 2*m1 + 1; k++)        {            // now calculate margin of R1