--
-- table.lua
-- Additions to Lua's built-in table functions.
-- Copyright (c) 2002-2013 Jason Perkins and the Premake project
--
local tbinsert = table.insert
local ipairs = ipairs
local pairs = pairs
local type = type
local error = error
--local setmetatable = setmetatable
local getmetatable = getmetatable


---
--- Make a copy of the indexed elements of the table.
function table.arraycopy(object)
	if not object then return nil end
	local result = {}
	for i, value in ipairs(object) do
		result[i] = value
	end
	return result
end

--- array
--- remove elm only the values satisfying the given predicate.
--- Swap to last, then remove last

--- local object = {{a=1},{a=2},{a=3},{a=4}}
--- table.fastremove(object, function (o)
---     return o.a == 2
--- end )

--- print_r(object) {{a=1},{a=4},{a=3}}

function table.fastremove(object, fn)
	local n
	for i, value in ipairs(object) do
		if fn(value) then
			n = i
			break
		end
	end

	if n then
		local v
		if #object == 1 then
			v = table.remove(object)
		else
			if n == #object then
				v = table.remove(object, n)
			else
				v = object[n]
				object[n] = table.remove(object)
			end
		end
		return true, v
	end

	return false
end

---
--- Returns true if the table contains the specified value.
function table.contains(t, value)
	for _, v in pairs(t) do
		if (v == value) then
			return true
		end
	end
	return false
end

---
--- Make a shallow copy of a table
function table.shallowcopy(object)
	local copy = {}
	for k, v in pairs(object) do
		copy[k] = v
	end
	return copy
end

---
--- Make a complete copy of a table, including any child tables it contains.
function table.deepcopy(obj)
	-- keep track of already seen objects to avoid loops
	local seen = {}

	local function copy(object)
		if type(object) ~= "table" then
			return object
		elseif seen[object] then
			return seen[object]
		end

		local clone = {}
		seen[object] = clone
		for key, value in pairs(object) do
			clone[key] = copy(value)
		end

		-- setmetatable(clone, getmetatable(object))
		return clone
	end

	return copy(obj)
end

---
--- Enumerates an array of objects and returns a new table containing
--- only the value of one particular field.
function table.extract(arr, fname)
	local result = {}
	for _, v in ipairs(arr) do
		tbinsert(result, v[fname])
	end
	return result
end

---
--- Enumerates an array of objects and returns a new table containing
--- only the values satisfying the given predicate.
function table.filter(arr, fn)
	local result = {}
	table.foreachi(
		arr,
		function(val)
			if fn(val) then
				tbinsert(result, val)
			end
		end
	)
	return result
end

---
--- Flattens a hierarchy of tables into a single array containing all
--- of the values.
function table.flatten(arr_)
	local result = {}

	local function flatten(arr)
		local n = #arr
		for i = 1, n do
			local v = arr[i]
			if type(v) == "table" then
				flatten(v)
			elseif v then
				tbinsert(result, v)
			end
		end
	end

	flatten(arr_)
	return result
end

---
--- Walk the elements of an array and call the specified function
--- for each non-nil element. This works around a "feature" of the
--- ipairs() function that stops iteration at the first nil.
---
---@param arr table The array to iterate.
---@param func function The function to call. The value (not the index) will be passed
--- as the only argument.
function table.foreachi(arr, func)
	if arr then
		local n = #arr
		for i = 1, n do
			local v = arr[i]
			if v then
				func(v, i)
			end
		end
	end
end

---
--- Merge two lists into an array of objects, containing pairs
--- of values, one from each list.
function table.fold(list1, list2)
	local result = {}
	for _, item1 in ipairs(list1 or {}) do
		if list2 and #list2 > 0 then
			for _, item2 in ipairs(list2) do
				tbinsert(result, {item1, item2})
			end
		else
			tbinsert(result, {item1})
		end
	end
	return result
end

---
--- Merges an array of items into a string.
function table.implode(arr, before, after, between)
	local result = ""
	for _, v in ipairs(arr) do
		if (result ~= "" and between) then
			result = result .. between
		end
		result = result .. before .. v .. after
	end
	return result
end

---
--- Looks for an object within an array. Returns its index if found,
--- or nil if the object could not be found.
function table.indexof(tbl, obj)
	for k, v in ipairs(tbl) do
		if v == obj then
			return k
		end
	end
end

---
--- Looks for an object within a table. Returns the key if found,
--- or nil if the object could not be found.
function table.findKeyByValue(tbl, obj)
	for k, v in pairs(tbl) do
		if v == obj then
			return k
		end
	end
end

---
--- Insert a new value into a table in the position after the specified
--- existing value. If the specified value does not exist in the table,
--- the new value is appended to the end of the table.
---
---@param tbl table
---    The table in which to insert.
---@param after any
---   The existing value to insert after.
---@param value any
---   The new value to insert.
function table.insertafter(tbl, after, value)
	local i = table.indexof(tbl, after)
	if i then
		tbinsert(tbl, i + 1, value)
	else
		tbinsert(tbl, value)
	end
end

---
--- Inserts a value or array of values into a table. If the value is
--- itself a table, its contents are enumerated and added instead. So
--- these inputs give these outputs:
---
---   "x" -> { "x" }
---   { "x", "y" } -> { "x", "y" }
---   { "x", { "y" }} -> { "x", "y" }
---
function table.insertflat(tbl, values)
	if values == nil then
		return
	elseif type(values) == "table" then
		for _, value in ipairs(values) do
			table.insertflat(tbl, value)
		end
	else
		tbinsert(tbl, values)
	end
	return tbl
end

---
--- Inserts a value into a table as both a list item and a key-value pair.
--- Useful for set operations. Returns false if the value already exists, true otherwise.
function table.insertkeyed(tbl, pos, value)
	if value == nil then
		value = pos
		pos = #tbl + 1
	end

	if tbl[value] ~= nil then
		return false
	end

	tbinsert(tbl, pos, value)
	tbl[value] = value
	return true
end

---
--- Inserts a value into a table in sorted order. Assumes that the
--- table is already sorted according to the sort function. If fn is
--- nil, the table is sorted according to the < operator.
function table.insertsorted(tbl, value, fn)
	if value == nil then
		return
	else
		fn = fn or function(a, b)
				return a < b
			end

		local minindex = 1
		local maxindex = #tbl + 1
		while minindex < maxindex do
			local index = minindex + ((maxindex - minindex) >> 1)
			local test = tbl[index]
			if fn(value, test) then
				maxindex = index
			else
				minindex = index + 1
				if not fn(test, value) then
					break
				end
			end
		end

		tbinsert(tbl, minindex, value)
	end

	return tbl
end

---
--- Returns true if the table is empty, and contains no indexed or keyed values.
---
function table.isempty(t)
	return next(t) == nil
end

---
--- Adds the values from one array to the end of another and
--- returns the result.
---
function table.join(...)
	local result = {}
	local arg = {...}
	for _, t in ipairs(arg) do
		if type(t) == "table" then
			for _, v in ipairs(t) do
				tbinsert(result, v)
			end
		else
			tbinsert(result, t)
		end
	end
	return result
end

---
--- Return a list of all keys used in a table.
---
function table.keys(tbl)
	local keys = {}
	for k, _ in pairs(tbl) do
		tbinsert(keys, k)
	end
	return keys
end

---
--- Adds the key-value associations from one table into another
--- and returns the resulting merged table.
---
function table.merge(...)
	local result = {}
	local arg = {...}
	for _, t in ipairs(arg) do
		if type(t) == "table" then
			for k, v in pairs(t) do
				if type(result[k]) == "table" and type(v) == "table" then
					result[k] = table.merge(result[k], v)
				else
					result[k] = v
				end
			end
		else
			error("invalid value")
		end
	end

	return result
end

---
--- Replace all instances of `value` with `replacement` in an array. Array
--- elements are modified in place.
---
---@param value any
---   The value to be replaced.
---@param replacement any
---   The new value.
---
function table.replace(self, value, replacement)
	for i = 1, #self do
		if self[i] == value then
			self[i] = replacement
		end
	end
end

---
--- Translates the values contained in array, using the specified
--- translation table, and returns the results in a new array.
---
function table.translate(arr, translation)
	if not translation then
		return {}
	end

	local result = {}
	for i = 1, #arr do
		local tvalue
		if type(translation) == "function" then
			tvalue = translation(arr[i])
		else
			tvalue = translation[arr[i]]
		end
		if (tvalue) then
			tbinsert(result, tvalue)
		end
	end
	return result
end

---
--- Dumps a table to a string
---
function table.tostring(tab, recurse, indent)
	local res = ""

	if not indent then
		indent = 0
	end

	local format_value = function(k, v, i)
		local formatting = string.rep("\t", i)

		if k then
			if type(k) == "table" then
				k = "[table]"
			end
			formatting = formatting .. k .. ": "
		end

		if not v then
			return formatting .. "(nil)"
		elseif type(v) == "table" then
			if recurse and recurse > 0 then
				return formatting .. "\n" .. table.tostring(v, recurse - 1, i + 1)
			else
				return formatting .. "<table>"
			end
		elseif type(v) == "function" then
			return formatting .. tostring(v)
		elseif type(v) == "userdata" then
			return formatting .. "<userdata>"
		elseif type(v) == "boolean" then
			if v then
				return formatting .. "true"
			else
				return formatting .. "false"
			end
		else
			return formatting .. v
		end
	end

	if type(tab) == "table" then
		local first = true

		-- add the meta table.
		local mt = getmetatable(tab)
		if mt then
			res = res .. format_value("__mt", mt, indent)
			first = false
		end

		-- add all values.
		for k, v in pairs(tab) do
			if not first then
				res = res .. "\n"
			end

			res = res .. format_value(k, v, indent)
			first = false
		end
	else
		res = res .. format_value(nil, tab, indent)
	end

	return res
end

---
--- Returns a copy of a list with all duplicate elements removed.
---
function table.unique(tab)
	local elems = {}
	local result = {}
	table.foreachi(
		tab,
		function(elem)
			if not elems[elem] then
				tbinsert(result, elem)
				elems[elem] = true
			end
		end
	)

	return result
end

---
--- Filters a table for empty entries. primarly useful for lists of string.
---
function table.filterempty(dirs)
	return table.translate(
		dirs,
		function(val)
			if val and #val > 0 then
				return val
			else
				return nil
			end
		end
	)
end

---
--- Compares two tables.
---
function table.equals(a, b)
	for k, v in pairs(a) do
		if b[k] ~= v then
			return false
		end
	end
	for k, v in pairs(b) do
		if a[k] ~= v then
			return false
		end
	end
	return true
end

---
--- Enumerate a table sorted by its keys.
---
function table.spairs(t)
	-- collect the keys
	local keys = {}
	for k in pairs(t) do
		tbinsert(keys, k)
	end
	table.sort(keys)

	-- return the iterator function
	local i = 0
	return function()
		i = i + 1
		if keys[i] then
			return keys[i], t[keys[i]]
		end
	end
end

---
--- Intersect two arrays and return a new array
---
function table.intersect(a, b)
	local result = {}
	for _, v in ipairs(b) do
		if table.indexof(a, v) then
			tbinsert(result, v)
		end
	end
	return result
end

---
--- The difference of A and B is the set containing those elements that are in A but not in B
---
function table.difference(a, b)
	local result = {}
	for _, v in ipairs(a) do
		if not table.indexof(b, v) then
			tbinsert(result, v)
		end
	end
	return result
end

function table.count(t)
	local n = 0
	for _ in pairs(t) do
		n = n + 1
	end
	return n
end

---t must ordered
function table.search_bound(t, value, comp)
	local count = #t
	if count == 0 then
		return 1
	end
	local pos, step, first
	first = 1
	while count > 0 do
		pos = first
		step = count//2
		pos = pos + step
		if comp(t[pos], value) then
			pos = pos + 1
			first = pos
			count = count - (step+1)
		else
			count = step
		end
	end
	return first
end

function table.shuffle(t)
	local n = #t
	if n <= 0 then
		return t
	end
    local tab = {}
    local index = 1
    while n > 0 do
        local tmp = math.random(1, n)
        tab[index] = t[tmp]
        table.remove(t, tmp)
        index = index + 1
		n = #t
    end
    return tab
end