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; // minimum node utilization |
29 |
pp_function PROMOTE_PART_FUNCTION; // promotion method |
30 |
pv_function PROMOTE_VOTE_FUNCTION; // confirmed promotion method (if needed) |
31 |
pp_function SECONDARY_PART_FUNCTION; // root promotion method (can't use stored distances): used only for confirmed and MAX_UB_DIST methods |
32 |
r_function RADIUS_FUNCTION; // mM_RAD promotion method (if needed) |
33 |
int NUM_CANDIDATES; // number of candidates for sampling |
34 |
s_function SPLIT_FUNCTION; // 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 |
} |