1 /* vim:set shiftwidth=4 ts=8: */
2
3 /*************************************************************************
4 * Copyright (c) 2011 AT&T Intellectual Property
5 * All rights reserved. This program and the accompanying materials
6 * are made available under the terms of the Eclipse Public License v1.0
7 * which accompanies this distribution, and is available at
8 * http://www.eclipse.org/legal/epl-v10.html
9 *
10 * Contributors: See CVS logs. Details at http://www.graphviz.org/
11 *************************************************************************/
12
13 #include "index.h"
14 #include <stdio.h>
15 #include <assert.h>
16 #include "split.q.h"
17 #include "logic.h"
18
19 /* Forward declarations */
20 static void MethodZero(RTree_t * rtp);
21 static void InitPVars(RTree_t * rtp);
22 static void LoadNodes(RTree_t * rtp, Node_t * n, Node_t * q,
23 struct PartitionVars *p);
24 static void Classify(RTree_t * rtp, int i, int group);
25 static void PickSeeds(RTree_t * rtp);
26 static void GetBranches(RTree_t * rtp, Node_t * n, Branch_t * b);
27
28 /*-----------------------------------------------------------------------------
29 | Split a node.
30 | Divides the nodes branches and the extra one between two nodes.
31 | Old node is one of the new ones, and one really new one is created.
32 | Tries more than one method for choosing a partition, uses best result.
33 -----------------------------------------------------------------------------*/
SplitNode(RTree_t * rtp,Node_t * n,Branch_t * b,Node_t ** nn)34 void SplitNode(RTree_t * rtp, Node_t * n, Branch_t * b, Node_t ** nn)
35 {
36 register struct PartitionVars *p;
37 register int level;
38 int area;
39
40 assert(n);
41 assert(b);
42
43 #ifdef RTDEBUG
44 fprintf(stderr, "Splitting:\n");
45 PrintNode(n);
46 fprintf(stderr, "new branch:\n");
47 PrintBranch(-1, b);
48 #endif
49
50 if (rtp->StatFlag) {
51 if (rtp->Deleting)
52 rtp->DeSplitCount++;
53 else
54 rtp->InSplitCount++;
55 }
56
57 /* load all the branches into a buffer, initialize old node */
58 level = n->level;
59 GetBranches(rtp, n, b);
60
61 #ifdef RTDEBUG
62 {
63 int i;
64 /* Indicate that a split is about to take place */
65 for (i = 0; i < NODECARD + 1; i++) {
66 PrintRect(&rtp->split.BranchBuf[i].rect);
67 }
68 PrintRect(&rtp->split.CoverSplit);
69 }
70 #endif
71
72 /* find partition */
73 p = &rtp->split.Partitions[0];
74 MethodZero(rtp);
75
76 area = RectArea(&p->cover[0]) + RectArea(&p->cover[1]);
77
78 /* record how good the split was for statistics */
79 if (rtp->StatFlag && !rtp->Deleting && area)
80 rtp->SplitMeritSum += (float) rtp->split.CoverSplitArea / area;
81
82 /* put branches from buffer into 2 nodes according to chosen partition */
83 *nn = RTreeNewNode(rtp);
84 (*nn)->level = n->level = level;
85 LoadNodes(rtp, n, *nn, p);
86 assert(n->count + (*nn)->count == NODECARD + 1);
87
88 #ifdef RTDEBUG
89 PrintPVars(p);
90 fprintf(stderr, "group 0:\n");
91 PrintNode(n);
92 fprintf(stderr, "group 1:\n");
93 PrintNode(*nn);
94 fprintf(stderr, "\n");
95 #endif
96
97 }
98
99 /*-----------------------------------------------------------------------------
100 | Load branch buffer with branches from full node plus the extra branch.
101 -----------------------------------------------------------------------------*/
GetBranches(RTree_t * rtp,Node_t * n,Branch_t * b)102 static void GetBranches(RTree_t * rtp, Node_t * n, Branch_t * b)
103 {
104 register int i;
105
106 assert(n);
107 assert(b);
108
109 /* load the branch buffer */
110 for (i = 0; i < NODECARD; i++) {
111 assert(n->branch[i].child); /* node should have every entry full */
112 rtp->split.BranchBuf[i] = n->branch[i];
113 }
114 rtp->split.BranchBuf[NODECARD] = *b;
115
116 /* calculate rect containing all in the set */
117 rtp->split.CoverSplit = rtp->split.BranchBuf[0].rect;
118 for (i = 1; i < NODECARD + 1; i++) {
119 rtp->split.CoverSplit = CombineRect(&rtp->split.CoverSplit,
120 &rtp->split.BranchBuf[i].rect);
121 }
122 rtp->split.CoverSplitArea = RectArea(&rtp->split.CoverSplit);
123
124 InitNode(n);
125 }
126
127 /*-----------------------------------------------------------------------------
128 | Method #0 for choosing a partition:
129 | As the seeds for the two groups, pick the two rects that would waste the
130 | most area if covered by a single rectangle, i.e. evidently the worst pair
131 | to have in the same group.
132 | Of the remaining, one at a time is chosen to be put in one of the two groups.
133 | The one chosen is the one with the greatest difference in area expansion
134 | depending on which group - the rect most strongly attracted to one group
135 | and repelled from the other.
136 | If one group gets too full (more would force other group to violate min
137 | fill requirement) then other group gets the rest.
138 | These last are the ones that can go in either group most easily.
139 -----------------------------------------------------------------------------*/
MethodZero(RTree_t * rtp)140 static void MethodZero(RTree_t * rtp)
141 {
142 register Rect_t *r;
143 register int i, growth0, growth1, diff, biggestDiff;
144 register int group, chosen = 0, betterGroup = 0;
145
146 InitPVars(rtp);
147 PickSeeds(rtp);
148
149 while (rtp->split.Partitions[0].count[0] +
150 rtp->split.Partitions[0].count[1] < NODECARD + 1 &&
151 rtp->split.Partitions[0].count[0] < NODECARD + 1 - rtp->MinFill
152 && rtp->split.Partitions[0].count[1] <
153 NODECARD + 1 - rtp->MinFill) {
154 biggestDiff = -1;
155 for (i = 0; i < NODECARD + 1; i++) {
156 if (!rtp->split.Partitions[0].taken[i]) {
157 Rect_t rect;
158 r = &rtp->split.BranchBuf[i].rect;
159 /* growth0 = RectArea(&CombineRect(r,
160 &rtp->split.Partitions[0].cover[0])) -
161 rtp->split.Partitions[0].area[0];
162 */
163 /* growth1 = RectArea(&CombineRect(r,
164 &rtp->split.Partitions[0].cover[1])) -
165 rtp->split.Partitions[0].area[1];
166 */
167 rect = CombineRect(r, &rtp->split.Partitions[0].cover[0]);
168 growth0 =
169 RectArea(&rect) - rtp->split.Partitions[0].area[0];
170 rect = CombineRect(r, &rtp->split.Partitions[0].cover[1]);
171 growth1 =
172 RectArea(&rect) - rtp->split.Partitions[0].area[1];
173 diff = growth1 - growth0;
174 if (diff >= 0)
175 group = 0;
176 else {
177 group = 1;
178 diff = -diff;
179 }
180
181 if (diff > biggestDiff) {
182 biggestDiff = diff;
183 chosen = i;
184 betterGroup = group;
185 } else if (diff == biggestDiff &&
186 rtp->split.Partitions[0].count[group] <
187 rtp->split.Partitions[0].count[betterGroup]) {
188 chosen = i;
189 betterGroup = group;
190 }
191 }
192 }
193 Classify(rtp, chosen, betterGroup);
194 }
195
196 /* if one group too full, put remaining rects in the other */
197 if (rtp->split.Partitions[0].count[0] +
198 rtp->split.Partitions[0].count[1] < NODECARD + 1) {
199 group = 0;
200 if (rtp->split.Partitions[0].count[0] >=
201 NODECARD + 1 - rtp->MinFill)
202 group = 1;
203 for (i = 0; i < NODECARD + 1; i++) {
204 if (!rtp->split.Partitions[0].taken[i])
205 Classify(rtp, i, group);
206 }
207 }
208
209 assert(rtp->split.Partitions[0].count[0] +
210 rtp->split.Partitions[0].count[1] == NODECARD + 1);
211 assert(rtp->split.Partitions[0].count[0] >= rtp->MinFill
212 && rtp->split.Partitions[0].count[1] >= rtp->MinFill);
213 }
214
215 /*-----------------------------------------------------------------------------
216 | Pick two rects from set to be the first elements of the two groups.
217 | Pick the two that waste the most area if covered by a single rectangle.
218 -----------------------------------------------------------------------------*/
PickSeeds(RTree_t * rtp)219 static void PickSeeds(RTree_t * rtp)
220 {
221 register int i, j;
222 unsigned int waste, worst;
223 int seed0 = 0, seed1 = 0;
224 unsigned int area[NODECARD + 1];
225
226 for (i = 0; i < NODECARD + 1; i++)
227 area[i] = RectArea(&rtp->split.BranchBuf[i].rect);
228
229 //worst = -rtp->split.CoverSplitArea - 1;
230 worst=0;
231 for (i = 0; i < NODECARD; i++) {
232 for (j = i + 1; j < NODECARD + 1; j++) {
233 Rect_t rect;
234 /* waste = RectArea(&CombineRect(&rtp->split.BranchBuf[i].rect,
235 // &rtp->split.BranchBuf[j].rect)) - area[i] - area[j];
236 */
237 rect = CombineRect(&rtp->split.BranchBuf[i].rect,
238 &rtp->split.BranchBuf[j].rect);
239 waste = RectArea(&rect) - area[i] - area[j];
240 if (waste > worst) {
241 worst = waste;
242 seed0 = i;
243 seed1 = j;
244 }
245 }
246 }
247 Classify(rtp, seed0, 0);
248 Classify(rtp, seed1, 1);
249 }
250
251 /*-----------------------------------------------------------------------------
252 | Put a branch in one of the groups.
253 -----------------------------------------------------------------------------*/
Classify(RTree_t * rtp,int i,int group)254 static void Classify(RTree_t * rtp, int i, int group)
255 {
256
257 assert(!rtp->split.Partitions[0].taken[i]);
258
259 rtp->split.Partitions[0].partition[i] = group;
260 rtp->split.Partitions[0].taken[i] = TRUE;
261
262 if (rtp->split.Partitions[0].count[group] == 0)
263 rtp->split.Partitions[0].cover[group] =
264 rtp->split.BranchBuf[i].rect;
265 else
266 rtp->split.Partitions[0].cover[group] =
267 CombineRect(&rtp->split.BranchBuf[i].rect,
268 &rtp->split.Partitions[0].cover[group]);
269 rtp->split.Partitions[0].area[group] =
270 RectArea(&rtp->split.Partitions[0].cover[group]);
271 rtp->split.Partitions[0].count[group]++;
272
273 # ifdef RTDEBUG
274 {
275 /* redraw entire group and its cover */
276 int j;
277 MFBSetColor(WHITE); /* cover is white */
278 PrintRect(&rtp->split.Partitions[0].cover[group]);
279 MFBSetColor(group + 3); /* group 0 green, group 1 blue */
280 for (j = 0; j < NODECARD + 1; j++) {
281 if (rtp->split.Partitions[0].taken[j] &&
282 rtp->split.Partitions[0].partition[j] == group)
283 PrintRect(&rtrtp->split.Partitions[0].BranchBuf[j].rect);
284 }
285 GraphChar();
286 }
287 # endif
288 }
289
290 /*-----------------------------------------------------------------------------
291 | Copy branches from the buffer into two nodes according to the partition.
292 -----------------------------------------------------------------------------*/
LoadNodes(RTree_t * rtp,Node_t * n,Node_t * q,struct PartitionVars * p)293 static void LoadNodes(RTree_t * rtp, Node_t * n, Node_t * q,
294 struct PartitionVars *p)
295 {
296 register int i;
297 assert(n);
298 assert(q);
299 assert(p);
300
301 for (i = 0; i < NODECARD + 1; i++) {
302 assert(rtp->split.Partitions[0].partition[i] == 0 ||
303 rtp->split.Partitions[0].partition[i] == 1);
304 if (rtp->split.Partitions[0].partition[i] == 0)
305 AddBranch(rtp, &rtp->split.BranchBuf[i], n, NULL);
306 else if (rtp->split.Partitions[0].partition[i] == 1)
307 AddBranch(rtp, &rtp->split.BranchBuf[i], q, NULL);
308 }
309 }
310
311 /*-----------------------------------------------------------------------------
312 | Initialize a PartitionVars structure.
313 -----------------------------------------------------------------------------*/
InitPVars(RTree_t * rtp)314 static void InitPVars(RTree_t * rtp)
315 {
316 register int i;
317
318 rtp->split.Partitions[0].count[0] = rtp->split.Partitions[0].count[1] =
319 0;
320 rtp->split.Partitions[0].cover[0] = rtp->split.Partitions[0].cover[1] =
321 NullRect();
322 rtp->split.Partitions[0].area[0] = rtp->split.Partitions[0].area[1] =
323 0;
324 for (i = 0; i < NODECARD + 1; i++) {
325 rtp->split.Partitions[0].taken[i] = FALSE;
326 rtp->split.Partitions[0].partition[i] = -1;
327 }
328 }
329
330 #ifdef RTDEBUG
331
332 /*-----------------------------------------------------------------------------
333 | Print out data for a partition from PartitionVars struct.
334 -----------------------------------------------------------------------------*/
PrintPVars(RTree_t * rtp)335 PrintPVars(RTree_t * rtp)
336 {
337 register int i;
338
339 fprintf(stderr, "\npartition:\n");
340 for (i = 0; i < NODECARD + 1; i++) {
341 fprintf(stderr, "%3d\t", i);
342 }
343 fprintf(stderr, "\n");
344 for (i = 0; i < NODECARD + 1; i++) {
345 if (rtp->split.Partitions[0].taken[i])
346 fprintf(stderr, " t\t");
347 else
348 fprintf(stderr, "\t");
349 }
350 fprintf(stderr, "\n");
351 for (i = 0; i < NODECARD + 1; i++) {
352 fprintf(stderr, "%3d\t", rtp->split.Partitions[0].partition[i]);
353 }
354 fprintf(stderr, "\n");
355
356 fprintf(stderr, "count[0] = %d area = %d\n",
357 rtp->split.Partitions[0].count[0],
358 rtp->split.Partitions[0].area[0]);
359 fprintf(stderr, "count[1] = %d area = %d\n",
360 rtp->split.Partitions[0].count[1],
361 rtp->split.Partitions[0].area[1]);
362 if (rtp->split.Partitions[0].area[0] +
363 rtp->split.Partitions[0].area[1] > 0) {
364 fprintf(stderr, "total area = %d effectiveness = %3.2f\n",
365 rtp->split.Partitions[0].area[0] +
366 rtp->split.Partitions[0].area[1],
367 (float) rtp->split.CoverSplitArea /
368 (rtp->split.Partitions[0].area[0] +
369 rtp->split.Partitions[0].area[1]));
370 }
371 fprintf(stderr, "cover[0]:\n");
372 PrintRect(&rtp->split.Partitions[0].cover[0]);
373
374 fprintf(stderr, "cover[1]:\n");
375 PrintRect(&rtp->split.Partitions[0].cover[1]);
376 }
377 #endif
378