const normalizeSearchText = (value: string) =>
	value.normalize('NFKC').trim().toLocaleLowerCase('en-US');

const editDistance = (left: string, right: string) => {
	let previous = Array.from(
		{ length: right.length + 1 },
		(_, index) => index
	);
	for (
		let leftIndex = 1;
		leftIndex <= left.length;
		leftIndex += 1
	) {
		const current = [leftIndex];
		for (
			let rightIndex = 1;
			rightIndex <= right.length;
			rightIndex += 1
		) {
			current[rightIndex] = Math.min(
				current[rightIndex - 1] + 1,
				previous[rightIndex] + 1,
				previous[rightIndex - 1] +
					Number(left[leftIndex - 1] !== right[rightIndex - 1])
			);
		}
		previous = current;
	}
	return previous[right.length];
};

export const matchesCatalogQuery = (
	query: string,
	values: readonly string[]
) => {
	const needle = normalizeSearchText(query);
	if (!needle) return true;
	const haystacks = values.map(normalizeSearchText);
	if (haystacks.some((value) => value.includes(needle)))
		return true;
	if (needle.length < 4) return false;
	const maximumDistance = needle.length >= 6 ? 2 : 1;
	return haystacks
		.flatMap((value) => [value, ...value.split(/[\s-]+/)])
		.some(
			(value) =>
				Math.abs(value.length - needle.length) <=
					maximumDistance &&
				editDistance(value, needle) <= maximumDistance
		);
};