huffman source code

1 module huffman;
2 
3 import std.algorithm.iteration : Group;
4 
5 /** Huffman Encode $(D sf). */
6 auto encode(T)(Group!("a == b", T[]) sf)
7 {
8     import std.algorithm.iteration : map;
9     import std.algorithm.sorting : schwartzSort;
10     import std.typecons : tuple;
11     import std.array : array;
12     import std.container.binaryheap : heapify;
13     // TODO instead used import mir.container.binaryheap : heapify;
14 
15     auto heap = sf.map!(s => tuple(s[1], [tuple(s[0], "")]))
16                   .array.heapify!q{b < a};
17 
18     while (heap.length > 1)
19     {
20         auto lo = heap.front; heap.removeFront();
21         auto hi = heap.front; heap.removeFront();
22 
23         foreach (ref pair; lo[1]) pair[1] = '0' ~ pair[1];
24         foreach (ref pair; hi[1]) pair[1] = '1' ~ pair[1];
25 
26         heap.insert(tuple(lo[0] + hi[0], lo[1] ~ hi[1]));
27     }
28     return heap.front[1].schwartzSort!q{tuple(a[1].length, a[0])};
29 }
30 
31 unittest
32 {
33     import std.algorithm.sorting : sort;
34     import std.algorithm.iteration : group;
35     import std.stdio : writefln;
36     auto s = "this is an example for huffman encoding"d;
37     foreach (p; s.dup.sort().release.group.encode)
38         writefln("'%s'  %s", p[]);
39 }