OSDN Git Service

Add new source files
[armadillo/armadillo1.git] / src / jp / sfjp / armadillo / compression / lzhuf / LzhHuffmanTable.java
1 package jp.sfjp.armadillo.compression.lzhuf;
2
3 import java.util.*;
4 import jp.sfjp.armadillo.archive.lzh.*;
5
6 /**
7  * A huffman table for LZHUF.
8  */
9 public final class LzhHuffmanTable {
10
11     private static final int MAX_CODE_LENGTH = 16;
12
13     final int[] codeTable;
14     final int[] codeLengthTable;
15
16     private LzhHuffmanTable(int[] frequencyTable) {
17         int tableSize = frequencyTable.length;
18         for (int i = tableSize - 1; i >= 0; i--) {
19             if (frequencyTable[i] > 0)
20                 break;
21             --tableSize;
22         }
23         int[] ct = new int[tableSize];
24         int[] lt = new int[tableSize];
25         build(frequencyTable, tableSize, ct, lt);
26         this.codeTable = ct;
27         this.codeLengthTable = lt;
28     }
29
30     public static LzhHuffmanTable build(int[] frequencyTable) {
31         return new LzhHuffmanTable(frequencyTable);
32     }
33
34     /**
35      * Builds tables.
36      * @param frequencyTable
37      * @param tableSize
38      * @param ct code table
39      * @param lt code length table
40      */
41     private void build(int[] frequencyTable, int tableSize, int[] ct, int[] lt) {
42         // create node list
43         LinkedList<Node> q = new LinkedList<Node>();
44         for (int i = 0; i < tableSize; i++) {
45             final int frequency = frequencyTable[i];
46             if (frequency > 0)
47                 q.add(new Node(i, frequency));
48         }
49         if (q.size() < 2) {
50             // queue size = ( 0, 1, 2 )
51             int queueSize = q.size();
52             if (queueSize == 1) {
53                 // queue size = ( 1 )
54                 lt[tableSize - 1] = 1;
55             }
56             else if (queueSize == 2) {
57                 // queue size = ( 2 )
58                 Node node1 = q.get(0);
59                 Node node2 = q.get(1);
60                 int[] numbers = {node1.number, node2.number};
61                 Arrays.sort(numbers);
62                 ct[numbers[0]] = 0;
63                 lt[numbers[0]] = 1;
64                 ct[numbers[1]] = 1;
65                 lt[numbers[1]] = 1;
66             }
67             return;
68         }
69         // create tree
70         int number = tableSize;
71         while (q.size() > 1) {
72             Collections.sort(q);
73             Node node1 = q.remove(0);
74             Node node2 = q.remove(0);
75             q.add(new Node(number++, node1, node2));
76         }
77         Node root = q.get(0);
78         // create tables
79         createCodeLengthTable(root, tableSize, 0, lt);
80         createCodeTable(ct, lt);
81     }
82
83     /**
84      * Creates code length table.
85      * It traverses huffman tree recursively.
86      * @param node node of huffman tree
87      * @param size table size
88      * @param codeLength
89      * @param lt (output) code length table
90      */
91     private static void createCodeLengthTable(Node node, int size, int codeLength, int[] lt) {
92         if (codeLength > 16)
93             throw new LzhQuit("code length = " + codeLength);
94         final int number = node.number;
95         if (number < size)
96             lt[number] = codeLength;
97         else {
98             createCodeLengthTable(node.left, size, codeLength + 1, lt);
99             createCodeLengthTable(node.right, size, codeLength + 1, lt);
100         }
101     }
102
103     /**
104      * Creates code table from code length table.
105      * @param lt code length table
106      * @return ct code table
107      */
108     static int[] createCodeTable(int[] lt) {
109         int[] ct = new int[lt.length];
110         createCodeTable(ct, lt);
111         return ct;
112     }
113
114     /**
115      * Creates code table from code length table.
116      * @param ct (output) code length table
117      * @param lt code length table
118      */
119     static void createCodeTable(int[] ct, int[] lt) {
120         final int workSize = MAX_CODE_LENGTH + 1;
121         int[] counts = new int[workSize];
122         for (int i = 0; i < lt.length; i++)
123             ++counts[lt[i]];
124         int[] baseCodes = new int[workSize];
125         for (int i = 0; i < MAX_CODE_LENGTH; i++)
126             baseCodes[i + 1] = baseCodes[i] + counts[i + 1] << 1;
127         assert baseCodes[MAX_CODE_LENGTH] == 1 << workSize : baseCodes[MAX_CODE_LENGTH];
128         for (int i = 0; i < ct.length; i++) {
129             final int codeLength = lt[i];
130             if (codeLength > 0)
131                 ct[i] = baseCodes[codeLength - 1]++;
132         }
133     }
134
135     private static final class Node implements Comparable<Node> {
136
137         final int number;
138         final int weight;
139
140         Node left;
141         Node right;
142
143         public Node(int number, int weight) {
144             this.number = number;
145             this.weight = weight;
146             this.left = null;
147             this.right = null;
148         }
149
150         public Node(int number, Node node1, Node node2) {
151             this.number = number;
152             this.weight = node1.weight + node2.weight;
153             this.left = node1;
154             this.right = node2;
155         }
156
157         @Override
158         public int compareTo(Node anotherNode) {
159             int tn;
160             int an;
161             if (anotherNode.weight == this.weight) {
162                 tn = anotherNode.number;
163                 an = this.number;
164             }
165             else {
166                 tn = this.weight;
167                 an = anotherNode.weight;
168             }
169             return tn < an ? -1 : (tn == an ? 0 : 1);
170         }
171
172         @Override
173         public int hashCode() {
174             final int prime = 31;
175             int result = 1;
176             result = prime * result + ((left == null) ? 0 : left.hashCode());
177             result = prime * result + number;
178             result = prime * result + ((right == null) ? 0 : right.hashCode());
179             result = prime * result + weight;
180             return result;
181         }
182
183         @Override
184         public boolean equals(Object obj) {
185             if (this == obj)
186                 return true;
187             if (obj == null)
188                 return false;
189             if (getClass() != obj.getClass())
190                 return false;
191             Node other = (Node)obj;
192             if (left == null) {
193                 if (other.left != null)
194                     return false;
195             }
196             else if (!left.equals(other.left))
197                 return false;
198             if (number != other.number)
199                 return false;
200             if (right == null) {
201                 if (other.right != null)
202                     return false;
203             }
204             else if (!right.equals(other.right))
205                 return false;
206             if (weight != other.weight)
207                 return false;
208             return true;
209         }
210
211         @Override
212         public String toString() {
213             return "Node:" + number + " (" + weight + ")";
214         }
215
216     }
217
218 }