--!native
--!nonstrict
--!optimize 2
-- Compiled with roblox-ts v2.3.0
local function findClosest(array, priority, low, high)
	local middle
	do
		local sum = low + high
		middle = (sum - (sum % 2)) / 2
	end
	if middle == -1 then
		return -2
	end
	local element = array[middle + 1]
	while middle ~= high do
		local priority2 = element.priority
		if priority == priority2 then
			return middle
		end
		if priority < priority2 then
			high = middle - 1
		else
			low = middle + 1
		end
		local sum = low + high
		middle = (sum - (sum % 2)) / 2
		element = array[middle + 1]
	end
	return middle
end
--[[
	*
	 * In a max priority queue, elements are inserted in the order in which they arrive to
	 * the queue and the maximum value is always removed first from the queue.
	 
]]
local MaxPriorityQueue
do
	MaxPriorityQueue = setmetatable({}, {
		__tostring = function()
			return "MaxPriorityQueue"
		end,
	})
	MaxPriorityQueue.__index = MaxPriorityQueue
	function MaxPriorityQueue.new(...)
		local self = setmetatable({}, MaxPriorityQueue)
		return self:constructor(...) or self
	end
	function MaxPriorityQueue:constructor()
		self.array = {}
		self.length = 0
	end
	function MaxPriorityQueue:insertWithPriority(value, priority)
		local array = self.array
		local position = findClosest(array, priority, 0, self.length - 1)
		local element = array[position + 1]
		if element then
			position = if priority < element.priority then position else position + 1
		else
			position = 0
		end
		local _position = position
		local _arg1 = {
			priority = priority,
			value = value,
		}
		table.insert(array, _position + 1, _arg1)
		self.length += 1
		return position
	end
	function MaxPriorityQueue:insert(value, priority)
		return self:insertWithPriority(value, priority)
	end
	function MaxPriorityQueue:changePriority(value, newPriority)
		local array = self.array
		-- ▼ ReadonlyArray.findIndex ▼
		local _callback = function(element)
			return element.value == value
		end
		local _result = -1
		for _i, _v in array do
			if _callback(_v, _i - 1, array) == true then
				_result = _i - 1
				break
			end
		end
		-- ▲ ReadonlyArray.findIndex ▲
		local index = _result
		if index ~= -1 then
			table.remove(array, index + 1)
			self.length -= 1
			return self:insertWithPriority(value, newPriority)
		end
		error("Couldn't find value in the queue?")
	end
	function MaxPriorityQueue:getFirstPriority()
		return if self.length == 0 then nil else self.array[1].priority
	end
	function MaxPriorityQueue:getLastPriority()
		local length = self.length
		return if length == 0 then nil else self.array[length].priority
	end
	function MaxPriorityQueue:popElement(onlyValue)
		local _binding = self
		local array = _binding.array
		local length = _binding.length
		if length == 0 then
			return nil
		end
		local _arg0 = length - 1
		local element = table.remove(array, _arg0 + 1)
		if element then
			self.length = length - 1
			return if onlyValue then element.value else element
		end
		return nil
	end
	function MaxPriorityQueue:clear()
		table.clear(self.array)
		self.length = 0
		return self
	end
	function MaxPriorityQueue:contains(value)
		local _exp = self.array
		-- ▼ ReadonlyArray.findIndex ▼
		local _callback = function(element)
			return element.value == value
		end
		local _result = -1
		for _i, _v in _exp do
			if _callback(_v, _i - 1, _exp) == true then
				_result = _i - 1
				break
			end
		end
		-- ▲ ReadonlyArray.findIndex ▲
		return _result ~= -1
	end
	function MaxPriorityQueue:removePriority(priority)
		local array = self.array
		local index = findClosest(array, priority, 0, self.length - 1)
		if index == -2 then
			return nil
		end
		table.remove(array, index + 1)
		self.length -= 1
	end
	function MaxPriorityQueue:removeValue(value)
		local array = self.array
		-- ▼ ReadonlyArray.findIndex ▼
		local _callback = function(element)
			return element.value == value
		end
		local _result = -1
		for _i, _v in array do
			if _callback(_v, _i - 1, array) == true then
				_result = _i - 1
				break
			end
		end
		-- ▲ ReadonlyArray.findIndex ▲
		local index = _result
		if index == -1 then
			return nil
		end
		table.remove(array, index + 1)
		self.length -= 1
	end
	function MaxPriorityQueue:size()
		return self.length
	end
	function MaxPriorityQueue:isEmpty()
		return self.length == 0
	end
	MaxPriorityQueue.instanceof = function(value)
		local _value = value
		local _condition = type(_value) == "table"
		if _condition then
			_condition = getmetatable(value) == MaxPriorityQueue
		end
		return _condition
	end
end
local metatable = MaxPriorityQueue
-- hello luau users
metatable.__len = function(maxPriorityQueue)
	return maxPriorityQueue.length
end
metatable.__tostring = function(maxPriorityQueue)
	local _exp = maxPriorityQueue.array
	-- ▼ ReadonlyArray.map ▼
	local _newValue = table.create(#_exp)
	local _callback = function(_param)
		local priority = _param.priority
		local value = _param.value
		return `\t\{ priority: {priority}, value: {value} \},`
	end
	for _k, _v in _exp do
		_newValue[_k] = _callback(_v, _k - 1, _exp)
	end
	-- ▲ ReadonlyArray.map ▲
	return `MaxPriorityQueue<[\n{table.concat(_newValue, "\n")}\n]>`
end
return {
	MaxPriorityQueue = MaxPriorityQueue,
}