dynamic_huffman_tree.zig

/// allocator: for allocating working memory which is released at the end of the function
/// arena_allocator: a &(std.heap.ArenaAllocator).allocator that should later be used to free all nodes of the returned Huffman tree without traversal
pub fn fromFrequencies(allocator: *Allocator, arena_allocator: *Allocator, symbols: []Node) !*Node {
    // index symbols
    const index: []*Node = try allocator.alloc(*Node, symbols.len);
    defer allocator.free(index);
    for (symbols) |*node, i| {
        var n = node;
        index[i] = n;
    }

    // view of index that shrinks to n=1 (root node) as nodes are combined and the tree is built
    var remaining_nodes = index[0..];

    while (remaining_nodes.len > 1) {
        std.sort.insertionSort(*Node, remaining_nodes, Node.sortByWeight);
        var lowest1 = remaining_nodes[0];
        var lowest2 = remaining_nodes[1];

        //std.debug.warn("\nlen: {} - lowest: {}({}), {}({})", remaining_nodes.len, if (lowest1.symbol) |sym| sym.val else null, lowest1.weight, if (lowest2.symbol) |sym| sym.val else null, lowest2.weight);

        var node = try arena_allocator.create(Node);
        node.* = Node{ .weight = lowest1.weight + lowest2.weight };

        var child_nodes = [2]*Node{ lowest1, lowest2 };

        if (lowest1.symbol != null and lowest1.symbol != null) {
            if (lowest1.symbol) |sym1| {
                if (lowest2.symbol) |sym2| {
                    if (sym1.code > sym2.code) {
                        child_nodes = [2]*Node{ lowest2, lowest1 };
                    }
                }
            }
        } else {
            if (lowest1.symbol == null and lowest2.symbol != null) {
                child_nodes = [2]*Node{ lowest2, lowest1 };
            }
        }

        node.nodes = child_nodes;

        remaining_nodes[1] = node;
        remaining_nodes = remaining_nodes[1..];
    }

    var root_node = remaining_nodes[0].*;
    return &root_node;
}