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).

1  
// Builds a HuffmanTree from a byte histogram
2  
sclass HuffmanTreeMaker {
3  
  delegate Node, Branch, Leaf to HuffmanTree.
4  
  
5  
  // output
6  
  gettable new HuffmanTree tree;
7  
  
8  
  // internal
9  
  new TreeSet<Head> pool; // combinable trees sorted by incidence (symbol frequency)
10  
  int indexCounter; // counter to keep order deterministic
11  
  
12  
  class Head is Comparable<Head> {
13  
    int index = indexCounter++;
14  
    settable Node node;
15  
    settable double freq; // using floating point to keep things futureproof
16  
17  
    // sort by frequency first, then by index (order of creation)
18  
    public int compareTo(Head h) {
19  
      if (this == h) ret 0;
20  
      var c = cmp(freq, h.freq);
21  
      if (c != 0) ret c;
22  
      ret cmp(index, h.index);
23  
    }
24  
    
25  
    toString { ret freq + "x " + node; }
26  
  }
27  
  
28  
  // histogram[0] = incidence for byte 00
29  
  // histogram[1] = incidence for byte 01
30  
  // etc. up to 255 (or less)
31  
  selfType importByteHistogram(int[] histogram) {
32  
    int n = l(histogram);
33  
    for i to n: {
34  
      double freq = histogram[i];
35  
      if (freq != 0)
36  
        pool.add(new Head().freq(freq).node(tree.new Leaf(i)));
37  
    }
38  
    this;
39  
  }
40  
  
41  
  run {
42  
    while ping (l(pool) > 1) {
43  
      var it = iterator(pool);
44  
      var a = it.next();
45  
      it.remove();
46  
      var b = it.next();
47  
      it.remove();
48  
      //print("Merging frequencies: " + commaCombine(a.freq, b.freq));
49  
      var newHead = new Head()
50  
        .freq(a.freq+b.freq)
51  
        .node(tree.new Branch().zero(b.node).one(a.node));
52  
      //print("Merging: " + commaCombine(a, b) + " to " + newHead);
53  
      pool.add(newHead);
54  
    }
55  
  }
56  
  
57  
  HuffmanTree get() {
58  
    run();
59  
    if (nempty(pool))
60  
      tree.root(popFirst(pool).node());
61  
    ret tree;
62  
  }
63  
}

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: 156 / 308
Version history: 13 change(s)
Referenced in: [show references]