--[[----------------------------------------------------------------------------

KSTableUtils.lua

--------------------------------------------------------------------------------

ADOBE CONFIDENTIAL
------------------
Copyright 2010 Adobe Systems Incorporated
All Rights Reserved.

NOTICE: All information contained herein is, and remain the property of
Adobe Systems Incorporated and its suppliers, if any. The intellectual and
technical concepts contained herein are proprietary to Adobe Systems
Incorporated and its suppliers and may be covered by U.S. and Foreign
Patents, patents in process, and are protected by trade secret or copyright
law.  Dissemination of this information or reproduction of this material is
strictly forbidden unless prior written permission is obtained from
Adobe Systems Incorporated.

------------------------------------------------------------------------------]]

--[[

KSTableUtils:

	function KSTableUtils.makeWithMode( mode )
		-- mode is a weak table mode string (nil, "", "k", "v", or "kv")
		-- result is a table with the appropriate metatable (or no metatable
		-- if mode is nil or the empty string)
		
	function KSTableUtils.makeFullyWeak()
		-- Optimizes for KSTableUtils.makeWithMode( "kv" )
		
	function KSTableUtils.make()
		-- Makes an empty table
		
	function KSTableUtils.makeWithMetatable( mt )
		-- Makes a table with the given metatable
		
	function KSTableUtils.makeFactoryWithMetatable( mt )
		-- Makes a function which makes tables with the given metatable
		
	function KSTableUtils.makeWrapWithMetatable( mt )
		-- Makes a function that wraps its parameter with the given metatable
		
	function KSTableUtils.makeReadOnly( t )
		-- Returns a table that provides a read-only view of t if t is a table.
		-- Otherwise, this just return t.
	
	function KSTableUtils.readOnlyPairs( t )
		-- A version of pairs that is savvy about read-only tables.
		
	function KSTableUtils.mapArrayToSet( [ fn, ] array )
		-- Runs the array through fn (if provided) and builds a set of the
		-- results. Optimized for use with field extractors (see KSFunctionUtils).
		
	function KSTableUtils.merge( base, a, b [ , getMergeAlgorithm ] )
		-- Perform a 3-way recursive table merge from b going to a and b.
		-- Returns the merged result if it succeeds or throws an error if
		-- it fails.
		
		-- The naive merge algorithm is based on a dictionary variation
		-- on set merges where the result of a set merge is calculated
		-- as ( a - base ) + ( b - base ) + ( a * b ) -- i.e., those
		-- elements added in either a or b unioned with the elements that
		-- were in both. In the dictionary case, where we deal with more
		-- than just membership, we treat the keys as the set elements,
		-- but we need to recursively process the values. We treat a
		-- value of nil -- i.e., missing entries -- as the empty table
		-- when merging with the additional behavior that we will map
		-- this promotion away if the resulting merged table is nil.
		-- Furthermore, we allow any base value to be promoted to a pair
		-- of tables and allow for further recursion. We also allow
		-- a base value and a matching successor on one side to lead to
		-- any atomic value on the other side.
		
		-- As a further wrinkle, we also allow the specification of
		-- alternative merge algorithms that may handle the merge
		-- process in other ways. For example, an atomic merge will
		-- insist on equality rather than recursing. We do this via the
		-- optional fourth parameter which can specify a function to determine
		-- the merge algorithm to use based on the path (as an array) and
		-- the target tables. (Signature: path, base, a, b)
		-- It should return one of the following values:
		--		nil, '', or 'dictionary': A standard dictionary merge
		--		'atomic': Treat values atomically using deep equals
		--		function( forPath, base, a, b, mergeForPath ): A custom merge function
				
		-- Finally, this routine guarantees that the result that it
		-- produces will not share any mutable values with its source
		-- material -- i.e., it will perform a full clone.
	
	function KSTableUtils.invert( t )
		-- inverts the k,v pair relationship in the map. This assumes the map is 1:1. If not, an error is thrown.
		
	function KSTableUtils.filter( fn, t )
		-- Applies the function( k, v ) which returns either true or false to each k,v pair in the table and 
		-- returns a new table containing only those k,v pairs for which the function returned true
	
	function KSTableUtils.derefOpt( t, ... )
		-- Dereference a potentially long chain of tables in which any
		-- member might be nil. Use this to avoid the pattern of

			-- local foo = t and t.x and t.x.y and t.x.y.z (etc.)
	
		-- The above could now be written as:
			
			-- local foo = KSTableUtils.derefOpt( t, 'x', 'y', 'z' )
			
	function KSTableUtils.setNested( t, value, ... )
		-- Dereference a nested table given the path in ... where any intermediate key
		-- might not be present. If a component in the path can not be found, it is created. 
		-- The last element is set to value.

	function KSTableUtils.applyOpt( t, valueOrFn, ... )
		-- Dereference a nested table given the path in ... where any intermediate key
		-- might not be present. If the full path can be resolved, replace the value 
		-- of the last element with valueOrFn. If valueOrFn is a function, it is evaluated with 
		-- the current value as the sole parameter and that result replaces the existing value. 
		-- Wildcards in the path are possible with keyMatch or similar functions.
	
	function KSTableUtils.applyKeyOpt( t, fn, ... )
		-- Dereference a nested table given the path in ..., where any intermediate key might not be present.
		-- If the full path can be resolved, transform the last key(s) using fn.


	function KSTableUtils.extractKeys( t )
		-- return the keys of a table as an array
		
	function KSTableUtils.extractValues( t )
		-- return the toplevel values of a table as an array
	
	function KSTableUtils.slice( a, first, end, step )
		-- Create a slice of a, from first to end with stepsize step. 
		-- Negative end values are allowed and are treated as offsets from the end to the left.
		-- Default values are: first: 1, end: #a and step: 1

	function KSTableUtils.flatten( t )
		-- Flattens a hierarchy of tables into a single array containing all
		-- of the values.
		
	function KSTableUtils.trimmedMean( percentage, values )
		-- Given a table full of numbers, removes a small percentage of the largest
		-- and smallest values before calculating the mean.
		
	function KSTableUtils.deepEquals( a, b, depthLimit )
		-- Given two values, compare if they are identical. If a and b are both tables, we
		-- compare them til depthLimit. If a and b are the same table, we always return true
		-- regardless the depthLimit constraint
		
	function KSTableUtils.deepCopy( v )
		-- Return a copy of input value v

	function KSTableUtils.findInTable( t, f )
		-- Given a table and a function of the form f(key, value), 
		-- return the _first_ key, value pair for which f(key, value) is truthy
		-- returns nil, nil in the case where f(key, value) is falsy in all cases
]]

--------------------------------------------------------------------------------

local assert = assert
local string = string
local string_format = string.format
local tostring = tostring
local setmetatable = setmetatable
local pairs = pairs
local ipairs = ipairs
local type = type

local KSTableUtilsImp = require 'KSTableUtilsImp'
local KSFunctionUtils -- = require 'KSFunctionUtils' (lazy loaded)

local WFArguments = require 'WFArguments'
local WFArguments_check = assert( WFArguments.check )

--------------------------------------------------------------------------------

local KSTableUtils = KSTableUtilsImp

--------------------------------------------------------------------------------

local weakMetas = { }

for _, mode in ipairs( { 'k', 'v', 'kv' } ) do
	weakMetas[ mode ] = {
		__mode = mode,
		__metatable = string_format( "< Weak Metatable: %s >", mode )
	}
end

--------------------------------------------------------------------------------

function KSTableUtils.makeWithMode( mode )

	local result = { }

	if mode == nil or mode == "" then
		return result
	end
	
	local mt = weakMetas[ mode ]
	if not mt then
		error( string_format( "Invalid mode for weak metas: %s", mode ), 2 )
	end
	
	return setmetatable( result, mt )

end

--------------------------------------------------------------------------------

local function makeFullyWeak()

	return setmetatable( { }, weakMetas[ 'kv' ] )

end

--------------------------------------------------------------------------------

KSTableUtils.makeFullyWeak = makeFullyWeak

--------------------------------------------------------------------------------

function KSTableUtils.make()

	return { }

end

--------------------------------------------------------------------------------

function KSTableUtils.makeWithMetatable( mt )

	local result = { }
	
	if mt ~= nil then
		assert( type( mt ) == 'table', "metatable should be a table" )
		setmetatable( result, mt )
	end

	return result

end

--------------------------------------------------------------------------------

function KSTableUtils.makeFactoryWithMetatable( mt )

	if mt == nil then
		return KSTableUtils.make
	end

	assert( type( mt ) == 'table', "metatable should be a table" )

	return function()
		return setmetatable( { }, mt )
	end

end

--------------------------------------------------------------------------------

function KSTableUtils.makeWrapWithMetatable( mt )

	assert( type( mt ) == 'table', "metatable should be a table" )

	return function( t )
		return setmetatable( t, mt )
	end

end

--------------------------------------------------------------------------------

-- Signal an error on attempts to write to a read-only field

local function readOnlyError( t, k, v )
	local err = string_format( "Attempt to write to read-only field '%s'", tostring( k ) )
	error( err )
end

--------------------------------------------------------------------------------

-- A map from the read-only wrapper back to the original. Needed for iteration. (Ugh.)

local readOnlyBase = KSTableUtils.makeFullyWeak()

-- A map from tables to their pre-existing read-only counterparts (to avoid repeated
-- wrapping). Wraps new values appropriately as they come in.

local readOnlyVersion = setmetatable( { }, {
	__mode = 'kv',
	__index = function( t, k )
		if type( k ) == 'table' then
			local v = setmetatable( { }, { __index = k, __newindex = readOnlyError, __metatable = "< read-only table >" } )
			readOnlyBase[ v ] = k
			t[ k ] = v
			return v
		else
			return k
		end
	end
} )

--------------------------------------------------------------------------------

-- Return a table that provides a read-only view of the supplied table.

function KSTableUtils.makeReadOnly( t )

	return t and readOnlyVersion[ t ]

end

--------------------------------------------------------------------------------

function KSTableUtils.readOnlyPairs( t )

	return pairs( ( t and readOnlyBase[ t ] ) or t )
		-- If t isn't nil or false, look for a read-only base table
		-- If we don't have or look for a read-only base table, just use t.

end

--------------------------------------------------------------------------------

function KSTableUtils.shallowcopy( t )
	local result = {}
	for k,v in pairs( t ) do
		result[ k ] = v
	end
	return result
end

--============================================================================--

local kMaxLevels = 20

local function deepCopyImp( v, depth, copied )

	-- Copied from Lightroom's AgTableUtils.deepCopy and deepCopyImp.

	if v then

		if kMaxLevels < depth then
			error( "Depth limit exceeded for deepCopy." )
		end
	
		local tv = type( v )
		
		-- Userdata is not supported.
		
		if tv == 'userdata' then
			error( "deepCopy does not support userdata: " .. tostring( v ) )
		end
		
--		if isNilSentinel( v ) then
--			return v	-- This is immutable (and has a mt), so handle it specially.
--		end
		
		-- Copy tables an entry at a time
		
		if tv == 'table' then
		
			if getmetatable( v ) ~= nil then
				error( "deepCopy does not support metatables" )
			end
		
			local vcopy = copied[ v ]
			
			if vcopy ~= nil then
				return vcopy
			end
			
			vcopy = {}
			
			copied[ v ] = vcopy
				-- Generate the link back now
			
			for k, v2 in pairs( v ) do
				local ck = deepCopyImp( k, depth + 1, copied )
				local cv = deepCopyImp( v2, depth + 1, copied )
				vcopy[ ck ] = cv
			end
			
			return vcopy
		
		end

	end
		
	-- All other cases are handled by just returning the value
	
	return v

end

--------------------------------------------------------------------------------

local function deepCopy( v )

	local tv = type( v )
	
	if tv == 'table' then
		return deepCopyImp( v, 0, { } )
	end
	
	if tv == 'userdata' then
		error( "deepCopy does not support userdata: " .. tostring( v ) )
	end

	return v

end

--------------------------------------------------------------------------------

KSTableUtils.deepCopy = deepCopy

--============================================================================--

local function mapArrayToSet( mapFn, array )

	if array == nil and type( mapFn ) == 'table' then
		return mapArrayToSet( nil, mapFn )
	end

	local result = { }

	if not KSFunctionUtils then
		KSFunctionUtils = assert( require 'KSFunctionUtils' )
	end
	
	-- Handle the case where we have no map to apply.

	if mapFn == nil or mapFn == KSFunctionUtils.identity then
	
		for i = 1, #array do
			local v = array[ i ]
			result[ v ] = v or true
		end
		
		return result
		
	end
	
	local processed = { }
		-- Track processed items so that we only process once
		
	-- Special case field extraction to avoid the function call overhead.

	local isFieldExtractor, fieldSelector = KSFunctionUtils.isFieldExtractorFn( mapFn )
	
	if isFieldExtractor then
		
		for _, v in ipairs( array ) do
			if not processed[ v ] then
				processed[ v ] = true
				local mappedV = v[ fieldSelector ]
				if mappedV ~= nil then
					result[ mappedV ] = mappedV or true
				end
			end
		end
		
		return result
		
	end
	
	-- Handle everything else
	
	for _, v in ipairs( array ) do
		if not processed[ v ] then
			processed[ v ] = true
			local mappedV = mapFn( v )
			if mappedV ~= nil then
				result[ mappedV ] = mappedV or true
			end
		end
	end
	
	return result

end

KSTableUtils.mapArrayToSet = mapArrayToSet

--============================================================================--

-- FIXME [mhamburg 2011-08-02]: The merge algorithm could really use a depth
-- limit. We could impose this in the dictMergeForPath code since we have the
-- path length there.

--------------------------------------------------------------------------------

-- Convert a path to a string for use in error messages. Just returns the
-- trailing element for now.

local function pathToString( path )

	if type( path ) == 'table' then
		return pathToString( path[ #path ] )
	end
	
	if path == nil then
		return '< none >'
	end
	
	return tostring( path )

end

--------------------------------------------------------------------------------

local function atomicMergeForPath( forPath, base, a, b, mergeForPath )

	WFArguments_check( 'table' )
	
	if KSTableUtils.deepEquals( a, b ) then
		return deepCopy( a )
	end
	
	if KSTableUtils.deepEquals( base, a ) then
		return deepCopy( b )
	end
	
	if KSTableUtils.deepEquals( base, b ) then
		return deepCopy( a )
	end
	
	error( "Atomic merge failed for key: " .. pathToString( forPath ) )

end

--------------------------------------------------------------------------------

local function dictMergeForPath( forPath, base, a, b, mergeForPath )

	WFArguments_check( 'table', 'table', 'table', 'table', 'function' )
	
	local r = { }
	
	-- Process all of the keys in a.
	
	local pathLength = #forPath + 1
	
	for k, v in pairs( a ) do
		forPath[ pathLength ] = k
		r[ k ] = mergeForPath( forPath, base[ k ], v, b[ k ] )
		forPath[ pathLength ] = nil
	end
	
	-- Process the keys in b that weren't in a
	
	for k, v in pairs( b ) do
		if a[ k ] == nil then
			forPath[ pathLength ] = k
			r[ k ] = mergeForPath( forPath, base[ k ], nil, v )
			forPath[ pathLength ] = nil
		end
	end
	
	-- That's everything
	
	return r

end

--------------------------------------------------------------------------------

local gMergeAlgorithms = {
	dictionary = dictMergeForPath,
	atomic = atomicMergeForPath
}

--------------------------------------------------------------------------------

-- Map empty tables to nil. Return other tables. Expects the parameter to be
-- a table.

local function mapEmptyToNil( t )

	if next( t ) == nil then
		return nil
	end
	
	return t

end

--------------------------------------------------------------------------------

local mergeFunctionsCache = makeFullyWeak()

--------------------------------------------------------------------------------

local function makeMergeFunction( getMergeAlgorithm )

	local cacheKey = getMergeAlgorithm or "< none >"
	
	local fn = mergeFunctionsCache[ cacheKey ]
	
	if fn then
		return fn
	end
	
	----------------------------------------------------------------------------
	
	local mergeForPath -- forward declaration
	
	----------------------------------------------------------------------------
	
	-- tableMergeForPath figures out which merge algorithm to use and then
	-- invokes it passing in mergeForPath to support appropriate recursion.
	
	local tableMergeForPath
	
	if getMergeAlgorithm then
	
		tableMergeForPath = function( forPath, base, a, b )
	
			WFArguments_check( 'table', 'table', 'table', 'table' )
			
			-- Figure out the merge algorithm to use.
			
			local algorithm = getMergeAlgorithm( forPath, base, a, b )
				
			if algorithm == nil or algorithm == '' then
			
				algorithm = dictMergeForPath
				
			else
			
				if type( algorithm ) == 'string' then
				
					algorithm = gMergeAlgorithms[ algorithm ]
					
					if not algorithm then
						error( "Unknown merge algorithm: " .. algorithm )
					end

				end
				
				assert( type( algorithm ) == 'function', "Merge algorithm needs to be a function" )
			
			end
			
			return algorithm( forPath, base, a, b, mergeForPath )
			
		end
		
	else
	
		tableMergeForPath = function( forPath, base, a, b )
		
			return dictMergeForPath( forPath, base, a, b, mergeForPath )
		
		end
	
	end

	----------------------------------------------------------------------------
	
	mergeForPath = function( forPath, base, a, b )
	
		-- Handle the easy equality cases that should behave the
		-- same regardless of algorithm.
		
		if a == b then
			return deepCopy( a )
		end
		
		if base == a then
			return deepCopy( b )
		end
		
		if base == b then
			return deepCopy( a )
		end
		
		-- Check the value types to see if it's a case we can handle via
		-- recursion.
		
		local type_base = type( base )
		local type_a = type( a )
		local type_b = type( b )
		
		-- Tables all across.
		
		if type_base == 'table' and type_a == 'table' and type_b == 'table' then
			return tableMergeForPath( forPath, base, a, b )
		end
		
		-- Any non-table value type promoted to two tables results in a recursion
		-- with an empty base table.
		
		if type_a == 'table' and type_b == 'table' then
			-- Pretend we had an empty base entry and merge from there. We won't
			-- be going back to nil, because both of the values are non-nil.
			return tableMergeForPath( forPath, { }, a, b )
		end
		
		-- Moving from a table to a table on one branch and to nil on the other
		-- is handled by treating the nil as an empty table and then checking
		-- to see whether the merge result is empty.
		
		if type_base == 'table' and type_a == 'nil' and type_b == 'table' then
			return mapEmptyToNil( tableMergeForPath( forPath, base, { }, b ) )
		end
		
		if type_base == 'table' and type_a == 'table' and type_b == 'nil' then
			return mapEmptyToNil( tableMergeForPath( forPath, base, a, { } ) )
		end
		
		-- We can also handle the case where base is a table and one of the targets
		-- is an identical table by checking for deep equality.
		
		if type_base == 'table' and ( type_a == 'table' or type_b == 'table' ) then
			return atomicMergeForPath( forPath, base, a, b )
		end
		
		-- Otherwise, we're in a case we can't handle via recursion and equality
		-- tests failed above, so error out.
		
		local pathName = pathToString( forPath )
		
		error( string_format(
				"Types do not support recursive merge %s -> %s and %s for path: %s",
				type_base, type_a, type_b, pathName ) )
				
	end

	----------------------------------------------------------------------------
	
	mergeFunctionsCache[ cacheKey ] = mergeForPath
	
	return mergeForPath
	
end

--------------------------------------------------------------------------------

function KSTableUtils.merge( base, a, b, getMergeAlgorithm )

	local mergeForPath = makeMergeFunction( getMergeAlgorithm )
	
	return mergeForPath( { }, base, a, b )

end

--------------------------------------------------------------------------------

function KSTableUtils.appendArray( dstArray, arrayToAppend )

	if arrayToAppend then

		local j = #dstArray
	
		for _, v in ipairs( arrayToAppend ) do
		
			j = j + 1
		
			dstArray[ j ] = v
			
		end

	end
	
	return dstArray

end

--------------------------------------------------------------------------------

function KSTableUtils.invert( t )
	
	WFArguments_check( 'table' )
	
	local ret = {}
	for k, v in pairs( t ) do
		if ret[ v ] then
			error( string.format( "cannot invert a one to many table: k = %s, v = %s, ret[ v ] = %s",
									k, v, ret[ v ] ) )
		end
		ret[ v ] = k
	end
	
	return ret
	
end

--------------------------------------------------------------------------------

function KSTableUtils.filter( filterFunc, t )
	
	WFArguments_check( 'function', 'table' )
	
	local ret = {}
	for k, v in pairs( t ) do 
		if filterFunc( k, v ) == true then
			ret[ k ] = v
		end
	end
	
	return ret
end

--------------------------------------------------------------------------------

function KSTableUtils.extractColumnAsTable( t, column )

	WFArguments_check( 'table', 'number' )

	local ret = {}
	
	for k, v in pairs( t ) do
		ret[ k ] = v[ column ]
	end
	
	return ret

end

--------------------------------------------------------------------------------

-- SPAM [matthewj 2018-03-12]: This is now provided by native code as it is 
-- much faster in native code than in pure lua.
--function KSTableUtils.derefOpt( t, ... )
--
--	local path = { ... }
--	local nPathSegments = select( '#', ... )
--	
--	local result = t
--	
--	for i = 1, nPathSegments do
--	
--		if type( result ) ~= 'table' then
--			return nil
--		end
--		
--		if path[ i ] == nil then
--			return nil
--		end
--		
--		result = result[ path[ i ] ]
--	
--	end
--	
--	return result
--
--end

--------------------------------------------------------------------------------

function KSTableUtils.keyMatch( pattern )

	return function( key )
		return string.match( key, pattern )
	end

end

--------------------------------------------------------------------------------

function KSTableUtils.slice( tbl, first, last, step )
 	local sliced = {}

	local function translate_negative( index )
		if index < 0 then
			return #tbl + index
		end

		return index
	end

	for i = translate_negative(first or 1), translate_negative(last or #tbl), step or 1 do
		sliced[#sliced+1] = tbl[i]
	end

  	return sliced
end

--------------------------------------------------------------------------------

local function _apply( tbl, valueOrFn, replace, ... )

	if not tbl then
		return false
	end

	local path =  { ... }

	for i, key in ipairs( path ) do
	
		if type( key ) == 'function' then
	
			-- we can't change keys while iterating
			local keyschanged = {}
	
			for k, v in pairs( tbl ) do
				if key( k ) then
				
					if i == #path then
						table.insert( keyschanged, k )
					else
						_apply( tbl[ k ], valueOrFn, replace, unpack( KSTableUtils.slice( path, i + 1 ) ) )
					end
					
				end
			end

			for _, k in ipairs( keyschanged ) do
				replace( tbl, k, valueOrFn)
			end
		
		else
		
			local st = tbl[ key ]

			if not st then
				return false
			end

			if i == #path then
				replace( tbl, key, valueOrFn )
				return true
			end
			
			tbl = st

		end
		
	end
	
	return true

end

--------------------------------------------------------------------------------

-- dereference a potentially deeply nested table given the path in ... and, if present, replace the value 
-- of the last element with valueOrFn (or valueOrFn( value ) if it is a function). 
-- wildcards in the path are possible with keyMatch or similar functions

function KSTableUtils.applyOpt( tbl, valueOrFn, ... )

	local function replace( t, k, fnv )
	
		if type( fnv ) == 'function' then
			t[ k ] = fnv( t[ k ] )
		else
			t[ k ] = fnv
		end
	
	end

	return _apply( tbl, valueOrFn, replace, ... )

end

--------------------------------------------------------------------------------

-- dereference a deeply nested table and transform the last key(s) using fn. Wildcards are allowed

function KSTableUtils.applyKeyOpt( tbl, fn, ... )

	WFArguments_check( 'table', 'function' )

	local function replace( t, k, fn )

		local v = t[ k ]
		local newkey = fn( k)
		
		if newkey then
			t[ newkey ] = v
		end

		t[ k ] = nil

	end

	return _apply( tbl, fn, replace, ... )

end

--------------------------------------------------------------------------------

function KSTableUtils.setNested( tbl, value, ... )

	if not tbl then
		return false
	end

	local path =  { ... }

	if not next( path ) then
		return false
	end

	for i, key in ipairs( path ) do
			
		if i == #path then
	
			tbl[ key ] = value
	
		elseif not tbl[ key ] then
		
			tbl[ key ] = {}
		
		end

		tbl = tbl[ key ]

	end
	
	return true


end


--------------------------------------------------------------------------------

function KSTableUtils.extractKeys( t )

	WFArguments_check( 'table' )

	local keys = {}

	for k in pairs( t ) do

		keys[ #keys + 1 ] = k

	end

	return keys

end

--------------------------------------------------------------------------------

function KSTableUtils.extractValues( t )

	WFArguments_check( 'table' )

	local values = {}

	for _, v in pairs( t ) do

		values[ #values + 1 ] = v

	end

	return values

end

--------------------------------------------------------------------------------

function KSTableUtils.flatten( t )

	WFArguments_check( 'table' )

	local result = { }

	local function _flatten( t )

		for k, v in pairs( t ) do

		if type( v ) == "table" then
				_flatten( v )
			else
				table.insert(result, v)
			end
		end
	end

	_flatten( t )

	return result
end

--------------------------------------------------------------------------------

function KSTableUtils.trimmedMean( percentage, values )

	WFArguments_check( 'number', 'table' )
	
	local numElements = #values
	
	if percentage <= 0 or percentage >= 1 then
		error( "Invalid percentage. Must be between 0 and 1." )
	end
	
	if numElements == 0 then
		error( "Unable to calculate the mean of an empty table." )
	end
	
	table.sort( values )
	
	-- https://www.tutorialspoint.com/statistics/trimmed_mean.htm
	
	local trimSize = math.floor( numElements * percentage )
	
	local trimmedSum = 0
	
	local trimmedStart = trimSize
	local trimmedEnd = numElements - trimSize
	
	for i = trimmedStart + 1, trimmedEnd, 1 do
		trimmedSum = trimmedSum + values[ i ]
	end
	
	return trimmedSum / ( trimmedEnd - trimmedStart )
	
end

--------------------------------------------------------------------------------

function KSTableUtils.findInTable( t, f )

	for k, v in pairs( t ) do

		if f( k, v ) then

			return k, v

		end

	end

end

--------------------------------------------------------------------------------

return KSTableUtils
