-- A complete function to extend forward paths from (d - 1) to d changes.
-- Return true if a path overlaps reverse path of (d - 1) changes in its diagonal.


local function extendOverlappablePathsF(
	d: number,
	aStart: number,
	aEnd: number,
	bStart: number,
	bEnd: number,
	isCommon: IsCommon,
	aIndexesF: Indexes, -- update indexes in sequence a of paths in diagonals kF
	iMaxF: number,
	aIndexesR: Indexes,
	iMaxR: number,
	division: Division -- update prop values if return true
): boolean
	local bF = bStart - aStart -- bIndex = bF + aIndex - kF
	local aLength = aEnd - aStart
	local bLength = bEnd - bStart
	local baDeltaLength = bLength - aLength -- kF = kR + baDeltaLength

	-- Range of diagonals in which forward and reverse paths might overlap.
	local kMinOverlapF = -baDeltaLength - (d - 1) -- -(d - 1) <= kR
	local kMaxOverlapF = -baDeltaLength + (d - 1) -- kR <= (d - 1)

	local aIndexPrev1 = 0 -- prev value of [iF - 1] in next iteration

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

	-- The diagonals kF = 2 * iF - d are odd when d is odd and even when d is even.
	-- ROBLOX FIXME? why aren't we just starting iF at 1?
	local iF = 0
	local kF: number = -d
	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 first iteration when iF === 0 and kF === -d always insert.
		-- In last possible iteration when iF === d and kF === d always delete.
		local insert = iF == 0 or (iF ~= d and aIndexPrev1 < aIndexesF[iF + 1])
		-- ROBLOX FIXME? should the values inserted into aIndexesF be 1-based so we don't have to adjust in several places here?
		local aLastPrev = insert and aIndexesF[iF + 1] or aIndexPrev1
		local aFirst: number = insert and aLastPrev -- vertical to insert from b
			or aLastPrev + 1 -- horizontal to delete from a

		-- To get last point of path segment, move along diagonal of common items.
		local bFirst = bF + aFirst - kF
		local nCommonF = countCommonItemsF(aFirst + 1, aEnd, bFirst + 1, bEnd, isCommon)
		local aLast = aFirst + nCommonF

		aIndexPrev1 = aIndexesF[iF + 1]
		aIndexesF[iF + 1] = aLast

		if kMinOverlapF <= kF and kF <= kMaxOverlapF then
			-- Solve for iR of reverse path with (d - 1) changes in diagonal kF:
			-- kR = kF + baDeltaLength
			-- kR = (d - 1) - 2 * iR
			local iR = (d - 1 - (kF + baDeltaLength)) / 2

			-- If this forward path overlaps the reverse path in this diagonal,
			-- then this is the middle change of the index intervals.
			if iR <= iMaxR and aIndexesR[iR + 1] - 1 <= aLast then
				-- Unlike the Myers algorithm which finds only the middle “snake”
				-- this package can find two common subsequences per division.
				-- Last point of previous path segment is on an adjacent diagonal.
				local bLastPrev = bF + aLastPrev - (insert and kF + 1 or kF - 1)

				-- Because of invariant that intervals preceding the middle change
				-- cannot have common items at the end,
				-- move in reverse direction along a diagonal of common items.
				local nCommonR = countCommonItemsR(aStart, aLastPrev, bStart, bLastPrev, isCommon)

				local aIndexPrevFirst = aLastPrev - nCommonR
				local bIndexPrevFirst = bLastPrev - nCommonR

				local aEndPreceding = aIndexPrevFirst + 1
				local bEndPreceding = bIndexPrevFirst + 1

				division.nChangePreceding = d - 1
				if d - 1 == aEndPreceding + bEndPreceding - aStart - bStart then
					-- Optimization: number of changes in reverse direction
					-- is equal to number of items in preceding interval,
					-- therefore it cannot contain any common items.
					division.aEndPreceding = aStart
					division.bEndPreceding = bStart
				else
					division.aEndPreceding = aEndPreceding
					division.bEndPreceding = bEndPreceding
				end

				division.nCommonPreceding = nCommonR
				if nCommonR ~= 0 then
					division.aCommonPreceding = aEndPreceding
					division.bCommonPreceding = bEndPreceding
				end

				division.nCommonFollowing = nCommonF
				if nCommonF ~= 0 then
					division.aCommonFollowing = aFirst + 1
					division.bCommonFollowing = bFirst + 1
				end

				local aStartFollowing = aLast + 1
				local bStartFollowing = bFirst + nCommonF + 1

				division.nChangeFollowing = d - 1
				if d - 1 == aEnd + bEnd - aStartFollowing - bStartFollowing then
					-- Optimization: number of changes in reverse direction
					-- is equal to number of items in following interval,
					-- therefore it cannot contain any common items.
					division.aStartFollowing = aEnd
					division.bStartFollowing = bEnd
				else
					division.aStartFollowing = aStartFollowing
					division.bStartFollowing = bStartFollowing
				end

				return true
			end
		end
		iF = iF + 1
		kF = kF + 2
	end

	return false
end