-- Structure --
-- Elements are stored in a linked list with max size.
-- If max size is reached, the last element will be removed.
-- Access (get/set) will move the element to the first position.
-- TTL will only expire an element, but will not remove it.

local initCache = function(in_max_size)
-- returns table { get, set, free, clean }
-- set(key[, value[, ttl]]) set/update a key to value -> returns value[, removed key, removed value]
--   - optional time to live
--   - no value will unset
-- get(key) -> returns value[, ttl] (nil -> if not exist or nil, value -> if expired)
-- free() -> number of slots available
-- clean() -> will run through the list and remove expired elements (expensive) -> returns available slots, available before

  local n_size = tonumber(in_max_size)
  local t_cache
  local free = function()
    return n_size
  end
  if not(n_size) or n_size <= 0 then
    n_size = 0
    local set = function(ix_key, ix_value, i_selfcall)
      if ix_key == t_cache then
        return i_selfcall, ix_value, i_selfcall
      end
      return ix_value, ix_key, ix_value
    end
    t_cache = {get = function() end, set = set, free = free, clean = function() return 0, 0 end}
    return t_cache
  end

  local KEY, VAL, TTL, PRV, NXT = 1, 2, 3, 4, 5
  local t_data = {}
  local t_first = nil
  local t_last = nil

  local getTx = function()
  -- returns number timestamp
    local n_year, n_day, n_hour, n_minute, n_second = string.match(os.date("!%Y%j%H%M%S"),
      "(%d%d%d%d)(%d%d%d)(%d%d)(%d%d)(%d%d)")
    -- ttl < 1 year; the year is just prefix, cache will reset on Jan 01 00:00:00
    return (n_year * 100000000) + ((((((n_day * 24) + n_hour) * 60) + n_minute) * 60) + n_second)
  end

  local popElement = function(it_value)
  -- returns nil
    local t_prev = it_value[PRV]
    if t_prev then
      t_prev[NXT] = it_value[NXT]
    else
      t_first = it_value[NXT]
    end
    if it_value[NXT] then
      it_value[NXT][PRV] = it_value[PRV]
    else
      t_last = it_value[PRV]
    end
    it_value[PRV] = nil
    it_value[NXT] = nil
  end

  local pushFirst = function(it_value)
  -- returns nil
    if t_first then
      it_value[NXT] = t_first
      t_first[PRV] = it_value
    end
    t_first = it_value
    if not(t_last) then
      t_last = it_value
    end
  end

  local set = function(ix_key, ix_value, in_ttl, i_selfcall)
  -- returns value
    if ix_key == t_cache then
      return t_cache.set(ix_value, in_ttl, i_selfcall)
    end
    if t_data[ix_key] then
      popElement(t_data[ix_key])
      n_size = n_size + 1
      t_data[ix_key] = nil
    end
    if ix_value == nil then
      return
    end
    -- initialize with 5 elements
    t_data[ix_key] = {ix_key, ix_value, in_ttl and getTx() + in_ttl, false, false}
    pushFirst(t_data[ix_key])
    if n_size == 0 then
      local t_value = t_last
      t_data[t_last[KEY]] = nil
      t_last = t_last[PRV]
      t_last[NXT][PRV] = nil
      t_last[NXT] = nil
      return ix_value, t_value[KEY], t_value[VAL]
    end
    n_size = n_size - 1
    return ix_value
  end

  local get = function(ix_key, i_selfcall)
  -- returns value, ttl or nil, expired value
    if ix_key == t_cache then
      return t_cache.get(i_selfcall)
    end
    local t_value = t_data[ix_key]
    if t_value then
      local n_ttl
      if t_value[TTL] then
        n_ttl = t_value[TTL] - getTx()
        if n_ttl <= 0 then
          set(ix_key)
          return nil, t_value[VAL]
        end
      end
      popElement(t_value)
      pushFirst(t_value)
      return t_value[VAL], n_ttl
    end
  end

  local clean = function()
    local n_size_before = n_size
    local t_element = t_first
    while t_element do
      local ix_key = t_element[TTL] and (t_element[TTL] - getTx()) <= 0 and t_element[KEY] or nil
      t_element = t_element[NXT]
      if ix_key then
        set(ix_key)
      end
    end
    return n_size, n_size_before
  end

  t_cache = {get = get, set = set, free = free, clean = clean}
  return t_cache
end


--{TEST
local c = initCache()
assert(c.free() == 0)
assert(c.set(1, 1) == 1)
assert(c:set(1, 1) == 1)
local c = initCache(-1)
assert(c.free() == 0)
local c = initCache(0)
local n_value, n_lkey, n_lvalue = c.set(1,1)
assert(n_value == 1)
assert(n_lkey == 1)
assert(n_lvalue == 1)
assert(c.get(1) == nil)
local c = initCache(1)
local n_value, n_lkey, n_lvalue = c.set(1,1)
assert(n_value == 1)
assert(n_lkey == nil)
assert(n_lvalue == nil)
assert(c.get(1) == 1)
c.set(2,2)
assert(c.get(1) == nil)
assert(c.get(2) == 2)
local c = initCache(3)
c.set(1,1)
assert(c.get(1) == 1)
c.set(2,2)
assert(c.get(2) == 2)
c.set(3,3)
assert(c.get(3) == 3)
-- self access
local c = initCache(3)
c:set(1,1)
assert(c:get(1) == 1)
c:set(2,2)
assert(c:get(2) == 2)
c:set(3,3)
assert(c:get(3) == 3)
-- access -> first position
assert(c.get(1) == 1)
-- last (2) will be dropped
local n_value, n_lkey, n_lvalue = c.set(4,4)
assert(n_value == 4)
assert(n_lkey == 2)
assert(n_lvalue == 2)
assert(c.get(4) == 4)
assert(c.get(1) == 1)
assert(c.get(2) == nil)
-- check ttl
c.set(1,1,2)
c.set(2,2)
c.set(3,3,1)
local _, t = c.get(1)
assert(t == 2 or t == 1)
local _, t = c.get(2)
assert(t == nil)
assert(c.get(1) == 1)
if not(_BUILD_VERBOSE == false) then
  print("sleep 2 to test ttl")
  os.execute("sleep 2")
  local v, ev = c.get(1)
  assert(v == nil)
  assert(ev == 1)
  assert(c.free() == 1)
  assert(c.clean() == 2) -- (2, 1)
else
  assert(c.free() == 0)
  assert(c.clean() == 0) -- (0, 0)
end

