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