node.c
Go to the documentation of this file.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 static void RTreeInitBranch(struct Branch *b)
00026 {
00027 RTreeInitRect(&(b->rect));
00028 b->child = NULL;
00029 }
00030
00031
00032 void RTreeInitNode(struct Node *N)
00033 {
00034 register struct Node *n = N;
00035 register int i;
00036
00037 n->count = 0;
00038 n->level = -1;
00039 for (i = 0; i < MAXCARD; i++)
00040 RTreeInitBranch(&(n->branch[i]));
00041 }
00042
00043
00044 struct Node *RTreeNewNode(void)
00045 {
00046 register struct Node *n;
00047
00048
00049 n = (struct Node *)malloc(sizeof(struct Node));
00050 assert(n);
00051 RTreeInitNode(n);
00052 return n;
00053 }
00054
00055 void RTreeFreeNode(struct Node *p)
00056 {
00057 assert(p);
00058
00059 free(p);
00060 }
00061
00062 static void RTreePrintBranch(struct Branch *b, int depth)
00063 {
00064 RTreePrintRect(&(b->rect), depth);
00065 RTreePrintNode(b->child, depth);
00066 }
00067
00068 extern void RTreeTabIn(int depth)
00069 {
00070 int i;
00071
00072 for (i = 0; i < depth; i++)
00073 putchar('\t');
00074 }
00075
00076
00077 void RTreePrintNode(struct Node *n, int depth)
00078 {
00079 int i;
00080
00081 assert(n);
00082
00083 RTreeTabIn(depth);
00084 fprintf(stdout, "node");
00085 if (n->level == 0)
00086 fprintf(stdout, " LEAF");
00087 else if (n->level > 0)
00088 fprintf(stdout, " NONLEAF");
00089 else
00090 fprintf(stdout, " TYPE=?");
00091 fprintf(stdout, " level=%d count=%d address=%o\n", n->level, n->count,
00092 (unsigned)n);
00093
00094 for (i = 0; i < n->count; i++) {
00095 if (n->level == 0) {
00096
00097
00098 }
00099 else {
00100 RTreeTabIn(depth);
00101 fprintf(stdout, "branch %d\n", i);
00102 RTreePrintBranch(&n->branch[i], depth + 1);
00103 }
00104 }
00105 }
00106
00107
00108
00109
00110
00111 struct Rect RTreeNodeCover(struct Node *N)
00112 {
00113 register struct Node *n = N;
00114 register int i, first_time = 1;
00115 struct Rect r;
00116
00117 assert(n);
00118
00119 RTreeInitRect(&r);
00120 for (i = 0; i < MAXKIDS(n); i++)
00121 if (n->branch[i].child) {
00122 if (first_time) {
00123 r = n->branch[i].rect;
00124 first_time = 0;
00125 }
00126 else
00127 r = RTreeCombineRect(&r, &(n->branch[i].rect));
00128 }
00129 return r;
00130 }
00131
00132
00133
00134
00135
00136
00137
00138
00139 int RTreePickBranch(struct Rect *R, struct Node *N)
00140 {
00141 register struct Rect *r = R;
00142 register struct Node *n = N;
00143 register struct Rect *rr;
00144 register int i, first_time = 1;
00145 RectReal increase, bestIncr = (RectReal) - 1, area, bestArea = 0;
00146 int best = 0;
00147 struct Rect tmp_rect;
00148
00149 assert(r && n);
00150
00151 for (i = 0; i < MAXKIDS(n); i++) {
00152 if (n->branch[i].child) {
00153 rr = &n->branch[i].rect;
00154 area = RTreeRectSphericalVolume(rr);
00155 tmp_rect = RTreeCombineRect(r, rr);
00156 increase = RTreeRectSphericalVolume(&tmp_rect) - area;
00157 if (increase < bestIncr || first_time) {
00158 best = i;
00159 bestArea = area;
00160 bestIncr = increase;
00161 first_time = 0;
00162 }
00163 else if (increase == bestIncr && area < bestArea) {
00164 best = i;
00165 bestArea = area;
00166 bestIncr = increase;
00167 }
00168 }
00169 }
00170 return best;
00171 }
00172
00173
00174
00175
00176
00177
00178
00179 int RTreeAddBranch(struct Branch *B, struct Node *N, struct Node **New_node)
00180 {
00181 register struct Branch *b = B;
00182 register struct Node *n = N;
00183 register struct Node **new_node = New_node;
00184 register int i;
00185
00186 assert(b);
00187 assert(n);
00188
00189 if (n->count < MAXKIDS(n)) {
00190 for (i = 0; i < MAXKIDS(n); i++) {
00191 if (n->branch[i].child == NULL) {
00192 n->branch[i] = *b;
00193 n->count++;
00194 break;
00195 }
00196 }
00197 return 0;
00198 }
00199 else {
00200 assert(new_node);
00201 RTreeSplitNode(n, b, new_node);
00202 return 1;
00203 }
00204 }
00205
00206
00207 void RTreeDisconnectBranch(struct Node *n, int i)
00208 {
00209 assert(n && i >= 0 && i < MAXKIDS(n));
00210 assert(n->branch[i].child);
00211
00212 RTreeInitBranch(&(n->branch[i]));
00213 n->count--;
00214 }
00215
00216
00217 void RTreeDestroyNode(struct Node *n)
00218 {
00219 int i;
00220
00221 if (n->level > 0) {
00222 for (i = 0; i < NODECARD; i++) {
00223 if (n->branch[i].child) {
00224 RTreeDestroyNode(n->branch[i].child);
00225 }
00226 }
00227 }
00228
00229
00230 RTreeFreeNode(n);
00231 }