Module:Sandbox/Artoria2e5/CacheUtils explained

-- Cached function decorators.-- lru-- lfu-- rr

local defaultsize = 128

-- An ordered dict implementation.local orderedDict =

function orderedDict.create(argDict, argOrder) if (#dict) ~= (#order) then return nil end -- grrr, this won't work if I want (amortized) O(1) removal -- TODO: Use a double-linked map of the form table> local dict = for k, v in pairs(argDict) do dict[k] = end local order = -- tableArray local function len(this) return #dict end local function newindex(this, k, v) dict[k] = table.insert(order, k) end local function leak return dict, order end local ret = setmetatable(ret,) return retend

-- These need to go into the metatable. They interfere with indexing.function orderedDict:has(od, k) local dict, order, nils = getmetatable(od).__mwint__leak return (dict[k] ~= nil) or (nils[k])end

function orderedDict:pop(od, k) local dict, order, nils = getmetatable(od).__mwint__leak if orderedDict:has(od, k) then v = dict[k] table.remove(dict, k) if v

nil then table.remove(nils, k) end else return nil, false endend

local function lru_cache(func, size) size = size or defaultsize memo = OrderedDict.create end

return