-- A simple function to extend forward paths from (d - 1) to d changes
-- when forward and reverse paths cannot yet overlap.

local function extendPathsF(
	d: number,
	aEnd: number,
	bEnd: number,
	bF: number,
	isCommon: IsCommon,
	aIndexesF: Indexes,
	iMaxF: number
): number
	-- Unroll the first iteration.
	local iF = 0
	local kF = -d -- kF = 2 * iF - d
	-- ROBLOX FIXME? should the values inserted into aIndexesF be 1-based so we don't have to adjust in several places here?
	local aFirst = aIndexesF[iF + 1] -- in first iteration always insert
	local aIndexPrev1 = aFirst -- prev value of [iF - 1] in next iteration
	aIndexesF[iF + 1] += countCommonItemsF(aFirst + 1, aEnd, bF + aFirst - kF + 1, bEnd, isCommon)

	-- Optimization: skip diagonals in which paths cannot ever overlap.
	local nF = d < iMaxF and d or iMaxF

	-- The diagonals kF are odd when d is odd and even when d is even.
	iF += 1
	kF += 2
	while iF <= nF do
		-- To get first point of path segment, move one change in forward direction
		-- from last point of previous path segment in an adjacent diagonal.
		-- In last possible iteration when iF === d and kF === d always delete.
		-- ROBLOX deviation: add one to index for Lua 1-based arrays
		if iF ~= d and aIndexPrev1 < aIndexesF[iF + 1] then
			aFirst = aIndexesF[iF + 1] -- vertical to insert from b
		else
			aFirst = aIndexPrev1 + 1 -- horizontal to delete from a

			if aEnd <= aFirst then
				-- Optimization: delete moved past right of graph.
				return iF - 1
			end
		end

		-- To get last point of path segment, move along diagonal of common items.
		-- ROBLOX deviation: add one to index for Lua 1-based arrays
		aIndexPrev1 = aIndexesF[iF + 1]
		aIndexesF[iF + 1] = aFirst + countCommonItemsF(aFirst + 1, aEnd, bF + aFirst - kF + 1, bEnd, isCommon)

		iF += 1
		kF += 2
	end

	return iMaxF
end
