1 /*

     2  * Header file for GHeap

     3  *

     4  * Copyright (C) 2006 Nokia Corporation. All rights reserved.

     5  *

     6  * Contact: Olli Salli (Nokia-M/Helsinki) <olli.salli@nokia.com>

     7  *

     8  * This library is free software; you can redistribute it and/or

     9  * modify it under the terms of the GNU Lesser General Public

    10  * License as published by the Free Software Foundation; either

    11  * version 2.1 of the License, or (at your option) any later version.

    12  *

    13  * This library is distributed in the hope that it will be useful,

    14  * but WITHOUT ANY WARRANTY; without even the implied warranty of

    15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU

    16  * Lesser General Public License for more details.

    17  *

    18  * You should have received a copy of the GNU Lesser General Public

    19  * License along with this library; if not, write to the Free Software

    20  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

    21  */

    22 

    23 #include <glib.h>

    24 #include "gheap.h"

    25 

    26 #define DEFAULT_SIZE 64

    27 

    28 struct _GHeap

    29 {

    30   GPtrArray *data;

    31   GCompareFunc comparator;

    32 };

    33 

    34 

    35 GHeap *

    36 g_heap_new (GCompareFunc comparator)

    37 {

    38   GHeap *ret = g_slice_new (GHeap);

    39   g_assert (comparator != NULL);

    40 

    41   ret->data = g_ptr_array_sized_new (DEFAULT_SIZE);

    42   ret->comparator = comparator;

    43 

    44   return ret;

    45 }

    46 

    47 void

    48 g_heap_destroy (GHeap * heap)

    49 {

    50   g_return_if_fail (heap != NULL);

    51 

    52   g_ptr_array_free (heap->data, TRUE);

    53   g_slice_free (GHeap, heap);

    54 }

    55 

    56 void

    57 g_heap_clear (GHeap *heap)

    58 {

    59   g_return_if_fail (heap != NULL);

    60 

    61   g_ptr_array_free (heap->data, TRUE);

    62   heap->data = g_ptr_array_sized_new (DEFAULT_SIZE);

    63 }

    64 

    65 #define HEAP_INDEX(heap, index) (g_ptr_array_index ((heap)->data, (index)-1))

    66 

    67 

    68 void

    69 g_heap_add (GHeap *heap, gpointer element)

    70 {

    71   guint m;

    72 

    73   g_return_if_fail (heap != NULL);

    74 

    75   g_ptr_array_add (heap->data, element);

    76   m = heap->data->len;

    77   while (m != 1)

    78     {

    79       gpointer parent = HEAP_INDEX (heap, m / 2);

    80 

    81       if (heap->comparator (element, parent) == -1)

    82         {

    83           HEAP_INDEX (heap, m / 2) = element;

    84           HEAP_INDEX (heap, m) = parent;

    85           m /= 2;

    86         }

    87       else

    88         break;

    89     }

    90 }

    91 

    92 

    93 gpointer

    94 g_heap_peek_first (GHeap *heap)

    95 {

    96   g_return_val_if_fail (heap != NULL, NULL);

    97 

    98   if (heap->data->len > 0)

    99     return HEAP_INDEX (heap, 1);

   100   else

   101     return NULL;

   102 }

   103 

   104 

   105 gpointer

   106 g_heap_extract_first (GHeap * heap)

   107 {

   108   gpointer ret;

   109 

   110   g_return_val_if_fail (heap != NULL, NULL);

   111 

   112   if (heap->data->len > 0)

   113     {

   114       guint m = heap->data->len;

   115       guint i = 1, j;

   116       ret = HEAP_INDEX (heap, 1);

   117 

   118       HEAP_INDEX (heap, 1) = HEAP_INDEX (heap, m);

   119 

   120       while (i * 2 <= m)

   121         {

   122           /* select the child which is supposed to come FIRST */

   123           if ((i * 2 + 1 <= m)

   124               && (heap->

   125                   comparator (HEAP_INDEX (heap, i * 2),

   126                               HEAP_INDEX (heap, i * 2 + 1)) == 1))

   127             j = i * 2 + 1;

   128           else

   129             j = i * 2;

   130 

   131           if (heap->comparator (HEAP_INDEX (heap, i), HEAP_INDEX (heap, j)) ==

   132               1)

   133             {

   134               gpointer tmp = HEAP_INDEX (heap, i);

   135               HEAP_INDEX (heap, i) = HEAP_INDEX (heap, j);

   136               HEAP_INDEX (heap, j) = tmp;

   137               i = j;

   138             }

   139           else

   140             break;

   141         }

   142 

   143       g_ptr_array_remove_index (heap->data, m - 1);

   144     }

   145   else

   146     ret = NULL;

   147 

   148   return ret;

   149 }

   150 

   151 

   152 guint

   153 g_heap_size (GHeap *heap)

   154 {

   155   g_return_val_if_fail (heap != NULL, 0);

   156 

   157   return heap->data->len;

   158 }