mtnode.cpp

M树源代码

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