***********************************************************/
#include "ar.h"
-static int n, heapsize;
-static short heap[NC + 1];
+struct heap_t {
+ short buf[NC + 1]; /* buf[0] is not used */
+ int size;
+};
+
+static int n;
static ushort *freq, *sortptr, len_cnt[17];
static uchar *len;
}
static void
-downheap(int i)
+downheap(struct heap_t *heap, int i)
/* priority queue; send i-th entry down heap */
{
int j, k;
- k = heap[i];
- while ((j = 2 * i) <= heapsize) {
- if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
+ k = heap->buf[i];
+ while ((j = 2 * i) <= heap->size) {
+ if (j < heap->size && freq[heap->buf[j]] > freq[heap->buf[j + 1]])
j++;
- if (freq[k] <= freq[heap[j]])
+ if (freq[k] <= freq[heap->buf[j]])
break;
- heap[i] = heap[j];
+ heap->buf[i] = heap->buf[j];
i = j;
}
- heap[i] = k;
+ heap->buf[i] = k;
}
static void
/* make tree, calculate len[], return root */
{
int i, j, k, avail;
+ struct heap_t heap;
n = nparm;
freq = freqparm;
len = lenparm;
avail = n;
- heapsize = 0;
- heap[1] = 0;
+ heap.size = 0;
+ heap.buf[1] = 0;
for (i = 0; i < n; i++) {
len[i] = 0;
if (freq[i])
- heap[++heapsize] = i;
+ heap.buf[++heap.size] = i;
}
- if (heapsize < 2) {
- codeparm[heap[1]] = 0;
- return heap[1];
+ if (heap.size < 2) {
+ codeparm[heap.buf[1]] = 0;
+ return heap.buf[1];
}
- for (i = heapsize / 2; i >= 1; i--)
- downheap(i); /* make priority queue */
+ for (i = heap.size / 2; i >= 1; i--)
+ downheap(&heap, i); /* make priority queue */
sortptr = codeparm;
do { /* while queue has at least two entries */
- i = heap[1]; /* take out least-freq entry */
+ i = heap.buf[1]; /* take out least-freq entry */
if (i < n)
*sortptr++ = i;
- heap[1] = heap[heapsize--];
- downheap(1);
- j = heap[1]; /* next least-freq entry */
+ heap.buf[1] = heap.buf[heap.size--];
+ downheap(&heap, 1);
+
+ j = heap.buf[1]; /* next least-freq entry */
if (j < n)
*sortptr++ = j;
+
k = avail++; /* generate new node */
freq[k] = freq[i] + freq[j];
- heap[1] = k;
- downheap(1); /* put into queue */
+ heap.buf[1] = k;
+ downheap(&heap, 1); /* put into queue */
left[k] = i;
right[k] = j;
- } while (heapsize > 1);
+ } while (heap.size > 1);
sortptr = codeparm;
make_len(k);
make_code(nparm, lenparm, codeparm);