--!native
--!nonstrict
--!optimize 2
-- Compiled with roblox-ts v2.3.0
local TS = _G[script]
local binaryInsert = TS.import(script, script.Parent.Parent, "utilities", "binary-insert").binaryInsert
--[[
	*
	 * Here be dragons.
	 
]]
local Graph
do
	Graph = setmetatable({}, {
		__tostring = function()
			return "Graph"
		end,
	})
	Graph.__index = Graph
	function Graph.new(...)
		local self = setmetatable({}, Graph)
		return self:constructor(...) or self
	end
	function Graph:constructor(isDirected)
		if isDirected == nil then
			isDirected = false
		end
		self.isDirected = isDirected
		self.edges = {}
		self.vertices = {}
	end
	function Graph.getNeighbors(graphVertex)
		return graphVertex:getNeighbors()
	end
	function Graph:addVertex(graphVertex)
		local _vertices = self.vertices
		local _arg0 = graphVertex:getKey()
		local _graphVertex = graphVertex
		_vertices[_arg0] = _graphVertex
		return self
	end
	function Graph:getVertexByKey(key)
		local _vertices = self.vertices
		local _key = key
		return _vertices[_key]
	end
	function Graph:getAllEdges()
		local array = {}
		local length = 0
		for _, graphEdge in self.edges do
			local _original = length
			length += 1
			array[_original + 1] = graphEdge
		end
		return array
	end
	function Graph:getAllVertices()
		local array = {}
		local length = 0
		for _, graphVertex in self.vertices do
			local _original = length
			length += 1
			array[_original + 1] = graphVertex
		end
		return array
	end
	function Graph:addEdge(graphEdge)
		local _binding = self
		local edges = _binding.edges
		local isDirected = _binding.isDirected
		local vertices = _binding.vertices
		local _arg0 = graphEdge.startVertex:getKey()
		local startVertex = vertices[_arg0]
		if not startVertex then
			self:addVertex(graphEdge.startVertex)
			local _arg0_1 = graphEdge.startVertex:getKey()
			startVertex = vertices[_arg0_1]
		end
		local _arg0_1 = graphEdge.finishVertex:getKey()
		local finishVertex = vertices[_arg0_1]
		if not finishVertex then
			self:addVertex(graphEdge.finishVertex)
			local _arg0_2 = graphEdge.finishVertex:getKey()
			finishVertex = vertices[_arg0_2]
		end
		local _arg0_2 = graphEdge:getKey()
		if edges[_arg0_2] ~= nil then
			error("GraphEdge already exists.")
		end
		local _arg0_3 = graphEdge:getKey()
		local _graphEdge = graphEdge
		edges[_arg0_3] = _graphEdge
		if isDirected then
			startVertex:addEdge(graphEdge)
		else
			startVertex:addEdge(graphEdge)
			finishVertex:addEdge(graphEdge)
		end
		return self
	end
	function Graph:deleteEdge(graphEdge)
		local _binding = self
		local edges = _binding.edges
		local vertices = _binding.vertices
		local _arg0 = graphEdge:getKey()
		-- ▼ Map.delete ▼
		local _valueExisted = edges[_arg0] ~= nil
		edges[_arg0] = nil
		-- ▲ Map.delete ▲
		if not _valueExisted then
			error("GraphEdge does not exist.")
		end
		local _arg0_1 = graphEdge.startVertex:getKey()
		local _result = vertices[_arg0_1]
		if _result ~= nil then
			_result:deleteEdge(graphEdge)
		end
		local _arg0_2 = graphEdge.finishVertex:getKey()
		local _result_1 = vertices[_arg0_2]
		if _result_1 ~= nil then
			_result_1:deleteEdge(graphEdge)
		end
		return self
	end
	function Graph:findEdge(startVertex, finishVertex)
		local _vertices = self.vertices
		local _arg0 = startVertex:getKey()
		local _result = _vertices[_arg0]
		if _result ~= nil then
			_result = _result:findEdge(finishVertex)
		end
		return _result
	end
	function Graph:getWeight()
		local weight = 0
		for _, graphEdge in self:getAllEdges() do
			weight += graphEdge.weight
		end
		return weight
	end
	function Graph:reverse()
		for _, graphEdge in self:getAllEdges() do
			self:deleteEdge(graphEdge)
			graphEdge:reverse()
			self:addEdge(graphEdge)
		end
		return self
	end
	function Graph:getVerticesIndices()
		local verticesIndices = {}
		local index = 0
		for _, graphVertex in self:getAllVertices() do
			local _arg0 = graphVertex:getKey()
			local _index = index
			verticesIndices[_arg0] = _index
			index += 1
		end
		return verticesIndices
	end
	function Graph:getAdjacencyMatrix(shouldThrow)
		if shouldThrow == nil then
			shouldThrow = false
		end
		local vertices = self:getAllVertices()
		local length = #vertices
		local adjacencyMatrix = table.create(length)
		for index = 0, length - 1 do
			adjacencyMatrix[index + 1] = table.create(length, math.huge)
		end
		local verticesIndices = self:getVerticesIndices()
		local vertexIndex = 0
		for _, graphVertex in vertices do
			for _1, neighbor in graphVertex:getNeighbors() do
				local _arg0 = neighbor:getKey()
				local neighborIndex = verticesIndices[_arg0]
				if neighborIndex == nil then
					if shouldThrow then
						error("GraphVertex does not exist.")
					end
					continue
				end
				local graphEdge = self:findEdge(graphVertex, neighbor)
				if not graphEdge then
					error("Cannot read property 'Weight' of undefined edge.")
				end
				adjacencyMatrix[vertexIndex + 1][neighborIndex + 1] = graphEdge.weight
			end
			vertexIndex += 1
		end
		return adjacencyMatrix
	end
end
Graph.__tostring = function(graph)
	local keys = {}
	for vertexKey in graph.vertices do
		binaryInsert(keys, vertexKey)
	end
	return `Graph<[{table.concat(keys, ", ")}]>`
end
return {
	Graph = Graph,
}