ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/Tree-M/MT/MTnode.cpp
Revision: 1.2
Committed: Sun May 6 03:30:18 2001 UTC (23 years ago) by root
Branch: MAIN
CVS Tags: HEAD
Changes since 1.1: +7 -7 lines
Log Message: 
*** empty log message ***

File Contents

# Content
1 /*********************************************************************
2 * *
3 * Copyright (c) 1997,1998, 1999 *
4 * Multimedia DB Group and DEIS - CSITE-CNR, *
5 * University of Bologna, Bologna, ITALY. *
6 * *
7 * All Rights Reserved. *
8 * *
9 * Permission to use, copy, and distribute this software and its *
10 * documentation for NON-COMMERCIAL purposes and without fee is *
11 * hereby granted provided that this copyright notice appears in *
12 * all copies. *
13 * *
14 * THE AUTHORS MAKE NO REPRESENTATIONS OR WARRANTIES ABOUT THE *
15 * SUITABILITY OF THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING *
16 * BUT NOT LIMITED TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, *
17 * FITNESS FOR A PARTICULAR PURPOSE, OR NON-INFRINGEMENT. THE AUTHOR *
18 * SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A *
19 * RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS *
20 * DERIVATIVES. *
21 * *
22 *********************************************************************/
23
24 #include <string.h>
25 #include "MT.h"
26 #include "MTpredicate.h"
27
28 double MIN_UTIL = 0.35; // minimum node utilization
29 pp_function PROMOTE_PART_FUNCTION = CONFIRMED; // promotion method
30 pv_function PROMOTE_VOTE_FUNCTION = mM_RAD; // confirmed promotion method (if needed)
31 pp_function SECONDARY_PART_FUNCTION = RANDOM; // root promotion method (can't use stored distances): used only for confirmed and MAX_UB_DIST methods
32 r_function RADIUS_FUNCTION = LB; // mM_RAD promotion method (if needed)
33 int NUM_CANDIDATES = 10; // number of candidates for sampling
34 s_function SPLIT_FUNCTION = BAL_G_HYPERPL; // split method
35
36 extern int IOread;
37
38 // used to quick-sort the entries in a node according to their distance from the parent
39 int
40 MTentrycmp(const void *x, const void *y)
41 {
42 double d=(*(MTentry **)x)->Key()->distance-(*(MTentry **)y)->Key()->distance;
43 int i=0;
44
45 if(d>0) i=1;
46 else if(d<0) i=-1;
47 return i;
48 }
49
50 // used in Split to find the next nearest entry
51 int
52 FindMin(double *vec, int veclen)
53 {
54 int i, min_i=-1;
55 double min=MAXDOUBLE;
56
57 for(i=0; i<veclen; i++)
58 if(vec[i]<min) {
59 min_i=i;
60 min=vec[i];
61 }
62 return min_i;
63 }
64
65 GiSTobject *
66 MTnode::NCopy()
67 {
68 MTnode *newnode=(MTnode *)Copy();
69
70 if((obj==NULL)&&(Path().Level()>1)) {
71 MTentry *e=Entry();
72
73 obj=newnode->obj=&(e->object());
74 delete e;
75 }
76 newnode->InvalidateEntries();
77 return newnode;
78 }
79
80 #ifdef PRINTING_OBJECTS
81 void
82 MTnode::Print(ostream& os) const
83 {
84 if(obj!=NULL) os << *obj << " ";
85 // else cout << "obj NULL...\n";
86 os << ((MTnode *)this)->Path() << " #Entries: " << NumEntries() << ", Level " << Level();
87 if(IsLeaf()) os << "(Leaf)";
88 else os << "(Internal)";
89 os << ", Sibling: " << Sibling() << ", Size: " << Size() << "/" << Tree()->Store()->PageSize() << endl;
90 for(int i=0; i<NumEntries(); i++) (*this)[i]->Print(os);
91 }
92 #endif
93
94 int
95 MTnode::IsUnderFull(const GiSTstore &store) const
96 {
97 return ((MIN_UTIL>0)&&(Size()<(int)(store.PageSize()*MIN_UTIL)));
98 }
99
100 void
101 MTnode::InvalidateEntries()
102 {
103 for(int i=0; i<NumEntries(); i++)
104 ((MTentry *)((*this)[i].Ptr()))->Key()->distance=-maxDist();
105 }
106
107 void
108 MTnode::InvalidateEntry(BOOL isNew)
109 {
110 GiSTpath path=Path();
111 if(path.Level()>1) {
112 MTnode *parent=((MT *)Tree())->ParentNode((MTnode *)this), *gparent=((MT *)Tree())->ParentNode(parent);
113 int i;
114
115 for(i=0; i<parent->NumEntries(); i++) { // search the entry between the parent's children
116 MTentry *e=(MTentry *)((*parent)[i].Ptr());
117
118 if(e->Ptr()==path.Page()) {
119 if(isNew) e->Key()->distance=-maxDist();
120 // else e->Key()->distance=-e->Key()->distance;
121 e->Key()->splitted=TRUE;
122 break;
123 }
124 }
125 path.MakeParent();
126 for(i=0; i<gparent->NumEntries(); i++) { // search the parent entry between the grandparent's children
127 MTentry *e=(MTentry *)((*gparent)[i].Ptr());
128
129 if(e->Ptr()==path.Page()) {
130 e->setmaxradius(-1);
131 break;
132 }
133 }
134 ((MT *)Tree())->WriteNode(parent); // write parent node (in inconsistent state)
135 ((MT *)Tree())->WriteNode(gparent); // write gparent node (to invalidate the parent's entry)
136 delete parent;
137 delete gparent;
138 }
139 }
140
141 MTentry *
142 MTnode::Entry() const
143 {
144 GiSTpath path=((MTnode *)this)->Path();
145 MTnode *parent=((MT *)Tree())->ParentNode((MTnode *)this);
146 MTentry *returnEntry=NULL;
147
148 for(int i=0; (i<parent->NumEntries())&&(returnEntry==NULL); i++)
149 if((*parent)[i].Ptr()->Ptr()==path.Page()) returnEntry=(MTentry *)(*parent)[i].Ptr()->Copy();
150 delete parent;
151 return returnEntry;
152 }
153
154 double
155 MTnode::distance(int i) const
156 {
157 MTentry *e=(MTentry *)((*this)[i].Ptr());
158
159 // if(e->Key()->distance>=0) cout << "Distance between " << obj << " & " << e->object() << " = " << e->Key()->distance << endl;
160 // else cout << "Computing distance between " << obj << " & " << e->object() << "..." << endl;
161 return (e->Key()->distance<0)? ((e->Key()->distance>-maxDist())? -e->Key()->distance: obj->distance(e->object())): e->Key()->distance;
162 }
163
164 // SearchMinPenalty returns where a new entry should be inserted.
165 // Overriden to insert the distance from the parent in the new entry.
166 GiSTpage
167 MTnode::SearchMinPenalty(const GiSTentry& newEntry) const
168 {
169 MTentry *minEntry=NULL;
170 MTpenalty *minPenalty=NULL;
171
172 for(int i=0; i<NumEntries(); i++) {
173 MTentry *e=(MTentry *)((*this)[i].Ptr());
174
175 assert((MTnode *)e->Node()==this);
176 MTpenalty *penalty=(MTpenalty *)e->Penalty(newEntry, minPenalty); // use the alternate Penalty method in order to avoid some distance computations
177
178 if((minEntry==NULL)||(*penalty)<(*minPenalty)) {
179 minEntry=e;
180 if(minPenalty) delete minPenalty;
181 minPenalty=penalty;
182 }
183 else delete penalty;
184 }
185 ((MTentry&)newEntry).Key()->distance=minPenalty->distance;
186 delete minPenalty;
187 return minEntry->Ptr();
188 }
189
190 void
191 MTnode::InsertBefore(const GiSTentry& entry, int index)
192 {
193 int n=NumEntries();
194 BOOL ordered=TRUE;
195
196 if(index>0) ordered=((*this)[index-1]->Compare(entry)<=0);
197 if(index<n) ordered=ordered&&((*this)[index]->Compare(entry)>=0);
198 if(ordered) { // yes, the position is right for this entry
199 assert(index<=n);
200 GiSTentry *e=(GiSTentry *)entry.Copy();
201
202 e->SetLevel(Level());
203 e->SetPosition(index);
204 e->SetNode(this);
205 // Move everything else over
206 for(int i=n; i>index; i--) {
207 GiSTentry *e=(*this)[i-1];
208
209 e->SetPosition(i);
210 (*this)[i]=e;
211 }
212 // Stick the entry in
213 (*this)[index]=e;
214 // Bump up the count
215 SetNumEntries(n+1);
216 }
217 else Insert(entry); // find the right place
218 }
219
220 // quick-sort the entries with respect to the distance from the parent
221 void
222 MTnode::Order()
223 {
224 int i, obji=-1, n=NumEntries();
225 MTentry **array=new MTentry *[n], *objEntry=NULL;
226
227 for(i=0; i<n; i++) {
228 array[i]=(MTentry *)((MTentry *)(*this)[i].Ptr())->Copy();
229 if(obj==&((MTentry *)(*this)[i].Ptr())->object()) objEntry=array[i];
230 }
231 qsort(array, n, sizeof(MTentry *), MTentrycmp);
232 while(NumEntries()>0) DeleteEntry(0);
233 for(i=0; i<n; i++) {
234 InsertBefore(*(array[i]), i);
235 if(objEntry==array[i]) obji=i;
236 delete array[i];
237 }
238 delete []array;
239 if(obji>=0) obj=&((MTentry *)(*this)[obji].Ptr())->object();
240 }
241
242 GiSTnode *
243 MTnode::PickSplit()
244 {
245 MTnode *rightnode;
246 int leftdeletes, rightdeletes; // number of entries to be deleted from each node
247 int *leftvec=new int[NumEntries()], *rightvec=new int[NumEntries()]; // array of entries to be deleted from each node
248
249 // promote the right node (possibly reassigning the left node);
250 // the right node's page is copied from left node;
251 // we'll delete from the nodes as appropriate after the splitting phase
252 // cout << "In PickSplit with node " << this << "\n";
253 rightnode=PromotePart();
254 // now perform the split
255 Split(rightnode, leftvec, rightvec, &leftdeletes, &rightdeletes); // complexity: O(n)
256 // given the deletion vectors, do bulk deletes
257 DeleteBulk(leftvec, leftdeletes);
258 rightnode->DeleteBulk(rightvec, rightdeletes);
259 // cout << "Nodes:\n" << this << rightnode;
260 // order the entries in both nodes
261 Order();
262 rightnode->Order();
263 delete []leftvec;
264 delete []rightvec;
265 // return the right node
266 return rightnode;
267 }
268
269 MTnode *
270 MTnode::PromotePart()
271 {
272 MTnode *newnode;
273
274 switch(PROMOTE_PART_FUNCTION) {
275 case RANDOM: { // complexity: constant
276 int i, j;
277
278 // pick two *different* random entries
279 // cout << "Random promotion: ";
280 i=PickRandom(0, NumEntries());
281 do j=PickRandom(0, NumEntries());
282 while (j==i);
283 if(((MTentry *)(*this)[j].Ptr())->Key()->distance==0) {
284 int k=i; i=j; j=k; // if we chose the parent entry, put it in the left node
285 }
286 // cout << "Entries " << (*this)[i].Ptr() << " & " << (*this)[j].Ptr() << " chosen.\n";
287 newnode=(MTnode *)NCopy();
288 // re-assign the nodes' object
289 newnode->obj=&((MTentry *)((*newnode)[j].Ptr()))->object();
290 obj=&((MTentry *)((*this)[i].Ptr()))->object();
291 if(((MTentry *)(*this)[i].Ptr())->Key()->distance>0) { // if the parent object wasn't confirmed, invalidate also the parent
292 InvalidateEntry(TRUE);
293 InvalidateEntries();
294 }
295 else InvalidateEntry(FALSE); // else, invalidate only the node's radii
296 break;
297 }
298 case CONFIRMED: { // complexity: determined by the confirmed promotion algorithm
299 int i;
300 BOOL isRoot=TRUE;
301
302 // cout << "Confirmed promotion: ";
303 // for(i=0; (i<NumEntries())&&(isRoot); i++) isRoot=(((MTentry *)((*this)[i].Ptr()))->Key()->distance==-MAXDIST);
304 isRoot=(((MTentry *)((*this)[0].Ptr()))->Key()->distance==-maxDist()); // we have ordered entries
305 if(isRoot) { // if we're splitting the root we have to use a policy that doesn't use stored distances
306 PROMOTE_PART_FUNCTION=SECONDARY_PART_FUNCTION;
307 newnode=PromotePart();
308 PROMOTE_PART_FUNCTION=CONFIRMED;
309 }
310 else {
311 int index=-1;
312
313 for(i=0; (i<NumEntries())&&(index<0); i++) if(((MTentry *)((*this)[i].Ptr()))->Key()->distance==0) index=i;
314 obj=&((MTentry *)((*this)[index].Ptr()))->object();
315 // now choose the right node parent
316 newnode=PromoteVote();
317 }
318 InvalidateEntry(FALSE);
319 break;
320 }
321 case MAX_UB_DIST: { // complexity: constant
322 double maxdist=-1, maxdist2;
323 int i, maxcand1, maxcand2;
324 BOOL isRoot=TRUE;
325
326 // cout << "Largest max dist promotion:\n";
327 // for(i=0; (i<NumEntries())&&(isRoot); i++) isRoot=(((MTentry *)((*this)[i].Ptr()))->Key()->distance==-MAXDIST);
328 isRoot=(((MTentry *)((*this)[0].Ptr()))->Key()->distance==-maxDist()); // we have ordered entries
329 if(isRoot) { // if we're splitting the root we have to use a policy that doesn't use stored distances
330 PROMOTE_PART_FUNCTION=SECONDARY_PART_FUNCTION;
331 newnode=PromotePart();
332 PROMOTE_PART_FUNCTION=CONFIRMED;
333 }
334 else
335 if(Tree()->IsOrdered()) { // if the tree is ordered we can choose the last two elements
336 maxcand1=NumEntries()-1;
337 maxcand2=NumEntries()-2;
338 } // the following code should be unreachable
339 else // otherwise we have to search the two objects which are farthest from the parent
340 for (i=0; i<NumEntries(); i++) {
341 MTentry *e=(MTentry *)((*this)[i].Ptr());
342
343 if (e->Key()->distance>maxdist) {
344 maxdist2=maxdist;
345 maxdist=e->Key()->distance;
346 maxcand2=maxcand1;
347 maxcand1=i;
348 }
349 else if (e->Key()->distance>maxdist2) {
350 maxdist2=e->Key()->distance;
351 maxcand2=i;
352 }
353 }
354 // cout << "Entries " << (*this)[maxcand1].Ptr() << " & " << (*this)[maxcand2].Ptr() << " chosen.\n";
355 // for sure the parent isn't confirmed (unless we have a binary tree...)
356 obj=&((MTentry *)((*this)[maxcand1].Ptr()))->object();
357 InvalidateEntry(TRUE);
358 InvalidateEntries();
359 newnode=(MTnode *)NCopy();
360 newnode->obj=&((MTentry *)((*newnode)[maxcand2].Ptr()))->object();
361 break;
362 }
363 case SAMPLING: { // complexity: O(kn) distance computations
364 // cout << "Sampling: ";
365 int *vec=PickCandidates(), i, j, min1, min2, bestld, bestrd, *bestlv=new int[NumEntries()], *bestrv=new int[NumEntries()];
366 double minvalue=MAXDOUBLE, sec_minvalue=MAXDOUBLE, **distances=new double*[MIN(NUM_CANDIDATES, NumEntries())]; // distance matrix
367
368 // initialize distance matrix
369 for(i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++) {
370 distances[i]=new double[NumEntries()];
371 for(j=0; j<NumEntries(); j++) distances[i][j]=-maxDist();
372 }
373 for(i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++)
374 if(((MTentry *)((*this)[vec[i]].Ptr()))->Key()->distance==0) {
375 for(j=0; j<NumEntries(); j++) distances[i][j]=((MTentry *)((*this)[j].Ptr()))->Key()->distance;
376 break;
377 }
378 for(i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++) distances[i][vec[i]]=0;
379 // find the candidates with minimum radius
380 for(i=1; i<MIN(NUM_CANDIDATES, NumEntries()); i++)
381 for (j=0; j<i; j++) {
382 MTentry *e1=new MTentry, *e2=new MTentry;
383 MTnode *node1=(MTnode *)NCopy(), *node2=(MTnode *)NCopy();
384 double value, sec_value;
385 int leftdeletes, rightdeletes, *leftvec=new int[NumEntries()], *rightvec=new int[NumEntries()], k;
386
387 for(k=0; k<NumEntries(); k++) {
388 ((MTentry *)((*node1)[k].Ptr()))->Key()->distance=distances[i][k];
389 ((MTentry *)((*node2)[k].Ptr()))->Key()->distance=distances[j][k];
390 }
391 node1->obj=&((MTentry *)((*this)[vec[i]].Ptr()))->object();
392 node2->obj=&((MTentry *)((*this)[vec[j]].Ptr()))->object();
393 // perform the split
394 node1->Split(node2, leftvec, rightvec, &leftdeletes, &rightdeletes);
395 for(k=0; k<NumEntries(); k++) {
396 distances[i][k]=((MTentry *)((*node1)[k].Ptr()))->Key()->distance;
397 distances[j][k]=((MTentry *)((*node2)[k].Ptr()))->Key()->distance;
398 }
399 // given the deletion vectors, do bulk deletes
400 node1->DeleteBulk(leftvec, leftdeletes);
401 node2->DeleteBulk(rightvec, rightdeletes);
402 e1->InitKey();
403 e2->InitKey();
404 e1->setobject(*node1->obj);
405 e2->setobject(*node2->obj);
406 e1->setmaxradius(0);
407 e2->setmaxradius(0);
408 e1->setminradius(MAXDOUBLE);
409 e2->setminradius(MAXDOUBLE);
410 // compute the radii
411 node1->mMRadius(e1);
412 node2->mMRadius(e2);
413 // check the result
414 value=MAX(e1->maxradius(), e2->maxradius()); // this is minMAX_RADII
415 sec_value=MIN(e1->maxradius(), e2->maxradius());
416 if((value<minvalue)||((value==minvalue)&&(sec_value<sec_minvalue))) {
417 int index;
418
419 minvalue=value;
420 sec_minvalue=sec_value;
421 bestld=leftdeletes;
422 bestrd=rightdeletes;
423 for(index=0; index<leftdeletes; index++) bestlv[index]=leftvec[index];
424 for(index=0; index<rightdeletes; index++) bestrv[index]=rightvec[index];
425 min1=i;
426 min2=j;
427 }
428 // be tidy
429 delete []leftvec;
430 delete []rightvec;
431 delete node1;
432 delete node2;
433 delete e1;
434 delete e2;
435 }
436 // cout << "Entries " << (*this)[vec[min1]].Ptr() << " & " << (*this)[vec[min2]].Ptr() << " chosen.\n";
437 if(((MTentry *)(*this)[vec[min2]].Ptr())->Key()->distance>0) newnode=(MTnode *)NCopy();
438 else newnode=(MTnode *)Copy();
439 newnode->obj=&((MTentry *)((*newnode)[vec[min2]].Ptr()))->object();
440 obj=&((MTentry *)((*this)[vec[min1]].Ptr()))->object();
441 if(((MTentry *)(*this)[vec[min1]].Ptr())->Key()->distance>0) { // if the parent object wasn't confirmed, invalidate also the parent
442 InvalidateEntry(TRUE);
443 InvalidateEntries();
444 }
445 else InvalidateEntry(FALSE); // else, invalidate only the node's radii
446 for(i=0; i<NumEntries(); i++) {
447 ((MTentry *)((*this)[i].Ptr()))->Key()->distance=distances[min1][i];
448 ((MTentry *)((*newnode)[i].Ptr()))->Key()->distance=distances[min2][i];
449 }
450 delete []bestlv;
451 delete []bestrv;
452 for(i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++) delete []distances[i];
453 delete []distances;
454 break;
455 }
456 case MIN_RAD:
457 case MIN_OVERLAPS: { // complexity: O(n^2) distance computations
458 int min1, min2, i, j, bestld, bestrd, *bestlv=new int[NumEntries()], *bestrv=new int[NumEntries()];
459 double minvalue=MAXDOUBLE, sec_minvalue=MAXDOUBLE, **distances=new double *[NumEntries()]; // distance matrix
460
461 // initialize distance matrix
462 for(i=0; i<NumEntries(); i++) {
463 distances[i]=new double[NumEntries()];
464 for(j=0; j<NumEntries(); j++) distances[i][j]=-maxDist();
465 }
466 for(i=0; i<NumEntries(); i++)
467 if(((MTentry *)((*this)[i].Ptr()))->Key()->distance==0) {
468 for(j=0; j<NumEntries(); j++) {
469 distances[i][j]=((MTentry *)((*this)[j].Ptr()))->Key()->distance;
470 distances[j][i]=distances[i][j];
471 }
472 break;
473 }
474 for(i=0; i<NumEntries(); i++) distances[i][i]=0;
475 // if(PROMOTE_PART_FUNCTION==MIN_RADII) cout << "Min radii promotion: ";
476 // else cout << "Min overlaps promotion: ";
477 for (i=1; i<NumEntries(); i++)
478 for (j=0; j<i; j++) {
479 MTentry *e1=new MTentry, *e2=new MTentry;
480 MTnode *node1=(MTnode *)NCopy(), *node2=(MTnode *)NCopy();
481 double value, sec_value;
482 int leftdeletes, rightdeletes, *leftvec=new int[NumEntries()], *rightvec=new int[NumEntries()], k;
483
484 for(k=0; k<NumEntries(); k++) {
485 ((MTentry *)((*node1)[k].Ptr()))->Key()->distance=distances[i][k];
486 ((MTentry *)((*node2)[k].Ptr()))->Key()->distance=distances[j][k];
487 }
488 node1->obj=&((MTentry *)((*this)[i].Ptr()))->object();
489 node2->obj=&((MTentry *)((*this)[j].Ptr()))->object();
490 // perform the split
491 node1->Split(node2, leftvec, rightvec, &leftdeletes, &rightdeletes);
492 for(k=0; k<NumEntries(); k++) {
493 distances[i][k]=((MTentry *)((*node1)[k].Ptr()))->Key()->distance;
494 distances[j][k]=((MTentry *)((*node2)[k].Ptr()))->Key()->distance;
495 distances[k][i]=distances[i][k];
496 distances[k][j]=distances[j][k];
497 }
498 // given the deletion vectors, do bulk deletes
499 node1->DeleteBulk(leftvec, leftdeletes);
500 node2->DeleteBulk(rightvec, rightdeletes);
501 e1->InitKey();
502 e2->InitKey();
503 e1->setobject(*node1->obj);
504 e2->setobject(*node2->obj);
505 e1->setmaxradius(0);
506 e2->setmaxradius(0);
507 e1->setminradius(MAXDOUBLE);
508 e2->setminradius(MAXDOUBLE);
509 // compute the radii
510 node1->mMRadius(e1);
511 node2->mMRadius(e2);
512 // check the result
513 if(PROMOTE_PART_FUNCTION==MIN_RAD) {
514 value=MAX(e1->maxradius(), e2->maxradius()); // this is minMAX_RADII
515 sec_value=MIN(e1->maxradius(), e2->maxradius());
516 }
517 else value=e1->maxradius()+e2->maxradius()-distances[i][j];
518 if((value<minvalue)||((value==minvalue)&&(sec_value<sec_minvalue))) {
519 int index;
520
521 minvalue=value;
522 sec_minvalue=sec_value;
523 bestld=leftdeletes;
524 bestrd=rightdeletes;
525 for(index=0; index<leftdeletes; index++) bestlv[index]=leftvec[index];
526 for(index=0; index<rightdeletes; index++) bestrv[index]=rightvec[index];
527 min1=i;
528 min2=j;
529 }
530 // be tidy
531 delete []leftvec;
532 delete []rightvec;
533 delete node1;
534 delete node2;
535 delete e1;
536 delete e2;
537 }
538 // cout << "Entries " << (*this)[min1].Ptr() << " & " << (*this)[min2].Ptr() << " chosen.\n";
539 if(((MTentry *)(*this)[min2].Ptr())->Key()->distance>0) newnode=(MTnode *)NCopy();
540 else newnode=(MTnode *)Copy();
541 newnode->obj=&((MTentry *)((*newnode)[min2].Ptr()))->object();
542 obj=&((MTentry *)((*this)[min1].Ptr()))->object();
543 if(((MTentry *)(*this)[min1].Ptr())->Key()->distance>0) { // if the parent object wasn't confirmed, invalidate also the parent
544 InvalidateEntry(TRUE);
545 InvalidateEntries();
546 }
547 else InvalidateEntry(FALSE); // else, invalidate only the node's radii
548 for(i=0; i<NumEntries(); i++) {
549 ((MTentry *)((*this)[i].Ptr()))->Key()->distance=distances[min1][i];
550 ((MTentry *)((*newnode)[i].Ptr()))->Key()->distance=distances[min2][i];
551 }
552 delete bestlv;
553 delete bestrv;
554 for(i=0; i<NumEntries(); i++) delete []distances[i];
555 delete []distances;
556 break;
557 }
558 }
559 return newnode;
560 }
561
562 MTnode *
563 MTnode::PromoteVote()
564 {
565 MTnode *newnode=(MTnode *)NCopy();
566 int i;
567
568 switch(PROMOTE_VOTE_FUNCTION) {
569 case RANDOMV: { // complexity: constant
570 // cout << "Random voting: ";
571 // pick a random entry (different from the parent)
572 do i=PickRandom(0, NumEntries());
573 while(((MTentry *)(*this)[i].Ptr())->Key()->distance==0);
574 // cout << "Entry " << (*this)[i].Ptr() << " chosen.\n";
575 newnode->obj=&((MTentry *)((*newnode)[i].Ptr()))->object();
576 break;
577 }
578 case SAMPLINGV: { // complexity: O(kn) distance computations
579 // cout << "Sampling voting: ";
580 int *vec=PickCandidates(), bestcand, bestld, bestrd, *bestlv=new int[NumEntries()], *bestrv=new int[NumEntries()];
581 double minvalue=MAXDOUBLE, sec_minvalue=MAXDOUBLE, **distances=new double *[MIN(NUM_CANDIDATES, NumEntries())]; // distance matrix
582
583 // find the candidate with minimum radius
584 for (i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++) {
585 MTentry *cand=(MTentry *)((*this)[vec[i]].Ptr()), *e1=new MTentry, *e2=new MTentry;
586 MTnode *node1=(MTnode *)Copy(), *node2=(MTnode *)NCopy();
587 double value, sec_value;
588 int leftdeletes, rightdeletes, *leftvec=new int[NumEntries()], *rightvec=new int[NumEntries()], j;
589
590 // cout << "Entry " << cand;
591 // initialize distance matrix
592 distances[i]=new double[NumEntries()];
593 for (j=0; j<NumEntries(); j++) distances[i][j]=((vec[i]==j)? 0: cand->object().distance(((MTentry *)((*this)[j].Ptr()))->object()));
594 for(j=0; j<NumEntries(); j++) ((MTentry *)((*node2)[j].Ptr()))->Key()->distance=distances[i][j];
595 node1->obj=obj;
596 node2->obj=&((MTentry *)((*this)[vec[i]].Ptr()))->object();
597 // perform the split
598 node1->Split(node2, leftvec, rightvec, &leftdeletes, &rightdeletes);
599 // given the deletion vectors, do bulk deletes
600 node1->DeleteBulk(leftvec, leftdeletes);
601 node2->DeleteBulk(rightvec, rightdeletes);
602 e1->InitKey();
603 e2->InitKey();
604 e1->setobject(*node1->obj);
605 e2->setobject(*node2->obj);
606 e1->setmaxradius(0);
607 e2->setmaxradius(0);
608 e1->setminradius(MAXDOUBLE);
609 e2->setminradius(MAXDOUBLE);
610 // compute the radii
611 node1->mMRadius(e1);
612 node2->mMRadius(e2);
613 // check the result
614 value=MAX(e1->maxradius(), e2->maxradius()); // this is minMAX_RADII
615 sec_value=MIN(e1->maxradius(), e2->maxradius());
616 if((value<minvalue)||((value==minvalue)&&(sec_value<sec_minvalue))) {
617 int index;
618
619 minvalue=value;
620 sec_minvalue=sec_value;
621 bestld=leftdeletes;
622 bestrd=rightdeletes;
623 for(index=0; index<leftdeletes; index++) bestlv[index]=leftvec[index];
624 for(index=0; index<rightdeletes; index++) bestrv[index]=rightvec[index];
625 bestcand=i;
626 }
627 // be tidy
628 delete e1;
629 delete e2;
630 delete node1;
631 delete node2;
632 delete []leftvec;
633 delete []rightvec;
634 }
635 // cout << "Entry " << (*this)[vec[bestcand]].Ptr() << " chosen.\n";
636 newnode->obj=&((MTentry *)((*newnode)[vec[bestcand]].Ptr()))->object();
637 // update the distance of the children from the new parent
638 for (i=0; i<NumEntries(); i++)
639 ((MTentry *)((*newnode)[i].Ptr()))->Key()->distance=distances[bestcand][i];
640 for (i=0; i<MIN(NUM_CANDIDATES, NumEntries()); i++) delete []distances[i];
641 delete []distances;
642 delete []vec;
643 delete []bestlv;
644 delete []bestrv;
645 break;
646 }
647 case MAX_LB_DIST: { // complexity: constant
648 double maxdist=-1;
649 int maxcand;
650
651 // cout << "Largest min dist voting:\n";
652 if(Tree()->IsOrdered()) maxcand=NumEntries()-1; // if the tree is ordered we can choose the last element
653 else // otherwise we have to search the object which is farthest from the parent
654 for (i=0; i<NumEntries(); i++) {
655 MTentry *e=(MTentry *)((*this)[i].Ptr());
656
657 if (e->Key()->distance>maxdist) {
658 maxdist=e->Key()->distance;
659 maxcand=i;
660 }
661 }
662 // cout << "Entry " << (*this)[maxcand].Ptr() << " chosen.\n";
663 newnode->obj=&((MTentry *)((*newnode)[maxcand].Ptr()))->object();
664 break;
665 }
666 case mM_RAD: { // complexity: constant
667 double minradius=MAXDOUBLE;
668 int bestcand;
669
670 // cout << "Best radius voting:\n";
671 for (i=0; i<NumEntries(); i++) {
672 MTentry *cand=(MTentry *)((*this)[i].Ptr());
673 double radius=0;
674
675 if(cand->Key()->distance==0) continue;
676 for (int j=0; j<NumEntries(); j++) {
677 MTentry *e=(MTentry *)((*this)[j].Ptr());
678 double dmin, dmax;
679
680 if (i==j) continue;
681 dmin=fabs(cand->Key()->distance-e->Key()->distance);
682 dmax=cand->Key()->distance+e->Key()->distance;
683 switch (RADIUS_FUNCTION) {
684 case LB:
685 radius=MAX(radius, dmin);
686 break;
687 case AVG:
688 radius=MAX(radius, (dmin+dmax)/2);
689 break;
690 case UB:
691 radius=MAX(radius, dmax);
692 break;
693 }
694 }
695 if (radius<minradius) {
696 bestcand=i;
697 minradius=radius;
698 }
699 }
700 // cout << "Entry " << (*this)[bestcand].Ptr() << " chosen.\n";
701 newnode->obj=&((MTentry *)((*newnode)[bestcand].Ptr()))->object();
702 break;
703 }
704 }
705 return newnode;
706 }
707
708 int *
709 MTnode::PickCandidates()
710 {
711 int max_ind=MIN(NUM_CANDIDATES, NumEntries()), *vec=new int[max_ind], i;
712 BOOL *used=new BOOL[NumEntries()];
713
714 for(i=0; i<NumEntries(); i++) used[i]=(((MTentry *)(*this)[i].Ptr())->Key()->distance==0);
715 // insert in vec the indices of the candidates for promotion
716 for(i=0; i<max_ind; i++) {
717 int j;
718
719 do j=PickRandom(0, NumEntries());
720 while(used[j]);
721 vec[i]=j;
722 used[j]=TRUE;
723 }
724 return vec;
725 }
726
727 void
728 MTnode::Split(MTnode *node, int *leftvec, int *rightvec, int *leftdeletes, int *rightdeletes)
729 {
730 int i;
731
732 *rightdeletes=0;
733 *leftdeletes=0;
734 // cout << "Now splitting between:\n";
735 // cout << obj << " & " << node->obj << endl;
736 switch(SPLIT_FUNCTION) {
737 case G_HYPERPL: {
738 int numentries=NumEntries();
739 double *rightdistances=new double[numentries], *leftdistances=new double[numentries];
740
741 for(i=0; i<numentries; i++) {
742 leftdistances[i]=distance(i);
743 rightdistances[i]=node->distance(i);
744 }
745 while((*rightdeletes<numentries*MIN_UTIL)&&(*leftdeletes<numentries*MIN_UTIL)) { // balance entries up to minimum utilization (assigning to each node its remaining nearest entry)
746 i=FindMin(leftdistances, numentries);
747 ((MTentry *)(*this)[i].Ptr())->Key()->distance=leftdistances[i];
748 ((MTentry *)(*node)[i].Ptr())->Key()->distance=rightdistances[i];
749 // cout << (*this)[i].Ptr() << " (" << leftdistances[i] << ", " << rightdistances[i] << ") to the left\n";
750 rightvec[(*rightdeletes)++]=i;
751 rightdistances[i]=MAXDOUBLE;
752 leftdistances[i]=MAXDOUBLE;
753 i=FindMin(rightdistances, numentries);
754 if(i>=0) {
755 ((MTentry *)(*node)[i].Ptr())->Key()->distance=rightdistances[i];
756 ((MTentry *)(*this)[i].Ptr())->Key()->distance=leftdistances[i];
757 // cout << (*node)[i].Ptr() << " (" << leftdistances[i] << ", " << rightdistances[i] << ") to the right\n";
758 leftvec[(*leftdeletes)++]=i;
759 rightdistances[i]=MAXDOUBLE;
760 leftdistances[i]=MAXDOUBLE;
761 }
762 }
763 for(i=0; i<numentries; i++) { // then perform the hyperplane split (assigning each entry to its nearest node)
764 if(rightdistances[i]==MAXDOUBLE) continue;
765 // ((MTentry *)(*this)[i].Ptr())->Key()->distance=distance(i)+((MTentry *)(*this)[i].Ptr())->maxradius();
766 // ((MTentry *)(*node)[i].Ptr())->Key()->distance=node->distance(i)+((MTentry *)(*node)[i].Ptr())->maxradius();
767 ((MTentry *)(*this)[i].Ptr())->Key()->distance=leftdistances[i];
768 ((MTentry *)(*node)[i].Ptr())->Key()->distance=rightdistances[i];
769 if (((MTentry *)(*this)[i].Ptr())->Key()->distance<((MTentry *)(*node)[i].Ptr())->Key()->distance) {
770 // cout << (*this)[i].Ptr() << " (" << ((MTentry *)(*this)[i].Ptr())->Key()->distance << ", " << ((MTentry *)(*node)[i].Ptr())->Key()->distance << ") to the left\n";
771 rightvec[(*rightdeletes)++]=i;
772 }
773 else {
774 // cout << (*node)[i].Ptr() << " (" << ((MTentry *)(*this)[i].Ptr())->Key()->distance << ", " << ((MTentry *)(*node)[i].Ptr())->Key()->distance << ") to the right\n";
775 leftvec[(*leftdeletes)++]=i;
776 }
777 }
778 delete []rightdistances;
779 delete []leftdistances;
780 break;
781 }
782 case BAL_G_HYPERPL: {
783 int numentries=NumEntries(), j;
784
785 for(i=0; i<NumEntries(); i++) { // assign the parents' entries
786 if(obj==&((MTentry *)((*this)[i].Ptr()))->object()) {
787 // cout << (*this)[i].Ptr() << " to the left\n";
788 ((MTentry *)(*this)[i].Ptr())->Key()->distance=0;
789 rightvec[(*rightdeletes)++]=i;
790 }
791 if(node->obj==&((MTentry *)((*node)[i].Ptr()))->object()) {
792 // cout << (*node)[i].Ptr() << " to the right\n";
793 ((MTentry *)(*node)[i].Ptr())->Key()->distance=0;
794 leftvec[(*leftdeletes)++]=i;
795 }
796 }
797 for(i=0; (*rightdeletes<(numentries+1)/2)&&(*leftdeletes<(numentries+1)/2); i++) { // perform the hyperplane split up to a node utilization of the 50%
798 if((obj!=&((MTentry *)((*this)[i].Ptr()))->object())&&(node->obj!=&((MTentry *)((*node)[i].Ptr()))->object())) { // the parents' entries were already assigned
799 ((MTentry *)(*this)[i].Ptr())->Key()->distance=distance(i);
800 ((MTentry *)(*node)[i].Ptr())->Key()->distance=node->distance(i);
801 if (((MTentry *)(*this)[i].Ptr())->Key()->distance<((MTentry *)(*node)[i].Ptr())->Key()->distance) {
802 // cout << (*this)[i].Ptr() << " (" << ((MTentry *)(*this)[i].Ptr())->Key()->distance << ", " << ((MTentry *)(*node)[i].Ptr())->Key()->distance << ") to the left\n";
803 rightvec[(*rightdeletes)++]=i;
804 }
805 else {
806 // cout << (*node)[i].Ptr() << " (" << ((MTentry *)(*this)[i].Ptr())->Key()->distance << ", " << ((MTentry *)(*node)[i].Ptr())->Key()->distance << ") to the right\n";
807 leftvec[(*leftdeletes)++]=i;
808 }
809 }
810 }
811 // then balance the remaining entries
812 for(j=*rightdeletes; j<numentries/2; j++, i++)
813 if((obj!=&((MTentry *)((*this)[i].Ptr()))->object())&&(node->obj!=&((MTentry *)((*node)[i].Ptr()))->object())) { // the parents' entries were already assigned
814 ((MTentry *)(*this)[i].Ptr())->Key()->distance=distance(i);
815 ((MTentry *)(*node)[i].Ptr())->Key()->distance=-maxDist();
816 // cout << (*this)[i].Ptr() << " (" << ((MTentry *)(*this)[i].Ptr())->Key()->distance << ") to the left\n";
817 rightvec[(*rightdeletes)++]=i;
818 }
819 else j--;
820 for(j=*leftdeletes; j<numentries/2; j++, i++)
821 if((obj!=&((MTentry *)((*this)[i].Ptr()))->object())&&(node->obj!=&((MTentry *)((*node)[i].Ptr()))->object())) { // the parents' entries were already assigned
822 ((MTentry *)(*node)[i].Ptr())->Key()->distance=node->distance(i);
823 ((MTentry *)(*this)[i].Ptr())->Key()->distance=-maxDist();
824 // cout << (*node)[i].Ptr() << " (" << ((MTentry *)(*node)[i].Ptr())->Key()->distance << ") to the right\n";
825 leftvec[(*leftdeletes)++]=i;
826 }
827 else j--;
828 break;
829 }
830 case BALANCED: { // assign iteratively to each node its remaining nearest entry
831 int numentries=NumEntries();
832 double *rightdistances=new double[numentries], *leftdistances=new double[numentries];
833
834 for(i=0; i<numentries; i++) {
835 leftdistances[i]=distance(i);
836 rightdistances[i]=node->distance(i);
837 }
838 while((*rightdeletes<(numentries+1)/2)&&(*leftdeletes<(numentries+1)/2)) {
839 i=FindMin(leftdistances, numentries);
840 ((MTentry *)(*this)[i].Ptr())->Key()->distance=leftdistances[i];
841 ((MTentry *)(*node)[i].Ptr())->Key()->distance=rightdistances[i];
842 // cout << (*this)[i].Ptr() << " (" << leftdistances[i] << ", " << rightdistances[i] << ") to the left\n";
843 rightvec[(*rightdeletes)++]=i;
844 rightdistances[i]=MAXDOUBLE;
845 leftdistances[i]=MAXDOUBLE;
846 i=FindMin(rightdistances, numentries);
847 if(i>=0) {
848 ((MTentry *)(*node)[i].Ptr())->Key()->distance=rightdistances[i];
849 ((MTentry *)(*this)[i].Ptr())->Key()->distance=leftdistances[i];
850 // cout << (*node)[i].Ptr() << " (" << leftdistances[i] << ", " << rightdistances[i] << ") to the right\n";
851 leftvec[(*leftdeletes)++]=i;
852 rightdistances[i]=MAXDOUBLE;
853 leftdistances[i]=MAXDOUBLE;
854 }
855 }
856 delete []rightdistances;
857 delete []leftdistances;
858 break;
859 }
860 }
861 }
862
863 GiSTentry *
864 MTnode::Union() const
865 {
866 GiSTpath path=((MTnode *)this)->Path();
867 MTentry *u=new MTentry;
868 Object *o=NULL;
869
870 u->InitKey();
871 if(obj==NULL) { // retrieve the node's object
872 MTentry *e=Entry();
873
874 ((MTnode *)this)->obj=(o=new Object(e->object()));
875 delete e;
876 }
877 if(path.Level()>1) { // if we aren't in the root...
878 MTnode *parent=((MT *)Tree())->ParentNode((MTnode *)this);
879 MTentry *e=Entry();
880
881 if(e!=NULL) { // copy the entry
882 u->Key()->distance=e->Key()->distance;
883 if(e->Key()->splitted) u->Key()->recomp=TRUE;
884 delete e;
885 }
886 if(u->Key()->distance<0) { // compute the distance from the parent
887 MTentry *fe=parent->Entry();
888
889 if(u->Key()->distance==-maxDist()) u->Key()->distance=obj->distance(fe->object());
890 u->Key()->recomp=TRUE;
891 delete fe;
892 }
893 delete parent;
894 }
895 u->setobject(*obj);
896 u->setmaxradius(0);
897 u->setminradius(MAXDOUBLE);
898 mMRadius(u); // compute the radii
899 if(o!=NULL) delete o;
900 ((MTnode *)this)->obj=NULL;
901 return u;
902 }
903
904 void
905 MTnode::mMRadius(MTentry *e) const
906 {
907 for (int i=0; i<NumEntries(); i++) {
908 MTentry *mte=(MTentry *)(*this)[i].Ptr();
909
910 mte->Key()->recomp=FALSE;
911 if (mte->Key()->distance<0) { // this code should be unreachable
912 cout << "Computing distance with " << mte << "??????????????????????????????????????????????\n"; // this code should be unreachable
913 mte->Key()->distance=obj->distance(mte->object());
914 }
915 if (mte->Key()->distance+mte->maxradius()>e->maxradius()) e->setmaxradius(mte->Key()->distance+mte->maxradius());
916 if (MAX(mte->Key()->distance-mte->maxradius(), 0)<e->minradius()) e->setminradius(MAX(mte->Key()->distance-mte->maxradius(), 0));
917 }
918 }
919
920 GiSTlist<MTentry *>
921 MTnode::RangeSearch(const MTquery &query)
922 {
923 GiSTlist<MTentry *> result;
924
925 if(IsLeaf())
926 for(int i=0; i<NumEntries(); i++) {
927 MTentry *e=(MTentry *)(*this)[i].Ptr()->Copy();
928 MTquery *q=(MTquery *)query.Copy();
929
930 if(q->Consistent(*e)) { // object qualifies
931 e->setmaxradius(q->Grade());
932 result.Append(e);
933 }
934 else delete e;
935 delete q;
936 }
937 else
938 for(int i=0; i<NumEntries(); i++) {
939 MTentry *e=(MTentry *)(*this)[i].Ptr();
940 MTquery *q=(MTquery *)query.Copy();
941
942 if(q->Consistent(*e)) { // sub-tree not excluded
943 GiSTpath childpath=Path();
944 MTnode *child;
945 GiSTlist<MTentry *>list;
946
947 childpath.MakeChild(e->Ptr());
948 child=(MTnode *)((MT *)Tree())->ReadNode(childpath);
949 list=child->RangeSearch(*q); // recurse the search
950 while(!list.IsEmpty()) result.Append(list.RemoveFront());
951 delete child;
952 }
953 delete q;
954 }
955 return result;
956 }