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

local function extendPathsR(
	d: number,
	aStart: number,
	bStart: number,
	bR: number,
	isCommon: IsCommon,
	aIndexesR: Indexes,
	iMaxR: number
): number
	-- Unroll the first iteration.
	local iR = 0
	local kR = d -- kR = d - 2 * iR
	-- ROBLOX FIXME? should the values inserted into aIndexesR be 1-based so we don't have to adjust in several places here?
	local aFirst = aIndexesR[iR + 1] -- in first iteration always insert
	local aIndexPrev1 = aFirst -- prev value of [iR - 1] in next iteration
	aIndexesR[iR + 1] -= countCommonItemsR(aStart, aFirst - 1, bStart, bR + aFirst - kR - 1, isCommon)

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

	-- The diagonals kR are odd when d is odd and even when d is even.
	iR += 1
	kR -= 2
	while iR <= nR do
		-- To get first point of path segment, move one change in reverse direction
		-- from last point of previous path segment in an adjacent diagonal.
		-- In last possible iteration when iR === d and kR === -d always delete.
		if iR ~= d and aIndexesR[iR + 1] < aIndexPrev1 then
			aFirst = aIndexesR[iR + 1] -- vertical to insert from b
		else
			aFirst = aIndexPrev1 - 1 -- horizontal to delete from a

			if aFirst < aStart then
				-- Optimization: delete moved past left of graph.
				return iR - 1
			end
		end

		-- To get last point of path segment, move along diagonal of common items.
		aIndexPrev1 = aIndexesR[iR + 1]
		aIndexesR[iR + 1] = aFirst - countCommonItemsR(aStart, aFirst - 1, bStart, bR + aFirst - kR - 1, isCommon)
		iR += 1
		kR -= 2
	end

	return iMaxR
end
