00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017 #include <stdio.h>
00018 #include <stdlib.h>
00019 #include "assert.h"
00020 #include "index.h"
00021 #include "card.h"
00022
00023
00024 struct Node * RTreeNewIndex(void)
00025 {
00026 struct Node *x;
00027 x = RTreeNewNode();
00028 x->level = 0;
00029 return x;
00030 }
00031
00032
00033
00034
00035
00036
00037 int RTreeSearch(struct Node *N, struct Rect *R, SearchHitCallback shcb, void* cbarg)
00038 {
00039 register struct Node *n = N;
00040 register struct Rect *r = R;
00041
00042 register int hitCount = 0;
00043 register int i;
00044
00045 assert(n);
00046 assert(n->level >= 0);
00047 assert(r);
00048
00049 if (n->level > 0)
00050 {
00051 for (i=0; i<NODECARD; i++)
00052 if (n->branch[i].child &&
00053 RTreeOverlap(r,&n->branch[i].rect))
00054 {
00055 hitCount += RTreeSearch(n->branch[i].child, R, shcb, cbarg);
00056 }
00057 }
00058 else
00059 {
00060 for (i=0; i<LEAFCARD; i++)
00061 if (n->branch[i].child &&
00062 RTreeOverlap(r,&n->branch[i].rect))
00063 {
00064 hitCount++;
00065 if(shcb)
00066 if( ! shcb((int)n->branch[i].child, cbarg))
00067 return hitCount;
00068 }
00069 }
00070 return hitCount;
00071 }
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081 static int RTreeInsertRect2(struct Rect *r,
00082 int tid, struct Node *n, struct Node **new_node, int level)
00083 {
00084
00085
00086
00087
00088
00089
00090
00091 register int i;
00092 struct Branch b;
00093 struct Node *n2;
00094
00095 assert(r && n && new_node);
00096 assert(level >= 0 && level <= n->level);
00097
00098
00099 if (n->level > level)
00100 {
00101 i = RTreePickBranch(r, n);
00102 if (!RTreeInsertRect2(r, tid, n->branch[i].child, &n2, level))
00103 {
00104
00105 n->branch[i].rect =
00106 RTreeCombineRect(r,&(n->branch[i].rect));
00107 return 0;
00108 }
00109 else
00110 {
00111 n->branch[i].rect = RTreeNodeCover(n->branch[i].child);
00112 b.child = n2;
00113 b.rect = RTreeNodeCover(n2);
00114 return RTreeAddBranch(&b, n, new_node);
00115 }
00116 }
00117
00118
00119 else if (n->level == level)
00120 {
00121 b.rect = *r;
00122 b.child = (struct Node *) tid;
00123
00124 return RTreeAddBranch(&b, n, new_node);
00125 }
00126 else
00127 {
00128
00129 assert (FALSE);
00130 return 0;
00131 }
00132 }
00133
00134
00135
00136
00137
00138
00139
00140
00141
00142 int RTreeInsertRect(struct Rect *R, int Tid, struct Node **Root, int Level)
00143 {
00144 register struct Rect *r = R;
00145 register int tid = Tid;
00146 register struct Node **root = Root;
00147 register int level = Level;
00148 register int i;
00149 register struct Node *newroot;
00150 struct Node *newnode;
00151 struct Branch b;
00152 int result;
00153
00154 assert(r && root);
00155 assert(level >= 0 && level <= (*root)->level);
00156 for (i=0; i<NUMDIMS; i++) {
00157 assert(r->boundary[i] <= r->boundary[NUMDIMS+i]);
00158 }
00159
00160 if (RTreeInsertRect2(r, tid, *root, &newnode, level))
00161 {
00162 newroot = RTreeNewNode();
00163 newroot->level = (*root)->level + 1;
00164 b.rect = RTreeNodeCover(*root);
00165 b.child = *root;
00166 RTreeAddBranch(&b, newroot, NULL);
00167 b.rect = RTreeNodeCover(newnode);
00168 b.child = newnode;
00169 RTreeAddBranch(&b, newroot, NULL);
00170 *root = newroot;
00171 result = 1;
00172 }
00173 else
00174 result = 0;
00175
00176 return result;
00177 }
00178
00179
00180
00181
00182
00183 static struct ListNode * RTreeNewListNode(void)
00184 {
00185 return (struct ListNode *) malloc(sizeof(struct ListNode));
00186
00187 }
00188
00189 static void RTreeFreeListNode(struct ListNode *p)
00190 {
00191 free(p);
00192
00193 }
00194
00195
00196
00197
00198
00199 static void RTreeReInsert(struct Node *n, struct ListNode **ee)
00200 {
00201 register struct ListNode *l;
00202
00203 l = RTreeNewListNode();
00204 l->node = n;
00205 l->next = *ee;
00206 *ee = l;
00207 }
00208
00209
00210
00211
00212
00213
00214
00215 static int
00216 RTreeDeleteRect2(struct Rect *R, int Tid, struct Node *N, struct ListNode **Ee)
00217 {
00218 register struct Rect *r = R;
00219 register int tid = Tid;
00220 register struct Node *n = N;
00221 register struct ListNode **ee = Ee;
00222 register int i;
00223
00224 assert(r && n && ee);
00225 assert(tid >= 0);
00226 assert(n->level >= 0);
00227
00228 if (n->level > 0)
00229 {
00230 for (i = 0; i < NODECARD; i++)
00231 {
00232 if (n->branch[i].child && RTreeOverlap(r, &(n->branch[i].rect)))
00233 {
00234 if (!RTreeDeleteRect2(r, tid, n->branch[i].child, ee))
00235 {
00236 if (n->branch[i].child->count >= MinNodeFill) {
00237 n->branch[i].rect = RTreeNodeCover(
00238 n->branch[i].child);
00239 }
00240 else
00241 {
00242
00243 RTreeReInsert(n->branch[i].child, ee);
00244 RTreeDisconnectBranch(n, i);
00245 }
00246 return 0;
00247 }
00248 }
00249 }
00250 return 1;
00251 }
00252 else
00253 {
00254 for (i = 0; i < LEAFCARD; i++)
00255 {
00256 if (n->branch[i].child &&
00257 n->branch[i].child == (struct Node *) tid)
00258 {
00259 RTreeDisconnectBranch(n, i);
00260 return 0;
00261 }
00262 }
00263 return 1;
00264 }
00265 }
00266
00267
00268
00269
00270
00271
00272
00273 int RTreeDeleteRect(struct Rect *R, int Tid, struct Node**Nn)
00274 {
00275 register struct Rect *r = R;
00276 register int tid = Tid;
00277 register struct Node **nn = Nn;
00278 register int i;
00279 struct Node *tmp_nptr = NULL;
00280 struct ListNode *reInsertList = NULL;
00281 register struct ListNode *e;
00282
00283 assert(r && nn);
00284 assert(*nn);
00285 assert(tid >= 0);
00286
00287 if (!RTreeDeleteRect2(r, tid, *nn, &reInsertList))
00288 {
00289
00290
00291
00292 while (reInsertList)
00293 {
00294 tmp_nptr = reInsertList->node;
00295 for (i = 0; i < MAXKIDS(tmp_nptr); i++)
00296 {
00297 if (tmp_nptr->branch[i].child)
00298 {
00299 RTreeInsertRect(
00300 &(tmp_nptr->branch[i].rect),
00301 (int)tmp_nptr->branch[i].child,
00302 nn,
00303 tmp_nptr->level);
00304 }
00305 }
00306 e = reInsertList;
00307 reInsertList = reInsertList->next;
00308 RTreeFreeNode(e->node);
00309 RTreeFreeListNode(e);
00310 }
00311
00312
00313 if ((*nn)->count == 1 && (*nn)->level > 0)
00314 {
00315 for (i = 0; i < NODECARD; i++)
00316 {
00317 tmp_nptr = (*nn)->branch[i].child;
00318 if(tmp_nptr)
00319 break;
00320 }
00321 assert(tmp_nptr);
00322 RTreeFreeNode(*nn);
00323 *nn = tmp_nptr;
00324 }
00325 return 0;
00326 }
00327 else
00328 {
00329 return 1;
00330 }
00331 }
00332