move to front transform


See On Github

Data

Contributor

Generic placeholder thumbnail

by Yonaba

in lua

Source Code

-- Move-To-Front Transform implementation
-- See : http://en.wikipedia.org/wiki/Move-to-front_transform

-- Finds and returns the index of a value in a table
local function table_find(t, v)
  for k,_v in ipairs(t) do
    if _v == v then return k end
  end
end

-- Moves the value at index to a new index
local function table_move(t, i, newi)
  local v = t[i]
  table.remove(t, i)
  table.insert(t, newi, v)
end

-- Creates a ASCII based dictionnary
local function createDict()
  local mtf = {}
  for i=1,255 do mtf[i]=string.char(i) end
  return mtf
end

-- Encodes an string
-- @str    : a string to be encoded
-- @return : the mtf transform as a string of numbers
--           separated with dots.
local function mtf_encode(str)
  local dict = createDict()
  local encoded_str = ''
  for char in str:gmatch('.') do
    local index = table_find(dict, char)
    assert(index, ('Unknown char %s'):format(char))
    encoded_str = encoded_str .. index ..'.'
    table_move(dict, index, 1)
  end
  return (encoded_str:gsub('%.$',''))
end

-- Decodes an mtf transform
-- @str    : an mtf transform string to be decoded
-- @return : the decoded string
local function mtf_decode(str)
  local dict = createDict()
  local decoded_str = ''
  for value in str:gmatch('%.*(%d+)%.*') do
    local index = tonumber(value)
    assert(index and dict[index], 'Error decoding string')
    decoded_str = decoded_str .. dict[index]
    table_move(dict, index, 1)
  end
  return decoded_str
end

return {
  encode = mtf_encode,
  decode = mtf_decode,
}
-- Tests for mtf.lua
local mtf = require 'mtf'

local total, pass = 0, 0

local function dec(str, len)
  return #str < len
     and str .. (('.'):rep(len-#str))
      or str:sub(1,len)
end

local function run(message, f)
  total = total + 1
  local ok, err = pcall(f)
  if ok then pass = pass + 1 end
  local status = ok and 'PASSED' or 'FAILED'
  print(('%02d. %68s: %s'):format(total, dec(message,68), status))
end

-- Checks if t1 and t2 arrays are the same
local function same(t1, t2)
  if #t1 ~= #t2 then return false end
  for r, row in ipairs(t1) do
    for v, value in ipairs(row) do
      if t2[r][v] ~= value then return false end
    end
  end
  return true
end

run('Encoding string tests', function()
  assert(mtf.encode('banana') == '98.98.110.2.2.2')
  assert(mtf.encode('1578rr') == '49.53.55.56.114.1')
  assert(mtf.encode('')       == '')
  assert(mtf.encode('     ')  == '32.1.1.1.1')
  assert(mtf.encode('mtf')    == '109.116.104')
  assert(mtf.encode('M.T.F.') == '77.47.84.2.72.2')
end)

run('Decoding string tests', function()
  assert(mtf.decode(mtf.encode('banana')) == 'banana')
  assert(mtf.decode(mtf.encode('1578rr')) == '1578rr')
  assert(mtf.decode(mtf.encode('     '))  == '     ')
  assert(mtf.decode(mtf.encode(''))       == '')
  assert(mtf.decode(mtf.encode('mtf'))    == 'mtf')
  assert(mtf.decode(mtf.encode('M.T.F.'))    == 'M.T.F.')
end)

print(('-'):rep(80))
print(('Total : %02d: Pass: %02d - Failed : %02d - Success: %.2f %%')
  :format(total, pass, total-pass, (pass*100/total)))