home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 9 Archive / 09-Archive.zip / AR002.LZH / MAKETREE.C < prev   
C/C++ Source or Header  |  1990-08-13  |  3KB  |  111 lines
  1. /***********************************************************
  2.     maketree.c -- make Huffman tree
  3. ***********************************************************/
  4. #include "ar.h"
  5.  
  6. static int    n, heapsize;
  7. static short  heap[NC + 1];
  8. static ushort *freq, *sortptr, len_cnt[17];
  9. static uchar  *len;
  10.  
  11. static void count_len(int i)  /* call with i = root */
  12. {
  13.     static int depth = 0;
  14.  
  15.     if (i < n) len_cnt[(depth < 16) ? depth : 16]++;
  16.     else {
  17.         depth++;
  18.         count_len(left [i]);
  19.         count_len(right[i]);
  20.         depth--;
  21.     }
  22. }
  23.  
  24. static void make_len(int root)
  25. {
  26.     int i, k;
  27.     uint cum;
  28.  
  29.     for (i = 0; i <= 16; i++) len_cnt[i] = 0;
  30.     count_len(root);
  31.     cum = 0;
  32.     for (i = 16; i > 0; i--)
  33.         cum += len_cnt[i] << (16 - i);
  34.     while (cum != (1U << 16)) {
  35.         fprintf(stderr, "17");
  36.         len_cnt[16]--;
  37.         for (i = 15; i > 0; i--) {
  38.             if (len_cnt[i] != 0) {
  39.                 len_cnt[i]--;  len_cnt[i+1] += 2;  break;
  40.             }
  41.         }
  42.         cum--;
  43.     }
  44.     for (i = 16; i > 0; i--) {
  45.         k = len_cnt[i];
  46.         while (--k >= 0) len[*sortptr++] = i;
  47.     }
  48. }
  49.  
  50. static void downheap(int i)
  51.     /* priority queue; send i-th entry down heap */
  52. {
  53.     int j, k;
  54.  
  55.     k = heap[i];
  56.     while ((j = 2 * i) <= heapsize) {
  57.         if (j < heapsize && freq[heap[j]] > freq[heap[j + 1]])
  58.              j++;
  59.         if (freq[k] <= freq[heap[j]]) break;
  60.         heap[i] = heap[j];  i = j;
  61.     }
  62.     heap[i] = k;
  63. }
  64.  
  65. static void make_code(int n, uchar len[], ushort code[])
  66. {
  67.     int    i;
  68.     ushort start[18];
  69.  
  70.     start[1] = 0;
  71.     for (i = 1; i <= 16; i++)
  72.         start[i + 1] = (start[i] + len_cnt[i]) << 1;
  73.     for (i = 0; i < n; i++) code[i] = start[len[i]]++;
  74. }
  75.  
  76. int make_tree(int nparm, ushort freqparm[],
  77.                 uchar lenparm[], ushort codeparm[])
  78.     /* make tree, calculate len[], return root */
  79. {
  80.     int i, j, k, avail;
  81.  
  82.     n = nparm;  freq = freqparm;  len = lenparm;
  83.     avail = n;  heapsize = 0;  heap[1] = 0;
  84.     for (i = 0; i < n; i++) {
  85.         len[i] = 0;
  86.         if (freq[i]) heap[++heapsize] = i;
  87.     }
  88.     if (heapsize < 2) {
  89.         codeparm[heap[1]] = 0;  return heap[1];
  90.     }
  91.     for (i = heapsize / 2; i >= 1; i--)
  92.         downheap(i);  /* make priority queue */
  93.     sortptr = codeparm;
  94.     do {  /* while queue has at least two entries */
  95.         i = heap[1];  /* take out least-freq entry */
  96.         if (i < n) *sortptr++ = i;
  97.         heap[1] = heap[heapsize--];
  98.         downheap(1);
  99.         j = heap[1];  /* next least-freq entry */
  100.         if (j < n) *sortptr++ = j;
  101.         k = avail++;  /* generate new node */
  102.         freq[k] = freq[i] + freq[j];
  103.         heap[1] = k;  downheap(1);  /* put into queue */
  104.         left[k] = i;  right[k] = j;
  105.     } while (heapsize > 1);
  106.     sortptr = codeparm;
  107.     make_len(k);
  108.     make_code(nparm, lenparm, codeparm);
  109.     return k;  /* return root */
  110. }
  111.