open Js.String

module Ops = struct
  type t =
    | Delete of string * int
    | Insert of string * string * int
    | Replace of string * string * int

  let run op = match op with
    | Delete (str, i) ->
      (slice ~from:0 ~to_:i str) ^ (sliceToEnd ~from:(i + 1) str)
    | Insert (str, char, i) ->
      if i = 0 then char ^ str
      else if i = length str - 1 then str ^ char
      else (slice ~from:0 ~to_:i str) ^ char ^ (sliceToEnd ~from:i str)
    | Replace (str, char, i) ->
      (slice ~from:0 ~to_:i str) ^ char ^ (sliceToEnd ~from:(i + 1) str)
end

let max_safe_int = [%raw "Number.MAX_SAFE_INTEGER"]

let mem f = fun w1 w2 p1 ->
  let dict = Js.Dict.empty () in
  match Js.Dict.get dict w1 with
  | None ->
    let result = f w1 w2 p1 in
    Js.Dict.set dict w1 result;
    result
  | Some num -> num

let rec edit_distance w1 w2 idx =
  let len1, len2 = length w1, length w2 in
  if w1 = w2
    then 0
  else
    let (c1, c2) = (get w1 idx, get w2 idx) in
    if c1 = c2 then edit_distance w1 w2 (idx + 1)
    else
      let open Ops in
      if len1 > len2 then
        let delete =
          edit_distance (run (Delete (w1, idx))) w2 (idx - 1)
        in
        1 + if idx >= len2
          then delete
        else
          Js.Math.min_int (edit_distance (run (Replace (w1, c2, idx))) w2 (idx + 1)) delete
      else if len1 < len2 then
        let insert =
          edit_distance (run (Insert (w1, c2, idx))) w2 (idx + 1)
        in
        1 + if idx >= len2
          then insert
        else
          Js.Math.min_int (edit_distance (run (Replace (w1, c2, idx))) w2 (idx + 1)) insert
      else
        1 + Js.Math.min_int
          (edit_distance (run (Insert (w1, c2, idx))) w2 (idx + 1))
          (Js.Math.min_int
            (edit_distance (run (Replace (w1, c2, idx))) w2 (idx + 1))
            (edit_distance (run (Delete (w1, idx))) w2 (idx - 1)))

let minDistance w1 w2 = (mem edit_distance) w1 w2 0