Sat Dec 27 16:16:49 2003 Ben Pfaff <blp@gnu.org>
[pspp] / 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