Fixup draw.c not to special case based on HID name, use flags instead
[geda-pcb/pcjc2.git] / gts / hsurface.c
blob80ac66a06ae185a92ebb7927f75d815d74988b1c
1 /* GTS - Library for the manipulation of triangulated surfaces
2 * Copyright (C) 1999 Stéphane Popinet
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
14 * You should have received a copy of the GNU Library General Public
15 * License along with this library; if not, write to the
16 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
17 * Boston, MA 02111-1307, USA.
20 #include <stdlib.h>
21 #include <string.h>
22 #include "gts.h"
24 #define HEAP_INSERT_HSPLIT(h, e) ((e)->index = gts_eheap_insert (h, e))
25 #define HEAP_REMOVE_HSPLIT(h, e) (gts_eheap_remove (h, (e)->index),\
26 (e)->index = NULL)
28 static void hsplit_init (GtsHSplit * hsplit)
30 hsplit->index = NULL;
31 hsplit->parent = NULL;
32 hsplit->nchild = 0;
35 /**
36 * gts_hsplit_class:
38 * Returns: the #GtsHSplitClass.
40 GtsHSplitClass * gts_hsplit_class (void)
42 static GtsHSplitClass * klass = NULL;
44 if (klass == NULL) {
45 GtsObjectClassInfo hsplit_info = {
46 "GtsHSplit",
47 sizeof (GtsHSplit),
48 sizeof (GtsHSplitClass),
49 (GtsObjectClassInitFunc) NULL,
50 (GtsObjectInitFunc) hsplit_init,
51 (GtsArgSetFunc) NULL,
52 (GtsArgGetFunc) NULL
54 klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_split_class ()),
55 &hsplit_info);
58 return klass;
61 /**
62 * gts_hsplit_new:
63 * @klass: a #GtsHSplitClass.
64 * @vs: a #GtsSplit.
66 * Returns: a new #GtsHSplit, hierarchical extension of @vs.
68 GtsHSplit * gts_hsplit_new (GtsHSplitClass * klass, GtsSplit * vs)
70 GtsHSplit * hs;
72 g_return_val_if_fail (vs != NULL, NULL);
74 hs = GTS_HSPLIT (gts_object_new (GTS_OBJECT_CLASS (klass)));
75 memcpy (hs, vs, sizeof (GtsSplit));
76 GTS_OBJECT (hs)->reserved = NULL;
78 return hs;
81 /**
82 * gts_hsplit_collapse:
83 * @hs: a #GtsHSplit.
84 * @hsurface: a #GtsHSurface.
86 * Collapses the #GtsSplit defined by @hs, updates the expandable and
87 * collapsable priority heaps of @hsurface.
89 void gts_hsplit_collapse (GtsHSplit * hs,
90 GtsHSurface * hsurface)
92 GtsHSplit * parent;
93 GtsSplit * vs;
95 g_return_if_fail (hs != NULL);
96 g_return_if_fail (hs->nchild == 2);
97 g_return_if_fail (hsurface != NULL);
99 gts_split_collapse (GTS_SPLIT (hs), hsurface->s->edge_class, NULL);
101 hsurface->nvertex--;
102 hs->nchild = 0;
103 HEAP_REMOVE_HSPLIT (hsurface->collapsable, hs);
104 HEAP_INSERT_HSPLIT (hsurface->expandable, hs);
106 vs = GTS_SPLIT (hs);
107 if (GTS_IS_HSPLIT (vs->v1))
108 HEAP_REMOVE_HSPLIT (hsurface->expandable, GTS_HSPLIT (vs->v1));
109 if (GTS_IS_HSPLIT (vs->v2))
110 HEAP_REMOVE_HSPLIT (hsurface->expandable, GTS_HSPLIT (vs->v2));
112 parent = hs->parent;
113 if (parent && ++parent->nchild == 2)
114 HEAP_INSERT_HSPLIT (hsurface->collapsable, parent);
118 * gts_hsplit_expand:
119 * @hs: a #GtsHSplit.
120 * @hsurface: a #GtsHSurface.
122 * Expands the #GtsSplit defined by @hs (which must be expandable)
123 * and updates the priority heaps of @hsurface.
125 void gts_hsplit_expand (GtsHSplit * hs,
126 GtsHSurface * hsurface)
128 GtsHSplit * parent;
129 GtsSplit * vs;
131 g_return_if_fail (hs != NULL);
132 g_return_if_fail (hsurface != NULL);
133 g_return_if_fail (hs->nchild == 0);
135 gts_split_expand (GTS_SPLIT (hs), hsurface->s, hsurface->s->edge_class);
136 hsurface->nvertex++;
137 hs->nchild = 2;
138 HEAP_REMOVE_HSPLIT (hsurface->expandable, hs);
139 HEAP_INSERT_HSPLIT (hsurface->collapsable, hs);
141 vs = GTS_SPLIT (hs);
142 if (GTS_IS_HSPLIT (vs->v1))
143 HEAP_INSERT_HSPLIT (hsurface->expandable, GTS_HSPLIT (vs->v1));
144 if (GTS_IS_HSPLIT (vs->v2))
145 HEAP_INSERT_HSPLIT (hsurface->expandable, GTS_HSPLIT (vs->v2));
147 parent = hs->parent;
148 if (parent && parent->nchild-- == 2)
149 HEAP_REMOVE_HSPLIT (hsurface->collapsable, parent);
152 static void hsurface_destroy (GtsObject * object)
154 GtsHSurface * hs = GTS_HSURFACE (object);
156 gts_hsurface_traverse (hs, G_POST_ORDER, -1,
157 (GtsSplitTraverseFunc) gts_object_destroy,
158 NULL);
159 g_slist_free (hs->roots);
160 if (hs->expandable)
161 gts_eheap_destroy (hs->expandable);
162 if (hs->collapsable)
163 gts_eheap_destroy (hs->collapsable);
164 g_ptr_array_free (hs->split, TRUE);
166 (* GTS_OBJECT_CLASS (gts_hsurface_class ())->parent_class->destroy) (object);
169 static void hsurface_class_init (GtsObjectClass * klass)
171 klass->destroy = hsurface_destroy;
174 static void hsurface_init (GtsHSurface * hsurface)
176 hsurface->s = NULL;
177 hsurface->roots = NULL;
178 hsurface->expandable = hsurface->collapsable = NULL;
179 hsurface->split = g_ptr_array_new ();
180 hsurface->nvertex = 0;
184 * gts_hsurface_class:
186 * Returns: the #GtsHSurfaceClass.
188 GtsHSurfaceClass * gts_hsurface_class (void)
190 static GtsHSurfaceClass * klass = NULL;
192 if (klass == NULL) {
193 GtsObjectClassInfo hsurface_info = {
194 "GtsHSurface",
195 sizeof (GtsHSurface),
196 sizeof (GtsHSurfaceClass),
197 (GtsObjectClassInitFunc) hsurface_class_init,
198 (GtsObjectInitFunc) hsurface_init,
199 (GtsArgSetFunc) NULL,
200 (GtsArgGetFunc) NULL
202 klass = gts_object_class_new (gts_object_class (),
203 &hsurface_info);
206 return klass;
210 * gts_hsurface_new:
211 * @klass: a #GtsHSurfaceClass.
212 * @hsplit_class: a #GtsHSplitClass.
213 * @psurface: a #GtsPSurface.
214 * @expand_key: a #GtsKeyFunc used to order the priority heap of expandable
215 * #GtsHSplit.
216 * @expand_data: data to be passed to @expand_key.
217 * @collapse_key: a #GtsKeyFunc used to order the priority heap of collapsable
218 * #GtsHSplit.
219 * @collapse_data: data to be passed to @collapsed_key.
221 * Returns: a new #GtsHSurface, hierarchical extension of @psurface
222 * and using #GtsHSplit of class @hsplit_class. Note that @psurface is
223 * destroyed in the process.
225 GtsHSurface * gts_hsurface_new (GtsHSurfaceClass * klass,
226 GtsHSplitClass * hsplit_class,
227 GtsPSurface * psurface,
228 GtsKeyFunc expand_key,
229 gpointer expand_data,
230 GtsKeyFunc collapse_key,
231 gpointer collapse_data)
233 GtsHSurface * hsurface;
235 g_return_val_if_fail (klass != NULL, NULL);
236 g_return_val_if_fail (hsplit_class != NULL, NULL);
237 g_return_val_if_fail (psurface != NULL, NULL);
238 g_return_val_if_fail (expand_key != NULL, NULL);
239 g_return_val_if_fail (collapse_key != NULL, NULL);
241 hsurface = GTS_HSURFACE (gts_object_new (GTS_OBJECT_CLASS (klass)));
242 hsurface->s = psurface->s;
243 hsurface->expandable = gts_eheap_new (expand_key, expand_data);
244 hsurface->collapsable = gts_eheap_new (collapse_key, collapse_data);
245 g_ptr_array_set_size (hsurface->split, psurface->split->len);
247 while (gts_psurface_remove_vertex (psurface))
249 while (psurface->pos) {
250 GtsSplit * vs = g_ptr_array_index (psurface->split, psurface->pos - 1);
251 GtsHSplit * hs = gts_hsplit_new (hsplit_class, vs);
253 g_ptr_array_index (hsurface->split, psurface->pos - 1) = hs;
254 psurface->pos--;
256 hs->parent = GTS_OBJECT (vs)->reserved;
257 if (hs->parent) {
258 GtsSplit * vsp = GTS_SPLIT (hs->parent);
260 if (vsp->v1 == GTS_OBJECT (vs)) {
261 g_assert (vsp->v2 != GTS_OBJECT (vs));
262 vsp->v1 = GTS_OBJECT (hs);
264 else {
265 g_assert (vsp->v2 == GTS_OBJECT (vs));
266 vsp->v2 = GTS_OBJECT (hs);
269 else
270 hsurface->roots = g_slist_prepend (hsurface->roots, hs);
272 hs->nchild = 0;
273 if (GTS_IS_SPLIT (vs->v1))
274 GTS_OBJECT (vs->v1)->reserved = hs;
275 else
276 hs->nchild++;
277 if (GTS_IS_SPLIT (vs->v2))
278 GTS_OBJECT (vs->v2)->reserved = hs;
279 else
280 hs->nchild++;
282 gts_split_expand (vs, psurface->s, psurface->s->edge_class);
284 if (hs->nchild == 2)
285 HEAP_INSERT_HSPLIT (hsurface->collapsable, hs);
288 hsurface->nvertex = gts_surface_vertex_number (hsurface->s);
289 gts_object_destroy (GTS_OBJECT (psurface));
291 return hsurface;
295 * gts_hsurface_traverse:
296 * @hsurface: a #GtsHSurface.
297 * @order: the order in which nodes are visited - G_PRE_ORDER or G_POST_ORDER.
298 * @depth: the maximum depth of the traversal. Nodes below this depth
299 * will not be visited. If max_depth is -1 all nodes in the tree are
300 * visited. If depth is 1, only the root is visited. If depth is 2,
301 * the root and its children are visited. And so on.
302 * @func: the function to call for each visited #GtsHSplit.
303 * @data: user data to pass to the function.
305 * Traverses a hierarchical surface starting from its roots. It calls
306 * the given function for each #GtsHSplit visited.
307 * See also gts_split_traverse().
309 void gts_hsurface_traverse (GtsHSurface * hsurface,
310 GTraverseType order,
311 gint depth,
312 GtsSplitTraverseFunc func,
313 gpointer data)
315 GSList * i;
317 g_return_if_fail (hsurface != NULL);
318 g_return_if_fail (func != NULL);
319 g_return_if_fail (order < G_LEVEL_ORDER);
320 g_return_if_fail (depth == -1 || depth > 0);
322 i = hsurface->roots;
323 while (i) {
324 gts_split_traverse (i->data, order, depth, func, data);
325 i = i->next;
330 * gts_hsurface_foreach:
331 * @hsurface: a #GtsHSurface.
332 * @order: the order in which #GtsHSplit are visited - G_PRE_ORDER or
333 * G_POST_ORDER.
334 * @func: the function to call for each visited #GtsHSplit.
335 * @data: user data to pass to the function.
337 * Starts by expanding all the #GtsHSplit of @hsurface. If @order is
338 * G_PRE_ORDER, calls @func for each #GtsHSplit and collapses it. If
339 * order is G_POST_ORDER, collapses each #GtsHSplit first and then
340 * calls @func. The traversal can be halted at any point by returning
341 * TRUE from func.
343 void gts_hsurface_foreach (GtsHSurface * hsurface,
344 GTraverseType order,
345 GtsFunc func,
346 gpointer data)
348 GtsHSplit * hs;
349 guint i = 0, len;
350 gboolean stop = FALSE;
352 g_return_if_fail (hsurface != NULL);
353 g_return_if_fail (func != NULL);
354 g_return_if_fail (order == G_PRE_ORDER || order == G_POST_ORDER);
356 while ((hs = gts_eheap_top (hsurface->expandable, NULL)))
357 gts_hsplit_expand (hs, hsurface);
359 len = hsurface->split->len;
360 switch (order) {
361 case G_PRE_ORDER:
362 while (i < len && !stop) {
363 GtsHSplit * hs = g_ptr_array_index (hsurface->split, i);
364 stop = (*func) (hs, data);
365 if (!stop)
366 gts_hsplit_collapse (hs, hsurface);
367 i++;
369 break;
370 case G_POST_ORDER:
371 while (i < len && !stop) {
372 GtsHSplit * hs = g_ptr_array_index (hsurface->split, i);
373 gts_hsplit_collapse (hs, hsurface);
374 stop = (*func) (hs, data);
375 i++;
377 break;
378 default:
379 g_assert_not_reached ();
384 * gts_hsurface_height:
385 * @hsurface: a #GtsHSurface.
387 * Returns: the maximum height of the tree described by @hsurface.
389 guint gts_hsurface_height (GtsHSurface * hsurface)
391 GSList * i;
392 guint height = 0;
394 g_return_val_if_fail (hsurface != NULL, 0);
396 i = hsurface->roots;
397 while (i) {
398 guint tmp_height = gts_split_height (i->data);
399 if (tmp_height > height)
400 height = tmp_height;
401 i = i->next;
404 return height;