x_tree.h

X-tree的C++源码

	    // 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 ++ )