fork(6) download
copy 
  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
comments (?)
stdin
copy 
wqerdfdfd
stdout
copy 
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
https://ideone.com/CeyLzv
language:
C (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!