/**
 * Levenshtein distance utility
 * Used for fuzzy matching block/item names for inventory operations.
 * Inspired by runi95/turtle-control-panel utility.
 */

/**
 * Compute the Levenshtein edit distance between two strings.
 * @param {string} a - First string
 * @param {string} b - Second string
 * @returns {number} The edit distance
 */
export function levenshtein(a, b) {
  if (a === b) return 0;
  if (a.length === 0) return b.length;
  if (b.length === 0) return a.length;

  // Use a single-row approach for memory efficiency
  const aLen = a.length;
  const bLen = b.length;
  const row = new Array(bLen + 1);

  // Initialize the first row (distance from empty string to b[0..j])
  for (let j = 0; j <= bLen; j++) {
    row[j] = j;
  }

  for (let i = 1; i <= aLen; i++) {
    let prev = i; // row[0] for this iteration = i
    for (let j = 1; j <= bLen; j++) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
      const val = Math.min(
        row[j] + 1,       // deletion
        prev + 1,          // insertion
        row[j - 1] + cost  // substitution
      );
      row[j - 1] = prev;
      prev = val;
    }
    row[bLen] = prev;
  }

  return row[bLen];
}

/**
 * Find the best match for a query string among candidates using Levenshtein distance.
 * @param {string} query - The search term
 * @param {string[]} candidates - Array of candidate strings
 * @param {number} maxDistance - Maximum acceptable distance (default: Infinity)
 * @returns {{ match: string|null, distance: number }} Best match and its distance
 */
export function findBestMatch(query, candidates, maxDistance = Infinity) {
  let bestMatch = null;
  let bestDistance = Infinity;

  const lowerQuery = query.toLowerCase();

  for (const candidate of candidates) {
    const lowerCandidate = candidate.toLowerCase();

    // Exact substring match is distance 0
    if (lowerCandidate.includes(lowerQuery) || lowerQuery.includes(lowerCandidate)) {
      const dist = Math.abs(lowerCandidate.length - lowerQuery.length);
      if (dist < bestDistance) {
        bestDistance = dist;
        bestMatch = candidate;
      }
      continue;
    }

    const dist = levenshtein(lowerQuery, lowerCandidate);
    if (dist < bestDistance && dist <= maxDistance) {
      bestDistance = dist;
      bestMatch = candidate;
    }
  }

  return { match: bestMatch, distance: bestDistance };
}

/**
 * Find all matches within a given distance.
 * @param {string} query - The search term
 * @param {string[]} candidates - Array of candidate strings
 * @param {number} maxDistance - Maximum acceptable distance
 * @returns {Array<{match: string, distance: number}>} Matches sorted by distance
 */
export function findAllMatches(query, candidates, maxDistance = 3) {
  const lowerQuery = query.toLowerCase();
  const matches = [];

  for (const candidate of candidates) {
    const lowerCandidate = candidate.toLowerCase();

    // Exact substring match
    if (lowerCandidate.includes(lowerQuery) || lowerQuery.includes(lowerCandidate)) {
      matches.push({ match: candidate, distance: 0 });
      continue;
    }

    const dist = levenshtein(lowerQuery, lowerCandidate);
    if (dist <= maxDistance) {
      matches.push({ match: candidate, distance: dist });
    }
  }

  return matches.sort((a, b) => a.distance - b.distance);
}