local api = {}


--Type example
--local leaf = {freq = x, char = y}
--local node = {freq = x, right = t1,left = t2}
function dequeue(tab)
  local data = tab[1]
  for i=2,#tab do
    tab[i-1] = tab[i]
    tab[i] = nil
  end
  return data
end

function enqueue(tab,data,ind)
  if ind then
    for i=#tab,ind,-1 do
      tab[i+1] = tab[i]
    end
  else
    ind = #tab+1
  end
  tab[ind] = data
end

function insertOrder(data,tab,valueFunc)
  local n_val = valueFunc(data)
  for i2=1,#tab do
    local val = valueFunc(tab[i2])
    if n_val <= val then
      enqueue(tab,data,i2)
      return
    end
  end
  enqueue(tab,data)
end

function sort(tab,valueFunc)
  local tab2 = {}
  for i,v in pairs(tab) do
    tab2[i] = v
  end
  for i=1,#tab do
    tab[i] = nil
  end
  for i=1,#tab2 do
    local data = tab2[i]
    insertOrder(data,tab,valueFunc)
  end
end


function makeLeaf(freq,char)
  local leaf = {}
  leaf.freq = freq
  leaf.char = char
  return leaf
end

function isLeaf(leaf)
  return leaf.char ~= nil
end

function makeNode(n_l1,n_l2)
  local node = {}
  node.freq = n_l1.freq + n_l2.freq
  node.left = n_l1
  node.right = n_l2
  return node
end

function getFreq(node)
  return node.freq
end

function make_table(txt)
  local tab = {}
  for chr in txt:gmatch(".") do
    tab[chr] = (tab[chr] or 0) + 1
  end
  return tab
end

function sort_huffman_table(tab)
  while #tab > 1 do
    sort(tab,getFreq)
    print(textutils.serialize(tab))
    local n1 = dequeue(tab)
    print(textutils.serialize(tab))
    local n2 = dequeue(tab)
    print(textutils.serialize(tab))
    local n3 = makeNode(n1,n2)
    insertOrder(tab,n3,getFreq)
  end
  return tab
end

function make_huffman_table(txt)
  local tab = make_table(txt)
  print(#tab)
  local nodeTable = {}
  for chr,freq in pairs(tab) do
    nodeTable[#nodeTable+1] = makeLeaf(freq,chr)
  end
  print(textutils.serialize(nodeTable))
  sort_huffman_table(nodeTable)
  return nodeTable
end

function decode_node(node,bits)
  local m_bit = dequeue(bits)
  local m_node = nil
  if m_bit == 0 then
    m_node = node.left
  else
    m_node = node.right
  end
  if isLeaf(m_node) then
    return m_node.char
  else
    return decode_node(m_node,bits)
  end
end

function decode(node_tree,bits)
  local txt = ""
  while #bits > 0 do
    txt = txt..decode_node(node_tree,bits)
  end
  return txt
end

api.decode = decode
api.makeTable = make_huffman_table

_G.huffman = api