--!native
--!nonstrict
--!optimize 2
-- Compiled with roblox-ts v2.3.0
local TS = _G[script]
local function findClosest(array, value, low, high, eq, lt)
	local middle
	do
		local sum = low + high
		middle = (sum - (sum % 2)) / 2
	end
	if middle == -1 then
		return nil
	end
	local value2 = array[middle + 1]
	while middle ~= high do
		if eq then
			if eq(value, value2) then
				return middle
			end
		elseif value == value2 then
			return middle
		end
		local _result = lt
		if _result ~= nil then
			_result = _result(value, value2)
		end
		local _condition = _result
		if _condition == nil then
			_condition = value < value2
		end
		local bool = _condition
		if bool then
			high = middle - 1
		else
			low = middle + 1
		end
		local sum = low + high
		middle = (sum - (sum % 2)) / 2
		value2 = array[middle + 1]
	end
	return middle
end
--[[
	*
	 * A class to create sorted arrays. Must contain objects comparable to
	 * one another (that can use the `<` and `==` operators). Numbers and
	 * strings support these operators by default.
	 *
	 * @example
	 * const array0 = new SortedArray([3, 1, 2]); // will sort
	 * const array1 = new SortedArray<string>();
	 *
	 * @author Validark
	 
]]
local SortedArray
do
	SortedArray = setmetatable({}, {
		__tostring = function()
			return "SortedArray"
		end,
	})
	SortedArray.__index = SortedArray
	function SortedArray.new(...)
		local self = setmetatable({}, SortedArray)
		return self:constructor(...) or self
	end
	function SortedArray:constructor(baseArray, comparison)
		if baseArray == nil then
			baseArray = {}
		end
		local _result
		if baseArray then
			local _exp = table.clone(baseArray)
			local _comparison = comparison
			table.sort(_exp, _comparison)
			_result = _exp
		else
			_result = {}
		end
		self.array = _result
		self.comparison = comparison
	end
	function SortedArray:map(callback, comparison)
		local _array = self.array
		local _callback = callback
		-- ▼ ReadonlyArray.map ▼
		local _newValue = table.create(#_array)
		for _k, _v in _array do
			_newValue[_k] = _callback(_v, _k - 1, _array)
		end
		-- ▲ ReadonlyArray.map ▲
		return SortedArray.new(_newValue, comparison):sort()
	end
	function SortedArray:mapFiltered(callback, comparison)
		local _array = self.array
		local _callback = callback
		-- ▼ ReadonlyArray.mapFiltered ▼
		local _newValue = {}
		local _length = 0
		for _k, _v in _array do
			local _result = _callback(_v, _k - 1, _array)
			if _result ~= nil then
				_length += 1
				_newValue[_length] = _result
			end
		end
		-- ▲ ReadonlyArray.mapFiltered ▲
		return SortedArray.new(_newValue, comparison):sort()
	end
	function SortedArray:insert(value)
		local array = self.array
		local _condition = findClosest(array, value, 0, #array - 1)
		if _condition == nil then
			_condition = 0
		end
		local position = _condition
		local value2 = array[position + 1]
		if value2 ~= nil then
			local _result = self.comparison
			if _result ~= nil then
				_result = _result(value, value2)
			end
			local _condition_1 = _result
			if _condition_1 == nil then
				_condition_1 = value < value2
			end
			local bool = _condition_1
			position = if bool then position else position + 1
		end
		local _position = position
		local _value = value
		table.insert(array, _position + 1, _value)
		return position
	end
	function SortedArray:find(value, eq, lt, low, high)
		if low == nil then
			low = 0
		end
		if high == nil then
			high = #self.array - 1
		end
		local array = self.array
		local position = findClosest(array, value, low, high, eq, lt or self.comparison)
		local bool
		if position ~= nil then
			local _result = eq
			if _result ~= nil then
				_result = _result(value, array[position + 1])
			end
			local _condition = _result
			if _condition == nil then
				_condition = value == array[position + 1]
			end
			bool = _condition
		end
		return if bool then position else nil
	end
	function SortedArray:indexOf(value, eq, lt, low, high)
		if low == nil then
			low = 0
		end
		if high == nil then
			high = #self.array - 1
		end
		return self:find(value, eq, lt, low, high)
	end
	function SortedArray:copy()
		return table.clone(self.array)
	end
	function SortedArray:clone()
		return SortedArray.new(table.clone(self.array), self.comparison):sort()
	end
	function SortedArray:removeElement(signature, eq, lt)
		local position = self:find(signature, eq, lt)
		return if position == nil then nil else self:removeIndex(position)
	end
	function SortedArray:removeIndex(index)
		local _array = self.array
		local _index = index
		return table.remove(_array, _index + 1)
	end
	function SortedArray:unorderedRemoveIndex(index)
		local _array = self.array
		local _index = index
		-- ▼ Array.unorderedRemove ▼
		local _index_1 = _index + 1
		local _length = #_array
		local _value = _array[_index_1]
		if _value ~= nil then
			_array[_index_1] = _array[_length]
			_array[_length] = nil
		end
		-- ▲ Array.unorderedRemove ▲
		return _value
	end
	function SortedArray:pop()
		local _exp = self.array
		-- ▼ Array.pop ▼
		local _length = #_exp
		local _result = _exp[_length]
		_exp[_length] = nil
		-- ▲ Array.pop ▲
		return _result
	end
	function SortedArray:shift()
		return table.remove(self.array, 1)
	end
	function SortedArray:sort()
		local _array = self.array
		local _comparison = self.comparison
		table.sort(_array, _comparison)
		return self
	end
	function SortedArray:getIntersection(other, eq, lt)
		if not (TS.instanceof(other, SortedArray)) then
			local _other = other
			error(`invalid argument #2 to 'getIntersection' (SortedArray expected, got {typeof(_other)} ({other}))`)
		end
		local commonalities = SortedArray.new({}, self.comparison)
		local count = 0
		local position = 0
		-- eslint-disable-next-line unicorn/no-this-assignment, @typescript-eslint/no-this-alias
		local me = self
		local thisLength = #me.array
		local otherLength = #other.array
		if thisLength > otherLength then
			thisLength, otherLength = otherLength, thisLength
			me, other = other, me
		end
		for index = 0, thisLength - 1 do
			local current = me.array[index + 1]
			local currentPosition = other:find(current, eq, lt, position, otherLength - 1)
			if currentPosition ~= nil then
				position = currentPosition
				local _exp = commonalities.array
				local _original = count
				count += 1
				_exp[_original + 1] = current
			end
		end
		return commonalities
	end
	function SortedArray:size()
		return #self.array
	end
	function SortedArray:isEmpty()
		return #self.array == 0
	end
	function SortedArray:get(index)
		return self.array[index + 1]
	end
	SortedArray.instanceof = function(value)
		local _value = value
		local _condition = type(_value) == "table"
		if _condition then
			_condition = getmetatable(value) == SortedArray
		end
		return _condition
	end
end
local metatable = SortedArray
-- hello luau users
metatable.__len = function(sortedArray)
	return #sortedArray.array
end
metatable.__tostring = function(sortedArray)
	local _exp = sortedArray.array
	-- ▼ ReadonlyArray.map ▼
	local _newValue = table.create(#_exp)
	for _k, _v in _exp do
		_newValue[_k] = tostring(_v, _k - 1, _exp)
	end
	-- ▲ ReadonlyArray.map ▲
	return `SortedArray<[{table.concat(_newValue, ", ")}]>`
end
return {
	SortedArray = SortedArray,
}