-- Given index intervals and input function to compare items at indexes,
-- divide at the middle change.
--
-- DO NOT CALL if start === end, because interval cannot contain common items
-- and because this function will throw the “no overlap” error.


local function divide(
	nChange: number,
	aStart: number,
	aEnd: number,
	bStart: number,
	bEnd: number,
	isCommon: IsCommon,
	aIndexesF: Indexes, -- temporary memory, not input nor output
	aIndexesR: Indexes, -- temporary memory, not input nor output
	division: Division -- output
): ()
	local bF = bStart - aStart -- bIndex = bF + aIndex - kF
	local bR = bEnd - aEnd -- bIndex = bR + aIndex - kR
	local aLength = aEnd - aStart
	local bLength = bEnd - bStart

	-- Because graph has square or portrait orientation,
	-- length difference is minimum number of items to insert from b.
	-- Corresponding forward and reverse diagonals in graph
	-- depend on length difference of the sequences:
	-- kF = kR - baDeltaLength
	-- kR = kF + baDeltaLength
	local baDeltaLength = bLength - aLength

	-- Optimization: max diagonal in graph intersects corner of shorter side.
	local iMaxF = aLength
	local iMaxR = aLength

	-- Initialize no changes yet in forward or reverse direction:
	aIndexesF[1] = aStart - 1 -- at open start of interval, outside closed start
	aIndexesR[1] = aEnd -- at open end of interval

	if baDeltaLength % 2 == 0 then
		-- The number of changes in paths is 2 * d if length difference is even.
		-- ROBLOX deviation: lua treats 0 as a true value
		local dMin = (nChange ~= 0 and nChange or baDeltaLength) / 2
		local dMax = (aLength + bLength) / 2

		for d = 1, dMax do
			iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF)

			if d < dMin then
				iMaxR = extendPathsR(d, aStart, bStart, bR, isCommon, aIndexesR, iMaxR)
				-- If a reverse path overlaps a forward path in the same diagonal,
				-- return a division of the index intervals at the middle change.
			elseif
				extendOverlappablePathsR(
					d,
					aStart,
					aEnd,
					bStart,
					bEnd,
					isCommon,
					aIndexesF,
					iMaxF,
					aIndexesR,
					iMaxR,
					division
				)
			then
				return
			end
		end
	else
		-- The number of changes in paths is 2 * d - 1 if length difference is odd.
		local dMin = ((nChange ~= 0 and nChange or baDeltaLength) + 1) / 2
		local dMax = (aLength + bLength + 1) / 2

		-- Unroll first half iteration so loop extends the relevant pairs of paths.
		-- Because of invariant that intervals have no common items at start or end,
		-- and limitation not to call divide with empty intervals,
		-- therefore it cannot be called if a forward path with one change
		-- would overlap a reverse path with no changes, even if dMin === 1.
		local d = 1
		iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF)

		d = d + 1
		while d <= dMax do
			iMaxR = extendPathsR(d - 1, aStart, bStart, bR, isCommon, aIndexesR, iMaxR)

			if d < dMin then
				iMaxF = extendPathsF(d, aEnd, bEnd, bF, isCommon, aIndexesF, iMaxF)
				-- If a forward path overlaps a reverse path in the same diagonal,
				-- return a division of the index intervals at the middle change.
			elseif
				extendOverlappablePathsF(
					d,
					aStart,
					aEnd,
					bStart,
					bEnd,
					isCommon,
					aIndexesF,
					iMaxF,
					aIndexesR,
					iMaxR,
					division
				)
			then
				return
			end
			d = d + 1
		end
	end

	error(string.format("%s: no overlap aStart=%i aEnd=%i bStart=%i bEnd=%i", pkg, aStart, aEnd, bStart, bEnd))
end