gts/hsurface.c

   1 /* GTS - Library for the manipulation of triangulated surfaces
   2  * Copyright (C) 1999 Stéphane Popinet
   3  *
   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.
   8  *
   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.
  13  *
  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.
  18  */
  19
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #include "gts.h"
  23
  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)
  27
  28 static void hsplit_init (GtsHSplit * hsplit)
  29 {
  30   hsplit->index = NULL;
  31   hsplit->parent = NULL;
  32   hsplit->nchild = 0;
  33 }
  34
  35 /**
  36  * gts_hsplit_class:
  37  *
  38  * Returns: the #GtsHSplitClass.
  39  */
  40 GtsHSplitClass * gts_hsplit_class (void)
  41 {
  42   static GtsHSplitClass * klass = NULL;
  43
  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
  53     };
  54     klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_split_class ()),
  55                                   &hsplit_info);
  56   }
  57
  58   return klass;
  59 }
  60
  61 /**
  62  * gts_hsplit_new:
  63  * @klass: a #GtsHSplitClass.
  64  * @vs: a #GtsSplit.
  65  *
  66  * Returns: a new #GtsHSplit, hierarchical extension of @vs.
  67  */
  68 GtsHSplit * gts_hsplit_new (GtsHSplitClass * klass, GtsSplit * vs)
  69 {
  70   GtsHSplit * hs;
  71
  72   g_return_val_if_fail (vs != NULL, NULL);
  73
  74   hs = GTS_HSPLIT (gts_object_new (GTS_OBJECT_CLASS (klass)));
  75   memcpy (hs, vs, sizeof (GtsSplit));
  76   GTS_OBJECT (hs)->reserved = NULL;
  77
  78   return hs;
  79 }
  80
  81 /**
  82  * gts_hsplit_collapse:
  83  * @hs: a #GtsHSplit.
  84  * @hsurface: a #GtsHSurface.
  85  *
  86  * Collapses the #GtsSplit defined by @hs, updates the expandable and
  87  * collapsable priority heaps of @hsurface.
  88  */
  89 void gts_hsplit_collapse (GtsHSplit * hs,
  90                           GtsHSurface * hsurface)
  91 {
  92   GtsHSplit * parent;
  93   GtsSplit * vs;
  94
  95   g_return_if_fail (hs != NULL);
  96   g_return_if_fail (hs->nchild == 2);
  97   g_return_if_fail (hsurface != NULL);
  98
  99   gts_split_collapse (GTS_SPLIT (hs), hsurface->s->edge_class, NULL);
 100
 101   hsurface->nvertex--;
 102   hs->nchild = 0;
 103   HEAP_REMOVE_HSPLIT (hsurface->collapsable, hs);
 104   HEAP_INSERT_HSPLIT (hsurface->expandable, hs);
 105
 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));
 111
 112   parent = hs->parent;
 113   if (parent && ++parent->nchild == 2)
 114     HEAP_INSERT_HSPLIT (hsurface->collapsable, parent);
 115 }
 116
 117 /**
 118  * gts_hsplit_expand:
 119  * @hs: a #GtsHSplit.
 120  * @hsurface: a #GtsHSurface.
 121  *
 122  * Expands the #GtsSplit defined by @hs (which must be expandable)
 123  * and updates the priority heaps of @hsurface.
 124  */
 125 void gts_hsplit_expand (GtsHSplit * hs,
 126                         GtsHSurface * hsurface)
 127 {
 128   GtsHSplit * parent;
 129   GtsSplit * vs;
 130
 131   g_return_if_fail (hs != NULL);
 132   g_return_if_fail (hsurface != NULL);
 133   g_return_if_fail (hs->nchild == 0);
 134
 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);
 140
 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));
 146
 147   parent = hs->parent;
 148   if (parent && parent->nchild-- == 2)
 149     HEAP_REMOVE_HSPLIT (hsurface->collapsable, parent);
 150 }
 151
 152 static void hsurface_destroy (GtsObject * object)
 153 {
 154   GtsHSurface * hs = GTS_HSURFACE (object);
 155
 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);
 165
 166   (* GTS_OBJECT_CLASS (gts_hsurface_class ())->parent_class->destroy) (object);
 167 }
 168
 169 static void hsurface_class_init (GtsObjectClass * klass)
 170 {
 171   klass->destroy = hsurface_destroy;
 172 }
 173
 174 static void hsurface_init (GtsHSurface * hsurface)
 175 {
 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;
 181 }
 182
 183 /**
 184  * gts_hsurface_class:
 185  *
 186  * Returns: the #GtsHSurfaceClass.
 187  */
 188 GtsHSurfaceClass * gts_hsurface_class (void)
 189 {
 190   static GtsHSurfaceClass * klass = NULL;
 191
 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
 201     };
 202     klass = gts_object_class_new (gts_object_class (),
 203                                   &hsurface_info);
 204   }
 205
 206   return klass;
 207 }
 208
 209 /**
 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.
 220  *
 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.
 224  */
 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)
 232 {
 233   GtsHSurface * hsurface;
 234
 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);
 240
 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);
 246
 247   while (gts_psurface_remove_vertex (psurface))
 248     ;
 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);
 252
 253     g_ptr_array_index (hsurface->split, psurface->pos - 1) = hs;
 254     psurface->pos--;
 255
 256     hs->parent = GTS_OBJECT (vs)->reserved;
 257     if (hs->parent) {
 258       GtsSplit * vsp = GTS_SPLIT (hs->parent);
 259
 260       if (vsp->v1 == GTS_OBJECT (vs)) {
 261         g_assert (vsp->v2 != GTS_OBJECT (vs));
 262         vsp->v1 = GTS_OBJECT (hs);
 263       }
 264       else {
 265         g_assert (vsp->v2 == GTS_OBJECT (vs));
 266         vsp->v2 = GTS_OBJECT (hs);
 267       }
 268     }
 269     else
 270       hsurface->roots = g_slist_prepend (hsurface->roots, hs);
 271
 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++;
 281
 282     gts_split_expand (vs, psurface->s, psurface->s->edge_class);
 283
 284     if (hs->nchild == 2)
 285       HEAP_INSERT_HSPLIT (hsurface->collapsable, hs);
 286   }
 287
 288   hsurface->nvertex = gts_surface_vertex_number (hsurface->s);
 289   gts_object_destroy (GTS_OBJECT (psurface));
 290
 291   return hsurface;
 292 }
 293
 294 /**
 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.
 304  *
 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().
 308  */
 309 void gts_hsurface_traverse (GtsHSurface *    hsurface,
 310                             GTraverseType    order,
 311                             gint             depth,
 312                             GtsSplitTraverseFunc func,
 313                             gpointer         data)
 314 {
 315   GSList * i;
 316
 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);
 321
 322   i = hsurface->roots;
 323   while (i) {
 324     gts_split_traverse (i->data, order, depth, func, data);
 325     i = i->next;
 326   }
 327 }
 328
 329 /**
 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.
 336  *
 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.
 342  */
 343 void gts_hsurface_foreach (GtsHSurface * hsurface,
 344                            GTraverseType order,
 345                            GtsFunc       func,
 346                            gpointer      data)
 347 {
 348   GtsHSplit * hs;
 349   guint i = 0, len;
 350   gboolean stop = FALSE;
 351
 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);
 355
 356   while ((hs = gts_eheap_top (hsurface->expandable, NULL)))
 357     gts_hsplit_expand (hs, hsurface);
 358
 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++;
 368     }
 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++;
 376     }
 377     break;
 378   default:
 379     g_assert_not_reached ();
 380   }
 381 }
 382
 383 /**
 384  * gts_hsurface_height:
 385  * @hsurface: a #GtsHSurface.
 386  *
 387  * Returns: the maximum height of the tree described by @hsurface.
 388  */
 389 guint gts_hsurface_height (GtsHSurface * hsurface)
 390 {
 391   GSList * i;
 392   guint height = 0;
 393
 394   g_return_val_if_fail (hsurface != NULL, 0);
 395
 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;
 402   }
 403
 404   return height;
 405 }