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 <stdlib.h>
14
15#include "index.h"
16#include <stdio.h>
17#include <assert.h>
18#include "node.h"
19
20/* Make a new node and initialize to have all branch cells empty.
21*/
22Node_t *RTreeNewNode(RTree_t * rtp)
23{
24 register Node_t *n;
25
26 rtp->NodeCount++;
27 n = (Node_t *) malloc(sizeof(Node_t));
28 InitNode(n);
29 return n;
30}
31
32void RTreeFreeNode(RTree_t * rtp, Node_t * p)
33{
34 rtp->NodeCount--;
35 if (p->level == 0)
36 rtp->LeafCount--;
37 else
38 rtp->NonLeafCount--;
39 free(p);
40}
41
42/* Initialize a Node structure.
43*/
44void InitNode(Node_t * n)
45{
46 register int i;
47 n->count = 0;
48 n->level = -1;
49 for (i = 0; i < NODECARD; i++)
50 InitBranch(&(n->branch[i]));
51}
52
53/* Initialize one branch cell in a node.
54*/
55void InitBranch(Branch_t * b)
56{
57 InitRect(&(b->rect));
58 b->child = NULL;
59}
60
61#ifdef RTDEBUG
62/* Print out the data in a node.
63*/
64void PrintNode(Node_t * n)
65{
66 int i;
67 assert(n);
68
69 fprintf(stderr, "node");
70 if (n->level == 0)
71 fprintf(stderr, " LEAF");
72 else if (n->level > 0)
73 fprintf(stderr, " NONLEAF");
74 else
75 fprintf(stderr, " TYPE=?");
76 fprintf(stderr, " level=%d count=%d child address=%X\n",
77 n->level, n->count, (unsigned int) n);
78
79 for (i = 0; i < NODECARD; i++) {
80 if (n->branch[i].child != NULL)
81 PrintBranch(i, &n->branch[i]);
82 }
83}
84
85void PrintBranch(int i, Branch_t * b)
86{
87 fprintf(stderr, " child[%d] X%X\n", i, (unsigned int) b->child);
88 PrintRect(&(b->rect));
89}
90#endif
91
92/* Find the smallest rectangle that includes all rectangles in
93** branches of a node.
94*/
95Rect_t NodeCover(Node_t * n)
96{
97 register int i, flag;
98 Rect_t r;
99 assert(n);
100
101 InitRect(&r);
102 flag = 1;
103 for (i = 0; i < NODECARD; i++)
104 if (n->branch[i].child) {
105 if (flag) {
106 r = n->branch[i].rect;
107 flag = 0;
108 } else
109 r = CombineRect(&r, &(n->branch[i].rect));
110 }
111 return r;
112}
113
114/* Pick a branch. Pick the one that will need the smallest increase
115** in area to accommodate the new rectangle. This will result in the
116** least total area for the covering rectangles in the current node.
117** In case of a tie, pick the one which was smaller before, to get
118** the best resolution when searching.
119*/
120int PickBranch(Rect_t * r, Node_t * n)
121{
122 register Rect_t *rr=0;
123 register int i=0, flag=1, increase=0, bestIncr=0, area=0, bestArea=0;
124 int best=0;
125 assert(r && n);
126
127 for (i = 0; i < NODECARD; i++) {
128 if (n->branch[i].child) {
129 Rect_t rect;
130 rr = &n->branch[i].rect;
131 area = RectArea(rr);
132 /* increase = RectArea(&CombineRect(r, rr)) - area; */
133 rect = CombineRect(r, rr);
134 increase = RectArea(&rect) - area;
135 if (increase < bestIncr || flag) {
136 best = i;
137 bestArea = area;
138 bestIncr = increase;
139 flag = 0;
140 } else if (increase == bestIncr && area < bestArea) {
141 best = i;
142 bestArea = area;
143 bestIncr = increase;
144 }
145# ifdef RTDEBUG
146 fprintf(stderr,
147 "i=%d area before=%d area after=%d increase=%d\n",
148 i, area, area + increase, increase);
149# endif
150 }
151 }
152# ifdef RTDEBUG
153 fprintf(stderr, "\tpicked %d\n", best);
154# endif
155 return best;
156}
157
158/* Add a branch to a node. Split the node if necessary.
159** Returns 0 if node not split. Old node updated.
160** Returns 1 if node split, sets *new to address of new node.
161** Old node updated, becomes one of two.
162*/
163int AddBranch(RTree_t * rtp, Branch_t * b, Node_t * n, Node_t ** new)
164{
165 register int i;
166
167 assert(b);
168 assert(n);
169
170 if (n->count < NODECARD) { /* split won't be necessary */
171 for (i = 0; i < NODECARD; i++) { /* find empty branch */
172 if (n->branch[i].child == NULL) {
173 n->branch[i] = *b;
174 n->count++;
175 break;
176 }
177 }
178 assert(i < NODECARD);
179 return 0;
180 } else {
181 if (rtp->StatFlag) {
182 if (rtp->Deleting)
183 rtp->DeTouchCount++;
184 else
185 rtp->InTouchCount++;
186 }
187 assert(new);
188 SplitNode(rtp, n, b, new);
189 if (n->level == 0)
190 rtp->LeafCount++;
191 else
192 rtp->NonLeafCount++;
193 return 1;
194 }
195}
196
197/* Disconnect a dependent node.
198*/
199void DisconBranch(Node_t * n, int i)
200{
201 assert(n && i >= 0 && i < NODECARD);
202 assert(n->branch[i].child);
203
204 InitBranch(&(n->branch[i]));
205 n->count--;
206}
207