src/recurse.js

import assert from 'assert';

import {ValueError} from '@failure-abstraction/error';

import twoWayAlloc from './twoWayAlloc.js';
import twoWayScan from './twoWayScan.js';

import RecurseDeeper from './RecurseDeeper.js';
import StackEntry from './StackEntry.js';

/**
 * Recurse.
 *
 * @param {number} MAX
 * @param {Function} eq
 * @param {number} li
 * @param {number} lj
 * @param {number} ri
 * @param {number} rj
 * @return {IterableIterator}
 */
export default function recurse(MAX, eq, li, lj, ri, rj) {
	assert(MAX >= 0);
	assert(lj - li + rj - ri > MAX);
	if (li === lj || ri === rj) {
		assert(lj - li > MAX || rj - ri > MAX);
		throw new ValueError();
	}

	assert(li < lj);
	assert(ri < rj);
	assert(!eq(li, ri));
	assert(!eq(lj - 1, rj - 1));

	const {V, centerF, centerB} = twoWayAlloc(MAX, li, lj, ri, rj);

	const split = twoWayScan(MAX, V, centerF, centerB, eq, li, lj, ri, rj);

	const k = split.k;
	const xBegin = split.xBegin;
	const xEnd = split.xEnd;
	const distanceLeft = split.distanceLeft;
	const distance = split.distance;
	const distanceRight = (distance - distanceLeft) | 0;

	console.debug({k, xBegin, xEnd, distance});

	if (distance === -1) throw new ValueError();

	assert(distance > 0);
	const maxDistance =
		(((lj - li) | 0) + ((((rj - ri) | 0) - ((xEnd - xBegin) << 1)) | 0)) | 0;
	if (distance === maxDistance) {
		// Early exit when there is no match in the recursive calls
		assert(xBegin < xEnd);
		return [
			[li, xBegin, ri, (xBegin - k) | 0],
			[xEnd, lj, (xEnd - k) | 0, rj],
		][Symbol.iterator]();
	}

	assert(distance < maxDistance);
	return new RecurseDeeper(
		V,
		[
			new StackEntry(distanceRight, xEnd, lj, (xEnd - k) | 0, rj),
			new StackEntry(distanceLeft, li, xBegin, ri, (xBegin - k) | 0),
		],
		eq,
	);
}