// recalculate # of succeeders in the tree    entries[follow].num_of_data = succ->get_num_of_data();    if (ret == SPLIT)    // Einfuegen von d in Sohn hat zum Split des Sohns gefuehrt -->    // neuen Sohn *new_succ einfuegen    {        if (get_num() == capacity)     	    error("XTDataNode::insert: maximum capacity violation", TRUE);        // update split-history of old son	entries[follow].history = entries[follow].history | (1 << dimen);		// create and insert new entry        de = new DirEntry<DATA>(dimension, my_tree);	nmbr = new_succ->get_mbr();        memcpy(de->bounces, nmbr, 2*dimension*sizeof(float));	delete [] nmbr;        de->son = new_succ->block;        de->son_ptr = new_succ;        de->son_is_data = son_is_data;        de->num_of_data = new_succ->get_num_of_data();        	// set split-history of new son        de->history = entries[follow].history;        enter(de);        if (get_num() == (capacity - 1))        // Knoten laeuft ueber --> Split        // this happens already if the node is nearly filled        // for the algorithms are more easy then        {	    if (split(&brother, &dimen) == TRUE)	    {		*dim = dimen;		*sn = brother;		printf("splitting node %d, creating %d\n", block, (*sn)->block);		ret = SPLIT;	    }	    else	    {               // no split occured in son, but supernode was created	       delete sn;	       ret = SUPERNODE;	    }	}        else      	    ret = NONE;    }    // must write page    dirty = TRUE;    return ret;}template <class DATA> DATA * XTDirNode<DATA>::get(int i){    int j, n, sum;    XTNode<DATA> *sn;    n = get_num();    sum = 0;    for (j = 0; j < n; j++)    {        sum += entries[j].num_of_data;        if (sum > i)	// i-th object is behind this node --> follow son        {            sn = entries[j].get_son();            return sn->get(i - (sum - entries[j].num_of_data));        }    }    return NULL;}template <class DATA> void XTDirNode<DATA>::region(float *mbr){    int i, n;    SECTION s;    XTNode<DATA> *succ;    n = get_num();    for (i = 0; i < n; i++)    // teste alle Rechtecke auf Ueberschneidung    {        s = entries[i].section(mbr);        if (s == INSIDE || s == OVERLAP)        {            // Rechteck ist interessant --> rekursiv weiter            succ = entries[i].get_son();            succ->region(mbr);        }    }}template <class DATA> void XTDirNode<DATA>::point_query(float *p){    int i, n;    XTNode<DATA> *succ;    n = get_num();    for (i = 0; i < n; i++)    // teste alle Rechtecke auf Ueberschneidung    {	if (entries[i].is_inside(p))        {            // Rechteck ist interessant --> rekursiv weiter            succ = entries[i].get_son();            succ->point_query(p);        }    }}template <class DATA> void XTDirNode<DATA>::range_query(float *mbr, SortedLinList<DATA> *res){    int i, n;    SECTION s;    XTNode<DATA> *succ;#ifdef ZAEHLER    page_access += my_tree->node_weight[level];#endif    n = get_num();    for (i = 0; i < n; i++)    // teste alle Rechtecke auf Ueberschneidung    {        s = entries[i].section(mbr);        if (s == INSIDE || s == OVERLAP)        {            // Rechteck ist interessant --> rekursiv weiter            succ = entries[i].get_son();            succ->range_query(mbr,res);        }    }}template <class DATA> void XTDirNode<DATA>::range_query(DATA *center, float radius, 		SortedLinList<DATA> *res){    int i, n;    bool s;    XTNode<DATA> *succ;    #ifdef ZAEHLER	page_access += my_tree->node_weight[level];    #endif    n = get_num();    for (i = 0; i < n; i++)    // teste alle Rechtecke auf Ueberschneidung    {        s = entries[i].section_circle(center,radius);        if (s)        {            // Rechteck ist interessant --> rekursiv weiter            succ = entries[i].get_son();            succ->range_query(center,radius,res);        }    }}#ifdef S3template <class DATA> void XTDirNode<DATA>::neighbours(LinList<DATA> *sl,                                 float eps,                                 Result *rs,                                 norm_ptr norm){    int i, j;    DATA *s;    float *mbr;    XTNode<DATA> *succ;    mbr = new float[2*dimension];    for (i = 0; i < get_num(); i++)    {        for (s = sl->get_first(); s != NULL; s = sl->get_next())        {           for (j = 0; j < dimension; j++)           {               mbr[2*j] = s->data[j] - eps;               mbr[2*j+1] = s->data[j] + eps;           }           if (entries[i].section(mbr) != S_NONE)           {               // Rechteck ist interessant --> rekursiv weiter               succ = entries[i].get_son();               succ->neighbours(sl, eps, rs, norm);           }        }    }    delete [] mbr;}#endif // S3template <class DATA>void XTDirNode<DATA>::nearest_neighbour_search(DATA *QueryPoint, DATA *Nearest,				float *nearest_distanz){    float *minmax_distanz;		// Array fuer MINMAXDIST aller Eintraege    int *indexliste;		// Liste (for Sorting and Prunching)    int i,j,k,last,n;    float akt_min_dist;		// minimal distanz computed upto now     float minmaxdist,mindist;        BranchList *activebranchList;    #ifdef ZAEHLER    page_access += my_tree->node_weight[level];#endif        n = get_num();        activebranchList = new BranchList [n]; // Array erzeugen mit n Elementen        for( i = 0; i < n; i++)    {	activebranchList[i].entry_number = i;	activebranchList[i].minmaxdist = MINMAXDIST(QueryPoint,entries[i].bounces);	activebranchList[i].mindist = MINDIST(QueryPoint,entries[i].bounces);	    }	        // sort branchList    qsort(activebranchList,n,sizeof(BranchList),sort_min_dist);         // prune BrunchList    last = prune_branch_list(nearest_distanz,activebranchList,n);        for( i = 0; i < last; i++)    {	entries[activebranchList[i].entry_number].get_son()->nearest_neighbour_search(QueryPoint, Nearest, nearest_distanz); 		last = prune_branch_list(nearest_distanz,activebranchList,last);    }        delete [] activebranchList;}template <class DATA>void XTDirNode<DATA>::nearest_neighbour_search(DATA *QueryPoint, 				SortedLinList<DATA> *res,				float *nearest_distanz){    float *minmax_distanz;		// Array fuer MINMAXDIST aller Eintraege    int *indexliste;		// Liste (for Sorting and Prunching)    int i,j,k,last,n;    float akt_min_dist;		// minimal distanz computed upto now     float minmaxdist,mindist;        BranchList *activebranchList;    #ifdef ZAEHLER    page_access += my_tree->node_weight[level];#endif    n = get_num();        k = res->get_num(); 	// wird haben eine k-nearest-Narbor-Query        *nearest_distanz = res->get(k-1)->distanz;  // der aktuell letzte                                                 // naechste Nachbar wird                                                // versucht zu ersetzen.    activebranchList = new BranchList [n]; // Array erzeugen mit n Elementen     for( i = 0; i < n; i++)    {	activebranchList[i].entry_number = i;	activebranchList[i].minmaxdist = MINMAXDIST(QueryPoint,entries[i].bounces);	activebranchList[i].mindist = MINDIST(QueryPoint,entries[i].bounces);	    }	    // sort_branch_list    qsort(activebranchList,n,sizeof(BranchList),sort_min_dist);      // prune_branch_list    last = prune_branch_list(nearest_distanz,activebranchList,n);    for( i = 0; i < last; i++)    {	entries[activebranchList[i].entry_number].get_son()->nearest_neighbour_search(QueryPoint, res, nearest_distanz); 		last = prune_branch_list(nearest_distanz,activebranchList,last);    }    delete [] activebranchList;}template <class DATA>void XTDirNode<DATA>::overlapping(float *p, int *nodes_t){    int i, n;    XTNode<DATA> *succ;    // ein Knoten mehr besucht    nodes_t[level]++;    n = get_num();    for (i = 0; i < n; i++)    // teste alle Rechtecke auf Ueberschneidung    {        if (entries[i].is_inside(p))        {            // Rechteck ist interessant --> rekursiv weiter            succ = entries[i].get_son();            succ->overlapping(p, nodes_t);        }    }}template <class DATA>void XTDirNode<DATA>::nodes(int *nodes_a){    int i, n;    XTNode<DATA> *succ;    // ein Knoten mehr besucht    nodes_a[level]++;    n = get_num();    for (i = 0; i < n; i++)    // teste alle Rechtecke auf Ueberschneidung    {	succ = entries[i].get_son();	succ->nodes(nodes_a);    }}template <class DATA> void XTDirNode<DATA>::write_info(FILE *f){    int i,j,n;    float *mbr;    mbr = get_mbr();    fprintf(f,"%d\n",level+1);    fprintf(f,"move %f %f\n",mbr[0],mbr[2]);    fprintf(f,"draw %f %f\n",mbr[1],mbr[2]);    fprintf(f,"draw %f %f\n",mbr[1],mbr[3]);    fprintf(f,"draw %f %f\n",mbr[0],mbr[3]);    fprintf(f,"draw %f %f\n",mbr[0],mbr[2]);    fprintf(f,"\n");    delete [] mbr;    n = get_num();    for( i = 0; i < n ; i++)	entries[i].get_son()->write_info(f);}//////////////////////////////////////////////////////////////////////////////// XTDataNode//////////////////////////////////////////////////////////////////////////////template <class DATA> XTDataNode<DATA>::XTDataNode(XTree<DATA> *rt)    : XTNode<DATA>(rt)// zugehoeriger Plattenblock muss erst erzeugt werden{    int header_size;    DATA * d;    level = 0;    // mal kurz einen Dateneintrag erzeugen und schauen, wie gross der wird..    d = new DATA(&dimension);    // von der Blocklaenge geht die Headergroesse ab    header_size = sizeof(char) + sizeof(int);    capacity = (rt->file->get_blocklength() - header_size) / d->get_size();    delete d;    // Eintraege erzeugen; das geht mit einem Trick, da C++ beim     // Initialisieren von Objektarrays nur Defaultkonstruktoren kapiert.    // Daher wird ueber statische Variablen die Information uebergeben.    XTDataNode__dimension = dimension;    data = new DATA[capacity];    // neuen Plattenblock an File anhaengen    block = rt->file->append_block(rt->block_buffer);    rt->num_of_dnodes ++;    // Plattenblock muss auf jeden Fall neu geschrieben werden    dirty = TRUE;}template <class DATA> XTDataNode<DATA>::XTDataNode(XTree<DATA> *rt, int _block)    : XTNode<DATA>(rt)// zugehoeriger Plattenblock existiert schon{    int header_size;    DATA *d;    // mal kurz einen Dateneintrag erzeugen und schauen, wie gross der wird..    d = new DATA(&dimension);    // von der Blocklaenge geht die Headergroesse ab    header_size = sizeof(char) + sizeof(int);    capacity = (rt->file->get_blocklength() - header_size) / d->get_size();    delete d;    // Eintraege erzeugen; das geht mit einem Trick, da C++ beim     // Initialisieren von Objektarrays nur Defaultkonstruktoren kapiert.    // Daher wird ueber statische Variablen die Information uebergeben.    XTDataNode__dimension = dimension;    data = new 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    block = _block;    rt->file->read_block(rt->block_buffer, block);    read_from_buffer(rt->block_buffer);    // Plattenblock muss vorerst nicht geschrieben werden    dirty = FALSE;}template <class DATA> XTDataNode<DATA>::~XTDataNode(){    if (dirty)    {	// Daten auf zugehoerigen Plattenblock schreiben	write_to_buffer(my_tree->block_buffer);	my_tree->file->write_block(my_tree->block_buffer, block);    }    delete [] data;}template <class DATA> void XTDataNode<DATA>::read_from_buffer(char *buffer){    int i, j, s;    // Level des Knotens lesen    memcpy(&level, buffer, sizeof(char));    j = sizeof(char);///////////////////////////////////////////////////////////    // da das Abspeichern des levels voellig ueberfluessig ist    // und level manchmal falsch in den Dateien steht, dieser HACK:    level = 0;///////////////////////////////