nicoster · March 25, 2021 02:42 · nicoster · Mar 24, 2021
diff --git a/Huffman.lua b/Huffman.lua
 local ins = require 'inspect'

 local function insert_prioq(prioq, el, freq, insert_after)

    for i, v in ipairs(prioq) do
        -- print('i:', i, ' v:', ins(v))
        if insert_after then
            if freq < v[2] then
                table.insert(prioq, i, {el, freq})
                -- print(ins(prioq))
                return prioq
            end
        else
            if freq <= v[2] then
                table.insert(prioq, i, {el, freq})
                -- print(ins(prioq))
                return prioq
            end
        end
    end
    table.insert(prioq, {el, freq})
    -- print('default:', ins(prioq))

    return prioq
 end

 local function make_prioq(str)
    local freqs = {}
    for i = 1, #str do
        local ch = string.sub(str, i, i)
        freqs[ch] = (freqs[ch] or 0) + 1
    end

    local sorted_freqs = {}
    for i = 1, #str do
        local ch = string.sub(str, i, i)
        if freqs[ch] then
            table.insert(sorted_freqs, {ch, freqs[ch]})
            freqs[ch] = nil
        end
    end

    -- print(ins(freqs))
    -- print(ins(sorted_freqs))

    local prioq = {}    --todo reserve buffer to prevent reallocations.
    for _, v in ipairs(sorted_freqs) do
        local ch, freq = unpack(v)
        -- print('ch:', ch, ' freq:', freq)
        insert_prioq(prioq, ch, freq, true)
    end

    return prioq
 end

 local function make_tree(prioq)
    if #prioq > 1 then
        local l = table.remove(prioq, 1)
        local r = table.remove(prioq, 1)
        -- print('#prioq:', #prioq)
        insert_prioq(prioq, {l[1], r[1]}, l[2] + r[2])
        -- print('after insert, #prioq:', #prioq)
        return make_tree(prioq)
    else
        return prioq
    end
 end

 local function print_tree(tree, code)
    code = code or ''

    local l, r = tree[1], tree[2]
    if type(l) == 'table' then
        print_tree(l, code .. '0')
    else
        print(l, code .. '0')
    end
    if type(r) == 'table' then
        return print_tree(r, code .. '1')
    else
        print(r, code .. '1')
    end
 end

 local function main()
    local sample = "beep boop beer!"
    local prioq = make_prioq(sample)
    print('prioq:', ins(prioq))
    local tree = make_tree(prioq)
    print('tree:', ins(tree))
    -- remove the enclosing parens
    print_tree(tree[1][1])
 end

 main()
	local ins = require 'inspect'

	local function insert_prioq(prioq, el, freq, insert_after)

	for i, v in ipairs(prioq) do
	-- print('i:', i, ' v:', ins(v))
	if insert_after then
	if freq < v[2] then
	table.insert(prioq, i, {el, freq})
	-- print(ins(prioq))
	return prioq
	end
	else
	if freq <= v[2] then
	table.insert(prioq, i, {el, freq})
	-- print(ins(prioq))
	return prioq
	end
	end
	end
	table.insert(prioq, {el, freq})
	-- print('default:', ins(prioq))

	return prioq
	end

	local function make_prioq(str)
	local freqs = {}
	for i = 1, #str do
	local ch = string.sub(str, i, i)
	freqs[ch] = (freqs[ch] or 0) + 1
	end

	local sorted_freqs = {}
	for i = 1, #str do
	local ch = string.sub(str, i, i)
	if freqs[ch] then
	table.insert(sorted_freqs, {ch, freqs[ch]})
	freqs[ch] = nil
	end
	end

	-- print(ins(freqs))
	-- print(ins(sorted_freqs))

	local prioq = {} --todo reserve buffer to prevent reallocations.
	for _, v in ipairs(sorted_freqs) do
	local ch, freq = unpack(v)
	-- print('ch:', ch, ' freq:', freq)
	insert_prioq(prioq, ch, freq, true)
	end

	return prioq
	end

	local function make_tree(prioq)
	if #prioq > 1 then
	local l = table.remove(prioq, 1)
	local r = table.remove(prioq, 1)
	-- print('#prioq:', #prioq)
	insert_prioq(prioq, {l[1], r[1]}, l[2] + r[2])
	-- print('after insert, #prioq:', #prioq)
	return make_tree(prioq)
	else
	return prioq
	end
	end

	local function print_tree(tree, code)
	code = code or ''

	local l, r = tree[1], tree[2]
	if type(l) == 'table' then
	print_tree(l, code .. '0')
	else
	print(l, code .. '0')
	end
	if type(r) == 'table' then
	return print_tree(r, code .. '1')
	else
	print(r, code .. '1')
	end
	end

	local function main()
	local sample = "beep boop beer!"
	local prioq = make_prioq(sample)
	print('prioq:', ins(prioq))
	local tree = make_tree(prioq)
	print('tree:', ins(tree))
	-- remove the enclosing parens
	print_tree(tree[1][1])
	end

	main()