Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

63
LINES

< > BotCompany Repo | #1035667 // HuffmanTreeMaker [OK]

JavaX fragment (include) [tags: use-pretranspiled]

Libraryless. Click here for Pure Java version (15084L/89K).

// Builds a HuffmanTree from a byte histogram
sclass HuffmanTreeMaker {
  delegate Node, Branch, Leaf to HuffmanTree.
  
  // output
  gettable new HuffmanTree tree;
  
  // internal
  new TreeSet<Head> pool; // combinable trees sorted by incidence (symbol frequency)
  int indexCounter; // counter to keep order deterministic
  
  class Head is Comparable<Head> {
    int index = indexCounter++;
    settable Node node;
    settable 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) ret 0;
      var c = cmp(freq, h.freq);
      if (c != 0) ret c;
      ret cmp(index, h.index);
    }
    
    toString { ret freq + "x " + node; }
  }
  
  // histogram[0] = incidence for byte 00
  // histogram[1] = incidence for byte 01
  // etc. up to 255 (or less)
  selfType importByteHistogram(int[] histogram) {
    int n = l(histogram);
    for i to n: {
      double freq = histogram[i];
      if (freq != 0)
        pool.add(new Head().freq(freq).node(tree.new Leaf(i)));
    }
    this;
  }
  
  run {
    while ping (l(pool) > 1) {
      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);
    }
  }
  
  HuffmanTree get() {
    run();
    if (nempty(pool))
      tree.root(popFirst(pool).node());
    ret tree;
  }
}

Author comment

Began life as a copy of #1035665

download  show line numbers  debug dex  old transpilations   

Travelled to 2 computer(s): elmgxqgtpvxh, mqqgnosmbjvj

No comments. add comment

Snippet ID: #1035667
Snippet name: HuffmanTreeMaker [OK]
Eternal ID of this version: #1035667/14
Text MD5: 8c84c4a34cc09bee987f49d1537bba10
Transpilation MD5: 65da45965eaad1d64726fc9d9569fb12
Author: stefan
Category: javax / huffman encoding
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2022-07-15 19:23:09
Source code size: 1756 bytes / 63 lines
Pitched / IR pitched: No / No
Views / Downloads: 94 / 218
Version history: 13 change(s)
Referenced in: [show references]