BWT

local bwt = {}

local function rollOver(num,limit)
    return num%limit
end

local function rollOverString(str,startPos)
    return str:sub(startPos,#str)..str:sub(1,startPos-1)
end

local function copy(t)
    local tt = {}
    for k,v in pairs(t) do tt[k] = v end
    return tt
end

local function lexSort(tbl)
    local function sorter(a,b)
        return string.lower(a) < string.lower(b)
    end
    table.sort(tbl,sorter)
    return tbl
end

local function getRotations(str)
    local limit = #str
    local rot = {}
    for i = 1,#str do
        rot[#rot+1] = rollOverString(str,i)
    end
    return rot
end

local function tSub(tbl,f,l)
    local sub = {}
    for k,v in pairs(tbl) do
        sub[k] = v:sub(f,l)
    end
    return sub
end

local function addToTable(tbl,add)
    local t = {}
    for k,v in pairs(add) do
        t[k] = v..tbl[k]
    end
    return t
end

local function split(str)
    local tbl = {}
    for c in str:gmatch(".") do
        tbl[#tbl+1] = c
    end
    return tbl
end

function bwt.searchEndCharacter(str,offset)
    local os = offset and offset or 0
    local possibleChars = "abcdefghijklmnopqrstuvwxyz1234567890?=)(/%\"\\}][{-.,;:_#+~<>|@*"
    for i = 1,#possibleChars do
        if(not string.find(str,possibleChars:sub(i,i))) then
            return possibleChars:sub(i+os,i+os)
        end
    end
    return nil
end

function bwt.BWT(str,endc)
    local ed = endc and endc or bwt.searchEndCharacter(str)
    if(not str:find(ed)) then str = str..bwt.searchEndCharacter(str) end
    local rotations = getRotations(str)
    local sorted = lexSort(rotations)
    local sub = tSub(sorted,#str,#str)

    return table.concat(sub,""),ed
end



function bwt.reverseBWT(str,ed)
    local splitted = split(str)
    local cur = split(str)
    cur = lexSort(cur)
    for i = 1,#str do
        cur = addToTable(cur,splitted)
        cur = lexSort(cur)
    end
    for k,v in pairs(cur) do
        if(v:sub(#v,#v) == ed) then
            return v:sub(2,#v)
        end
    end
    error("Something went wrong!")
end



_G["bwt"] = bwt