Fuzzy Searches

function searchContains(text, query) {
	const normalized = text.toLowerCase();
	const normalizedQuery = query.toLowerCase();
	return normalized.includes(normalizedQuery);
}

// Example: searchContains("Elderberry", "berry") → true

function hammingDistance(needle, haystack) {
	if (needle.length !== haystack.length) {
		return Infinity;
	}
	
	let distance = 0;
	for (let i = 0; i < needle.length; i++) {
		if (needle[i] !== haystack[i]) {
			distance++;
		}
	}
	return distance;
}

// Sliding window to find best match
function slidingHamming(needle, haystack) {
	let bestDistance = Infinity;
	for (let offset = 0; offset <= haystack.length - needle.length; offset++) {
		const segment = haystack.slice(offset, offset + needle.length);
		const distance = hammingDistance(needle, segment);
		if (distance < bestDistance) {
			bestDistance = distance;
			if (bestDistance === 0) break;
		}
	}
	return bestDistance;
}

// Memory-optimized version: O(min(n,m)) space instead of O(n*m)
function levenshteinDistance(source, target, maxDistance = Infinity) {
	// Early exit if length difference exceeds threshold
	if (Math.abs(source.length - target.length) > maxDistance) {
		return Infinity;
	}
	
	// KEY OPTIMIZATION: Use shorter string for rows to minimize memory
	// This reduces space from O(n*m) to O(min(n,m))
	if (source.length > target.length) {
		[source, target] = [target, source];
	}
	
	// KEY OPTIMIZATION: Only store 2 rows instead of full matrix
	// Naive approach: const matrix = Array(n+1).fill(Array(m+1)) // O(n*m) space
	// Optimized: only need previous and current row // O(min(n,m)) space
	const previousRow = new Array(source.length + 1).fill(0);
	const currentRow = new Array(source.length + 1).fill(0);
	
	// Initialize first row: distance from empty string
	for (let i = 0; i <= source.length; i++) {
		previousRow[i] = i;
	}
	
	// Fill matrix row by row, reusing the two-row buffer
	for (let row = 1; row <= target.length; row++) {
		currentRow[0] = row;
		let rowMin = currentRow[0];
		
		for (let col = 1; col <= source.length; col++) {
			const cost = source[col - 1] === target[row - 1] ? 0 : 1;
			
			// Standard DP recurrence: min of 3 operations
			currentRow[col] = Math.min(
				previousRow[col] + 1,      // deletion
				currentRow[col - 1] + 1,    // insertion
				previousRow[col - 1] + cost // substitution
			);
			
			rowMin = Math.min(rowMin, currentRow[col]);
		}
		
		// Early termination if row minimum exceeds threshold
		if (rowMin > maxDistance) {
			return Infinity;
		}
		
		// Swap rows: current becomes previous for next iteration
		// This reuses memory instead of allocating new rows
		for (let i = 0; i <= source.length; i++) {
			previousRow[i] = currentRow[i];
		}
	}
	
	return previousRow[source.length];
}

// Example: levenshteinDistance("kitten", "sitting") → 3
// Memory: O(6) instead of O(42) for full matrix

import { searchLevenshtein } from "@/scripts/FuzzySearch";

const fruits = ["Apple", "Banana", "Cherry", "Dragonfruit", "Elderberry"];
const misspellings = ["strawbery", "rasberry", "kiwwi"];

const suggestions = misspellings.map((word) => {
	const [best] = searchLevenshtein(fruits.map((title) => ({ title })), word);
	return { word, suggestion: best?.title, edits: best?.score };
});

function jaroWinklerSimilarity(source, target, prefixScale = 0.1) {
	if (!source.length || !target.length) return 0;
	if (source === target) return 1;
	
	// Match window: characters within this distance can match
	const matchDistance = Math.floor(Math.max(source.length, target.length) / 2) - 1;
	const sourceMatches = new Array(source.length).fill(false);
	const targetMatches = new Array(target.length).fill(false);
	
	// Find matching characters
	let matches = 0;
	for (let i = 0; i < source.length; i++) {
		const start = Math.max(0, i - matchDistance);
		const end = Math.min(i + matchDistance + 1, target.length);
		
		for (let j = start; j < end; j++) {
			if (targetMatches[j] || source[i] !== target[j]) continue;
			sourceMatches[i] = true;
			targetMatches[j] = true;
			matches++;
			break;
		}
	}
	
	if (!matches) return 0;
	
	// Count transpositions (characters that match but are out of order)
	let transpositions = 0;
	for (let i = 0, j = 0; i < source.length; i++) {
		if (!sourceMatches[i]) continue;
		while (!targetMatches[j]) j++;
		if (source[i] !== target[j]) transpositions++;
		j++;
	}
	transpositions /= 2;
	
	// Calculate Jaro similarity
	const jaro = (
		matches / source.length +
		matches / target.length +
		(matches - transpositions) / matches
	) / 3;
	
	// Winkler modification: boost score for common prefix
	let prefixLength = 0;
	const maxPrefix = Math.min(4, Math.min(source.length, target.length));
	for (let i = 0; i < maxPrefix && source[i] === target[i]; i++) {
		prefixLength++;
	}
	
	return jaro + prefixLength * prefixScale * (1 - jaro);
}

function damerauLevenshteinDistance(source, target, maxDistance = Infinity) {
	if (Math.abs(source.length - target.length) > maxDistance) {
		return Infinity;
	}
	
	const rows = source.length + 1;
	const cols = target.length + 1;
	const matrix = Array.from({ length: rows }, () => 
		new Array(cols).fill(0)
	);
	
	// Initialize first row and column
	for (let i = 0; i < rows; i++) matrix[i][0] = i;
	for (let j = 0; j < cols; j++) matrix[0][j] = j;
	
	// Fill matrix
	for (let i = 1; i < rows; i++) {
		let rowMin = Infinity;
		for (let j = 1; j < cols; j++) {
			const cost = source[i - 1] === target[j - 1] ? 0 : 1;
			
			// Standard Levenshtein operations
			matrix[i][j] = Math.min(
				matrix[i - 1][j] + 1,      // deletion
				matrix[i][j - 1] + 1,      // insertion
				matrix[i - 1][j - 1] + cost // substitution
			);
			
			// Damerau addition: transposition (swap adjacent chars)
			if (i > 1 && j > 1 &&
				source[i - 1] === target[j - 2] &&
				source[i - 2] === target[j - 1]) {
				matrix[i][j] = Math.min(
					matrix[i][j],
					matrix[i - 2][j - 2] + cost
				);
			}
			
			rowMin = Math.min(rowMin, matrix[i][j]);
		}
		
		// Early termination
		if (rowMin > maxDistance) return Infinity;
	}
	
	return matrix[rows - 1][cols - 1];
}