huffman

--BASE FUNCTIONS
local huffman = _G.huffman or {}

function dequeue(buff)
    local val = buff[1]
    if #buff <= 1 then
        buff[1] = nil
        return val
    else
        for i=2,#buff do
            buff[i-1]  = buff[i]
            buff[i] = nil
        end
    end
    return val
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
  print("Node made")
  return node
end

function getFreq(node)
  return node.freq
end

function makeCharBitTable_node(node,tbl,base)
    if isLeaf(node) then
        tbl[node.char] = base
        return
    end
    local m_base1 = {}
    local m_base2 = {}
    for i=1,#base do
        m_base1[i] = base[i]
        m_base2[i] = base[i]
    end
    m_base1[#base+1] = 0
    m_base2[#base+1] = 1

    makeCharBitTable_node(node.left,tbl,m_base1)

    makeCharBitTable_node(node.right,tbl,m_base2)
end

function makeCharBitTable(node_tree)
    print(node_tree)
    local tbl = {}
    makeCharBitTable_node(node_tree.left,tbl,{0})
    makeCharBitTable_node(node_tree.right,tbl,{1})
    return tbl
end

huffman.checkNodeTable = makeCharBitTable



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("node1: "..textutils.serialize(n1))
    local n2 = dequeue(tab)
    --print("node2: "..textutils.serialize(n2))
    --print(#tab)
    local n3 = makeNode(n1,n2)
    --print("Node3: "..textutils.serialise(n3))
    --print(textutils.serialise(tab))
    insertOrder(n3,tab,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[1]
end

function decode_node(node_base,bits)
  --print("NodeBase: "..textutils.serialize(node_base or {}))
  local m_bit = dequeue(bits)
  --print("Bit: "..m_bit)
  local m_node = nil
  if m_bit == 0 then
    m_node = node_base.left
    --print("Node: "..textutils.serialize(m_node))
  else
    m_node = node_base.right
  end
  if isLeaf(m_node) then
    --print("IS a leaf")
    return m_node.char
  else
    return decode_node(m_node,bits)
  end
end

function decode(node_tree,bits_str,has_table)
  local bits_appended = {}
  for chr in bits_str:gmatch(".") do
      local chr_bits = bit.table(string.byte(chr))
      for i=1,8 do
          bits_appended[#bits_appended+1] = chr_bits[i]
      end
  end

  print("DEPEND")
  local bits = huffman.depend(bits_appended)
  print("DEPENDED")
  if has_table then
      node_tree = huffman.unserializeTree(bits)
  end

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

function encode(node_tree,txt,addTree)
    local chartbl = {}
    local nodeCharTable = makeCharBitTable(node_tree,chartbl)
    for i,v in pairs(nodeCharTable) do
        write(i)
        print(unpack(v))
    end
    for chr in string.gmatch(txt,".") do
        chartbl[#chartbl+1] = nodeCharTable[chr]
    end
    local end_table = {}

    local function m_unpack(tbl)
        for i=1,#tbl do
            end_table[#end_table+1] = tbl[i]
        end
    end
    if addTree == true then
        huffman.serializeTree(node_tree,end_table)
    end
    for i=1,#chartbl do
        m_unpack(chartbl[i])
    end

    local tbl = huffman.append(end_table)

    local enc_str = ""

    for i=1,(#tbl/8) do
        local byte_bits = {}
        for i2=1,8 do
            byte_bits[i2] = tbl[(8*(i-1))+i2]
        end
        enc_str = enc_str..string.char(bit.untable(byte_bits))
    end

    print("Returned")
    return tbl,enc_str
end


huffman.decode = decode
huffman.makeTable = make_huffman_table
huffman.encode = encode

--api.makeTable("hi")
local tab = {1,2}
dequeue(tab)
--

local m_text = read()
local hutab = api.makeTable(m_text)

local tbl,str = encode(hutab,m_text)
print(str)
print(tbl)
print(decode(hutab,str))
read()


--FUNCTIONS For bit Resizing

function huffman.append(bit_tbl)
    local needed = 8 - (#bit_tbl%8)
    if needed == 8 then
        needed = 0
    else
        for i=1,needed do
            bit_tbl[#bit_tbl+1] = 0
        end
    end
    local num_tbl = bit.table(needed)
    for i=1,#num_tbl do
        bit_tbl[#bit_tbl+1] = num_tbl[i]
    end
    return bit_tbl
end

function huffman.depend(bit_tbl)
    print("Bit table"..tostring(bit_tbl))
    local needed_bits = {}
    for i=0,7 do
        needed_bits[8-i] = bit_tbl[#bit_tbl]
        bit_tbl[#bit_tbl] = nil
    end
    local needed = bit.untable(needed_bits)
    if needed ~= 0 then
        for i=1,needed do
            bit_tbl[#bit_tbl] = nil
        end
    end
    return bit_tbl
end
function bitPrint(bitTbl)
    for i=1,#bitTbl do
        write(bitTbl[i].."\t")
    end
    print()
end

huffman.printBit = bitPrint



--FUNCTIONS For bit manipulation
function bit_table(num)
  local tab = {}
  for i=1,8 do
    if (num % 2) == 1 then
      tab[9-i] = 1
      num = num - 1
    else
      tab[9-i] = 0
    end
    num = num / 2
  end
  return tab
end

function bit_untable(tab)
    local num = 0
    for i=1,8 do
        num = num * 2
        num = num + tab[i]
    end
    return num
end


_G.bit.table = bit_table
_G.bit.untable = bit_untable

--FUNCTIONS For tree serialization
function add(buff,val)
    buff[#buff+1] = val
end

function addLeaf(leaf,buff)
    local chr = leaf.char
    add(buff,1)
    for i,v in pairs(bit.table(string.byte(chr))) do
        add(buff,v)
    end
end


function addNode(node,buff)
    add(buff,0)
    if isLeaf(node.left) then
        addLeaf(node.left,buff)
    else
        addNode(node.left,buff)
    end
    if isLeaf(node.right) then
        addLeaf(node.right,buff)
    else
        addNode(node.right,buff)
    end
end

function huffman.serializeTree(tree,buff)
    buff = buff or {}
    addNode(tree,buff)
    return buff
end


function unserializeLeaf(buff)
    local leaf = {}
    local chr_bits = {}
    for i=1,8 do
        chr_bits[i] = dequeue(buff)
    end
    leaf.char = string.char(bit.untable(chr_bits))
    return leaf
end

function unserializeNode(buff)
    local node = {}
    local n_bit = dequeue(buff)
    if n_bit == 1 then
        node.left = unserializeLeaf(buff)
    else
        node.left = unserializeNode(buff)
    end
    n_bit = dequeue(buff)
    if n_bit == 1 then
        node.right = unserializeLeaf(buff)
    else
        node.right = unserializeNode(buff)
    end
    return node
end

function huffman.unserializeTree(buff)
    dequeue(buff)
    return unserializeNode(buff)
end

_G.huffman = huffman