src/heap.c

   1 /* PSPP - computes sample statistics.
   2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
   3    Written by Ben Pfaff <blp@gnu.org>.
   4
   5    This program is free software; you can redistribute it and/or
   6    modify it under the terms of the GNU General Public License as
   7    published by the Free Software Foundation; either version 2 of the
   8    License, or (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful, but
  11    WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13    General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program; if not, write to the Free Software
  17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  18    02111-1307, USA. */
  19
  20 #include <config.h>
  21 #include "heap.h"
  22 #include <stdio.h>
  23 #include <stdlib.h>
  24 #include <assert.h>
  25
  26 #if STANDALONE
  27 #define GLOBAL_DEBUGGING 1
  28 #define _(x) (x)
  29 #endif
  30
  31 /* Creates and returns a heap with an initial capacity of M_ELEM
  32    elements.  Returns nonzero only if successful. */
  33 struct heap *
  34 heap_create (size_t m_elem)
  35 {
  36   struct heap *h = malloc (sizeof *h);
  37   if (h != NULL)
  38     {
  39       h->n_elem = 0;
  40       h->m_elem = m_elem;
  41       h->elem = malloc (h->m_elem * sizeof *h->elem);
  42       if (h->elem == NULL)
  43         {
  44           free (h);
  45           h = NULL;
  46         }
  47     }
  48   return h;
  49 }
  50
  51 /* Destroys the heap at *H. */
  52 void
  53 heap_destroy (struct heap *h)
  54 {
  55   assert (h != NULL);
  56   free (h->elem);
  57   free (h);
  58 }
  59
  60 /* Inserts into heap *H an element having index INDEX and key KEY.
  61    Returns nonzero only if successful. */
  62 int
  63 heap_insert (struct heap *h, int index, int key)
  64 {
  65   int i, j;
  66
  67   assert (h != NULL);
  68   if (h->n_elem >= h->m_elem)
  69     {
  70       h->elem = realloc (h->elem, 2 * h->m_elem * sizeof *h->elem);
  71       if (h->elem == NULL)
  72         return 0;
  73       h->m_elem *= 2;
  74     }
  75
  76   /* Knuth's Algorithm 5.2.3-16.  Step 1. */
  77   j = h->n_elem + 1;
  78
  79   for (;;)
  80     {
  81       /* Step 2. */
  82       i = j / 2;
  83
  84       /* Step 3. */
  85       if (i == 0 || h->elem[i - 1].key <= key)
  86         {
  87           h->elem[j - 1].index = index;
  88           h->elem[j - 1].key = key;
  89           h->n_elem++;
  90           return 1;
  91         }
  92
  93       /* Step 4. */
  94       h->elem[j - 1] = h->elem[i - 1];
  95       j = i;
  96     }
  97 }
  98
  99 /* Deletes the first element in the heap (the one with the greatest
 100    index) and returns its index, or -1 if the heap is empty.  If KEY
 101    is non-NULL then *KEY is set to the deleted element's key, if it
 102    returns non-NULL. */
 103 int
 104 heap_delete (struct heap *h, int *key)
 105 {
 106   /* Knuth's Algorithm 5.2.3H-19. */
 107   int first, K, R, l, r, i, j;
 108
 109   if (h->n_elem == 0)
 110     return -1;
 111   first = h->elem[0].index;
 112   if (key)
 113     *key = h->elem[0].key;
 114   K = h->elem[h->n_elem - 1].key;
 115   R = h->elem[h->n_elem - 1].index;
 116   l = 1;
 117   r = h->n_elem - 1;
 118
 119   /* H3. */
 120   j = 1;
 121
 122 H4:
 123   i = j;
 124   j *= 2;
 125   if (j == r)
 126     goto H6;
 127   else if (j > r)
 128     goto H8;
 129
 130   /* H5. */
 131   if (h->elem[j - 1].key > h->elem[j].key)
 132     j++;
 133
 134 H6:
 135   if (K <= h->elem[j - 1].key)
 136     goto H8;
 137
 138   /* H7. */
 139   h->elem[i - 1] = h->elem[j - 1];
 140   goto H4;
 141
 142 H8:
 143   h->elem[i - 1].key = K;
 144   h->elem[i - 1].index = R;
 145
 146   h->n_elem--;
 147   return first;
 148 }
 149
 150 /* Returns the number of elements in heap H. */
 151 int
 152 heap_size (struct heap *h)
 153 {
 154   return h->n_elem;
 155 }
 156
 157 #if GLOBAL_DEBUGGING
 158 /* Checks that a heap is really a heap. */
 159 void
 160 heap_verify (const struct heap *h)
 161 {
 162   size_t j;
 163
 164   for (j = 1; j <= h->n_elem; j++)
 165     {
 166       if (j / 2 >= 1 && h->elem[j / 2 - 1].key > h->elem[j - 1].key)
 167         printf (_("bad ordering of keys %d and %d\n"), j / 2 - 1, j - 1);
 168     }
 169 }
 170
 171 /* Dumps out the heap on stdout. */
 172 void
 173 heap_dump (const struct heap *h)
 174 {
 175   size_t j;
 176
 177   printf (_("Heap contents:\n"));
 178   for (j = 1; j <= h->n_elem; j++)
 179     {
 180       int partner;
 181       if (j / 2 >= 1)
 182         partner = h->elem[j / 2 - 1].key;
 183       else
 184         partner = -1;
 185       printf ("%6d-%5d", h->elem[j - 1].key, partner);
 186     }
 187 }
 188 #endif /* GLOBAL_DEBUGGING */
 189
 190 #if STANDALONE
 191 #include <time.h>
 192
 193 /* To perform a fairly thorough test of the heap routines, define
 194    STANDALONE to nonzero then compile this file by itself. */
 195
 196 /* Compares the second elements of the integer arrays at _A and _B and
 197    returns a strcmp()-type result. */
 198 int
 199 compare_int2 (const void *pa, const void *pb)
 200 {
 201   int *a = (int *) pa;
 202   int *b = (int *) pb;
 203
 204   return a[1] - b[1];
 205 }
 206
 207 #define N_ELEM 16
 208
 209 /* Arrange the N elements of ARRAY in random order. */
 210 void
 211 shuffle (int (*array)[2], int n)
 212 {
 213   int i;
 214
 215   for (i = 0; i < n; i++)
 216     {
 217       int j = i + rand () % (n - i);
 218       int t = array[j][0], s = array[j][1];
 219       array[j][0] = array[i][0], array[j][1] = array[i][1];
 220       array[i][0] = t, array[i][1] = s;
 221     }
 222 }
 223
 224 /* Test routine. */
 225 int
 226 main (void)
 227 {
 228   struct heap *h;
 229   int i;
 230   int array[N_ELEM][2];
 231
 232   srand (time (0));
 233
 234   h = heap_create (16);
 235   for (i = 0; i < N_ELEM; i++)
 236     {
 237       array[i][0] = i;
 238       array[i][1] = N_ELEM - i - 1;
 239     }
 240   shuffle (array, N_ELEM);
 241
 242   printf ("Insertion order:\n");
 243   for (i = 0; i < N_ELEM; i++)
 244     {
 245       printf ("(%d,%d) ", array[i][0], array[i][1]);
 246       heap_insert (h, array[i][0], array[i][1]);
 247       heap_verify (h);
 248     }
 249   putchar ('\n');
 250
 251   /*heap_dump(&h); */
 252
 253   printf ("\nDeletion order:\n");
 254   for (i = 0; i < N_ELEM; i++)
 255     {
 256       int index, key;
 257       index = heap_delete (h, &key);
 258       assert (index != -1);
 259       printf ("(%d,%d) ", index, key);
 260       fflush (stdout);
 261       assert (index == N_ELEM - i - 1 && key == i);
 262       heap_verify (h);
 263     }
 264   putchar ('\n');
 265   heap_destroy (h);
 266
 267   return 0;
 268 }
 269 #endif