import java.util.*; import java.util.zip.*; import java.util.List; import java.util.regex.*; import java.util.concurrent.*; import java.util.concurrent.atomic.*; import java.util.concurrent.locks.*; import java.util.function.*; import javax.swing.*; import javax.swing.event.*; import javax.swing.text.*; import javax.swing.table.*; import java.io.*; import java.net.*; import java.lang.reflect.*; import java.lang.ref.*; import java.lang.management.*; import java.security.*; import java.security.spec.*; import java.awt.*; import java.awt.event.*; import java.awt.image.*; import java.awt.geom.*; import javax.imageio.*; import java.math.*; import java.time.Duration; import java.lang.invoke.VarHandle; import java.lang.invoke.MethodHandles; // Builds a HuffmanTree from a byte histogram import java.awt.geom.*; import static x30_pkg.x30_util.DynamicObject; import java.text.*; import java.text.NumberFormat; import java.util.TimeZone; class main { static class HuffmanTreeMaker { // output final public HuffmanTree getTree(){ return tree(); } public HuffmanTree tree() { return tree; } HuffmanTree tree = new HuffmanTree(); // internal TreeSet
pool = new TreeSet(); // combinable trees sorted by incidence (symbol frequency) int indexCounter; // counter to keep order deterministic class Head implements Comparable { int index = indexCounter++; final public Head setNode(HuffmanTree.Node node){ return node(node); } public Head node(HuffmanTree.Node node) { this.node = node; return this; } final public HuffmanTree.Node getNode(){ return node(); } public HuffmanTree.Node node() { return node; } HuffmanTree.Node node; final public Head setFreq(double freq){ return freq(freq); } public Head freq(double freq) { this.freq = freq; return this; } final public double getFreq(){ return freq(); } public double freq() { return freq; } double freq; // using floating point to keep things futureproof // sort by frequency first, then by index (order of creation) public int compareTo(Head h) { if (this == h) return 0; var c = cmp(freq, h.freq); if (c != 0) return c; return cmp(index, h.index); } public String toString() { return freq + "x " + node; } } // histogram[0] = incidence for byte 00 // histogram[1] = incidence for byte 01 // etc. up to 255 (or less) HuffmanTreeMaker importByteHistogram(int[] histogram) { int n = l(histogram); for (int i = 0; i < n; i++) { double freq = histogram[i]; if (freq != 0) pool.add(new Head().freq(freq).node(tree.new Leaf(i))); } return this; } public void run() { try { while (l(pool) > 1) { ping(); var it = iterator(pool); var a = it.next(); it.remove(); var b = it.next(); it.remove(); //print("Merging frequencies: " + commaCombine(a.freq, b.freq)); var newHead = new Head() .freq(a.freq+b.freq) .node(tree.new Branch().zero(b.node).one(a.node)); //print("Merging: " + commaCombine(a, b) + " to " + newHead); pool.add(newHead); } } catch (Exception __e) { throw rethrow(__e); } } HuffmanTree get() { run(); if (nempty(pool)) tree.root(popFirst(pool).node()); return tree; } } static Frequency freq(double freq) { return toFrequency(freq); } static int cmp(Number a, Number b) { return a == null ? b == null ? 0 : -1 : cmp(a.doubleValue(), b.doubleValue()); } static int cmp(double a, double b) { return a < b ? -1 : a == b ? 0 : 1; } static int cmp(int a, int b) { return a < b ? -1 : a == b ? 0 : 1; } static int cmp(long a, long b) { return a < b ? -1 : a == b ? 0 : 1; } static int cmp(Object a, Object b) { if (a == null) return b == null ? 0 : -1; if (b == null) return 1; return ((Comparable) a).compareTo(b); } static int l(Object[] a) { return a == null ? 0 : a.length; } static int l(boolean[] a) { return a == null ? 0 : a.length; } static int l(byte[] a) { return a == null ? 0 : a.length; } static int l(short[] a) { return a == null ? 0 : a.length; } static int l(long[] a) { return a == null ? 0 : a.length; } static int l(int[] a) { return a == null ? 0 : a.length; } static int l(float[] a) { return a == null ? 0 : a.length; } static int l(double[] a) { return a == null ? 0 : a.length; } static int l(char[] a) { return a == null ? 0 : a.length; } static int l(Collection c) { return c == null ? 0 : c.size(); } static int l(Iterator i) { return iteratorCount_int_close(i); } // consumes the iterator && closes it if possible static int l(Map m) { return m == null ? 0 : m.size(); } static int l(CharSequence s) { return s == null ? 0 : s.length(); } static long l(File f) { return f == null ? 0 : f.length(); } static int l(IMultiMap mm) { return mm == null ? 0 : mm.size(); } static int l(AppendableChain a) { return a == null ? 0 : a.size; } static int l(IntSize o) { return o == null ? 0 : o.size(); } // legacy mode //sbool ping_actions_shareable = true; static volatile boolean ping_pauseAll = false; static int ping_sleep = 100; // poll pauseAll flag every 100 static volatile boolean ping_anyActions = false; static Map