type MatchCandidate = { candidate: string; score: number }

function findLongestMatch(a: string, b: string, aStart: number, aEnd: number, bStart: number, bEnd: number) {
  let bestI = aStart
  let bestJ = bStart
  let bestSize = 0
  const previous = new Map<number, number>()

  for (let i = aStart; i < aEnd; i++) {
    const current = new Map<number, number>()
    const leftChar = a[i] ?? ''
    for (let j = bStart; j < bEnd; j++) {
      if (leftChar !== (b[j] ?? '')) {
        continue
      }

      const size = (previous.get(j - 1) ?? 0) + 1
      current.set(j, size)
      if (size > bestSize) {
        bestI = i - size + 1
        bestJ = j - size + 1
        bestSize = size
      }
    }
    previous.clear()
    for (const [key, value] of current) {
      previous.set(key, value)
    }
  }

  return { aIndex: bestI, bIndex: bestJ, size: bestSize }
}

function matchingBlocks(a: string, b: string): Array<{ aIndex: number; bIndex: number; size: number }> {
  const queue: Array<[number, number, number, number]> = [[0, a.length, 0, b.length]]
  const out: Array<{ aIndex: number; bIndex: number; size: number }> = []

  while (queue.length > 0) {
    const next = queue.pop()
    if (!next) {
      continue
    }

    const [aStart, aEnd, bStart, bEnd] = next
    const match = findLongestMatch(a, b, aStart, aEnd, bStart, bEnd)
    if (match.size === 0) {
      continue
    }

    out.push(match)

    if (aStart < match.aIndex && bStart < match.bIndex) {
      queue.push([aStart, match.aIndex, bStart, match.bIndex])
    }

    const aMatchEnd = match.aIndex + match.size
    const bMatchEnd = match.bIndex + match.size
    if (aMatchEnd < aEnd && bMatchEnd < bEnd) {
      queue.push([aMatchEnd, aEnd, bMatchEnd, bEnd])
    }
  }

  out.sort((left, right) => left.aIndex - right.aIndex || left.bIndex - right.bIndex)

  const merged: Array<{ aIndex: number; bIndex: number; size: number }> = []
  for (const block of out) {
    const previous = merged.at(-1)
    if (
      previous &&
      previous.aIndex + previous.size === block.aIndex &&
      previous.bIndex + previous.size === block.bIndex
    ) {
      previous.size += block.size
      continue
    }
    merged.push({ ...block })
  }

  merged.push({ aIndex: a.length, bIndex: b.length, size: 0 })
  return merged
}

function similarityRatio(left: string, right: string): number {
  if (left === right) {
    return 1
  }

  const totalLength = left.length + right.length
  if (totalLength === 0) {
    return 1
  }

  const matches = matchingBlocks(left, right).reduce((sum, block) => sum + block.size, 0)
  return (2 * matches) / totalLength
}

export function get_close_matches(
  word: string,
  possibilities: string[] | unknown,
  n: number = 3,
  cutoff: number = 0.6,
): string[] {
  //      discuss at: https://locutus.io/python/difflib/get_close_matches/
  // parity verified: Python 3.12
  //     original by: Kevin van Zonneveld (https://kvz.io)
  //          note 1: Uses a SequenceMatcher-style similarity ratio to rank close string matches.
  //       example 1: get_close_matches('appel', ['ape', 'apple', 'peach', 'puppy'])
  //       returns 1: ['apple', 'ape']
  //       example 2: get_close_matches('wheel', ['while', 'whale', 'whole'], 2)
  //       returns 2: ['whole', 'while']
  //       example 3: get_close_matches('abc', ['xyz'], 3, 0.8)
  //       returns 3: []

  const count = Math.trunc(Number(n))
  const threshold = Number(cutoff)

  if (!Number.isFinite(count) || count <= 0) {
    throw new RangeError('get_close_matches(): n must be a positive integer')
  }

  if (!Number.isFinite(threshold) || threshold < 0 || threshold > 1) {
    throw new RangeError('get_close_matches(): cutoff must be between 0 and 1')
  }

  if (!Array.isArray(possibilities) || possibilities.length === 0) {
    return []
  }

  const query = String(word)
  const scored: MatchCandidate[] = []

  for (let i = 0; i < possibilities.length; i++) {
    const candidate = String(possibilities[i] ?? '')
    const score = similarityRatio(query, candidate)
    if (score >= threshold) {
      scored.push({ candidate, score })
    }
  }

  scored.sort((left, right) => {
    if (right.score !== left.score) {
      return right.score - left.score
    }
    return right.candidate.localeCompare(left.candidate)
  })

  return scored.slice(0, count).map((entry) => entry.candidate)
}