/*********************************************************************
* *
* 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. *
* *
*********************************************************************/
#include <string.h>
#include "MT.h"
#include "MTpredicate.h"
double MIN_UTIL = 0.35; // minimum node utilization
pp_function PROMOTE_PART_FUNCTION = CONFIRMED; // promotion method
pv_function PROMOTE_VOTE_FUNCTION = mM_RAD; // confirmed promotion method (if needed)
pp_function SECONDARY_PART_FUNCTION = RANDOM; // root promotion method (can't use stored distances): used only for confirmed and MAX_UB_DIST methods
r_function RADIUS_FUNCTION = LB; // mM_RAD promotion method (if needed)
int NUM_CANDIDATES = 10; // number of candidates for sampling
s_function SPLIT_FUNCTION = BAL_G_HYPERPL; // split method
extern int IOread;
// used to quick-sort the entries in a node according to their distance from the parent
int
MTentrycmp(const void *x, const void *y)
{
double d=(*(MTentry **)x)->Key()->distance-(*(MTentry **)y)->Key()->distance;
int i=0;
if(d>0) i=1;
else if(d<0) i=-1;
return i;
}
// used in Split to find the next nearest entry
int
FindMin(double *vec, int veclen)
{
int i, min_i=-1;
double min=MAXDOUBLE;
for(i=0; i<veclen; i++)
if(vec[i]<min) {
min_i=i;
min=vec[i];
}
return min_i;
}
GiSTobject *
MTnode::NCopy()
{
MTnode *newnode=(MTnode *)Copy();
if((obj==NULL)&&(Path().Level()>1)) {
MTentry *e=Entry();
obj=newnode->obj=&(e->object());
delete e;
}
newnode->InvalidateEntries();
return newnode;
}
#ifdef PRINTING_OBJECTS
void
MTnode::Print(ostream& os) const
{
if(obj!=NULL) os << *obj << " ";
// else cout << "obj NULL...\n";
os << ((MTnode *)this)->Path() << " #Entries: " << NumEntries() << ", Level " << Level();
if(IsLeaf()) os << "(Leaf)";
else os << "(Internal)";
os << ", Sibling: " << Sibling() << ", Size: " << Size() << "/" << Tree()->Store()->PageSize() << endl;
for(int i=0; i<NumEntries(); i++) (*this)[i]->Print(os);
}
#endif
int
MTnode::IsUnderFull(const GiSTstore &store) const
{
return ((MIN_UTIL>0)&&(Size()<(int)(store.PageSize()*MIN_UTIL)));
}
void
MTnode::InvalidateEntries()
{
for(int i=0; i<NumEntries(); i++)
((MTentry *)((*this)[i].Ptr()))->Key()->distance=-maxDist();
}
void
MTnode::InvalidateEntry(BOOL isNew)
{
GiSTpath path=Path();
if(path.Level()>1) {
MTnode *parent=((MT *)Tree())->ParentNode((MTnode *)this), *gparent=((MT *)Tree())->ParentNode(parent);
int i;
for(i=0; i<parent->NumEntries(); i++) { // search the entry between the parent's children
MTentry *e=(MTentry *)((*parent)[i].Ptr());
if(e->Ptr()==path.Page()) {
if(isNew) e->Key()->distance=-maxDist();
// else e->Key()->distance=-e->Key()->distance;
e->Key()->splitted=TRUE;
break;
}
}
path.MakeParent();
for(i=0; i<gparent->NumEntries(); i++) { // search the parent entry between the grandparent's children
MTentry *e=(MTentry *)((*gparent)[i].Ptr());
if(e->Ptr()==path.Page()) {
e->setmaxradius(-1);
break;
}
}
((MT *)Tree())->WriteNode(parent); // write parent node (in inconsistent state)
((MT *)Tree())->WriteNode(gparent); // write gparent node (to invalidate the parent's entry)
delete parent;
delete gparent;
}
}
MTentry *
MTnode::Entry() const
{
GiSTpath path=((MTnode *)this)->Path();
MTnode *parent=((MT *)Tree())->ParentNode((MTnode *)this);
MTentry *returnEntry=NULL;
for(int i=0; (i<parent->NumEntries())&&(returnEntry==NULL); i++)
if((*parent)[i].Ptr()->Ptr()==path.Page()) returnEntry=(MTentry *)(*parent)[i].Ptr()->Copy();
delete parent;
return returnEntry;
}
double
MTnode::distance(int i) const
{
MTentry *e=(MTentry *)((*this)[i].Ptr());
// if(e->Key()->distance>=0) cout << "Distance between " << obj << " & " << e->object() << " = " << e->Key()->distance << endl;
// else cout << "Computing distance between " << obj << " & " << e->object() << "..." << endl;
return (e->Key()->distance<0)? ((e->Key()->distance>-maxDist())? -e->Key()->distance: obj->distance(e->object())): e->Key()->distance;
}
// SearchMinPenalty returns where a new entry should be inserted.
// Overriden to insert the distance from the parent in the new entry.
GiSTpage
MTnode::SearchMinPenalty(const GiSTentry& newEntry) const
{
MTentry *minEntry=NULL;
MTpenalty *minPenalty=NULL;
for(int i=0; i<NumEntries(); i++) {
MTentry *e=(MTentry *)((*this)[i].Ptr());
assert((MTnode *)e->Node()==this);
MTpenalty *penalty=(MTpenalty *)e->Penalty(newEntry, minPenalty); // use the alternate Penalty method in order to avoid some distance computations
if((minEntry==NULL)||(*penalty)<(*minPenalty)) {
minEntry=e;
if(minPenalty) delete minPenalty;
minPenalty=penalty;
}
else delete penalty;
}
((MTentry&)newEntry).Key()->distance=minPenalty->distance;
delete minPenalty;
return minEntry->Ptr();
}
void
MTnode::InsertBefore(const GiSTentry& entry, int index)
{
int n=NumEntries();
BOOL ordered=TRUE;
if(index>0) ordered=((*this)[index-1]->Compare(entry)<=0);
if(index<n) ordered=ordered&&((*this)[index]->Compare(entry)>=0);
if(ordered) { // yes, the position is right for this entry
assert(index<=n);
GiSTentry *e=(GiSTentry *)entry.Copy();
e->SetLevel(Level());
e->SetPosition(index);
e->SetNode(this);
// Move everything else over
for(int i=n; i>index; i--) {
GiSTentry *e=(*this)[i-1];
e->SetPosition(i);
(*this)[i]=e;
}
// Stick the entry in
(*this)[index]=e;
// Bump up the count
SetNumEntries(n+1);
}
else Insert(entry); // find the right place
}
// quick-sort the entries with respect to the distance from the parent
void
MTnode::Order()
{
int i, obji=-1, n=NumEntries();
MTentry **array=new MTentry *[n], *objEntry=NULL;
for(i=0; i<n; i++) {
array[i]=(MTentry *)((MTentry *)(*this)[i].Ptr())->Copy();
if(obj==&((MTentry *)(*this)[i].Ptr())->object()) objEntry=array[i];
}
qsort(array, n, sizeof(MTentry *), MTentrycmp);
while(NumEntries()>0) DeleteEntry(0);
for(i=0; i<n; i++) {
InsertBefore(*(array[i]), i);
if(objEntry==array[i]) obji=i;
delete array[i];
}
delete []array;
if(obji>=0) obj=&((MTentry *)(*this)[obji].Ptr())->object();
}
GiSTnode *
MTnode::PickSplit()
{
MTnode *rightnode;
int leftdeletes, rightdeletes; // number of entries to be deleted from each node
int *leftvec=new int[NumEntries()], *rightvec=new int[NumEntries()]; // array of entries to be deleted from each node
// promote the right node (possibly reassigning the left node);
// the right node's page is copied from left node;
// we'll delete from the nodes as appropriate after the splitting phase
// cout << "In PickSplit with node " << this << "\n";
rightnode=PromotePart();
// now perform the split
Split(rightnode, leftvec, rightvec, &leftdeletes, &rightdeletes); // complexity: O(n)
// given the deletion vectors, do bulk deletes
DeleteBulk(leftvec, leftdeletes);
rightnode->DeleteBulk(rightvec, rightdeletes);
// cout << "Nodes:\n" << this << rightnode;
// order the entries in both nodes
Order();
rightnode->Order();
delete []leftvec;
delete []rightvec;
// return the right node
return rightnode;
}
MTnode *
MTnode::PromotePart()
{
MTnode *newnode;
switch(PROMOTE_PART_FUNCTION) {
case RANDOM: { // complexity: constant
int i, j;
// pick two *different* random entries
// cout << "Random promotion: ";
i=PickRandom(0, NumEntries());
do j=PickRandom(0, NumEntries());
while (j==i);
if(((MTentry *)(*this)[j].Ptr())->Key()->distance==0) {
int k=i; i=j; j=k; // if we chose the parent entry, put it in the left node
}
// cout << "Entries " << (*this)[i].Ptr() << " & " << (*this)[j].Ptr() << " chosen.\n";
newnode=(MTnode *)NCopy();
// re-assign the nodes' object
newnode->obj=&((MTentry *)((*newnode)[j].Ptr()))->object();
obj=&((MTentry *)((*this)[i].Ptr()))->object();
if(((MTentry *)(*this)[i].Ptr())->Key()->distance>0) { // if the parent object wasn't confirmed, invalidate also the parent
InvalidateEntry(TRUE);
InvalidateEntries();
}
else InvalidateEntry(FALSE); // else, invalidate only the node's radii
break;
}
case CONFIRMED: { // complexity: determined by the confirmed promotion algorithm
int i;
BOOL isRoot=TRUE;
// cout << "Confirmed promotion: ";
// for(i=0; (i<NumEntries())&&(isRoot); i++) isRoot=(((MTentry *)((*this)[i].Ptr()))->Key()->distance==-MAXDIST);
isRoot=(((MTentry *)((*this)[0].Ptr()))->Key()->distance==-maxDist()); // we have ordered entries
if(isRoot) { // if we're splitting the root we have to use a policy that doesn't use stored distances
PROMOTE_PART_FUNCTION=SECONDARY_PART_FUNCTION;
newnode=PromotePart();
PROMOTE_PART_FUNCTION=CONFIRMED;
}
else {
int index=-1;
for(i=0; (i<NumEntries())&&(index<0); i++) if(((MTentry *)((*this)[i].Ptr()))->Key()->distance==0) index=i;
obj=&((MTentry *)((*this)[index].Ptr()))->object();
// now choose the right node parent
newnode=PromoteVote();
}
InvalidateEntry(FALSE);
break;
}
case MAX_UB_DIST: { // complexity: constant
double maxdist=-1, maxdist2;
int i, maxcand1, maxcand2;
BOOL isRoot=TRUE;
// cout << "Largest max dist promotion:\n";
// for(i=0; (i<NumEntries())&&(isRoot); i++) isRoot=(((MTentry *)((*this)[i].Ptr()))->Key()->distance==-MAXDIST);
isRoot=(((MTentry *)((*this)[0].Ptr()))->Key()->distance==-maxDist()); // we have ordered entries
if(isRoot) { // if we're splitting the root we have to use a policy that doesn't use stored distances
PROMOTE_PART_FUNCTION=SECONDARY_PART_FUNCTION;
newnode=PromotePart();
PROMOTE_PART_FUNCTION=CONFIRMED;
}
else
if(Tree()->IsOrdered()) { // if the tree is ordered we can choose the last two elements
maxcand1=NumEntries()-1;
maxcand2=NumEntries()-2;
} // the following code should be unreachable
else // otherwise we have to search the two objects which are farthest from the parent
for (i=0; i<NumEntries(); i++) {
MTentry *e=(MTentry *)((*this)[i].Ptr());
if (e->Key()->distance>maxdist) {
maxdist2=maxdist;
maxdist=e->Key()->distance;
maxcand2=maxcand1;
maxcand1=i;
}
else if (e->Key()->distance>maxdist2) {
maxdist2=e->Key()->distance;
maxcand2=i;
}
}
// cout << "Entries " << (*this)[maxcand1].Ptr() << " & " << (*this)[maxcand2].Ptr() << " chosen.\n";
// for sure the parent isn't confirmed (unless we have a binary tree...)
obj=&((MTentry *)((*this)[maxcand1].Ptr()))->object();
InvalidateEntry(TRUE);
InvalidateEntries();
newnode=(MTnode *)NCopy();
newnode->obj=&((MTentry *)((*newnode)[maxcand2].Ptr()))->object();
break;
}
case SAMPLING: { // complexity: O(kn) distance computations
// cout << "Sampling: ";
int *vec=PickCandidates(), i, j, min1, min2, bestld, bestrd, *bestlv=new int[NumEntries()], *bestrv=new int[NumEntries()];
double minvalue=MAXDOUBLE, sec_minvalue=MAXDOUBLE, **distances=new double*[MIN(NUM_CANDIDATES, NumEntries())]; // distance matrix
// initialize distance matrix
for(i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++) {
distances[i]=new double[NumEntries()];
for(j=0; j<NumEntries(); j++) distances[i][j]=-maxDist();
}
for(i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++)
if(((MTentry *)((*this)[vec[i]].Ptr()))->Key()->distance==0) {
for(j=0; j<NumEntries(); j++) distances[i][j]=((MTentry *)((*this)[j].Ptr()))->Key()->distance;
break;
}
for(i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++) distances[i][vec[i]]=0;
// find the candidates with minimum radius
for(i=1; i<MIN(NUM_CANDIDATES, NumEntries()); i++)
for (j=0; j<i; j++) {
MTentry *e1=new MTentry, *e2=new MTentry;
MTnode *node1=(MTnode *)NCopy(), *node2=(MTnode *)NCopy();
double value, sec_value;
int leftdeletes, rightdeletes, *leftvec=new int[NumEntries()], *rightvec=new int[NumEntries()], k;
for(k=0; k<NumEntries(); k++) {
((MTentry *)((*node1)[k].Ptr()))->Key()->distance=distances[i][k];
((MTentry *)((*node2)[k].Ptr()))->Key()->distance=distances[j][k];
}
node1->obj=&((MTentry *)((*this)[vec[i]].Ptr()))->object();
node2->obj=&((MTentry *)((*this)[vec[j]].Ptr()))->object();
// perform the split
node1->Split(node2, leftvec, rightvec, &leftdeletes, &rightdeletes);
for(k=0; k<NumEntries(); k++) {
distances[i][k]=((MTentry *)((*node1)[k].Ptr()))->Key()->distance;
distances[j][k]=((MTentry *)((*node2)[k].Ptr()))->Key()->distance;
}
// given the deletion vectors, do bulk deletes
node1->DeleteBulk(leftvec, leftdeletes);
node2->DeleteBulk(rightvec, rightdeletes);
e1->InitKey();
e2->InitKey();
e1->setobject(*node1->obj);
e2->setobject(*node2->obj);
e1->setmaxradius(0);
e2->setmaxradius(0);
e1->setminradius(MAXDOUBLE);
e2->setminradius(MAXDOUBLE);
// compute the radii
node1->mMRadius(e1);
node2->mMRadius(e2);
// check the result
value=MAX(e1->maxradius(), e2->maxradius()); // this is minMAX_RADII
sec_value=MIN(e1->maxradius(), e2->maxradius());
if((value<minvalue)||((value==minvalue)&&(sec_value<sec_minvalue))) {
int index;
minvalue=value;
sec_minvalue=sec_value;
bestld=leftdeletes;
bestrd=rightdeletes;
for(index=0; index<leftdeletes; index++) bestlv[index]=leftvec[index];
for(index=0; index<rightdeletes; index++) bestrv[index]=rightvec[index];
min1=i;
min2=j;
}
// be tidy
delete []leftvec;
delete []rightvec;
delete node1;
delete node2;
delete e1;
delete e2;
}
// cout << "Entries " << (*this)[vec[min1]].Ptr() << " & " << (*this)[vec[min2]].Ptr() << " chosen.\n";
if(((MTentry *)(*this)[vec[min2]].Ptr())->Key()->distance>0) newnode=(MTnode *)NCopy();
else newnode=(MTnode *)Copy();
newnode->obj=&((MTentry *)((*newnode)[vec[min2]].Ptr()))->object();
obj=&((MTentry *)((*this)[vec[min1]].Ptr()))->object();
if(((MTentry *)(*this)[vec[min1]].Ptr())->Key()->distance>0) { // if the parent object wasn't confirmed, invalidate also the parent
InvalidateEntry(TRUE);
InvalidateEntries();
}
else InvalidateEntry(FALSE); // else, invalidate only the node's radii
for(i=0; i<NumEntries(); i++) {
((MTentry *)((*this)[i].Ptr()))->Key()->distance=distances[min1][i];
((MTentry *)((*newnode)[i].Ptr()))->Key()->distance=distances[min2][i];
}
delete []bestlv;
delete []bestrv;
for(i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++) delete []distances[i];
delete []distances;
break;
}
case MIN_RAD:
case MIN_OVERLAPS: { // complexity: O(n^2) distance computations
int min1, min2, i, j, bestld, bestrd, *bestlv=new int[NumEntries()], *bestrv=new int[NumEntries()];
double minvalue=MAXDOUBLE, sec_minvalue=MAXDOUBLE, **distances=new double *[NumEntries()]; // distance matrix
// initialize distance matrix
for(i=0; i<NumEntries(); i++) {
distances[i]=new double[NumEntries()];
for(j=0; j<NumEntries(); j++) distances[i][j]=-maxDist();
}
for(i=0; i<NumEntries(); i++)
if(((MTentry *)((*this)[i].Ptr()))->Key()->distance==0) {
for(j=0; j<NumEntries(); j++) {
distances[i][j]=((MTentry *)((*this)[j].Ptr()))->Key()->distance;
distances[j][i]=distances[i][j];
}
break;
}
for(i=0; i<NumEntries(); i++) distances[i][i]=0;
// if(PROMOTE_PART_FUNCTION==MIN_RADII) cout << "Min radii promotion: ";
// else cout << "Min overlaps promotion: ";
for (i=1; i<NumEntries(); i++)
for (j=0; j<i; j++) {
MTentry *e1=new MTentry, *e2=new MTentry;
MTnode *node1=(MTnode *)NCopy(), *node2=(MTnode *)NCopy();
double value, sec_value;
int leftdeletes, rightdeletes, *leftvec=new int[NumEntries()], *rightvec=new int[NumEntries()], k;
for(k=0; k<NumEntries(); k++) {
((MTentry *)((*node1)[k].Ptr()))->Key()->distance=distances[i][k];
((MTentry *)((*node2)[k].Ptr()))->Key()->distance=distances[j][k];
}
node1->obj=&((MTentry *)((*this)[i].Ptr()))->object();
node2->obj=&((MTentry *)((*this)[j].Ptr()))->object();
// perform the split
node1->Split(node2, leftvec, rightvec, &leftdeletes, &rightdeletes);
for(k=0; k<NumEntries(); k++) {
distances[i][k]=((MTentry *)((*node1)[k].Ptr()))->Key()->distance;
distances[j][k]=((MTentry *)((*node2)[k].Ptr()))->Key()->distance;
distances[k][i]=distances[i][k];
distances[k][j]=distances[j][k];
}
// given the deletion vectors, do bulk deletes
node1->DeleteBulk(leftvec, leftdeletes);
node2->DeleteBulk(rightvec, rightdeletes);
e1->InitKey();
e2->InitKey();
e1->setobject(*node1->obj);
e2->setobject(*node2->obj);
e1->setmaxradius(0);
e2->setmaxradius(0);
e1->setminradius(MAXDOUBLE);
e2->setminradius(MAXDOUBLE);
// compute the radii
node1->mMRadius(e1);
node2->mMRadius(e2);
// check the result
if(PROMOTE_PART_FUNCTION==MIN_RAD) {
value=MAX(e1->maxradius(), e2->maxradius()); // this is minMAX_RADII
sec_value=MIN(e1->maxradius(), e2->maxradius());
}
else value=e1->maxradius()+e2->maxradius()-distances[i][j];
if((value<minvalue)||((value==minvalue)&&(sec_value<sec_minvalue))) {
int index;
minvalue=value;
sec_minvalue=sec_value;
bestld=leftdeletes;
bestrd=rightdeletes;
for(index=0; index<leftdeletes; index++) bestlv[index]=leftvec[index];
for(index=0; index<rightdeletes; index++) bestrv[index]=rightvec[index];
min1=i;
min2=j;
}
// be tidy
delete []leftvec;
delete []rightvec;
delete node1;
delete node2;
delete e1;
delete e2;
}
// cout << "Entries " << (*this)[min1].Ptr() << " & " << (*this)[min2].Ptr() << " chosen.\n";
if(((MTentry *)(*this)[min2].Ptr())->Key()->distance>0) newnode=(MTnode *)NCopy();
else newnode=(MTnode *)Copy();
newnode->obj=&((MTentry *)((*newnode)[min2].Ptr()))->object();
obj=&((MTentry *)((*this)[min1].Ptr()))->object();
if(((MTentry *)(*this)[min1].Ptr())->Key()->distance>0) { // if the parent object wasn't confirmed, invalidate also the parent
InvalidateEntry(TRUE);
InvalidateEntries();
}
else InvalidateEntry(FALSE); // else, invalidate only the node's radii
for(i=0; i<NumEntries(); i++) {
((MTentry *)((*this)[i].Ptr()))->Key()->distance=distances[min1][i];
((MTentry *)((*newnode)[i].Ptr()))->Key()->distance=distances[min2][i];
}
delete bestlv;
delete bestrv;
for(i=0; i<NumEntries(); i++) delete []distances[i];
delete []distances;
break;
}
}
return newnode;
}
MTnode *
MTnode::PromoteVote()
{
MTnode *newnode=(MTnode *)NCopy();
int i;
switch(PROMOTE_VOTE_FUNCTION) {
case RANDOMV: { // complexity: constant
// cout << "Random voting: ";
// pick a random entry (different from the parent)
do i=PickRandom(0, NumEntries());
while(((MTentry *)(*this)[i].Ptr())->Key()->distance==0);
// cout << "Entry " << (*this)[i].Ptr() << " chosen.\n";
newnode->obj=&((MTentry *)((*newnode)[i].Ptr()))->object();
break;
}
case SAMPLINGV: { // complexity: O(kn) distance computations
// cout << "Sampling voting: ";
int *vec=PickCandidates(), bestcand, bestld, bestrd, *bestlv=new int[NumEntries()], *bestrv=new int[NumEntries()];
double minvalue=MAXDOUBLE, sec_minvalue=MAXDOUBLE, **distances=new double *[MIN(NUM_CANDIDATES, NumEntries())]; // distance matrix
// find the candidate with minimum radius
for (i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++) {
MTentry *cand=(MTentry *)((*this)[vec[i]].Ptr()), *e1=new MTentry, *e2=new MTentry;
MTnode *node1=(MTnode *)Copy(), *node2=(MTnode *)NCopy();
double value, sec_value;
int leftdeletes, rightdeletes, *leftvec=new int[NumEntries()], *rightvec=new int[NumEntries()], j;
// cout << "Entry " << cand;
// initialize distance matrix
distances[i]=new double[NumEntries()];
for (j=0; j<NumEntries(); j++) distances[i][j]=((vec[i]==j)? 0: cand->object().distance(((MTentry *)((*this)[j].Ptr()))->object()));
for(j=0; j<NumEntries(); j++) ((MTentry *)((*node2)[j].Ptr()))->Key()->distance=distances[i][j];
node1->obj=obj;
node2->obj=&((MTentry *)((*this)[vec[i]].Ptr()))->object();
// perform the split
node1->Split(node2, leftvec, rightvec, &leftdeletes, &rightdeletes);
// given the deletion vectors, do bulk deletes
node1->DeleteBulk(leftvec, leftdeletes);
node2->DeleteBulk(rightvec, rightdeletes);
e1->InitKey();
e2->InitKey();
e1->setobject(*node1->obj);
e2->setobject(*node2->obj);
e1->setmaxradius(0);
e2->setmaxradius(0);
e1->setminradius(MAXDOUBLE);
e2->setminradius(MAXDOUBLE);
// compute the radii
node1->mMRadius(e1);
node2->mMRadius(e2);
// check the result
value=MAX(e1->maxradius(), e2->maxradius()); // this is minMAX_RADII
sec_value=MIN(e1->maxradius(), e2->maxradius());
if((value<minvalue)||((value==minvalue)&&(sec_value<sec_minvalue))) {
int index;
minvalue=value;
sec_minvalue=sec_value;
bestld=leftdeletes;
bestrd=rightdeletes;
for(index=0; index<leftdeletes; index++) bestlv[index]=leftvec[index];
for(index=0; index<rightdeletes; index++) bestrv[index]=rightvec[index];
bestcand=i;
}
// be tidy
delete e1;
delete e2;
delete node1;
delete node2;
delete []leftvec;
delete []rightvec;
}
// cout << "Entry " << (*this)[vec[bestcand]].Ptr() << " chosen.\n";
newnode->obj=&((MTentry *)((*newnode)[vec[bestcand]].Ptr()))->object();
// update the distance of the children from the new parent
for (i=0; i<NumEntries(); i++)
((MTentry *)((*newnode)[i].Ptr()))->Key()->distance=distances[bestcand][i];
for (i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++) delete []distances[i];
delete []distances;
delete []vec;
delete []bestlv;
delete []bestrv;
break;
}
case MAX_LB_DIST: { // complexity: constant
double maxdist=-1;
int maxcand;
// cout << "Largest min dist voting:\n";
if(Tree()->IsOrdered()) maxcand=NumEntries()-1; // if the tree is ordered we can choose the last element
else // otherwise we have to search the object which is farthest from the parent
for (i=0; i<NumEntries(); i++) {
MTentry *e=(MTentry *)((*this)[i].Ptr());
if (e->Key()->distance>maxdist) {
maxdist=e->Key()->distance;
maxcand=i;
}
}
// cout << "Entry " << (*this)[maxcand].Ptr() << " chosen.\n";
newnode->obj=&((MTentry *)((*newnode)[maxcand].Ptr()))->object();
break;
}
case mM_RAD: { // complexity: constant
double minradius=MAXDOUBLE;
int bestcand;
// cout << "Best radius voting:\n";
for (i=0; i<NumEntries(); i++) {
MTentry *cand=(MTentry *)((*this)[i].Ptr());
double radius=0;
if(cand->Key()->distance==0) continue;
for (int j=0; j<NumEntries(); j++) {
MTentry *e=(MTentry *)((*this)[j].Ptr());
double dmin, dmax;
if (i==j) continue;
dmin=fabs(cand->Key()->distance-e->Key()->distance);
dmax=cand->Key()->distance+e->Key()->distance;
switch (RADIUS_FUNCTION) {
case LB:
radius=MAX(radius, dmin);
break;
case AVG:
radius=MAX(radius, (dmin+dmax)/2);
break;
case UB:
radius=MAX(radius, dmax);
break;
}
}
if (radius<minradius) {
bestcand=i;
minradius=radius;
}
}
// cout << "Entry " << (*this)[bestcand].Ptr() << " chosen.\n";
newnode->obj=&((MTentry *)((*newnode)[bestcand].Ptr()))->object();
break;
}
}
return newnode;
}
int *
MTnode::PickCandidates()
{
int max_ind=MIN(NUM_CANDIDATES, NumEntries()), *vec=new int[max_ind], i;
BOOL *used=new BOOL[NumEntries()];
for(i=0; i<NumEntries(); i++) used[i]=(((MTentry *)(*this)[i].Ptr())->Key()->distance==0);
// insert in vec the indices of the candidates for promotion
for(i=0; i<max_ind; i++) {
int j;
do j=PickRandom(0, NumEntries());
while(used[j]);
vec[i]=j;
used[j]=TRUE;
}
return vec;
}
void
MTnode::Split(MTnode *node, int *leftvec, int *rightvec, int *leftdeletes, int *rightdeletes)
{
int i;
*rightdeletes=0;
*leftdeletes=0;
// cout << "Now splitting between:\n";
// cout << obj << " & " << node->obj << endl;
switch(SPLIT_FUNCTION) {
case G_HYPERPL: {
int numentries=NumEntries();
double *rightdistances=new double[numentries], *leftdistances=new double[numentries];
for(i=0; i<numentries; i++) {
leftdistances[i]=distance(i);
rightdistances[i]=node->distance(i);
}
while((*rightdeletes<numentries*MIN_UTIL)&&(*leftdeletes<numentries*MIN_UTIL)) { // balance entries up to minimum utilization (assigning to each node its remaining nearest entry)
i=FindMin(leftdistances, numentries);
((MTentry *)(*this)[i].Ptr())->Key()->distance=leftdistances[i];
((MTentry *)(*node)[i].Ptr())->Key()->distance=rightdistances[i];
// cout << (*this)[i].Ptr() << " (" << leftdistances[i] << ", " << rightdistances[i] << ") to the left\n";
rightvec[(*rightdeletes)++]=i;
rightdistances[i]=MAXDOUBLE;
leftdistances[i]=MAXDOUBLE;
i=FindMin(rightdistances, numentries);
if(i>=0) {
((MTentry *)(*node)[i].Ptr())->Key()->distance=rightdistances[i];
((MTentry *)(*this)[i].Ptr())->Key()->distance=leftdistances[i];
// cout << (*node)[i].Ptr() << " (" << leftdistances[i] << ", " << rightdistances[i] << ") to the right\n";
leftvec[(*leftdeletes)++]=i;
rightdistances[i]=MAXDOUBLE;
leftdistances[i]=MAXDOUBLE;
}
}
for(i=0; i<numentries; i++) { // then perform the hyperplane split (assigning each entry to its nearest node)
if(rightdistances[i]==MAXDOUBLE) continue;
// ((MTentry *)(*this)[i].Ptr())->Key()->distance=distance(i)+((MTentry *)(*this)[i].Ptr())->maxradius();
// ((MTentry *)(*node)[i].Ptr())->Key()->distance=node->distance(i)+((MTentry *)(*node)[i].Ptr())->maxradius();
((MTentry *)(*this)[i].Ptr())->Key()->distance=leftdistances[i];
((MTentry *)(*node)[i].Ptr())->Key()->distance=rightdistances[i];
if (((MTentry *)(*this)[i].Ptr())->Key()->distance<((MTentry *)(*node)[i].Ptr())->Key()->distance) {
// cout << (*this)[i].Ptr() << " (" << ((MTentry *)(*this)[i].Ptr())->Key()->distance << ", " << ((MTentry *)(*node)[i].Ptr())->Key()->distance << ") to the left\n";
rightvec[(*rightdeletes)++]=i;
}
else {
// cout << (*node)[i].Ptr() << " (" << ((MTentry *)(*this)[i].Ptr())->Key()->distance << ", " << ((MTentry *)(*node)[i].Ptr())->Key()->distance << ") to the right\n";
leftvec[(*leftdeletes)++]=i;
}
}
delete []rightdistances;
delete []leftdistances;
break;
}
case BAL_G_HYPERPL: {
int numentries=NumEntries(), j;
for(i=0; i<NumEntries(); i++) { // assign the parents' entries
if(obj==&((MTentry *)((*this)[i].Ptr()))->object()) {
// cout << (*this)[i].Ptr() << " to the left\n";
((MTentry *)(*this)[i].Ptr())->Key()->distance=0;
rightvec[(*rightdeletes)++]=i;
}
if(node->obj==&((MTentry *)((*node)[i].Ptr()))->object()) {
// cout << (*node)[i].Ptr() << " to the right\n";
((MTentry *)(*node)[i].Ptr())->Key()->distance=0;
leftvec[(*leftdeletes)++]=i;
}
}
for(i=0; (*rightdeletes<(numentries+1)/2)&&(*leftdeletes<(numentries+1)/2); i++) { // perform the hyperplane split up to a node utilization of the 50%
if((obj!=&((MTentry *)((*this)[i].Ptr()))->object())&&(node->obj!=&((MTentry *)((*node)[i].Ptr()))->object())) { // the parents' entries were already assigned
((MTentry *)(*this)[i].Ptr())->Key()->distance=distance(i);
((MTentry *)(*node)[i].Ptr())->Key()->distance=node->distance(i);
if (((MTentry *)(*this)[i].Ptr())->Key()->distance<((MTentry *)(*node)[i].Ptr())->Key()->distance) {
// cout << (*this)[i].Ptr() << " (" << ((MTentry *)(*this)[i].Ptr())->Key()->distance << ", " << ((MTentry *)(*node)[i].Ptr())->Key()->distance << ") to the left\n";
rightvec[(*rightdeletes)++]=i;
}
else {
// cout << (*node)[i].Ptr() << " (" << ((MTentry *)(*this)[i].Ptr())->Key()->distance << ", " << ((MTentry *)(*node)[i].Ptr())->Key()->distance << ") to the right\n";
leftvec[(*leftdeletes)++]=i;
}
}
}
// then balance the remaining entries
for(j=*rightdeletes; j<numentries/2; j++, i++)
if((obj!=&((MTentry *)((*this)[i].Ptr()))->object())&&(node->obj!=&((MTentry *)((*node)[i].Ptr()))->object())) { // the parents' entries were already assigned
((MTentry *)(*this)[i].Ptr())->Key()->distance=distance(i);
((MTentry *)(*node)[i].Ptr())->Key()->distance=-maxDist();
// cout << (*this)[i].Ptr() << " (" << ((MTentry *)(*this)[i].Ptr())->Key()->distance << ") to the left\n";
rightvec[(*rightdeletes)++]=i;
}
else j--;
for(j=*leftdeletes; j<numentries/2; j++, i++)
if((obj!=&((MTentry *)((*this)[i].Ptr()))->object())&&(node->obj!=&((MTentry *)((*node)[i].Ptr()))->object())) { // the parents' entries were already assigned
((MTentry *)(*node)[i].Ptr())->Key()->distance=node->distance(i);
((MTentry *)(*this)[i].Ptr())->Key()->distance=-maxDist();
// cout << (*node)[i].Ptr() << " (" << ((MTentry *)(*node)[i].Ptr())->Key()->distance << ") to the right\n";
leftvec[(*leftdeletes)++]=i;
}
else j--;
break;
}
case BALANCED: { // assign iteratively to each node its remaining nearest entry
int numentries=NumEntries();
double *rightdistances=new double[numentries], *leftdistances=new double[numentries];
for(i=0; i<numentries; i++) {
leftdistances[i]=distance(i);
rightdistances[i]=node->distance(i);
}
while((*rightdeletes<(numentries+1)/2)&&(*leftdeletes<(numentries+1)/2)) {
i=FindMin(leftdistances, numentries);
((MTentry *)(*this)[i].Ptr())->Key()->distance=leftdistances[i];
((MTentry *)(*node)[i].Ptr())->Key()->distance=rightdistances[i];
// cout << (*this)[i].Ptr() << " (" << leftdistances[i] << ", " << rightdistances[i] << ") to the left\n";
rightvec[(*rightdeletes)++]=i;
rightdistances[i]=MAXDOUBLE;
leftdistances[i]=MAXDOUBLE;
i=FindMin(rightdistances, numentries);
if(i>=0) {
((MTentry *)(*node)[i].Ptr())->Key()->distance=rightdistances[i];
((MTentry *)(*this)[i].Ptr())->Key()->distance=leftdistances[i];
// cout << (*node)[i].Ptr() << " (" << leftdistances[i] << ", " << rightdistances[i] << ") to the right\n";
leftvec[(*leftdeletes)++]=i;
rightdistances[i]=MAXDOUBLE;
leftdistances[i]=MAXDOUBLE;
}
}
delete []rightdistances;
delete []leftdistances;
break;
}
}
}
GiSTentry *
MTnode::Union() const
{
GiSTpath path=((MTnode *)this)->Path();
MTentry *u=new MTentry;
Object *o=NULL;
u->InitKey();
if(obj==NULL) { // retrieve the node's object
MTentry *e=Entry();
((MTnode *)this)->obj=(o=new Object(e->object()));
delete e;
}
if(path.Level()>1) { // if we aren't in the root...
MTnode *parent=((MT *)Tree())->ParentNode((MTnode *)this);
MTentry *e=Entry();
if(e!=NULL) { // copy the entry
u->Key()->distance=e->Key()->distance;
if(e->Key()->splitted) u->Key()->recomp=TRUE;
delete e;
}
if(u->Key()->distance<0) { // compute the distance from the parent
MTentry *fe=parent->Entry();
if(u->Key()->distance==-maxDist()) u->Key()->distance=obj->distance(fe->object());
u->Key()->recomp=TRUE;
delete fe;
}
delete parent;
}
u->setobject(*obj);
u->setmaxradius(0);
u->setminradius(MAXDOUBLE);
mMRadius(u); // compute the radii
if(o!=NULL) delete o;
((MTnode *)this)->obj=NULL;
return u;
}
void
MTnode::mMRadius(MTentry *e) const
{
for (int i=0; i<NumEntries(); i++) {
MTentry *mte=(MTentry *)(*this)[i].Ptr();
mte->Key()->recomp=FALSE;
if (mte->Key()->distance<0) { // this code should be unreachable
cout << "Computing distance with " << mte << "??????????????????????????????????????????????\n"; // this code should be unreachable
mte->Key()->distance=obj->distance(mte->object());
}
if (mte->Key()->distance+mte->maxradius()>e->maxradius()) e->setmaxradius(mte->Key()->distance+mte->maxradius());
if (MAX(mte->Key()->distance-mte->maxradius(), 0)<e->minradius()) e->setminradius(MAX(mte->Key()->distance-mte->maxradius(), 0));
}
}
GiSTlist<MTentry *>
MTnode::RangeSearch(const MTquery &query)
{
GiSTlist<MTentry *> result;
if(IsLeaf())
for(int i=0; i<NumEntries(); i++) {
MTentry *e=(MTentry *)(*this)[i].Ptr()->Copy();
MTquery *q=(MTquery *)query.Copy();
if(q->Consistent(*e)) { // object qualifies
e->setmaxradius(q->Grade());
result.Append(e);
}
else delete e;
delete q;
}
else
for(int i=0; i<NumEntries(); i++) {
MTentry *e=(MTentry *)(*this)[i].Ptr();
MTquery *q=(MTquery *)query.Copy();
if(q->Consistent(*e)) { // sub-tree not excluded
GiSTpath childpath=Path();
MTnode *child;
GiSTlist<MTentry *>list;
childpath.MakeChild(e->Ptr());
child=(MTnode *)((MT *)Tree())->ReadNode(childpath);
list=child->RangeSearch(*q); // recurse the search
while(!list.IsEmpty()) result.Append(list.RemoveFront());
delete child;
}
delete q;
}
return result;
}