mbr[i] = entries[0].bounces[i];    n = get_num();    for (j = 1; j < n; j++)    {	for (i = 0; i < 2*dimension; i += 2)	{	    mbr[i]   = min(mbr[i],   entries[j].bounces[i]);	    mbr[i+1] = max(mbr[i+1], entries[j].bounces[i+1]);        }    }    return mbr;}template <class DATA>float* XTDirNode<DATA>::calc_mbr(DirEntry<DATA> *de, int num_entries)// Calculates the Minimal Bounding Rectangle for a set of Directory Entries {    int i, j;    float *mbr;        mbr = new float[2*dimension];    for (i = 0; i < 2*dimension; i++)        mbr[i] = de[0].bounces[i];        for (j = 0; j < num_entries; j++)    {        for (i = 0; i < 2*dimension; i += 2)	{	    mbr[i]   = min(mbr[i],   de[j].bounces[i]);	    mbr[i+1] = max(mbr[i+1], de[j].bounces[i+1]);	}    }        return mbr;}template <class DATA> void XTDirNode<DATA>::enter(DirEntry<DATA> *de){    // ist ein Einfuegen ueberhaupt moeglich?    if (get_num() > (capacity-1))        error("XTDirNode::enter: called, but node is full", TRUE);      // Eintrag an erste freie Stelle kopieren    entries[num_entries] = *de;    // jetzt gibts einen mehr    num_entries++;    // Eintrag freigeben, aber keine Nachfolgeknoten loeschen !!!!    de->son_ptr = NULL;    delete de;}template <class DATA>void XTDirNode<DATA>::adapt_node(int mult)// adapt node to a multiple of EXT_SIZE{    int i, n;    int size, upper_border;    int* intern_help;    DirEntry<DATA> *new_entries;            n = get_num();    // insure adapting to a multiple of EXT_SIZE    if (nodesize == 1)    {	size = 0;	upper_border = 4;    }    else    {	size = nodesize;	upper_border = EXT_SIZE*mult;    }        // adapt intern_block    // allocate one more intern blocks than necessary to avoid memory conflicts in    // read_from_buffer and write_to_buffer    intern_help = new int[size+EXT_SIZE*mult+1];    for (i = 0; i < nodesize; i++)	intern_help[i] = intern_block[i];    delete [] intern_block;    intern_block = intern_help;    // append new blocks to file    for (i = 0; i < upper_border; i++)	intern_block[nodesize+i] = my_tree->file->append_block(my_tree->block_buffer);    nodesize = size + EXT_SIZE * mult;    capacity = nodesize * block_capacity;        new_entries = new DirEntry<DATA>[capacity];    memcpy(new_entries, entries, n*sizeof(DirEntry<DATA>));    // delete old entries    for (i = 0; i < n; i++)    {	entries[i].bounces = NULL;	entries[i].son_ptr = NULL;    }    delete [] entries;    entries = new_entries;}template <class DATA> bool XTDirNode<DATA>::split(XTDirNode<DATA> **sn, int *dimen)// splittet den aktuellen Knoten so auf, dass m mbrs nach sn verschoben// werden und gibt TRUE zurueck, wenn der Split ausgefuehrt wird bzw. FALSE,// wenn ein Supernode erstellt wird.// In dimen wird die Split-Dimension an den aufrufenden Knoten zurueckgegeben, um dort// die Split-History zu aktualisieren.{    int i, *distribution, dist, dist2, n, dim;    float **mbr_array;    float *r1, *r2;    float a1, a2, o, overlap_relative;    int *split_hist;    DirEntry<DATA> *new_entries1, *new_entries2;    int size_of_new_node;#ifdef SHOWMBR	split_000++;#endif    // no split, if node is supernode    dim = 0;	    // wieviele sind denn nun belegt?    n = get_num();    // mbr_array allokieren und belegen    mbr_array = new floatptr[n];    split_hist = new int[n];    for (i = 0; i < n; i++)    {	mbr_array[i] = entries[i].bounces;	split_hist[i] = entries[i].history;    }        // Verteilung berechnen    dist = XTNode<DATA>::topological_split(mbr_array, &distribution, &dim);    // neues Datenarray erzeugen    // --> siehe Konstruktor    XTDirNode__dimension = dimension;    XTDirNode__my_tree = my_tree;    new_entries1 = new DirEntry<DATA>[capacity];    new_entries2 = new DirEntry<DATA>[capacity];        for (i = 0; i < dist; i++)    {	new_entries1[i] = entries[distribution[i]];    }    for (i = dist; i < n; i++)    {	new_entries2[i-dist] = entries[distribution[i]];    }        // Calculate the overlap size of the two mbrs    r1 = calc_mbr(new_entries1, dist);    r2 = calc_mbr(new_entries2, n-dist);    o = overlap(dimension, r1, r2);    a1 = area(dimension, r1);    a2 = area(dimension, r2);    overlap_relative = o / (a1+a2-o);        if (overlap_relative > MAX_OVERLAP)    {	// topological split fails -> try overlap minimal split        dist2 = XTNode<DATA>::overlap_free_split(mbr_array, split_hist, &distribution, &dim);		if (dist2 != 0)	{	    // split_axis found	    dist = dist2;	    	    // delete mbr_array and split history	    delete [] mbr_array;	    delete [] split_hist;	    	    // test for unbalanced nodes	    if (((dist < (block_capacity*MIN_FANOUT)) || ((n-dist) < (block_capacity*MIN_FANOUT))))	    {		// dirnode has to be adapted to the size of the next greater multiple of EXT_SIZE		adapt_node (((n/block_capacity+1) / EXT_SIZE) + 1);				for (i = 0; i < n; i++)		{		    new_entries1[i].bounces = NULL;		    new_entries1[i].son_ptr = NULL;                     		    new_entries2[i].bounces = NULL;		    new_entries2[i].son_ptr = NULL;                     		}		delete [] new_entries1;		delete [] new_entries2;                // Testausgabe		printf("DIRECTORY SPLIT : Creating Supernode.\n");		printf("Alter und neuer Knoten => Entries : %d, capacity : %d, nodesize : %d\n", num_entries, capacity, nodesize);				return FALSE;	    }	    else	    {		// nodes are balanced				for (i = 0; i < dist; i++)		{		    new_entries1[i] = entries[distribution[i]];		}		for (i = dist; i < n; i++)		{		    new_entries2[i-dist] = entries[distribution[i]];		}				for (i = 0; i < n; i++)		{		    entries[i].son_ptr = NULL;		}		delete [] entries;			        // decides, whether brother has to be a supernode or a regular directory node		size_of_new_node = ((((n-dist)/block_capacity+1) / EXT_SIZE) + 1)*EXT_SIZE;		if ((n-dist) < block_capacity)		{		    size_of_new_node = 1;		}		*sn = new XTDirNode<DATA>(size_of_new_node, my_tree);	    		(*sn)->son_is_data = son_is_data;		(*sn)->level = level;		// neue Datenarrays kopieren		entries = new_entries1;		(*sn)->entries = new_entries2;				// Anzahl der Eintraege berichtigen		num_entries = dist;		(*sn)->num_entries = n - dist;  // muss wegen Rundung so bleiben !!                // Testausgabe                printf("DIRECTORY SPLIT : Balanced overlap free split.\n");		printf("Alter Knoten => Entries : %d, capacity : %d, nodesize : %d\n", num_entries, capacity, nodesize);		printf("Neuer Knoten => Entries : %d, capacity : %d, nodesize : %d\n", (*sn)->num_entries, (*sn)->capacity, (*sn)->nodesize);                 		*dimen = dim;	    }                	}    }    else    {	// Datenarrays freigeben	// da die Nachfolgeknoten aber nicht geloescht werden sollen	// werden vor dem Aufruf von delete noch alle Pointer auf NULL gesetzt	for (i = 0; i < n; i++)	{	    entries[i].son_ptr = NULL;	}	delete [] entries;	// decides, whether brother has to be a supernode or a regular directory node	if ((n-dist) >= block_capacity)	{	    *sn = new XTDirNode<DATA>( (((((n-dist)/block_capacity+1) / EXT_SIZE) + 1)*EXT_SIZE), my_tree);	}	else	{	    *sn = new XTDirNode<DATA>( 1, my_tree);	}   	(*sn)->son_is_data = son_is_data;	(*sn)->level = level;			// neue Datenarrays kopieren	entries = new_entries1;	(*sn)->entries = new_entries2;		// Anzahl der Eintraege berichtigen	num_entries = dist;	(*sn)->num_entries = n - dist;  // muss wegen Rundung so bleiben !!        // Testausgabe	printf("DIRECTORY SPLIT : Topological Split.\n");	printf("Alter Knoten => Entries : %d, capacity : %d, nodesize : %d\n", num_entries, capacity, nodesize);	printf("Neuer Knoten => Entries : %d, capacity : %d, nodesize : %d\n", (*sn)->num_entries, (*sn)->capacity, (*sn)->nodesize);	*dimen = dim;    }    return TRUE;}template <class DATA> int XTDirNode<DATA>::choose_subtree(float *mbr){    int i, j, n, follow, minindex, *inside, inside_count, *over;    float *bmbr, old_o, o, omin, a, amin, f, fmin;    n = get_num();    // faellt d in einen bestehenden Eintrag ?    inside_count = 0;    inside = new int[n];    over = new int[n];    for (i = 0; i < n; i++)    {	switch (entries[i].section(mbr))	{	case INSIDE:	    inside[inside_count++] = i;	    break;	}    }    if (inside_count == 1)    // Fall 1: Rechteck faellt genau in einen Eintrag	follow = inside[0];    else if (inside_count > 1)    // Fall 2: Rechteck faellt in mehrere Eintrag --> nimm den    // mit der geringsten Flaeche (volumen!!!)    {	fmin = MAXFLOAT;	//printf("Punkt in %d von %d MBRs \n",inside_count,n);	for (i = 0; i < inside_count; i++)	{	    f = area(dimension, entries[inside[i]].bounces);	    if (f < fmin)	    {		minindex = i;      		fmin = f;       	    }       	}	follow = inside[minindex];    }    else    // Fall 3: Rechteck faellt in keinen Eintrag -->    // fuer Knoten, die auf interne Knoten zeigen:    // nimm den Eintrag, der am geringsten vergroessert wird;    // bei gleicher Vergroesserung:    // nimm den Eintrag, der die geringste Flaeche hat    //    // fuer Knoten, die auf Datenknoten zeigen:    // nimm den, der die geringste Ueberlappung verursacht    // bei gleicher Ueberlappung:    // nimm den Eintrag, der am geringsten vergroessert wird;    // bei gleicher Vergroesserung:    // nimm den Eintrag, der die geringste Flaeche hat    {       	if (son_is_data)	{            omin = MAXREAL;	    fmin = MAXREAL;	    amin = MAXREAL;	    for (i = 0; i < n; i++)	    {		// berechne die mbr, wenn mbr in entries[i] eingefuegt wird		enlarge(dimension, &bmbr, mbr, entries[i].bounces);		// calculate area and area enlargement		a = area(dimension, entries[i].bounces);		f = area(dimension, bmbr) - a;		// calculate overlap before enlarging entry_i		old_o = o = 0.0;		for (j = 0; j < n; j++)		{		    if (j != i)		    {			old_o += overlap(dimension,					 entries[i].bounces,					 entries[j].bounces);			o += overlap(dimension,				     bmbr,				     entries[j].bounces);		    }	        }	        o -= old_o;	        // is this entry better than the former optimum ?	        if ((o < omin) ||		    (o == omin && f < fmin) ||		    (o == omin && f == fmin && a < amin))	        {	       	    minindex = i;		    omin = o;		    fmin = f;		    amin = a;	        }	        delete [] bmbr;	    }        }        else        {	    fmin = MAXREAL;	    amin = MAXREAL;	    for (i = 0; i < n; i++)	    {	        // berechne die mbr, wenn mbr in entries[i] eingefuegt wird	        enlarge(dimension, &bmbr, mbr, entries[i].bounces);	        // calculate area and area enlargement	        a = area(dimension, entries[i].bounces);	        f = area(dimension, bmbr) - a;	        // is this entry better than the former optimum ?	        if ((f < fmin) ||		    (f == fmin && a < amin))	        {	       	    minindex = i;		    fmin = f;	            amin = a;	        }	        delete [] bmbr;	    }        }	// berechne die neue mbr und schreib sie in den Eintrag	enlarge(dimension, &bmbr, mbr, entries[minindex].bounces);	memcpy(entries[minindex].bounces, bmbr,	       dimension * 2 * sizeof(float));	follow = minindex;	delete [] bmbr;	// leider muss jetzt der Block auch geschrieben werden	dirty = TRUE;    }    delete [] inside;    delete [] over;    return follow;}template <class DATA> R_OVERFLOW XTDirNode<DATA>::insert(DATA *d, XTNode<DATA> **sn, int *dim)// dim references a variable in the father node, so the split history can be updated there{    int follow, dimen;    XTNode<DATA> *succ, *new_succ;    XTDirNode<DATA> *brother;    DirEntry<DATA> *de;    R_OVERFLOW ret;    float *mbr,*nmbr;        dimen = 0;        // Einfuegepfad waehlen    mbr = d->get_mbr();    follow = choose_subtree(mbr);    delete [] mbr;    // Sohn laden    succ = entries[follow].get_son();    // insert d into son    ret = succ->insert(d, &new_succ, &dimen);    *dim = dimen;    if (ret != NONE)    // if anything happend --> update bounces of entry "follow"    {        mbr = succ->get_mbr();        memcpy(entries[follow].bounces, mbr, sizeof(float) * 2*dimension);        delete [] mbr;    }