hsurface.c

Go to the documentation of this file.

/* GTS - Library for the manipulation of triangulated surfaces
 * Copyright (C) 1999 Stéphane Popinet
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public
 * License along with this library; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 02111-1307, USA.
 */

#include <stdlib.h>
#include <string.h>
#include "gts.h"

#define HEAP_INSERT_HSPLIT(h, e) ((e)->index = gts_eheap_insert (h, e))
#define HEAP_REMOVE_HSPLIT(h, e) (gts_eheap_remove (h, (e)->index),\
                                  (e)->index = NULL)

static void hsplit_init (GtsHSplit * hsplit)
{
  hsplit->index = NULL;
  hsplit->parent = NULL;
  hsplit->nchild = 0;
}

GtsHSplitClass * gts_hsplit_class (void)
{
  static GtsHSplitClass * klass = NULL;

  if (klass == NULL) {
    GtsObjectClassInfo hsplit_info = {
      "GtsHSplit",
      sizeof (GtsHSplit),
      sizeof (GtsHSplitClass),
      (GtsObjectClassInitFunc) NULL,
      (GtsObjectInitFunc) hsplit_init,
      (GtsArgSetFunc) NULL,
      (GtsArgGetFunc) NULL
    };
    klass = gts_object_class_new (GTS_OBJECT_CLASS (gts_split_class ()), 
                                  &hsplit_info);
  }

  return klass;
}

GtsHSplit * gts_hsplit_new (GtsHSplitClass * klass, GtsSplit * vs)
{
  GtsHSplit * hs;

  g_return_val_if_fail (vs != NULL, NULL);

  hs = GTS_HSPLIT (gts_object_new (GTS_OBJECT_CLASS (klass)));
  memcpy (hs, vs, sizeof (GtsSplit));
  GTS_OBJECT (hs)->reserved = NULL;

  return hs;
}

void gts_hsplit_collapse (GtsHSplit * hs,
                          GtsHSurface * hsurface)
{
  GtsHSplit * parent;
  GtsSplit * vs;

  g_return_if_fail (hs != NULL);
  g_return_if_fail (hs->nchild == 2);
  g_return_if_fail (hsurface != NULL);

  gts_split_collapse (GTS_SPLIT (hs), hsurface->s->edge_class, NULL);

  hsurface->nvertex--;
  hs->nchild = 0;
  HEAP_REMOVE_HSPLIT (hsurface->collapsable, hs);
  HEAP_INSERT_HSPLIT (hsurface->expandable, hs);

  vs = GTS_SPLIT (hs);
  if (GTS_IS_HSPLIT (vs->v1))
    HEAP_REMOVE_HSPLIT (hsurface->expandable, GTS_HSPLIT (vs->v1));
  if (GTS_IS_HSPLIT (vs->v2))
    HEAP_REMOVE_HSPLIT (hsurface->expandable, GTS_HSPLIT (vs->v2));

  parent = hs->parent;
  if (parent && ++parent->nchild == 2)
    HEAP_INSERT_HSPLIT (hsurface->collapsable, parent);
}

void gts_hsplit_expand (GtsHSplit * hs,
                        GtsHSurface * hsurface)
{
  GtsHSplit * parent;
  GtsSplit * vs;

  g_return_if_fail (hs != NULL);
  g_return_if_fail (hsurface != NULL);
  g_return_if_fail (hs->nchild == 0);

  gts_split_expand (GTS_SPLIT (hs), hsurface->s, hsurface->s->edge_class);
  hsurface->nvertex++;
  hs->nchild = 2;
  HEAP_REMOVE_HSPLIT (hsurface->expandable, hs);
  HEAP_INSERT_HSPLIT (hsurface->collapsable, hs);

  vs = GTS_SPLIT (hs);
  if (GTS_IS_HSPLIT (vs->v1))
    HEAP_INSERT_HSPLIT (hsurface->expandable, GTS_HSPLIT (vs->v1));
  if (GTS_IS_HSPLIT (vs->v2))
    HEAP_INSERT_HSPLIT (hsurface->expandable, GTS_HSPLIT (vs->v2));

  parent = hs->parent;
  if (parent && parent->nchild-- == 2)
    HEAP_REMOVE_HSPLIT (hsurface->collapsable, parent);
}

static void hsurface_destroy (GtsObject * object)
{
  GtsHSurface * hs = GTS_HSURFACE (object);

  gts_hsurface_traverse (hs, G_POST_ORDER, -1,
                         (GtsSplitTraverseFunc) gts_object_destroy, 
                         NULL);
  g_slist_free (hs->roots);
  if (hs->expandable)
    gts_eheap_destroy (hs->expandable);
  if (hs->collapsable)
    gts_eheap_destroy (hs->collapsable);
  g_ptr_array_free (hs->split, TRUE);

  (* GTS_OBJECT_CLASS (gts_hsurface_class ())->parent_class->destroy) (object);
}

static void hsurface_class_init (GtsObjectClass * klass)
{
  klass->destroy = hsurface_destroy;
}

static void hsurface_init (GtsHSurface * hsurface)
{
  hsurface->s = NULL;
  hsurface->roots = NULL;
  hsurface->expandable = hsurface->collapsable = NULL;
  hsurface->split = g_ptr_array_new ();
  hsurface->nvertex = 0;
}

GtsHSurfaceClass * gts_hsurface_class (void)
{
  static GtsHSurfaceClass * klass = NULL;

  if (klass == NULL) {
    GtsObjectClassInfo hsurface_info = {
      "GtsHSurface",
      sizeof (GtsHSurface),
      sizeof (GtsHSurfaceClass),
      (GtsObjectClassInitFunc) hsurface_class_init,
      (GtsObjectInitFunc) hsurface_init,
      (GtsArgSetFunc) NULL,
      (GtsArgGetFunc) NULL
    };
    klass = gts_object_class_new (gts_object_class (), 
                                  &hsurface_info);
  }

  return klass;
}

GtsHSurface * gts_hsurface_new (GtsHSurfaceClass * klass,
                                GtsHSplitClass * hsplit_class,
                                GtsPSurface * psurface,
                                GtsKeyFunc expand_key,
                                gpointer expand_data,
                                GtsKeyFunc collapse_key,
                                gpointer collapse_data)
{
  GtsHSurface * hsurface;

  g_return_val_if_fail (klass != NULL, NULL);
  g_return_val_if_fail (hsplit_class != NULL, NULL);
  g_return_val_if_fail (psurface != NULL, NULL);
  g_return_val_if_fail (expand_key != NULL, NULL);
  g_return_val_if_fail (collapse_key != NULL, NULL);

  hsurface = GTS_HSURFACE (gts_object_new (GTS_OBJECT_CLASS (klass)));
  hsurface->s = psurface->s;
  hsurface->expandable = gts_eheap_new (expand_key, expand_data);
  hsurface->collapsable = gts_eheap_new (collapse_key, collapse_data);
  g_ptr_array_set_size (hsurface->split, psurface->split->len);

  while (gts_psurface_remove_vertex (psurface))
    ;
  while (psurface->pos) {
    GtsSplit * vs = g_ptr_array_index (psurface->split, psurface->pos - 1);
    GtsHSplit * hs = gts_hsplit_new (hsplit_class, vs);

    g_ptr_array_index (hsurface->split, psurface->pos - 1) = hs;
    psurface->pos--;

    hs->parent = GTS_OBJECT (vs)->reserved;
    if (hs->parent) {
      GtsSplit * vsp = GTS_SPLIT (hs->parent);

      if (vsp->v1 == GTS_OBJECT (vs)) {
        g_assert (vsp->v2 != GTS_OBJECT (vs));
        vsp->v1 = GTS_OBJECT (hs);
      }
      else {
        g_assert (vsp->v2 == GTS_OBJECT (vs));
        vsp->v2 = GTS_OBJECT (hs);
      }
    }
    else
      hsurface->roots = g_slist_prepend (hsurface->roots, hs);

    hs->nchild = 0;
    if (GTS_IS_SPLIT (vs->v1))
      GTS_OBJECT (vs->v1)->reserved = hs;
    else
      hs->nchild++;
    if (GTS_IS_SPLIT (vs->v2))
      GTS_OBJECT (vs->v2)->reserved = hs;
    else
      hs->nchild++;
    
    gts_split_expand (vs, psurface->s, psurface->s->edge_class);

    if (hs->nchild == 2)
      HEAP_INSERT_HSPLIT (hsurface->collapsable, hs);
  }

  hsurface->nvertex = gts_surface_vertex_number (hsurface->s);
  gts_object_destroy (GTS_OBJECT (psurface));

  return hsurface;
}

void gts_hsurface_traverse (GtsHSurface *    hsurface,
                            GTraverseType    order,
                            gint             depth,
                            GtsSplitTraverseFunc func,
                            gpointer         data)
{
  GSList * i;

  g_return_if_fail (hsurface != NULL);
  g_return_if_fail (func != NULL);
  g_return_if_fail (order < G_LEVEL_ORDER);
  g_return_if_fail (depth == -1 || depth > 0);

  i = hsurface->roots;
  while (i) {
    gts_split_traverse (i->data, order, depth, func, data);
    i = i->next;
  }
}

void gts_hsurface_foreach (GtsHSurface * hsurface,
                           GTraverseType order,
                           GtsFunc       func,
                           gpointer      data)
{
  GtsHSplit * hs;
  guint i = 0, len;
  gboolean stop = FALSE;

  g_return_if_fail (hsurface != NULL);
  g_return_if_fail (func != NULL);
  g_return_if_fail (order == G_PRE_ORDER || order == G_POST_ORDER);

  while ((hs = gts_eheap_top (hsurface->expandable, NULL))) 
    gts_hsplit_expand (hs, hsurface);

  len = hsurface->split->len;
  switch (order) {
  case G_PRE_ORDER:
    while (i < len && !stop) {
      GtsHSplit * hs = g_ptr_array_index (hsurface->split, i);
      stop = (*func) (hs, data);
      if (!stop)
        gts_hsplit_collapse (hs, hsurface);
      i++;
    }
    break;
  case G_POST_ORDER:
    while (i < len && !stop) {
      GtsHSplit * hs = g_ptr_array_index (hsurface->split, i);
      gts_hsplit_collapse (hs, hsurface);
      stop = (*func) (hs, data);
      i++;
    }
    break;
  default:
    g_assert_not_reached ();
  }
}

guint gts_hsurface_height (GtsHSurface * hsurface)
{
  GSList * i;
  guint height = 0;

  g_return_val_if_fail (hsurface != NULL, 0);

  i = hsurface->roots;
  while (i) {
    guint tmp_height = gts_split_height (i->data);
    if (tmp_height > height)
      height = tmp_height;
    i = i->next;
  }

  return height;
}