--!native
--!nonstrict
--!optimize 2
-- Compiled with roblox-ts v2.3.0
-- This was entirely created by Validark. All credit goes to this incredible man!
local function indexString(value, index)
	local _value = value
	local _arg0 = index + 1
	return (string.byte(_value, _arg0))
end
--[[
	*
	 * # DynSDT Implementations
	 *
	 * Dynamic Score-Decomposed Tries* which solve the scored prefix completion problem. The C# version is the primary version at the moment. The preliminary TypeScript version in the main repo was created just to match the pseudocode from the paper to help verify the correctness of the pseudocode. The Zig version is still in-development.
	 *
	 * Paper: [validark.github.io/DynSDT](https://validark.github.io/DynSDT/), entitled *Heap-like Dynamic Score-Decomposed Tries for Top-k Autocomplete*
	 *
	 * Live Demo: [validark.github.io/DynSDT/demo](https://validark.github.io/DynSDT/demo/)
	 *
	 * Email autocomplete proof-of-concept: [validark.github.io/DynSDT/web-autocomplete](https://validark.github.io/DynSDT/web-autocomplete/)
	 *  - This uses another TypeScript implementation I made which supports aliasing so multiple names/emails can autocomplete to the same person. [The source code is available here](https://github.com/Validark/DynSDT/tree/paper/web-autocomplete).
	 *
	 * Paper & Demo website code: [/tree/paper](https://github.com/Validark/DynSDT/tree/paper)
	 *
	 * Give Validark a star [here](https://github.com/Validark/DynSDT)!
	 *
	 * Keywords: Query Autocomplete, QAC, type-ahead, ranked autosuggest, top-k autocomplete, trie decomposition, Dynamic Score-Decomposed Trie, trie autocomplete, Completion Trie.
	 *
	 * @author Validark
	 * Adapted for Luau + RobloxTS by HowManySmall.
	 
]]
local DynamicScoreDecomposedTrie
do
	DynamicScoreDecomposedTrie = setmetatable({}, {
		__tostring = function()
			return "DynamicScoreDecomposedTrie"
		end,
	})
	DynamicScoreDecomposedTrie.__index = DynamicScoreDecomposedTrie
	function DynamicScoreDecomposedTrie.new(...)
		local self = setmetatable({}, DynamicScoreDecomposedTrie)
		return self:constructor(...) or self
	end
	function DynamicScoreDecomposedTrie:constructor()
		self.rootBranchPoints = { {
			lcp = 0,
			node = nil,
		} }
	end
	function DynamicScoreDecomposedTrie:getRoot()
		return self.rootBranchPoints[1].node
	end
	function DynamicScoreDecomposedTrie:setRoot(node)
		self.rootBranchPoints[1].node = node
	end
	function DynamicScoreDecomposedTrie:topCompletions(prefix, kndex)
		local completions = {}
		if not (kndex > 0) then
			return completions
		end
		local locus = self:findLocusForPrefix(prefix)
		if not locus then
			return completions
		end
		local _key = locus.key
		table.insert(completions, _key)
		kndex -= 1
		if kndex == 0 then
			return completions
		end
		local branchPoints = locus.branchPoints
		local index = 0
		do
			local _shouldIncrement = false
			while true do
				if _shouldIncrement then
					index += 1
				else
					_shouldIncrement = true
				end
				if index == #branchPoints then
					return completions
				end
				if branchPoints[index + 1].lcp >= #prefix then
					break
				end
			end
		end
		local _key_1 = branchPoints[index + 1].node.key
		table.insert(completions, _key_1)
		local heapPointers = {}
		while true do
			kndex -= 1
			if not (kndex > 0) then
				break
			end
			if #branchPoints[index + 1].node.branchPoints > 0 then
				local _arg0 = {
					branchPoints = branchPoints[index + 1].node.branchPoints,
					index = 0,
				}
				table.insert(heapPointers, _arg0)
				local jndex = #heapPointers - 1
				local element = heapPointers[jndex + 1]
				local score = element.branchPoints[element.index + 1].node.score
				while true do
					jndex -= 1
					local _condition = jndex >= 0
					if _condition then
						_condition = score < heapPointers[jndex + 1].branchPoints[heapPointers[jndex + 1].index + 1].node.score
					end
					if not _condition then
						break
					end
					heapPointers[jndex + 2] = heapPointers[jndex + 1]
				end
				heapPointers[jndex + 2] = element
			end
			while true do
				index += 1
				if not (index < #branchPoints) then
					break
				end
				if branchPoints[index + 1].lcp >= #prefix then
					local _arg0 = {
						branchPoints = branchPoints,
						index = index,
					}
					table.insert(heapPointers, _arg0)
					local jndex = #heapPointers - 1
					local element = heapPointers[jndex + 1]
					local score = element.branchPoints[element.index + 1].node.score
					while true do
						jndex -= 1
						local _condition = jndex >= 0
						if _condition then
							_condition = score < heapPointers[jndex + 1].branchPoints[heapPointers[jndex + 1].index + 1].node.score
						end
						if not _condition then
							break
						end
						heapPointers[jndex + 2] = heapPointers[jndex + 1]
					end
					heapPointers[jndex + 2] = element
					break
				end
			end
			if #heapPointers == 0 then
				return completions
			end
			-- ▼ Array.pop ▼
			local _length = #heapPointers
			local _result = heapPointers[_length]
			heapPointers[_length] = nil
			-- ▲ Array.pop ▲
			local _binding = _result
			branchPoints = _binding.branchPoints
			index = _binding.index
			local _key_2 = branchPoints[index + 1].node.key
			table.insert(completions, _key_2)
		end
		return completions
	end
	function DynamicScoreDecomposedTrie:set(term, score)
		if not self:getRoot() then
			self:setRoot({
				branchPoints = {},
				key = term,
				score = score,
			})
			return nil
		end
		local branchPoints = self.rootBranchPoints
		local index = 0
		local node = self:getRoot()
		local lcp = 0
		while true do
			do
				local min = math.min(#term, #node.key)
				local _shouldIncrement = false
				while true do
					if _shouldIncrement then
						lcp += 1
					else
						_shouldIncrement = true
					end
					if not (lcp < min and indexString(term, lcp) == indexString(node.key, lcp)) then
						break
					end
				end
			end
			if lcp == #term and lcp == #node.key then
				self:setExactMatchFound(score, node, branchPoints, index)
				return nil
			end
			if score > node.score then
				self:setScoreLocationFound(term, score, lcp, branchPoints, index)
				return nil
			end
			branchPoints = node.branchPoints
			local newNode, newIndex = self:findNodeForLcp(branchPoints, lcp)
			if not newNode then
				local _branchPoints = branchPoints
				local _arg0 = {
					lcp = lcp,
					node = {
						branchPoints = {},
						key = term,
						score = score,
					},
				}
				table.insert(_branchPoints, _arg0)
				return nil
			end
			node, index = newNode, newIndex
		end
	end
	function DynamicScoreDecomposedTrie:setExactMatchFound(score, node, branchPoints, index)
		node.score = score
		local nodePoints = node.branchPoints
		if #nodePoints == 0 or score >= nodePoints[1].node.score then
			self:insertionSortIndex(branchPoints, index)
			return nil
		end
		local pointers = {}
		branchPoints[index + 1].node = nodePoints[1].node
		index = self:insertionSortIndexDown(branchPoints, index)
		local _arg0 = {
			branchPoints = branchPoints,
			index = index,
			lcp = nodePoints[1].lcp,
		}
		table.insert(pointers, _arg0)
		nodePoints[1] = {
			lcp = #node.key,
			node = {
				branchPoints = {},
				key = node.key,
				score = score,
			},
		}
		self:insertionSortIndexDown(nodePoints, 0)
		for _, branchPoint in nodePoints do
			local _binding = branchPoint
			local lcp = _binding.lcp
			local localNode = _binding.node
			-- eslint-disable-next-line prefer-const
			local _binding_1 = pointers[#pointers]
			local branchPoints = _binding_1.branchPoints
			local index = _binding_1.index
			local maxLcp = _binding_1.lcp
			if lcp >= maxLcp then
				while true do
					branchPoints = branchPoints[index + 1].node.branchPoints
					local newNode, newIndex = self:findNodeForLcp(branchPoints, maxLcp)
					if not newNode then
						branchPoint.lcp = maxLcp
						index = self:insertionSortIntoList(branchPoints, branchPoint)
						break
					end
					node, index = newNode, newIndex
					if localNode.score >= node.score then
						self:insertionSortIntoList(localNode.branchPoints, branchPoints[index + 1])
						branchPoint.lcp = maxLcp
						branchPoints[index + 1] = branchPoint
						index = self:insertionSortIndexUp(branchPoints, index)
						break
					end
				end
				if lcp > maxLcp and localNode ~= nodePoints[#nodePoints].node then
					local _arg0_1 = {
						branchPoints = branchPoints,
						index = index,
						lcp = lcp,
					}
					table.insert(pointers, _arg0_1)
				end
			else
				local left = 0
				local right = #pointers - 2
				while left <= right do
					local middle = left + (right - left) // 2
					if lcp < pointers[middle + 1].lcp then
						right = middle - 1
					else
						left = middle + 1
					end
				end
				local _binding_2 = pointers[left + 1]
				branchPoints = _binding_2.branchPoints
				index = _binding_2.index
				self:insertionSortIntoList(branchPoints[index + 1].node.branchPoints, branchPoint)
			end
		end
	end
	function DynamicScoreDecomposedTrie:insertionSortIntoList(branchPoints, branchPoint)
		local _fn = self
		local _exp = branchPoints
		local _branchPoints = branchPoints
		local _branchPoint = branchPoint
		table.insert(_branchPoints, _branchPoint)
		return _fn:insertionSortIndexUp(_exp, #_branchPoints - 1)
	end
	function DynamicScoreDecomposedTrie:findNodeForLcp(branchPoints, lcp)
		local index = 0
		for _, branchPoint in branchPoints do
			if branchPoint.lcp == lcp then
				return branchPoint.node, index
			end
			index += 1
		end
		return nil, 0 / 0
	end
	function DynamicScoreDecomposedTrie:setScoreLocationFound(term, score, lcp, branchPoints, index)
		local newBranchPoints = {}
		local node = branchPoints[index + 1].node
		local _arg0 = {
			lcp = lcp,
			node = node,
		}
		table.insert(newBranchPoints, _arg0)
		branchPoints[index + 1].node = {
			branchPoints = newBranchPoints,
			key = term,
			score = score,
		}
		index = self:insertionSortIndexUp(branchPoints, index)
		node.branchPoints = self:extractLcpsBelowThreshold(node.branchPoints, lcp, newBranchPoints)
		branchPoints = newBranchPoints
		index = 0
		while lcp ~= #term do
			repeat
				do
					branchPoints = branchPoints[index + 1].node.branchPoints
					local newNode, newIndex = self:findNodeForLcp(branchPoints, lcp)
					if not newNode then
						return nil
					end
					node, index = newNode, newIndex
				end
			until not (lcp == #node.key or indexString(term, lcp) ~= indexString(node.key, lcp))
			local branchPoint = branchPoints[index + 1]
			self:supplantNodeFromParent(branchPoints, index, node, lcp)
			do
				local min = math.min(#term, #node.key)
				while true do
					lcp += 1
					local _condition = lcp < min
					if _condition then
						_condition = indexString(term, lcp) == indexString(node.key, lcp)
					end
					if not _condition then
						break
					end
				end
			end
			if lcp ~= #term or lcp ~= #node.key then
				local jndex = #newBranchPoints
				branchPoint.lcp = lcp
				table.insert(newBranchPoints, branchPoint)
				node.branchPoints = self:extractLcpsBelowThreshold(node.branchPoints, lcp, newBranchPoints)
				index = self:mergeTwoSortedSubArrays(newBranchPoints, jndex)
				branchPoints = newBranchPoints
			end
		end
		if lcp ~= #node.key then
			repeat
				do
					branchPoints = branchPoints[index + 1].node.branchPoints
					local newNode, newIndex = self:findNodeForLcp(branchPoints, lcp)
					if not newNode then
						return nil
					end
					node, index = newNode, newIndex
				end
			until not (lcp ~= #node.key)
			self:supplantNodeFromParent(branchPoints, index, node, lcp)
		end
		local jndex = #newBranchPoints
		--Array.prototype.push.apply equivalent
		local _branchPoints = node.branchPoints
		local _arg1 = #node.branchPoints - 1
		table.move(_branchPoints, 1, _arg1 + 1, jndex + 1, newBranchPoints)
		self:mergeTwoSortedSubArrays(newBranchPoints, jndex)
	end
	function DynamicScoreDecomposedTrie:mergeTwoSortedSubArrays(branchPoints, index)
		local finalIndexOfFirstElement = index
		repeat
			do
				local localIndex = index
				local element = branchPoints[localIndex + 1]
				if element.node.score <= branchPoints[localIndex].node.score then
					break
				end
				repeat
					do
						branchPoints[localIndex + 1] = branchPoints[localIndex]
						localIndex -= 1
					end
				until not (element.node.score > branchPoints[localIndex].node.score)
				branchPoints[localIndex + 1] = element
				if finalIndexOfFirstElement == index then
					finalIndexOfFirstElement = localIndex
				end
			end
			index += 1
		until not (index < #branchPoints)
		return finalIndexOfFirstElement
	end
	function DynamicScoreDecomposedTrie:findLocusForPrefix(prefix)
		local node = self:getRoot()
		local lcp = 0
		while node do
			do
				local min = math.min(#prefix, #node.key)
				local _shouldIncrement = false
				while true do
					if _shouldIncrement then
						lcp += 1
					else
						_shouldIncrement = true
					end
					if not (lcp < min and indexString(prefix, lcp) == indexString(node.key, lcp)) then
						break
					end
				end
			end
			if lcp == #prefix then
				break
			end
			node = self:findNodeForLcp(node.branchPoints, lcp)
		end
		return node
	end
	function DynamicScoreDecomposedTrie:supplantNodeFromParent(branchPoints, index, node, lcp)
		local cull, jndex = self:findNodeForLcp(node.branchPoints, lcp)
		if cull == nil then
			local _branchPoints = branchPoints
			local _index = index
			table.remove(_branchPoints, _index + 1)
			return nil
		end
		branchPoints[index + 1] = node.branchPoints[jndex + 1]
		self:insertionSortIndexDown(branchPoints, index)
		table.remove(node.branchPoints, jndex + 1)
	end
	function DynamicScoreDecomposedTrie:extractLcpsBelowThreshold(source, lcp, destination)
		local extracted = {}
		for _, branchPoint in source do
			local _exp = (if lcp > branchPoint.lcp then destination else extracted)
			table.insert(_exp, branchPoint)
		end
		return extracted
	end
	function DynamicScoreDecomposedTrie:insertionSortIndex(branchPoints, index)
		local element = branchPoints[index + 1]
		do
			local _shouldIncrement = false
			while true do
				if _shouldIncrement then
					index -= 1
				else
					_shouldIncrement = true
				end
				if not (index ~= 0 and element.node.score > branchPoints[index].node.score) then
					break
				end
				branchPoints[index + 1] = branchPoints[index]
			end
		end
		do
			local _shouldIncrement = false
			while true do
				if _shouldIncrement then
					index += 1
				else
					_shouldIncrement = true
				end
				if not (index + 1 < #branchPoints and element.node.score < branchPoints[index + 2].node.score) then
					break
				end
				branchPoints[index + 1] = branchPoints[index + 2]
			end
		end
		branchPoints[index + 1] = element
	end
	function DynamicScoreDecomposedTrie:insertionSortIndexUp(branchPoints, index)
		local element = branchPoints[index + 1]
		do
			local _shouldIncrement = false
			while true do
				if _shouldIncrement then
					index -= 1
				else
					_shouldIncrement = true
				end
				if not (index ~= 0 and element.node.score > branchPoints[index].node.score) then
					break
				end
				branchPoints[index + 1] = branchPoints[index]
			end
		end
		branchPoints[index + 1] = element
		return index
	end
	function DynamicScoreDecomposedTrie:insertionSortIndexDown(branchPoints, index)
		local element = branchPoints[index + 1]
		do
			local _shouldIncrement = false
			while true do
				if _shouldIncrement then
					index += 1
				else
					_shouldIncrement = true
				end
				if not (index + 1 < #branchPoints and element.node.score < branchPoints[index + 2].node.score) then
					break
				end
				branchPoints[index + 1] = branchPoints[index + 2]
			end
		end
		branchPoints[index + 1] = element
		return index
	end
end
local metatable = DynamicScoreDecomposedTrie
metatable.__tostring = function()
	return "DynamicScoreDecomposedTrie"
end
return {
	DynamicScoreDecomposedTrie = DynamicScoreDecomposedTrie,
}