Libraryless. Click here for Pure Java version (13725L/78K).
1 | sclass HuffmanTree is BitIO {
|
2 | settable Node root; |
3 | Leaf[] characterMap = new[256]; |
4 | |
5 | settable bool debug; |
6 | replace print with if (debug) print. |
7 | |
8 | /* |
9 | algebraic type Node {
|
10 | constructor Branch(Node zero, Node one) {}
|
11 | constructor Leaf(byte literal) {}
|
12 | } |
13 | */ |
14 | |
15 | abstract class Node is BitIO {
|
16 | settable Branch parent; |
17 | |
18 | void buildSymbol(BitBuffer head, Node child) {
|
19 | parent?.buildSymbol(head, this); |
20 | } |
21 | |
22 | abstract Leaf readSymbol(BitHead head); |
23 | } |
24 | |
25 | class Branch > Node {
|
26 | gettable Node zero; |
27 | gettable Node one; |
28 | |
29 | meta-for zero also as one {
|
30 | selfType zero(Node zero) {
|
31 | this.zero = zero; |
32 | zero.parent = this; |
33 | this; |
34 | } |
35 | } |
36 | |
37 | public void readWrite(BitHead head) {
|
38 | head.exchangeBit(1); |
39 | head.exchange(zero, -> zero(readNode(head))); |
40 | head.exchange(one, -> one(readNode(head))); |
41 | } |
42 | |
43 | void buildSymbol(BitBuffer head, Node child) {
|
44 | head.add(child == one); |
45 | super.buildSymbol(head, child); |
46 | } |
47 | |
48 | Leaf readSymbol(BitHead head) {
|
49 | bool bit = head.readBit(); |
50 | print("Read bit " + bit);
|
51 | ret (bit ? one : zero).readSymbol(head); |
52 | } |
53 | } |
54 | |
55 | class Leaf > Node {
|
56 | gettable byte literal; |
57 | |
58 | *() {}
|
59 | *(int literal) { literal((byte) literal); }
|
60 | |
61 | byte get() { ret literal; }
|
62 | |
63 | selfType literal(byte b) {
|
64 | literal = b; |
65 | fillCharacterMap(); |
66 | this; |
67 | } |
68 | |
69 | public void readWrite(BitHead head) {
|
70 | head.exchangeBit(0); |
71 | head.exchangeByte(literal, l1 literal); |
72 | print(this); |
73 | } |
74 | |
75 | void fillCharacterMap {
|
76 | characterMap[ubyteToInt(literal)] = this; |
77 | } |
78 | |
79 | Leaf readSymbol(BitHead head) {
|
80 | print("Reached symbol " + this);
|
81 | this; |
82 | } |
83 | |
84 | toString {
|
85 | ret "Literal " + byteToHex(literal); |
86 | } |
87 | } |
88 | |
89 | void makeRootIfEmpty {
|
90 | root ifNull = new Leaf(0); |
91 | } |
92 | |
93 | Node readNode(BitHead head) {
|
94 | bool type = head.peekBit(); |
95 | Node node = type ? new Branch : new Leaf; |
96 | print(type ? "Branch" : "Leaf"); |
97 | node.readWrite(head); |
98 | ret node; |
99 | } |
100 | |
101 | public void readWrite(BitHead head) {
|
102 | if (head.writeMode()) {
|
103 | makeRootIfEmpty(); |
104 | root.readWrite(head); |
105 | } |
106 | |
107 | if (head.readMode()) |
108 | root = readNode(head); |
109 | } |
110 | |
111 | toString {
|
112 | makeRootIfEmpty(); |
113 | new LS out; |
114 | new StringBuilder symbol; |
115 | |
116 | embedded void toString_collect(Node node) {
|
117 | if (node cast Leaf) {
|
118 | out.add(symbol + ": " + /*ubyteToHex*/quote(codePoint(ubyteToInt(node!)))); |
119 | } else {
|
120 | cast node to Branch; |
121 | symbol.append("0");
|
122 | toString_collect(node.zero()); |
123 | removeLast(symbol); |
124 | symbol.append("1");
|
125 | toString_collect(node.one()); |
126 | removeLast(symbol); |
127 | } |
128 | } |
129 | |
130 | toString_collect(root); |
131 | ret lines(out); |
132 | } |
133 | |
134 | void writeCharacter aka writeSymbol(int sym, BitHead head) {
|
135 | sym &= 0xFF; |
136 | Leaf node = characterMap[sym]; |
137 | if (node == null) |
138 | fail("Symbol cannot be encoded: " + sym);
|
139 | new BitBuffer buffer; |
140 | node.buildSymbol(buffer, null); |
141 | |
142 | // when there is only one symbol |
143 | if (buffer.isEmpty()) |
144 | buffer.add(0); |
145 | |
146 | for (int i = l(buffer)-1; i >= 0; i--) |
147 | head.writeBit(buffer.get(i)); |
148 | } |
149 | |
150 | int readSymbol(BitHead head) {
|
151 | if (head.isEOF()) ret -1; |
152 | |
153 | if (root instanceof Leaf) |
154 | head.advanceBit(); // don't even care |
155 | |
156 | ret ubyteToInt(root.readSymbol(head)!); |
157 | } |
158 | } |
download show line numbers debug dex old transpilations
Travelled to 2 computer(s): elmgxqgtpvxh, mqqgnosmbjvj
No comments. add comment
| Snippet ID: | #1035665 |
| Snippet name: | HuffmanTree |
| Eternal ID of this version: | #1035665/41 |
| Text MD5: | 7958e64a838760d732647aa3e60ed5b3 |
| Transpilation MD5: | a32895591c00765eddc0fc320d79e588 |
| Author: | stefan |
| Category: | javax / compression |
| Type: | JavaX fragment (include) |
| Public (visible to everyone): | Yes |
| Archived (hidden from active list): | No |
| Created/modified: | 2022-07-15 20:57:14 |
| Source code size: | 3647 bytes / 158 lines |
| Pitched / IR pitched: | No / No |
| Views / Downloads: | 202 / 490 |
| Version history: | 40 change(s) |
| Referenced in: | [show references] |