x_tree.h

X-tree的C++源码

    // 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 S3
template <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 // S3




template <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;
///////////////////////////////