Libraryless. Click here for Pure Java version (13725L/78K).
sclass HuffmanTree is BitIO { settable Node root; Leaf[] characterMap = new[256]; settable bool debug; replace print with if (debug) print. /* algebraic type Node { constructor Branch(Node zero, Node one) {} constructor Leaf(byte literal) {} } */ abstract class Node is BitIO { settable Branch parent; void buildSymbol(BitBuffer head, Node child) { parent?.buildSymbol(head, this); } abstract Leaf readSymbol(BitHead head); } class Branch > Node { gettable Node zero; gettable Node one; meta-for zero also as one { selfType zero(Node zero) { this.zero = zero; zero.parent = this; this; } } public void readWrite(BitHead head) { head.exchangeBit(1); head.exchange(zero, -> zero(readNode(head))); head.exchange(one, -> one(readNode(head))); } void buildSymbol(BitBuffer head, Node child) { head.add(child == one); super.buildSymbol(head, child); } Leaf readSymbol(BitHead head) { bool bit = head.readBit(); print("Read bit " + bit); ret (bit ? one : zero).readSymbol(head); } } class Leaf > Node { gettable byte literal; *() {} *(int literal) { literal((byte) literal); } byte get() { ret literal; } selfType literal(byte b) { literal = b; fillCharacterMap(); this; } public void readWrite(BitHead head) { head.exchangeBit(0); head.exchangeByte(literal, l1 literal); print(this); } void fillCharacterMap { characterMap[ubyteToInt(literal)] = this; } Leaf readSymbol(BitHead head) { print("Reached symbol " + this); this; } toString { ret "Literal " + byteToHex(literal); } } void makeRootIfEmpty { root ifNull = new Leaf(0); } Node readNode(BitHead head) { bool type = head.peekBit(); Node node = type ? new Branch : new Leaf; print(type ? "Branch" : "Leaf"); node.readWrite(head); ret node; } public void readWrite(BitHead head) { if (head.writeMode()) { makeRootIfEmpty(); root.readWrite(head); } if (head.readMode()) root = readNode(head); } toString { makeRootIfEmpty(); new LS out; new StringBuilder symbol; embedded void toString_collect(Node node) { if (node cast Leaf) { out.add(symbol + ": " + /*ubyteToHex*/quote(codePoint(ubyteToInt(node!)))); } else { cast node to Branch; symbol.append("0"); toString_collect(node.zero()); removeLast(symbol); symbol.append("1"); toString_collect(node.one()); removeLast(symbol); } } toString_collect(root); ret lines(out); } void writeCharacter aka writeSymbol(int sym, BitHead head) { sym &= 0xFF; Leaf node = characterMap[sym]; if (node == null) fail("Symbol cannot be encoded: " + sym); new BitBuffer buffer; node.buildSymbol(buffer, null); // when there is only one symbol if (buffer.isEmpty()) buffer.add(0); for (int i = l(buffer)-1; i >= 0; i--) head.writeBit(buffer.get(i)); } int readSymbol(BitHead head) { if (head.isEOF()) ret -1; if (root instanceof Leaf) head.advanceBit(); // don't even care ret ubyteToInt(root.readSymbol(head)!); } }
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: | 203 / 490 |
Version history: | 40 change(s) |
Referenced in: | #1003674 - Standard Classes + Interfaces (LIVE continued in #1034167) #1035667 - HuffmanTreeMaker [OK] |