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