Tree-M/MT/BulkLoad.cpp

/*********************************************************************
*                                                                    *
* Copyright (c) 1997,1998, 1999                                      *
* Multimedia DB Group and DEIS - CSITE-CNR,                          *
* University of Bologna, Bologna, ITALY.                             *
*                                                                    *
* All Rights Reserved.                                               *
*                                                                    *
* Permission to use, copy, and distribute this software and its      *
* documentation for NON-COMMERCIAL purposes and without fee is       *
* hereby granted provided  that this copyright notice appears in     *
* all copies.                                                        *
*                                                                    *
* THE AUTHORS MAKE NO REPRESENTATIONS OR WARRANTIES ABOUT THE        *
* SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING  *
* BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY,      *
* FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHOR  *
* SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A      *
* RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS    *
* DERIVATIVES.                                                       *
*                                                                    *
*********************************************************************/

#ifdef UNIX
#include <unistd.h>
#endif
#include "MT.h"

extern double MIN_UTIL;

// find the node having the minimum number of children
// this is used in the redistributing phase of the BulkLoad algorithm
int
FindMin(int *children, int max)
{
        int j, jmin=0;

        for(j=1; j<max; j++)
                if(children[j]<children[jmin]) jmin=j;
        return jmin;
}

// return root level+1 (the height of the tree)
// this is used in the "splitting" phase of the BulkLoad algorithm
int
MT::MaxLevel() const
{
        GiSTnode *root;
        GiSTpath path;
        int i;

        path.MakeRoot();
        root=ReadNode(path);
        i=root->Level();
        delete root;
        return i+1;
}

// split this M-tree into a list of trees having height level
// this is used in the "splitting" phase of the BulkLoad algorithm
GiSTlist<char *> *
MT::SplitTree(int *ncreated, int level, GiSTlist<MTentry *> *children, char *name)
// ncreated is the number of created sub-trees,
// level is the split level for the tree,
// children is the list of the parents of each sub-tree,
// name is the root for the sub-trees names
// the return value is the list of splitted sub-trees
{
        GiSTlist<char *> *trees=new GiSTlist<char *>;   // this is the results list
        GiSTlist<MTnode *> *oldList=new GiSTlist<MTnode *>;     // this is the nodes list
        GiSTpath path;
        MTnode *node=new MTnode;        // this is because the first operation on node is a delete
        char newname[50];

        path.MakeRoot();
        oldList->Append((MTnode *)ReadNode(path));
        do {    // build the roots list
                GiSTlist<MTnode *> *newList=new GiSTlist<MTnode *>;     // this is the list of the current level nodes

                while(!oldList->IsEmpty()) {
                        delete node;    // delete the old node created by ReadNode
                        node=oldList->RemoveFront();    // retrieve next node to be examined
                        path=node->Path();
                        for(int i=0; i<node->NumEntries(); i++) {       // append all its children to the new list
                                MTentry *e=(MTentry *)(*node)[i].Ptr();

                                path.MakeChild(e->Ptr());
                                newList->Append((MTnode *)ReadNode(path));
                                path.MakeParent();
                        }
                }
                delete oldList;
                oldList=newList;
        } while(node->Level()>level);   // stop if we're at the split level
        delete node;
        while(!oldList->IsEmpty()) {    // now append each sub-tree to its root
                MT *subtree=new MT (4096);
                assert (!"fixme: pagesize above taken wherefrom?");
                MTnode *newnode;

                node=oldList->RemoveFront();
                sprintf(newname, "%s.%i", name, ++(*ncreated));
                unlink(newname);        // if this M-tree already exists, delete it
                subtree->Create(newname);       // create a new M-tree
                path.MakeRoot();
                newnode=(MTnode *)subtree->ReadNode(path);      // read the root of the tree
                subtree->Append(newnode, (MTnode *)node->Copy());       // append the sub-tree of current node to the root of this M-tree
                children->Append(node->Entry());        // insert the root entry into the list
                trees->Append(strdup(newname)); // insert the new M-tree name into the list
                delete node;
                delete newnode;
                delete subtree;
        }
        delete oldList;
        return trees;
}

// load this M-tree with n data using the BulkLoad algorithm [CP98]
void
MT::BulkLoad(MTentry **data, int n, double padFactor, char *name)
// data is an array of n entries
// padFactor is the maximum node utilization (use 1)
// name is the name of the tree
{
        int i, Size=0, totSize, addEntrySize=(sizeofEntry()? sizeof(GiSTpage): sizeof(GiSTlte)+sizeof(GiSTpage)), minSize=(int)(Store()->PageSize()*MIN_UTIL), NumEntries;      // this is the total size of entries

        if(sizeofEntry()) Size=n*(sizeof(GiSTpage)+sizeofEntry());      // (only valid if we've fixed size entries)
        else for(i=0; i<n; i++) Size+=sizeof(GiSTlte)+sizeof(GiSTpage)+data[i]->CompressedLength();
        totSize=Size+GIST_PAGE_HEADER_SIZE+sizeof(GiSTlte);
        NumEntries=(int)(Store()->PageSize()*padFactor*n)/totSize;
//      cout << "exp. size=" << totSize << endl;
        if(totSize>Store()->PageSize()) {       // we need to split the entries into several sub-trees
                GiSTlist<char *> nameslist, othernameslist;     // list of the sub-trees names
                GiSTlist<MTentry *> plist, parentslist; // lists of the root entries of each sub-tree
                GiSTlist<int> *lists=NULL;      // list of entries for each sub-tree
                GiSTlist<double> *dists=NULL;   // list of distances for each sub-tree
                char **trees;   // array of the sub-trees names
                GiSTlist<MTnode *> *oldList=new GiSTlist<MTnode *>;
                GiSTpath path;
                MTentry ***arrays;      // array of the entries for each sub-tree
                MTentry **parents;      // array of the root entries for each sub-tree
                MTnode *node=NULL;
                GiSTlist<double *> *distm;      // distance matrix
                int s=(int)MAX(MIN(NumEntries, ceil(((float)n)/NumEntries)), NumEntries*MIN_UTIL);      // initial number of samples
                int j, nsamples, *samples=new int[s], *sizes=NULL, *ns=NULL, ncreated=0, minLevel=MAXINT, nInit, l, iters=0, MAXITER=s*s;
                char newname[50];
                BOOL *sampled=new BOOL[n];      // is this entry in the samples set?

//              cout << "NE*pF=" << NumEntries*padFactor << ", n/NE*pF=" << n/floor(NumEntries*padFactor) << ", s=" << s << endl;
                distm=(GiSTlist<double *> *)calloc(s,sizeof(GiSTlist<double *>));
                do {    // sampling phase
                        iters++;
                        if(iters>1) {   // this is a new sampling phase
//                              cout << "Re-sampling: " << iters << "/" << MAXITER << endl;
                                while(!lists[0].IsEmpty()) {
                                        lists[0].RemoveFront();
                                        dists[0].RemoveFront();
                                }
                                delete []lists;
                                delete []dists;
                                delete []sizes;
                                delete []ns;
                                while(!distm[0].IsEmpty()) delete []distm[0].RemoveFront();     // empty the distance list
                                for(i=1; i<s; i++) distm[i].front=distm[i].rear=NULL;
                        }
//                      if(iters>=MAXITER) minSize=0;
                        if(iters>=MAXITER) {
                                cout << "Too many loops in BulkLoad!\nPlease select a lower minimum node utilization or a bigger node size.\n";
                                exit(1);
                        }
                        nsamples=0;
                        for(i=0; i<n; i++) sampled[i]=FALSE;
                        // pick samples to create parents
                        while(nsamples<s) {
                                do i=PickRandom(0, n);
                                while(sampled[i]);
                                sampled[i]=TRUE;
                                samples[nsamples++]=i;
                        }
//                      cout << "Samples:\n";
//                      for(i=0; i<s; i++) cout << "\t" << i << ":\t" << data[samples[i]];
                        lists=new GiSTlist<int>[s];
                        dists=new GiSTlist<double>[s];
                        sizes=new int[s];
                        ns=new int[s];
                        for(i=0; i<s; i++) {
                                sizes[i]=GIST_PAGE_HEADER_SIZE+sizeof(GiSTlte);
                                ns[i]=1;
                        }
                        for(i=0; i<s; i++) distm[i].Prepend(new double[s]);
                        for(i=0; i<s; i++) {    // compute the relative distances between samples
                                for(j=0; j<i; j++)
                                        distm[j].front->entry[i]=(distm[i].front->entry[j]=data[samples[j]]->object().distance(data[samples[i]]->object()));
                                distm[i].front->entry[i]=0;
                        }
                        for(i=0; i<n; i++) {    // assign each entry to its nearest parent
//                              cout << "Now assigning " << data[i];
                                if(sampled[i]) {
                                        for(j=0; samples[j]!=i; j++);
                                        lists[j].Prepend(i);    // insert the entry in the right list
                                        dists[j].Prepend(0);
                                        sizes[j]+=addEntrySize+data[i]->CompressedLength();
//                                      cout << "\tAssigned (0) to " << j << ", " << data[samples[j]];
                                }
                                else {  // here we optimize the distance computations (like we do in the insert algorithm)
                                        double *dist=new double[s];
                                        int minindex=0;

                                        dist[0]=data[samples[0]]->object().distance(data[i]->object());
                                        for(j=1; j<s; j++) {
                                                BOOL cont=TRUE;

                                                dist[j]=-1;
                                                if(fabs(data[samples[j]]->Key()->distance-data[i]->Key()->distance)>dist[minindex]) continue;   // pruning for reference point (parent)
                                                for(int k=0; (k<j)&&cont; k++)  // pruning for reference points (other samples)
                                                        if(dist[k]<0) continue;
                                                        else cont=(fabs(dist[k]-distm[j].front->entry[k])<dist[minindex]);
                                                if(!cont) continue;
                                                dist[j]=data[samples[j]]->object().distance(data[i]->object()); // we have to compute this distance
                                                if(dist[j]<dist[minindex]) minindex=j;
                                        }
//                                      cout << "\tAssigned (" << dist[minindex] << ") to " << minindex << ", " << data[samples[minindex]];
                                        lists[minindex].Append(i);
                                        dists[minindex].Append(dist[minindex]);
                                        sizes[minindex]+=addEntrySize+data[i]->CompressedLength();
                                        ns[minindex]++;
                                        if(sizes[minindex]>=minSize) delete []dist;
                                        else distm[minindex].Append(dist);
                                }
                        }
                        // redistribute underfilled parents
//                      cout << "Underfilled parents redistribution...\n";
                        while(sizes[i=FindMin(sizes, nsamples)]<minSize) {
                                GiSTlist<int> list=lists[i];
                                GiSTlist<double *> dlist=distm[i];

                                while(!dists[i].IsEmpty()) dists[i].RemoveFront();
//                              cout << "Redistributing " << i << "' set (" << sizes[i] << "/" << minSize << ")...\n";
                                for(j=0; j<nsamples; j++)
                                        for(GiSTlistnode<double *> *lnode=distm[j].front; lnode; lnode=lnode->next) lnode->entry[i]=lnode->entry[nsamples-1];
                                // substitute this set with last set 
                                distm[i]=distm[nsamples-1];
                                lists[i]=lists[nsamples-1];
                                dists[i]=dists[nsamples-1];
                                samples[i]=samples[nsamples-1];
                                sizes[i]=sizes[nsamples-1];
                                ns[i]=ns[nsamples-1];
                                nsamples--;
                                while(!list.IsEmpty()) {        // assign each entry to its nearest parent
                                        double *d=dlist.RemoveFront();
                                        int k=list.RemoveFront(), index, minindex=-1;
//                                      cout << "Now assigning " << data[k];

                                        for(index=0; (index<nsamples)&&(minindex<0); index++)   // search for a computed distance
                                                if(d[index]>0) minindex=index;
                                        if(minindex<0) {        // no distance was computed (i.e. all distances were pruned)
                                                d[0]=data[samples[0]]->object().distance(data[k]->object());
                                                minindex=0;
                                        }
                                        for(index=0; index<nsamples; index++) {
                                                BOOL cont=TRUE;

                                                if(index==minindex) continue;
                                                if(d[index]<0) {        // distance wasn't computed
                                                        if(fabs(data[samples[index]]->Key()->distance-data[k]->Key()->distance)>d[minindex]) continue;  // pruning for reference point (parent)
                                                        for(l=0; (l<index)&&cont; l++)  // pruning for reference points (other samples)
                                                                if(d[l]<0) continue;
                                                                else cont=(fabs(d[l]-distm[index].front->entry[l])<d[minindex]);
                                                        if(!cont) continue;
                                                        d[index]=data[samples[index]]->object().distance(data[k]->object());    // we have to compute this distance
                                                }
                                                if(d[index]<d[minindex]) minindex=index;
                                        }
//                                      cout << "\tAssigned (" << d[minindex] << ") to " << minindex << ", " << data[samples[minindex]];
                                        lists[minindex].Append(k);
                                        dists[minindex].Append(d[minindex]);
                                        sizes[minindex]+=addEntrySize+data[k]->CompressedLength();
                                        ns[minindex]++;
                                        if(sizes[minindex]>=minSize) delete []d;
                                        else distm[minindex].Append(d);
                                }
                                assert(dlist.IsEmpty());
                        }
                } while(nsamples==1);   // if there's only one child, repeat the sampling phase
//              cout << "Samples:\n";
//              for(i=0; i<nsamples; i++) cout << "\t" << i << ": " << data[samples[i]];
                arrays=new MTentry **[nsamples];
                for(i=0; i<nsamples; i++) {     // convert the lists into arrays
                        arrays[i]=new MTentry *[ns[i]];
                        for(j=0; j<ns[i]; j++) {
                                int k=lists[i].RemoveFront();

                                arrays[i][j]=(MTentry *)data[k]->Copy();
                                arrays[i][j]->Key()->distance=dists[i].RemoveFront();
                        }
                        assert(lists[i].IsEmpty());
                        assert(dists[i].IsEmpty());
                }
                delete []dists;
                delete []lists;
                for(i=0; i<nsamples; i++)
                        while(!distm[i].IsEmpty())
                                delete [](distm[i].RemoveFront());
                free(distm);
                // build an M-tree under each parent
                nInit=nsamples;
//              cout << "Now building " << nsamples << " sub-trees...\n";
                MT *tree=new MT (4096);
                assert (!"fixme: pagesize above taken wherefrom?");

//              for(i=0; i<nsamples; i++) cout << i+1 << "' set: " << ns[i] << endl;
                for(i=0; i<nInit; i++) {
                        MTnode *root;
                        GiSTpath path;

                        sprintf(newname, "%s.%i", name, ++ncreated);
                        unlink(newname);
                        tree->Create(newname);  // create the new sub-tree
//                      cout << "Now building sub-tree " << newname << " on " << ns[i] << " data (exp. size=" << sizes[i] << ")...\n";
                        tree->BulkLoad(arrays[i], ns[i], padFactor, newname);   // insert the data into the sub-tree
//                      cout << "Tree level=" << tree->MaxLevel() << endl;
                        // if the root node is underfilled, we have to split the tree
                        path.MakeRoot();
                        root=(MTnode *)tree->ReadNode(path);
                        if(root->IsUnderFull(*Store())) {
                                GiSTlist<MTentry *> *roots=new GiSTlist<MTentry *>;
                                GiSTlist<char *> *list=tree->SplitTree(&ncreated, tree->MaxLevel()-1, roots, name);     // split the tree

                                nsamples--;
                                while(!list->IsEmpty()) {       // insert all the new trees in the sub-trees list
                                        MTentry *e=roots->RemoveFront();

                                        othernameslist.Append(list->RemoveFront());
                                        for(j=0; j<n; j++) if(data[j]->object()==e->object()) { // append also the root entry to the parents list
//                                              cout << "parent=" << data[j];
                                                plist.Append(data[j]);
                                                j=n;
                                        }
                                        delete e;
                                        nsamples++;
                                }
                                delete list;
                                delete roots;
                                minLevel=MIN(minLevel, tree->MaxLevel()-1);
                        }
                        else {
                                char *tmp=new char[50];

                                strcpy(tmp, newname);
                                othernameslist.Append(tmp);
                                plist.Append(data[samples[i]]);
                                minLevel=MIN(minLevel, tree->MaxLevel());
                        }
                        delete root;
                        tree->Close();
                        delete tree->Store();   // it was created in tree->Create()
                }
                for(i=0; i<nInit; i++)  {
                        for(j=0; j<ns[i]; j++) delete arrays[i][j];
                        delete []arrays[i];
                }
                delete []arrays;
                while(!plist.IsEmpty()) {       // insert the trees in the list (splitting if necessary)
                        MTentry *parent=plist.RemoveFront();
                        char *tmp=othernameslist.RemoveFront();

                        strcpy(newname, tmp);
                        delete []tmp;
                        tree->Open(newname);
//                      cout << ": Tree level=" << tree->MaxLevel() << " (" << minLevel << ")\n";
                        if(tree->MaxLevel()>minLevel) { // we have to split the tree to reduce its height
//                      cout << "level too high!!! (min=" << minLevel << ") Splitting the tree...\n";
                                GiSTlist<MTentry *> *roots=new GiSTlist<MTentry *>;
                                GiSTlist<char *> *list=tree->SplitTree(&ncreated, minLevel, roots, name);       // split the tree

                                nsamples--;
                                while(!list->IsEmpty()) {       // insert all the new trees in the sub-trees list
                                        MTentry *e=roots->RemoveFront();

                                        nameslist.Append(list->RemoveFront());
                                        for(j=0; j<n; j++) if(data[j]->object()==e->object()) { // append also the root entry to the parents list
//                                              cout << "parent=" << data[j];
                                                parentslist.Append(data[j]);
                                                j=n;
                                        }
                                        delete e;
                                        nsamples++;
                                }
                                delete list;
                                delete roots;
                        }
                        else {  // simply insert the tree and its root to the lists
                                char *tmp=new char[50];

                                strcpy(tmp, newname);
                                nameslist.Append(tmp);
//                              cout << "parent=" << data[samples[i]];
                                parentslist.Append(parent);
                        }
                        tree->Close();
                        delete tree->Store();   // it was created in tree->Open()
                }
                parents=new MTentry *[nsamples];
                trees=new char *[nsamples];
                for(i=0; i<nsamples; i++) {     // convert the lists into arrays
                        trees[i]=nameslist.RemoveFront();
                        parents[i]=parentslist.RemoveFront();
                }
                // build the super-tree upon the parents
                sprintf(newname, "%s.0", name);
//              cout << "Now building super-tree " << newname << " on " << nsamples << " data...\n";
                BulkLoad(parents, nsamples, padFactor, newname);
                // attach each sub-tree to the leaves of the super-tree
                path.MakeRoot();
                node=(MTnode *)ReadNode(path);
                oldList->Append(node);
//              cout << "super-tree built!\n";
                l=node->Level();
                while(l>0) {    // build the leaves list for super-tree
                        GiSTlist<MTnode *> *newList=new GiSTlist<MTnode *>;

                        while(!oldList->IsEmpty()) {
                                node=oldList->RemoveFront();
                                path=node->Path();
                                node->SetLevel(node->Level()+minLevel); // update level of the upper nodes of the super-tree
                                WriteNode(node);
                                for(i=0; i<node->NumEntries(); i++) {
                                        MTentry *e=(MTentry *)(*node)[i].Ptr();

                                        path.MakeChild(e->Ptr());
                                        newList->Append((MTnode *)ReadNode(path));
                                        path.MakeParent();
                                }
                                delete node;
                        }
                        delete oldList;
                        oldList=newList;
                        l--;
                }
//              cout << "Finished " << newname << endl;
                while(!oldList->IsEmpty()) {    // attach each sub-tree to its leaf
                        GiSTpath rootpath;

                        rootpath.MakeRoot();
                        node=oldList->RemoveFront();    // retrieve next leaf (root of sub tree)
                        node->SetLevel(minLevel);       // update level of the root of the sub-tree
                        path=node->Path();
                        for(i=0; i<node->NumEntries(); i++) {
                                MTnode *newnode=(MTnode *)CreateNode();
                                MTentry *e=(MTentry *)(*node)[i].Ptr();
                                GiSTpath newpath;

                                path.MakeChild(Store()->Allocate());
                                newnode->Path()=path;
                                e->SetPtr(path.Page());
                                path.MakeParent();
                                for(j=0; e->object()!=parents[j]->object(); j++);       // search the tree to append
                                tree->Open(trees[j]);
//                              cout << "Now appending sub-tree " << trees[j] << endl;
                                Append(newnode, (MTnode *)tree->ReadNode(rootpath));    // append this sub-tree to the super-tree
                                tree->Close();
                                delete tree->Store();   // it was created in tree->Open()
                                newpath=newnode->Path();
                                delete newnode;
                        }
                        WriteNode(node);
                        delete node;
                }
                tree->Open(trees[0]);   // in order to destroy the object tree
                delete tree;
                for(i=0; i<nsamples; i++) delete []trees[i];
                delete []trees;
                // update radii of the upper nodes of the result M-tree
                path.MakeRoot();
                node=(MTnode *)ReadNode(path);
                oldList->Append(node);
                l=node->Level();
                while(l>=minLevel) {    // build the list of the nodes which radii should be recomputed
                        GiSTlist<MTnode *> *newList=new GiSTlist<MTnode *>;

                        while(!oldList->IsEmpty()) {

                                node=oldList->RemoveFront();
                                path=node->Path();
                                for(i=0; i<node->NumEntries(); i++) {
                                        MTentry *e=(MTentry *)(*node)[i].Ptr();

                                        path.MakeChild(e->Ptr());
                                        newList->Append((MTnode *)ReadNode(path));
                                        path.MakeParent();
                                }
                                delete node;
                        }
                        delete oldList;
                        oldList=newList;
                        l--;
                }
                while(!oldList->IsEmpty()) {    // adjust the radii of the nodes
                        MTnode *node=oldList->RemoveFront();

                        AdjKeys(node);
                        delete node;
                }
                // be tidy...
                delete oldList;
                delete []parents;
                delete []sizes;
                delete []ns;
                delete []sampled;
                delete []samples;
                for(i=0; i<=ncreated; i++) {    // delete all temporary sub-trees
                          sprintf(newname, "%s.%i", name, i);
                          unlink(newname);
                }
        }
        else {  // we can insert all the entries in a single node
                GiSTpath path;
                GiSTnode *node;

                path.MakeRoot();
                node=ReadNode(path);
                for(i=0; i<n; i++)
                        node->Insert(*(data[i]));
                assert(!node->IsOverFull(*Store()));
//              cout << "real size=" << node->Size() << endl;
                WriteNode(node);
                delete node;
        }
}

// append the sub-tree rooted at from to the node to
// this is used in the "append" phase of the BulkLoad algorithm
void
MT::Append(MTnode *to, MTnode *from)
{
        GiSTlist<MTnode *> *oldList=new GiSTlist<MTnode *>;     // list of the nodes to append
        GiSTlist<GiSTpath> pathList;
        MT *fromtree=(MT *)from->Tree();
        MTnode *node=new MTnode, *newnode;

//      cout << "Appending " << from;
        oldList->Append(from);
        pathList.Append(to->Path());
        do {
                GiSTlist<MTnode *> *newList=new GiSTlist<MTnode *>;

                while(!oldList->IsEmpty()) {
                        GiSTpath newpath=pathList.RemoveFront();

                        delete node;
                        node=oldList->RemoveFront();
                        newnode=(MTnode *)ReadNode(newpath);
//                      cout << "Inserting " << node->NumEntries() << " entries:\n";
                        for(int i=0; i<node->NumEntries(); i++) {
                                MTentry *e=(MTentry *)(*node)[i].Ptr()->Copy();

                                if(node->Level()>0) {   // if node isn't a leaf, we've to allocate its children
                                        GiSTpath nodepath=node->Path();
                                        MTnode *childnode=(MTnode *)CreateNode(), *fromnode;

                                        nodepath.MakeChild(e->Ptr());
                                        fromnode=(MTnode *)fromtree->ReadNode(nodepath);
                                        newList->Append(fromnode);
                                        e->SetPtr(Store()->Allocate());
                                        newpath.MakeChild(e->Ptr());
                                        childnode->Path()=newpath;
                                        childnode->SetTree(this);
                                        WriteNode(childnode);   // write the empty node
                                        pathList.Append(newpath);
                                        newpath.MakeParent();
                                        nodepath.MakeParent();
                                        delete childnode;
                                }
                                newnode->Insert(*e);
//                              cout << "\tInserted " << e;
                                delete e;
                        }
                        newnode->SetLevel(node->Level());
                        WriteNode(newnode); // write the node
//                      cout << "Created " << newnode;
                        delete newnode;
                }
                delete oldList;
                oldList=newList;
        } while(node->Level()>0);       // until we reach the leaves' level
//      cout << node;
        delete node;
        delete oldList;
}

// adjust the keys of node
// this is used during the final phase of the BulkLoad algorithm
void
MT::AdjKeys(GiSTnode *node)
{
        GiSTnode *P;
        GiSTpath parent_path=node->Path();
        GiSTentry *entry, *actual;

        if(node->Path().IsRoot()) return;
        parent_path.MakeParent();
        P=ReadNode(parent_path);
        entry=P->SearchPtr(node->Path().Page());
        assert(entry!=NULL);
        actual=node->Union();
        actual->SetPtr(node->Path().Page());
        ((MTkey *)actual->Key())->distance=((MTkey *)entry->Key())->distance;   // necessary to keep track of the distance from the parent
        if(!entry->IsEqual(*actual)) {  // replace this entry
                int pos=entry->Position();

                P->DeleteEntry(pos);
                P->Insert(*actual);
/*              if(P->IsOverFull(*Store())) {   // this code should be unnecessary (if we have fixed length entries)
                  GiSTpage page=node->Path().Page();

                  Split(&P, *actual);
                  node->Path()=P->Path();
                  node->Path().MakeChild(page);
                }
                else {
                  WriteNode(P);
                  AdjKeys(P);
                }       */
                WriteNode(P);
                AdjKeys(P);
        }
        delete P;
        delete actual;
        delete entry;
}
Revision:	1.2
Committed:	Wed May 23 02:11:14 2001 UTC (23 years ago) by root
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.1:	+4 -2 lines
Log Message:	* empty log message *