ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/Tree-M/MT/MTcursor.cpp
Revision: 1.1
Committed: Sun May 6 00:45:52 2001 UTC (23 years ago) by root
Branch: MAIN
CVS Tags: HEAD
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 "MTcursor.h"
25 #include "MT.h"
26 #include "MTpredicate.h"
27
28 class MTnode;
29
30 int
31 sign(double x)
32 {
33 if(x>0) return 1;
34 if(x<0) return -1;
35 return 0;
36 }
37
38 int comparedst(dst *a, dst *b) { return sign(a->Bound()-b->Bound()); }
39 int comparedst(dst& a, dst& b) { return sign(a.Bound()-b.Bound()); }
40 int compareentry(MTentry *a, MTentry *b) { return sign(a->maxradius()-b->maxradius()); }
41
42 MTcursor::MTcursor(const MT& tree, const MTpred& query): queue(comparedst), results(compareentry), tree(tree)
43 {
44 GiSTpath path;
45 dst *d;
46
47 path.MakeRoot();
48 d=new dst(path, 0, MAXDOUBLE);
49 this->query=(MTpred *)query.Copy();
50 queue.Insert(d);
51 }
52
53 BOOL
54 MTcursor::IsReady() const
55 {
56 if(queue.IsEmpty()) return (!results.IsEmpty());
57 else if(results.IsEmpty()) return FALSE;
58 else return (queue.First()->Bound()>=results.First()->maxradius());
59 }
60
61 double
62 MTcursor::Bound() const
63 {
64 if(queue.IsEmpty())
65 if(results.IsEmpty()) return maxDist();
66 else return(results.First()->maxradius());
67 else if(results.IsEmpty()) return(queue.First()->Bound());
68 else return MIN(queue.First()->Bound(), results.First()->maxradius());
69 }
70
71 void
72 MTcursor::FetchNode()
73 {
74 if(queue.IsEmpty()) return;
75
76 int i, iprev, inext; // these are the previous and the next entries to be examined
77 dst *d=queue.RemoveFirst();
78 MTnode *node=(MTnode *)tree.ReadNode(d->Path()); // retrieve next node to be examined
79
80 // cout << "Read node " << node->Path() << ": " << d->Bound() << endl;
81 // search the first children to be examined
82 for(unsigned int i=0; i<node->NumEntries(); i++) { // for each entry in the current node
83 MTentry *e=(MTentry *)((*node)[i].Ptr());
84 double dist=query->distance(e->object());
85
86 if(!e->IsLeaf()) { // insert the child node in the priority queue
87 dst *dnew;
88 GiSTpath path=node->Path();
89 double dmin=dist-e->maxradius(), dmax=dist+e->maxradius(); // these are lower- and upper-bounds on the distances of the descendants of the entry from the query object
90
91 if(dmin<0) dmin=0;
92 path.MakeChild(e->Ptr());
93 dnew=new dst(path, dmin, dist);
94 queue.Insert(dnew);
95 }
96 else { // insert the entry in the result list
97 MTentry *key=(MTentry *)e->Copy();
98
99 key->setminradius(0);
100 key->setmaxradius(dist); // we insert the actual distance from the query object as the key radius
101 results.Insert(key);
102 // cout << "Inserted (" << dist << ") into list in " << j <<"-th place\n";
103 }
104 }
105 delete node; // delete examined node
106 delete d;
107 }
108
109 MTentry *
110 MTcursor::Next()
111 {
112 while(!IsReady()) FetchNode();
113 if(!results.IsEmpty()) return results.RemoveFirst();
114 else return NULL;
115 }
116
117 MTcursor::~MTcursor()
118 {
119 delete query;
120 while(!results.IsEmpty()) delete results.RemoveFirst();
121 while(!queue.IsEmpty()) delete queue.RemoveFirst();
122 }