mtnode.cpp

M树源代码

				((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;
}