pub const HuffmanTree = struct {
    max_bit_count: u4,
    symbol_count_minus_one: u8,
    nodes: [256]PrefixedSymbol,

    pub const PrefixedSymbol = struct {
        symbol: u8,
        prefix: u16,
        weight: u4,
    };

    pub const Result = union(enum) {
        symbol: u8,
        index: usize,
    };

    pub fn query(self: HuffmanTree, index: usize, prefix: u16) error{NotFound}!Result {
        var node = self.nodes[index];
        const weight = node.weight;
        var i: usize = index;
        while (node.weight == weight) {
            if (node.prefix == prefix) return Result{ .symbol = node.symbol };
            if (i == 0) return error.NotFound;
            i -= 1;
            node = self.nodes[i];
        }
        return Result{ .index = i };
    }

    pub fn weightToBitCount(weight: u4, max_bit_count: u4) u4 {
        return if (weight == 0) 0 else ((max_bit_count + 1) - weight);
    }
}