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


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

	-- Range of diagonals in which forward and reverse paths might overlap.
	local kMinOverlapR = baDeltaLength - d -- -d <= kF
	local kMaxOverlapR = baDeltaLength + d -- kF <= d

	local aIndexPrev1 = NOT_YET_SET -- prev value of [iR - 1] in next iteration

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

	-- The diagonals kR = d - 2 * iR are odd when d is odd and even when d is even.
	local iR = 0
	local kR = d
	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 first iteration when iR === 0 and kR === d always insert.
		-- In last possible iteration when iR === d and kR === -d always delete.
		-- ROBLOX FIXME? should the values inserted into aIndexesF be 1-based so we don't have to adjust in several places here?
		local insert = iR == 0 or (iR ~= d and aIndexesR[iR + 1] < aIndexPrev1)
		local aLastPrev = insert and aIndexesR[iR + 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 = bR + aFirst - kR
		local nCommonR = countCommonItemsR(aStart, aFirst - 1, bStart, bFirst - 1, isCommon)
		local aLast = aFirst - nCommonR

		aIndexPrev1 = aIndexesR[iR + 1]
		aIndexesR[iR + 1] = aLast

		if kMinOverlapR <= kR and kR <= kMaxOverlapR then
			-- Solve for iF of forward path with d changes in diagonal kR:
			-- kF = kR - baDeltaLength
			-- kF = 2 * iF - d
			local iF = (d + (kR - baDeltaLength)) / 2

			-- If this reverse path overlaps the forward path in this diagonal,
			-- then this is a middle change of the index intervals.
			if iF <= iMaxF and aLast - 1 <= aIndexesF[iF + 1] then
				local bLast = bFirst - nCommonR

				division.nChangePreceding = d
				if d == aLast + bLast - 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 = aLast
					division.bEndPreceding = bLast
				end

				division.nCommonPreceding = nCommonR
				if nCommonR ~= 0 then
					-- The last point of reverse path segment is start of common subsequence.
					division.aCommonPreceding = aLast
					division.bCommonPreceding = bLast
				end

				division.nChangeFollowing = d - 1
				if d == 1 then
					-- There is no previous path segment.
					division.nCommonFollowing = 0
					division.aStartFollowing = aEnd
					division.bStartFollowing = bEnd
				else
					-- 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 = bR + aLastPrev - (insert and kR - 1 or kR + 1)

					-- Because of invariant that intervals following the middle change
					-- cannot have common items at the start,
					-- move in forward direction along a diagonal of common items.
					local nCommonF = countCommonItemsF(aLastPrev, aEnd, bLastPrev, bEnd, isCommon)

					division.nCommonFollowing = nCommonF
					if nCommonF ~= 0 then
						-- The last point of reverse path segment is start of common subsequence.
						division.aCommonFollowing = aLastPrev
						division.bCommonFollowing = bLastPrev
					end

					local aStartFollowing = aLastPrev + nCommonF -- aFirstPrev
					local bStartFollowing = bLastPrev + nCommonF -- bFirstPrev

					if d - 1 == aEnd + bEnd - aStartFollowing - bStartFollowing then
						-- Optimization: number of changes in forward 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
				end

				return true
			end
		end
		iR += 1
		kR -= 2
	end

	return false
end