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 (25 years, 4 months ago) by root
Branch: MAIN
CVS Tags: HEAD
Changes since 1.1: +7 -7 lines
Log Message: 
*** empty log message ***

File Contents

# User Rev Content
1 root 1.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 root 1.2 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 root 1.1
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     }