Module:User:QFQ/ordered-table

-- see also: 
local ordered_table = {}

local _v = {} -- key: k, value: v
local _k = {} -- key: i, value: k
local _i = {} -- key: k, value: i

function ordered_table.insert(t, k, v)
	if v == nil then
		ordered_table.remove(t, k)
	else
		if t == nil then
			t + 1] = k
			t = #t
		end
		t = v 
	end
end

function ordered_table.findk(t, k)
	return t
end

local function find(t, v)
	for i, val in ipairs(t) do
		if v == val then
			return i
		end
	end
end

-- O(n)
function ordered_table.remove(t, k)
	local tv = t
	local ti = t
	local v = tv
	local i = ti
	if i then
		local tk = t
		table.remove(tk, i)
		for j = i, #tk do
			ti] = j
		end
		ti = nil
		tv = nil
	end 
	return v
end

function ordered_table.pairs(t)
	local i = 0
	return function()
		i = i + 1
		local k = t
		if k ~= nil then
			return k, t
		end
	end
end

function ordered_table.index(t, ik)
	return type(ik) == 'number' and t or t
end

ordered_table.__newindex = ordered_table.insert
ordered_table.__len = function(t) return #t end
ordered_table.__pairs = ordered_table.pairs
ordered_table.__index = ordered_table.index

function ordered_table:new(init)
	init = init or {}
	local key_table = {}
	local value_table = {}
	local index_table = {}
	local t = { =key_table, =value_table, =index_table }
	local n = #init
	if n % 2 ~= 0 then
		error("key: " .. tostring(init).. " is missing value", 2)
	end
	for i = 1, n/2 do
		local k = init
		local v = init
		if value_table ~= nil then
			error("duplicated key: " .. tostring(k), 2)
		end
		key_table = k
		index_table = #key_table
		value_table = v
	end
	return setmetatable(t, self)
end

return setmetatable(ordered_table, { __call=ordered_table.new })