Editing Module:Sandbox/Artoria2e5/CacheUtils

-- 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<key:T, node<val:T, prev:node, next:node>>
	local dict = {}
	for k, v in pairs(argDict) do
		dict[k] = { ['v'] = v }
	end
	local order = {} -- tableArray
	
	local function len(this) 
		return #dict
	end
	
	local function newindex(this, k, v)
		dict[k] = { ['v'] = v }
		table.insert(order, k)
	end
	
	local function leak()
		return dict, order
	end
	
	local ret = {}
	setmetatable(ret, {
		["__len"] = len,
		["__newindex"] = __newindex,
		-- FIXME
		["__index"] = dict,
		["__mwint__leak"] = leak,
	})
	return ret
end

-- 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
	end
end


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

return {
	["lru"] = lru_cache,
	["_"] =  {
		["orderedDict"] = orderedDict
	}
}