fork(4) download
  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4.  
  5.  
  6. char buf[] = "zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzzvvvvvvvvvvvvvvxxxxxxxxxxxxxxxxxxxddddddddd";
  7. int counts[256];
  8. //int testdata[] = { 2, 3, 3, 4, 13, 14 };
  9. int testdata[] = { 1, 1, 1, 2, 3, 5, 6, 6, 6, 6, 6 };
  10. int tdsize = sizeof(testdata)/sizeof(*testdata);
  11.  
  12. static int cmpint(const void *p1, const void *p2);
  13.  
  14. void disp_array(char const * const title, int A[], int n);
  15.  
  16. void inplace_huffman_p1(int *A, int n) {
  17. int i;
  18.  
  19. // Phase 1
  20. int s,r,t;
  21. for(s=0, r=0, t=0; t<n-1; t++) {
  22. int sum = 0;
  23. for(i=0; i<2; i++) {
  24. if(s>=n || (r<t && A[r]<A[s])) {
  25. sum += A[r];
  26. A[r] = t;
  27. r++;
  28. }
  29. else {
  30. sum += A[s];
  31. if(s > t) {
  32. A[s] = 0;
  33. }
  34. s++;
  35. }
  36. }
  37. A[t] = sum;
  38. }
  39.  
  40. disp_array("Phase 1", A, n);
  41. }
  42.  
  43. void inplace_huffman_p2(int *A, int n) {
  44. // Phase 2
  45. int level_top = n - 2; //root
  46. int depth = 1;
  47. int i = n, j, k;
  48. int total_nodes_at_level = 2;
  49. while(i > 0) {
  50. for(k=level_top; k>0 && A[k-1]>=level_top; k--) {}
  51.  
  52. int internal_nodes_at_level = level_top - k;
  53. int leaves_at_level = total_nodes_at_level - internal_nodes_at_level;
  54. for(j=0; j<leaves_at_level; j++) {
  55. A[--i] = depth;
  56. }
  57.  
  58. total_nodes_at_level = internal_nodes_at_level * 2;
  59. level_top = k;
  60. depth++;
  61. }
  62.  
  63. disp_array("Phase 2", A, n);
  64.  
  65. }
  66.  
  67. void n_to_binary_str(int n);
  68.  
  69. int check_code_kraft(int *A, int n) {
  70. int i, sum=0;
  71. int largep2 = 1 << 30;
  72. for(i=0; i<n; i++) {
  73. sum += largep2 >> A[i];
  74. //printf("Check: sum = %x. (sum==largep2)==%d\n", sum, sum == largep2);
  75. //n_to_binary_str(sum);
  76. //putchar('\n');
  77. }
  78. //printf("Check: sum = %x. (sum==largep2)==%d\n", sum, sum == largep2);
  79. return sum==largep2;
  80. }
  81.  
  82. int calc_code_cost(int *A, int n) {
  83. int i, sum=0;
  84. for(i=0; i<n; i++) {
  85. sum += A[i] * testdata[i];
  86. }
  87. return sum;
  88. }
  89.  
  90. void n_to_binary_str(int n) {
  91. char str[30], *p=str, *octal_to_binary[] = {
  92. "000", "001", "010", "011",
  93. "100", "101", "111"
  94. };
  95. sprintf(str, "%011o", n);
  96. while(*p) {
  97. printf("%s", octal_to_binary[*p - '0']);
  98. p++;
  99. }
  100. }
  101.  
  102. int main() {
  103. int A[256],i,n;
  104. int alphasize = sizeof(A)/sizeof(*A);
  105.  
  106. #if 0
  107. for(i=0; i<strlen(buf); i++) {
  108. counts[buf[i]]++;
  109. }
  110.  
  111. n=0;
  112. for(i=0; i<alphasize; i++) {
  113. if(counts[i] != 0) {
  114. A[n++] = counts[i];
  115. }
  116. }
  117.  
  118. qsort(A, n, sizeof(A[0]), cmpint);
  119. #endif
  120.  
  121.  
  122. #if 1
  123. memcpy(A, testdata, tdsize * sizeof(testdata[0]));
  124. n = tdsize;
  125. qsort(A, n, sizeof(A[0]), cmpint);
  126. #endif
  127.  
  128. disp_array("Phase 0", A, n);
  129.  
  130. inplace_huffman_p1(A, n);
  131. inplace_huffman_p2(A, n);
  132.  
  133. if(!check_code_kraft(A, n)) {
  134. printf("Failed Kraft ineq!\n");
  135. }
  136. else {
  137. printf("Passed Kraft check.\n");
  138. }
  139.  
  140. int cost=calc_code_cost(A, n);
  141. printf("Total code cost: %d\n", cost);
  142.  
  143. return 0;
  144. }
  145.  
  146. void disp_array(char const * const title, int A[], int n)
  147. {
  148. int i;
  149. printf("%s:\n", title);
  150. for(i=0; i<n; i++) {
  151. if(i>0) {
  152. putchar('|');
  153. }
  154. printf("%d", A[i]);
  155. }
  156. putchar('\n');
  157. }
  158.  
  159. static int cmpint(const void *p1, const void *p2) {
  160. return *((const int *)p1) - *((const int *)p2);
  161. }
  162.  
Success #stdin #stdout 0s 2052KB
stdin
wqerdfdfd
stdout
Phase 0:
1|1|1|2|3|5|6|6|6|6|6
Phase 1:
2|3|4|7|7|8|8|9|9|43|0
Phase 2:
5|5|4|4|4|3|3|3|3|3|3
Passed Kraft check.
Total code cost: 139