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 int tid, 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, tid, 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 = (struct Node *)tid;
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 register struct Rect *r = R;
00141 register int tid = Tid;
00142 register struct Node **root = Root;
00143 register int level = Level;
00144 register int i;
00145 register struct Node *newroot;
00146 struct Node *newnode;
00147 struct Branch b;
00148 int result;
00149
00150 assert(r && root);
00151 assert(level >= 0 && level <= (*root)->level);
00152 for (i = 0; i < NUMDIMS; i++) {
00153 assert(r->boundary[i] <= r->boundary[NUMDIMS + i]);
00154 }
00155
00156 if (RTreeInsertRect2(r, tid, *root, &newnode, level)) {
00157 newroot = RTreeNewNode();
00158 newroot->level = (*root)->level + 1;
00159 b.rect = RTreeNodeCover(*root);
00160 b.child = *root;
00161 RTreeAddBranch(&b, newroot, NULL);
00162 b.rect = RTreeNodeCover(newnode);
00163 b.child = newnode;
00164 RTreeAddBranch(&b, newroot, NULL);
00165 *root = newroot;
00166 result = 1;
00167 }
00168 else
00169 result = 0;
00170
00171 return result;
00172 }
00173
00174
00175
00176
00177
00178 static struct ListNode *RTreeNewListNode(void)
00179 {
00180 return (struct ListNode *)malloc(sizeof(struct ListNode));
00181
00182 }
00183
00184 static void RTreeFreeListNode(struct ListNode *p)
00185 {
00186 free(p);
00187
00188 }
00189
00190
00191
00192
00193
00194 static void RTreeReInsert(struct Node *n, struct ListNode **ee)
00195 {
00196 register struct ListNode *l;
00197
00198 l = RTreeNewListNode();
00199 l->node = n;
00200 l->next = *ee;
00201 *ee = l;
00202 }
00203
00204
00205
00206
00207
00208
00209
00210 static int
00211 RTreeDeleteRect2(struct Rect *R, int Tid, struct Node *N,
00212 struct ListNode **Ee)
00213 {
00214 register struct Rect *r = R;
00215 register int tid = Tid;
00216 register struct Node *n = N;
00217 register struct ListNode **ee = Ee;
00218 register int i;
00219
00220 assert(r && n && ee);
00221 assert(tid >= 0);
00222 assert(n->level >= 0);
00223
00224 if (n->level > 0) {
00225 for (i = 0; i < NODECARD; i++) {
00226 if (n->branch[i].child && RTreeOverlap(r, &(n->branch[i].rect))) {
00227 if (!RTreeDeleteRect2(r, tid, n->branch[i].child, ee)) {
00228 if (n->branch[i].child->count >= MinNodeFill) {
00229 n->branch[i].rect =
00230 RTreeNodeCover(n->branch[i].child);
00231 }
00232 else {
00233
00234 RTreeReInsert(n->branch[i].child, ee);
00235 RTreeDisconnectBranch(n, i);
00236 }
00237 return 0;
00238 }
00239 }
00240 }
00241 return 1;
00242 }
00243 else {
00244
00245 for (i = 0; i < LEAFCARD; i++) {
00246 if (n->branch[i].child &&
00247 n->branch[i].child == (struct Node *)tid) {
00248 RTreeDisconnectBranch(n, i);
00249 return 0;
00250 }
00251 }
00252 return 1;
00253 }
00254 }
00255
00256
00257
00258
00259
00260
00261
00262 int RTreeDeleteRect(struct Rect *R, int Tid, struct Node **Nn)
00263 {
00264 register struct Rect *r = R;
00265 register int tid = Tid;
00266 register struct Node **nn = Nn;
00267 register int i;
00268 struct Node *tmp_nptr = NULL;
00269 struct ListNode *reInsertList = NULL;
00270 register struct ListNode *e;
00271
00272 assert(r && nn);
00273 assert(*nn);
00274 assert(tid >= 0);
00275
00276 if (!RTreeDeleteRect2(r, tid, *nn, &reInsertList)) {
00277
00278
00279
00280 while (reInsertList) {
00281 tmp_nptr = reInsertList->node;
00282 for (i = 0; i < MAXKIDS(tmp_nptr); i++) {
00283 if (tmp_nptr->branch[i].child) {
00284 RTreeInsertRect(&(tmp_nptr->branch[i].rect),
00285 (int)tmp_nptr->branch[i].child,
00286 nn, tmp_nptr->level);
00287 }
00288 }
00289 e = reInsertList;
00290 reInsertList = reInsertList->next;
00291 RTreeFreeNode(e->node);
00292 RTreeFreeListNode(e);
00293 }
00294
00295
00296 if ((*nn)->count == 1 && (*nn)->level > 0) {
00297 for (i = 0; i < NODECARD; i++) {
00298 tmp_nptr = (*nn)->branch[i].child;
00299 if (tmp_nptr)
00300 break;
00301 }
00302 assert(tmp_nptr);
00303 RTreeFreeNode(*nn);
00304 *nn = tmp_nptr;
00305 }
00306 return 0;
00307 }
00308 else {
00309 return 1;
00310 }
00311 }