1 | for (int i = alphaSize; --i >= 0;) {↵ | | 1 | for (int i = alphaSize; --i >= 0;) {↵
|
2 | weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8;↵ | | 2 | weight[i + 1] = (freq[i] == 0 ? 1 : freq[i]) << 8;↵
|
3 | }↵ | | 3 | }↵
|
|
4 | for (boolean tooLong = true; tooLong;) {↵ | | 4 | for (boolean tooLong = true; tooLong;) {↵
|
5 | tooLong = false;↵ | | 5 | tooLong = false;↵
|
|
6 | int nNodes = alphaSize;↵ | | 6 | int nNodes = alphaSize;↵
|
7 | int nHeap = 0;↵ | | 7 | int nHeap = 0;↵
|
8 | heap[0] = 0;↵ | | 8 | heap[0] = 0;↵
|
9 | weight[0] = 0;↵ | | 9 | weight[0] = 0;↵
|
10 | parent[0] = -2;↵ | | 10 | parent[0] = -2;↵
|
|
11 | for (int i = 1; i <= alphaSize; i++) {↵ | | 11 | for (int i = 1; i <= alphaSize; i++) {↵
|
12 | parent[i] = -1;↵ | | 12 | parent[i] = -1;↵
|
13 | nHeap++;↵ | | 13 | nHeap++;↵
|
14 | heap[nHeap] = i;↵ | | 14 | heap[nHeap] = i;↵
|
|
15 | int zz = nHeap;↵ | | 15 | int zz = nHeap;↵
|
16 | int tmp = heap[zz];↵ | | 16 | int tmp = heap[zz];↵
|
17 | while (weight[tmp] < weight[heap[zz >> 1]]) {↵ | | 17 | while (weight[tmp] < weight[heap[zz >> 1]]) {↵
|
18 | heap[zz] = heap[zz >> 1];↵ | | 18 | heap[zz] = heap[zz >> 1];↵
|
19 | zz >>= 1;↵ | | 19 | zz >>= 1;↵
|
20 | }↵ | | 20 | }↵
|
21 | heap[zz] = tmp;↵ | | 21 | heap[zz] = tmp;↵
|
22 | }↵ | | 22 | }↵
|
|
| | | 23 | // assert (nHeap < (MAX_ALPHA_SIZE + 2)) : nHeap;↵
|
|
23 | while (nHeap > 1) {↵ | | 24 | while (nHeap > 1) {↵
|
24 | int n1 = heap[1];↵ | | 25 | int n1 = heap[1];↵
|
25 | heap[1] = heap[nHeap];↵ | | 26 | heap[1] = heap[nHeap];↵
|
26 | nHeap--;↵ | | 27 | nHeap--;↵
|
|
27 | int yy = 0;↵ | | 28 | int yy = 0;↵
|
28 | int zz = 1;↵ | | 29 | int zz = 1;↵
|
29 | int tmp = heap[1];↵ | | 30 | int tmp = heap[1];↵
|
|
30 | while (true) {↵ | | 31 | while (true) {↵
|
31 | yy = zz << 1;↵ | | 32 | yy = zz << 1;↵
|
|
32 | if (yy > nHeap) {↵ | | 33 | if (yy > nHeap) {↵
|
33 | break;↵ | | 34 | break;↵
|
34 | }↵ | | 35 | }↵
|
|
35 | if ((yy < nHeap)↵ | | 36 | if ((yy < nHeap)↵
|
36 | && (weight[heap[yy + 1]] < weight[heap[yy]])) {↵ | | 37 | && (weight[heap[yy + 1]] < weight[heap[yy]])) {↵
|
37 | yy++;↵ | | 38 | yy++;↵
|
38 | }↵ | | 39 | }↵
|
|
39 | if (weight[tmp] < weight[heap[yy]]) {↵ | | 40 | if (weight[tmp] < weight[heap[yy]]) {↵
|
40 | break;↵ | | 41 | break;↵
|
41 | }↵ | | 42 | }↵
|
|
42 | heap[zz] = heap[yy];↵ | | 43 | heap[zz] = heap[yy];↵
|
43 | zz = yy;↵ | | 44 | zz = yy;↵
|
44 | }↵ | | 45 | }↵
|
|
45 | heap[zz] = tmp;↵ | | 46 | heap[zz] = tmp;↵
|
|
46 | int n2 = heap[1];↵ | | 47 | int n2 = heap[1];↵
|
47 | heap[1] = heap[nHeap];↵ | | 48 | heap[1] = heap[nHeap];↵
|
48 | nHeap--;↵ | | 49 | nHeap--;↵
|
|
49 | yy = 0;↵ | | 50 | yy = 0;↵
|
50 | zz = 1;↵ | | 51 | zz = 1;↵
|
51 | tmp = heap[1];↵ | | 52 | tmp = heap[1];↵
|
|
52 | while (true) {↵ | | 53 | while (true) {↵
|
53 | yy = zz << 1;↵ | | 54 | yy = zz << 1;↵
|
|
54 | if (yy > nHeap) {↵ | | 55 | if (yy > nHeap) {↵
|
55 | break;↵ | | 56 | break;↵
|
56 | }↵ | | 57 | }↵
|
|
57 | if ((yy < nHeap)↵ | | 58 | if ((yy < nHeap)↵
|
58 | && (weight[heap[yy + 1]] < weight[heap[yy]])) {↵ | | 59 | && (weight[heap[yy + 1]] < weight[heap[yy]])) {↵
|
59 | yy++;↵ | | 60 | yy++;↵
|
60 | }↵ | | 61 | }↵
|
|
61 | if (weight[tmp] < weight[heap[yy]]) {↵ | | 62 | if (weight[tmp] < weight[heap[yy]]) {↵
|
62 | break;↵ | | 63 | break;↵
|
63 | }↵ | | 64 | }↵
|
|
64 | heap[zz] = heap[yy];↵ | | 65 | heap[zz] = heap[yy];↵
|
65 | zz = yy;↵ | | 66 | zz = yy;↵
|
66 | }↵ | | 67 | }↵
|
|
67 | heap[zz] = tmp;↵ | | 68 | heap[zz] = tmp;↵
|
68 | nNodes++;↵ | | 69 | nNodes++;↵
|
69 | parent[n1] = parent[n2] = nNodes;↵ | | 70 | parent[n1] = parent[n2] = nNodes;↵
|
|
70 | final int weight_n1 = weight[n1];↵ | | 71 | final int weight_n1 = weight[n1];↵
|
71 | final int weight_n2 = weight[n2]; | | 72 | final int weight_n2 = weight[n2];
|