gts/eheap.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
  28 /**
  29  * gts_eheap_new:
  30  * @key_func: a #GtsKeyFunc or %NULL.
  31  * @data: user data to be passed to @key_func.
  32  *
  33  * Returns: a new #GtsEHeap using @key_func as key.
  34  */
  35 GtsEHeap * gts_eheap_new (GtsKeyFunc key_func,
  36                           gpointer data)
  37 {
  38   GtsEHeap * heap;
  39
  40   heap = g_malloc (sizeof(GtsEHeap));
  41   heap->elts = g_ptr_array_new ();
  42   heap->func = key_func;
  43   heap->data = data;
  44   heap->frozen = FALSE;
  45   heap->randomized = FALSE;
  46   return heap;
  47 }
  48
  49 static void sift_up (GtsEHeap * heap, guint i)
  50 {
  51   GtsEHeapPair * parent, * child;
  52   guint p;
  53   gpointer * pdata = heap->elts->pdata;
  54   gdouble key;
  55
  56   child = pdata[i - 1];
  57   key = child->key;
  58   while ((p = PARENT (i))) {
  59     parent = pdata[p - 1];
  60     if (parent->key > key ||
  61         (heap->randomized && parent->key == key && rand () < RAND_MAX/2)) {
  62       pdata[p - 1] = child;
  63       pdata[i - 1] = parent;
  64       child->pos = p;
  65       parent->pos = i;
  66       i = p;
  67     }
  68     else
  69       i = 0;
  70   }
  71 }
  72
  73 /**
  74  * gts_eheap_insert:
  75  * @heap: a #GtsEHeap.
  76  * @p: a pointer to add to the heap.
  77  *
  78  * Inserts a new element @p in the heap.
  79  *
  80  * Returns: a #GtsEHeapPair describing the position of the element in the heap.
  81  * This pointer is necessary for gts_eheap_remove() and
  82  * gts_eheap_decrease_key().
  83  */
  84 GtsEHeapPair * gts_eheap_insert (GtsEHeap * heap, gpointer p)
  85 {
  86   GtsEHeapPair * pair;
  87   GPtrArray * elts;
  88
  89   g_return_val_if_fail (heap != NULL, NULL);
  90   g_return_val_if_fail (heap->func != NULL, NULL);
  91
  92   elts = heap->elts;
  93   pair = g_malloc (sizeof (GtsEHeapPair));
  94   g_ptr_array_add (elts, pair);
  95   pair->data = p;
  96   pair->pos = elts->len;
  97   pair->key = (*heap->func) (p, heap->data);
  98   if (!heap->frozen)
  99     sift_up (heap, elts->len);
 100   return pair;
 101 }
 102
 103 /**
 104  * gts_eheap_insert_with_key:
 105  * @heap: a #GtsEHeap.
 106  * @p: a pointer to add to the heap.
 107  * @key: the value of the key associated to @p.
 108  *
 109  * Inserts a new element @p in the heap.
 110  *
 111  * Returns: a #GtsEHeapPair describing the position of the element in the heap.
 112  * This pointer is necessary for gts_eheap_remove() and
 113  * gts_eheap_decrease_key().
 114  */
 115 GtsEHeapPair * gts_eheap_insert_with_key (GtsEHeap * heap,
 116                                           gpointer p,
 117                                           gdouble key)
 118 {
 119   GtsEHeapPair * pair;
 120   GPtrArray * elts;
 121
 122   g_return_val_if_fail (heap != NULL, NULL);
 123
 124   elts = heap->elts;
 125   pair = g_malloc (sizeof (GtsEHeapPair));
 126   g_ptr_array_add (elts, pair);
 127   pair->data = p;
 128   pair->pos = elts->len;
 129   pair->key = key;
 130   if (!heap->frozen)
 131     sift_up (heap, elts->len);
 132   return pair;
 133 }
 134
 135 static void sift_down (GtsEHeap * heap, guint i)
 136 {
 137   GtsEHeapPair * left_child, * right_child, * child, * parent;
 138   guint lc, rc, c;
 139   gpointer * pdata = heap->elts->pdata;
 140   guint len = heap->elts->len;
 141   gdouble key;
 142
 143   lc = LEFT_CHILD (i);
 144   rc = RIGHT_CHILD (i);
 145   left_child = lc <= len ? pdata[lc - 1] : NULL;
 146   right_child = rc <= len ? pdata[rc - 1] : NULL;
 147
 148   parent = pdata[i - 1];
 149   key = parent->key;
 150   while (left_child != NULL) {
 151     if (right_child == NULL || left_child->key  < right_child->key) {
 152       child = left_child;
 153       c = lc;
 154     }
 155     else {
 156       child = right_child;
 157       c = rc;
 158     }
 159     if (key > child->key) {
 160       pdata[i - 1] = child;
 161       child->pos = i;
 162       pdata[c - 1] = parent;
 163       parent->pos = c;
 164       i = c;
 165       lc = LEFT_CHILD (i);
 166       rc = RIGHT_CHILD (i);
 167       left_child = lc <= len ? pdata[lc - 1] : NULL;
 168       right_child = rc <= len ? pdata[rc - 1] : NULL;
 169     }
 170     else
 171       left_child = NULL;
 172   }
 173 }
 174
 175 /**
 176  * gts_eheap_remove_top:
 177  * @heap: a #GtsEHeap.
 178  * @key: a pointer on a gdouble or %NULL.
 179  *
 180  * Removes the element at the top of the heap and optionally (if @key is not
 181  * %NULL) returns the value of its key.
 182  *
 183  * Returns: the element at the top of the heap.
 184  */
 185 gpointer gts_eheap_remove_top (GtsEHeap * heap, gdouble * key)
 186 {
 187   gpointer root;
 188   GPtrArray * elts;
 189   guint len;
 190   GtsEHeapPair * pair;
 191
 192   g_return_val_if_fail (heap != NULL, NULL);
 193
 194   elts = heap->elts;
 195   len = elts->len;
 196
 197   if (len == 0)
 198     return NULL;
 199   if (len == 1) {
 200     pair = g_ptr_array_remove_index (elts, 0);
 201     root = pair->data;
 202     if (key)
 203       *key = pair->key;
 204     g_free (pair);
 205     return root;
 206   }
 207
 208   pair = elts->pdata[0];
 209   root = pair->data;
 210   if (key)
 211     *key = pair->key;
 212   g_free (pair);
 213   pair = g_ptr_array_remove_index (elts, len - 1);
 214   elts->pdata[0] = pair;
 215   pair->pos = 1;
 216   sift_down (heap, 1);
 217   return root;
 218 }
 219
 220 /**
 221  * gts_eheap_top:
 222  * @heap: a #GtsEHeap.
 223  * @key: a pointer on a gdouble or %NULL.
 224  *
 225  * Returns: the element at the top of the heap and optionally (if @key is not
 226  * %NULL) its key.
 227  */
 228 gpointer gts_eheap_top (GtsEHeap * heap, gdouble * key)
 229 {
 230   GtsEHeapPair * pair;
 231   GPtrArray * elts;
 232
 233   g_return_val_if_fail (heap != NULL, NULL);
 234
 235   elts = heap->elts;
 236
 237   if (elts->len == 0)
 238     return NULL;
 239
 240   pair = elts->pdata[0];
 241   if (key)
 242     *key = pair->key;
 243   return pair->data;
 244 }
 245
 246 /**
 247  * gts_eheap_destroy:
 248  * @heap: a #GtsEHeap.
 249  *
 250  * Free all the memory allocated for @heap.
 251  */
 252 void gts_eheap_destroy (GtsEHeap * heap)
 253 {
 254   guint i;
 255
 256   g_return_if_fail (heap != NULL);
 257
 258   for (i = 0; i < heap->elts->len; i++)
 259     g_free (heap->elts->pdata[i]);
 260   g_ptr_array_free (heap->elts, TRUE);
 261   g_free (heap);
 262 }
 263
 264 /**
 265  * gts_eheap_thaw:
 266  * @heap: a #GtsEHeap.
 267  *
 268  * If @heap has been frozen previously using gts_eheap_freeze(), reorder it
 269  * in O(n) time and unfreeze it.
 270  */
 271 void gts_eheap_thaw (GtsEHeap * heap)
 272 {
 273   guint i;
 274
 275   g_return_if_fail (heap != NULL);
 276
 277   if (!heap->frozen)
 278     return;
 279
 280   for (i = heap->elts->len/2; i > 0; i--)
 281     sift_down (heap, i);
 282
 283   heap->frozen = FALSE;
 284 }
 285
 286 /**
 287  * gts_eheap_foreach:
 288  * @heap: a #GtsEHeap.
 289  * @func: the function to call for each element in the heap.
 290  * @data: to pass to @func.
 291  */
 292 void gts_eheap_foreach (GtsEHeap * heap,
 293                         GFunc func,
 294                         gpointer data)
 295 {
 296   guint i;
 297   GPtrArray * elts;
 298
 299   g_return_if_fail (heap != NULL);
 300   g_return_if_fail (func != NULL);
 301
 302   elts = heap->elts;
 303   for (i = 0; i < elts->len; i++)
 304     (*func) (((GtsEHeapPair *) elts->pdata[i])->data, data);
 305 }
 306
 307 /**
 308  * gts_eheap_remove:
 309  * @heap: a #GtsEHeap.
 310  * @p: a #GtsEHeapPair.
 311  *
 312  * Removes element corresponding to @p from @heap in O(log n).
 313  *
 314  * Returns: the element just removed from @heap.
 315  */
 316 gpointer gts_eheap_remove (GtsEHeap * heap, GtsEHeapPair * p)
 317 {
 318   GtsEHeapPair ** pdata;
 319   GtsEHeapPair * parent;
 320   guint i, par;
 321   gpointer data;
 322
 323   g_return_val_if_fail (heap != NULL, NULL);
 324   g_return_val_if_fail (p != NULL, NULL);
 325
 326   pdata = (GtsEHeapPair **)heap->elts->pdata;
 327   i = p->pos;
 328   data = p->data;
 329
 330   g_return_val_if_fail (i > 0 && i <= heap->elts->len, NULL);
 331   g_return_val_if_fail (p == pdata[i - 1], NULL);
 332
 333   /* move element to the top */
 334   while ((par = PARENT (i))) {
 335     parent = pdata[par - 1];
 336     pdata[par - 1] = p;
 337     pdata[i - 1] = parent;
 338     p->pos = par;
 339     parent->pos = i;
 340     i = par;
 341   }
 342
 343   gts_eheap_remove_top (heap, NULL);
 344
 345   return data;
 346 }
 347
 348 /**
 349  * gts_eheap_decrease_key:
 350  * @heap: a #GtsEHeap.
 351  * @p: a #GtsEHeapPair.
 352  * @new_key: the new value of the key for this element. Must be smaller than
 353  * the current key.
 354  *
 355  * Decreases the value of the key of the element at position @p.
 356  */
 357 void gts_eheap_decrease_key (GtsEHeap * heap,
 358                              GtsEHeapPair * p,
 359                              gdouble new_key)
 360 {
 361   guint i;
 362
 363   g_return_if_fail (heap != NULL);
 364   g_return_if_fail (p != NULL);
 365
 366   i = p->pos;
 367   g_return_if_fail (i > 0 && i <= heap->elts->len);
 368   g_return_if_fail (p == heap->elts->pdata[i - 1]);
 369
 370   g_return_if_fail (new_key <= p->key);
 371
 372   p->key = new_key;
 373   if (!heap->frozen)
 374     sift_up (heap, i);
 375 }
 376
 377 /**
 378  * gts_eheap_freeze:
 379  * @heap: a #GtsEHeap.
 380  *
 381  * Freezes the heap. Any subsequent operation will not preserve the heap
 382  * property. Used in conjunction with gts_eheap_insert() and gts_eheap_thaw()
 383  * to create a heap in O(n) time.
 384  */
 385 void gts_eheap_freeze (GtsEHeap * heap)
 386 {
 387   g_return_if_fail (heap != NULL);
 388
 389   heap->frozen = TRUE;
 390 }
 391
 392 /**
 393  * gts_eheap_size:
 394  * @heap: a #GtsEHeap.
 395  *
 396  * Returns: the number of items in @heap.
 397  */
 398 guint gts_eheap_size (GtsEHeap * heap)
 399 {
 400   g_return_val_if_fail (heap != NULL, 0);
 401
 402   return heap->elts->len;
 403 }
 404
 405 /**
 406  * gts_eheap_update:
 407  * @heap: a #GtsEHeap.
 408  *
 409  * Updates the key of each element of @heap and reorders it.
 410  */
 411 void gts_eheap_update (GtsEHeap * heap)
 412 {
 413   guint i, len;
 414   GtsEHeapPair ** pairs;
 415   gpointer data;
 416   GtsKeyFunc func;
 417
 418   g_return_if_fail (heap != NULL);
 419   g_return_if_fail (heap->func != NULL);
 420
 421   heap->frozen = TRUE;
 422
 423   len = heap->elts->len;
 424   pairs = (GtsEHeapPair **) heap->elts->pdata;
 425   data = heap->data;
 426   func = heap->func;
 427
 428   for (i = 0; i < len; i++) {
 429     GtsEHeapPair * pair = pairs[i];
 430     pair->key = (*func) (pair->data, data);
 431   }
 432
 433   gts_eheap_thaw (heap);
 434 }
 435
 436 /**
 437  * gts_eheap_key:
 438  * @heap: a #GtsEHeap.
 439  * @p: a pointer to be tested;
 440  *
 441  * Returns: the value of the key for pointer @p.
 442  */
 443 gdouble gts_eheap_key (GtsEHeap * heap, gpointer p)
 444 {
 445   g_return_val_if_fail (heap != NULL, 0.);
 446   g_return_val_if_fail (heap->func != NULL, 0.);
 447
 448   return (* heap->func) (p, heap->data);
 449 }
 450
 451 /**
 452  * gts_eheap_randomized:
 453  * @heap: a #GtsEHeap.
 454  * @randomized: whether @heap should be randomized.
 455  */
 456 void gts_eheap_randomized (GtsEHeap * heap, gboolean randomized)
 457 {
 458   g_return_if_fail (heap != NULL);
 459
 460   heap->randomized = randomized;
 461 }