gts/heap.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 "gts.h"
  22
  23 #define PARENT(i) ((i) >= 2 ? (i)/2 : 0)
  24 #define LEFT_CHILD(i) (2*(i))
  25 #define RIGHT_CHILD(i) (2*(i) + 1)
  26
  27 struct _GtsHeap {
  28   GPtrArray * elts;
  29   GCompareFunc func;
  30   gboolean frozen;
  31 };
  32
  33 /**
  34  * gts_heap_new:
  35  * @compare_func: a GCompareFunc.
  36  *
  37  * Returns: a new #GtsHeap using @compare_func as a sorting function.
  38  */
  39 GtsHeap * gts_heap_new (GCompareFunc compare_func)
  40 {
  41   GtsHeap * heap;
  42
  43   g_return_val_if_fail (compare_func != NULL, NULL);
  44
  45   heap = g_malloc (sizeof(GtsHeap));
  46   heap->elts = g_ptr_array_new ();
  47   heap->func = compare_func;
  48   heap->frozen = FALSE;
  49   return heap;
  50 }
  51
  52 static void sift_up (GtsHeap * heap, guint i)
  53 {
  54   gpointer parent, child;
  55   guint p;
  56   gpointer * pdata = heap->elts->pdata;
  57   GCompareFunc func = heap->func;
  58
  59   child = pdata[i - 1];
  60   while ((p = PARENT (i))) {
  61     parent = pdata[p - 1];
  62     if ((*func) (parent, child) > 0) {
  63       pdata[p - 1] = child;
  64       pdata[i - 1] = parent;
  65       i = p;
  66     }
  67     else
  68       i = 0;
  69   }
  70 }
  71
  72 /**
  73  * gts_heap_insert:
  74  * @heap: a #GtsHeap.
  75  * @p: a pointer to add to the heap.
  76  *
  77  * Inserts a new element @p in the heap.
  78  */
  79 void gts_heap_insert (GtsHeap * heap, gpointer p)
  80 {
  81   g_return_if_fail (heap != NULL);
  82
  83   g_ptr_array_add (heap->elts, p);
  84   if (!heap->frozen)
  85     sift_up (heap, heap->elts->len);
  86 }
  87
  88 static void sift_down (GtsHeap * heap, guint i)
  89 {
  90   gpointer left_child, right_child, child, parent;
  91   guint lc, rc, c;
  92   gpointer * pdata = heap->elts->pdata;
  93   guint len = heap->elts->len;
  94   GCompareFunc func = heap->func;
  95
  96   lc = LEFT_CHILD (i);
  97   rc = RIGHT_CHILD (i);
  98   left_child = lc <= len ? pdata[lc - 1] : NULL;
  99   right_child = rc <= len ? pdata[rc - 1] : NULL;
 100
 101   parent = pdata[i - 1];
 102   while (left_child != NULL) {
 103     if (right_child == NULL ||
 104         (*func) (left_child, right_child) < 0) {
 105       child = left_child;
 106       c = lc;
 107     }
 108     else {
 109       child = right_child;
 110       c = rc;
 111     }
 112     if ((*func) (parent, child) > 0) {
 113       pdata[i - 1] = child;
 114       pdata[c - 1] = parent;
 115       i = c;
 116       lc = LEFT_CHILD (i);
 117       rc = RIGHT_CHILD (i);
 118       left_child = lc <= len ? pdata[lc - 1] : NULL;
 119       right_child = rc <= len ? pdata[rc - 1] : NULL;
 120     }
 121     else
 122       left_child = NULL;
 123   }
 124 }
 125
 126 /**
 127  * gts_heap_remove_top:
 128  * @heap: a #GtsHeap.
 129  *
 130  * Removes the element at the top of the heap.
 131  *
 132  * Returns: the element at the top of the heap.
 133  */
 134 gpointer gts_heap_remove_top (GtsHeap * heap)
 135 {
 136   gpointer root;
 137   GPtrArray * elts;
 138   guint len;
 139
 140   g_return_val_if_fail (heap != NULL, NULL);
 141
 142   elts = heap->elts; len = elts->len;
 143
 144   if (len == 0)
 145     return NULL;
 146   if (len == 1)
 147     return g_ptr_array_remove_index (elts, 0);
 148
 149   root = elts->pdata[0];
 150   elts->pdata[0] = g_ptr_array_remove_index (elts, len - 1);
 151   sift_down (heap, 1);
 152   return root;
 153 }
 154
 155 /**
 156  * gts_heap_top:
 157  * @heap: a #GtsHeap.
 158  *
 159  * Returns: the element at the top of the heap.
 160  */
 161 gpointer gts_heap_top (GtsHeap * heap)
 162 {
 163   GPtrArray * elts;
 164   guint len;
 165
 166   g_return_val_if_fail (heap != NULL, NULL);
 167
 168   elts = heap->elts;
 169   len = elts->len;
 170   if (len == 0)
 171     return NULL;
 172   return elts->pdata[0];
 173 }
 174
 175 /**
 176  * gts_heap_destroy:
 177  * @heap: a #GtsHeap.
 178  *
 179  * Free all the memory allocated for @heap.
 180  */
 181 void gts_heap_destroy (GtsHeap * heap)
 182 {
 183   g_return_if_fail (heap != NULL);
 184
 185   g_ptr_array_free (heap->elts, TRUE);
 186   g_free (heap);
 187 }
 188
 189 /**
 190  * gts_heap_thaw:
 191  * @heap: a #GtsHeap.
 192  *
 193  * If @heap has been frozen previously using gts_heap_freeze(), reorder it
 194  * in O(n) time and unfreeze it.
 195  */
 196 void gts_heap_thaw (GtsHeap * heap)
 197 {
 198   guint i;
 199
 200   g_return_if_fail (heap != NULL);
 201
 202   if (!heap->frozen)
 203     return;
 204
 205   for (i = heap->elts->len/2; i > 0; i--)
 206     sift_down (heap, i);
 207
 208   heap->frozen = FALSE;
 209 }
 210
 211 /**
 212  * gts_heap_foreach:
 213  * @heap: a #GtsHeap.
 214  * @func: the function to call for each element in the heap.
 215  * @user_data: to pass to @func.
 216  */
 217 void gts_heap_foreach (GtsHeap * heap,
 218                        GFunc func,
 219                        gpointer user_data)
 220 {
 221   guint i;
 222   GPtrArray * elts;
 223
 224   g_return_if_fail (heap != NULL);
 225   g_return_if_fail (func != NULL);
 226
 227   elts = heap->elts;
 228   for (i = 0; i < elts->len; i++)
 229     (*func) (elts->pdata[i], user_data);
 230 }
 231
 232 /**
 233  * gts_heap_freeze:
 234  * @heap: a #GtsHeap.
 235  *
 236  * Freezes the heap. Any subsequent operation will not preserve the heap
 237  * property. Used in conjunction with gts_heap_insert() and gts_heap_thaw()
 238  * to create a heap in O(n) time.
 239  */
 240 void gts_heap_freeze (GtsHeap * heap)
 241 {
 242   g_return_if_fail (heap != NULL);
 243
 244   heap->frozen = TRUE;
 245 }
 246
 247 /**
 248  * gts_heap_size:
 249  * @heap: a #GtsHeap.
 250  *
 251  * Returns: the number of items in @heap.
 252  */
 253 guint gts_heap_size (GtsHeap * heap)
 254 {
 255   g_return_val_if_fail (heap != NULL, 0);
 256
 257   return heap->elts->len;
 258 }