///|
priv struct DoubleMetaphoneState {
  input : String
  index : Int
  primary : String
  alternate : String
  maximum : Int
  slavo_germanic : Bool
}

///|
fn dm_char(input : String, index : Int) -> UInt16 {
  if index < 0 || index >= input.length() {
    0
  } else {
    input[index]
  }
}

///|
fn dm_contains_any(
  input : String,
  index : Int,
  patterns : Array[String],
) -> Bool {
  for pattern in patterns {
    if ascii_starts_with_at(input, index, pattern) {
      return true
    }
  }
  false
}

///|
fn dm_has_anywhere(input : String, pattern : String) -> Bool {
  if pattern.length() == 0 {
    return true
  }
  for i = 0; i + pattern.length() <= input.length(); i = i + 1 {
    if ascii_starts_with_at(input, i, pattern) {
      return true
    }
  }
  false
}

///|
fn dm_is_vowel(code : UInt16) -> Bool {
  code == 65 ||
  code == 69 ||
  code == 73 ||
  code == 79 ||
  code == 85 ||
  code == 89
}

///|
fn dm_is_slavo_germanic(input : String) -> Bool {
  dm_has_anywhere(input, "W") ||
  dm_has_anywhere(input, "K") ||
  dm_has_anywhere(input, "CZ") ||
  dm_has_anywhere(input, "WITZ")
}

///|
fn dm_has_silent_start(input : String) -> Bool {
  dm_contains_any(input, 0, ["GN", "KN", "PN", "WR", "PS"])
}

///|
fn dm_move(
  state : DoubleMetaphoneState,
  index : Int,
  primary : String,
  alternate : String,
) -> DoubleMetaphoneState {
  {
    input: state.input,
    index,
    primary: append_bounded(state.primary, primary, state.maximum),
    alternate: append_bounded(state.alternate, alternate, state.maximum),
    maximum: state.maximum,
    slavo_germanic: state.slavo_germanic,
  }
}

///|
fn dm_same(
  state : DoubleMetaphoneState,
  index : Int,
  value : String,
) -> DoubleMetaphoneState {
  dm_move(state, index, value, value)
}

///|
fn dm_primary_only(
  state : DoubleMetaphoneState,
  index : Int,
  value : String,
) -> DoubleMetaphoneState {
  dm_move(state, index, value, "")
}

///|
fn dm_alternate_only(
  state : DoubleMetaphoneState,
  index : Int,
  value : String,
) -> DoubleMetaphoneState {
  dm_move(state, index, "", value)
}

///|
fn dm_condition_c0(input : String, index : Int) -> Bool {
  if ascii_starts_with_at(input, index, "CHIA") {
    return true
  }
  if index <= 1 ||
    dm_is_vowel(dm_char(input, index - 2)) ||
    !ascii_starts_with_at(input, index - 1, "ACH") {
    return false
  }
  let after = dm_char(input, index + 2)
  (after != 73 && after != 69) ||
  dm_contains_any(input, index - 2, ["BACHER", "MACHER"])
}

///|
fn dm_condition_ch0(input : String, index : Int) -> Bool {
  index == 0 &&
  (
    dm_contains_any(input, 1, ["HARAC", "HARIS"]) ||
    dm_contains_any(input, 1, ["HOR", "HYM", "HIA", "HEM"])
  ) &&
  !ascii_starts_with_at(input, 0, "CHORE")
}

///|
fn dm_condition_ch1(input : String, index : Int) -> Bool {
  ascii_starts_with_at(input, 0, "VAN ") ||
  ascii_starts_with_at(input, 0, "VON ") ||
  ascii_starts_with_at(input, 0, "SCH") ||
  dm_contains_any(input, index - 2, ["ORCHES", "ARCHIT", "ORCHID"]) ||
  dm_contains_any(input, index + 2, ["T", "S"]) ||
  (
    (index == 0 || dm_contains_any(input, index - 1, ["A", "O", "U", "E"])) &&
    (
      index + 2 >= input.length() ||
      dm_contains_any(input, index + 2, [
        "L", "R", "N", "M", "B", "H", "F", "V", "W", " ",
      ])
    )
  )
}

///|
fn dm_handle_ch(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if i > 0 && ascii_starts_with_at(state.input, i, "CHAE") {
    dm_move(state, i + 2, "K", "X")
  } else if dm_condition_ch0(state.input, i) || dm_condition_ch1(state.input, i) {
    dm_same(state, i + 2, "K")
  } else if i > 0 {
    if ascii_starts_with_at(state.input, 0, "MC") {
      dm_same(state, i + 2, "K")
    } else {
      dm_move(state, i + 2, "X", "K")
    }
  } else {
    dm_same(state, i + 2, "X")
  }
}

///|
fn dm_handle_cc(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if dm_contains_any(state.input, i + 2, ["I", "E", "H"]) &&
    !ascii_starts_with_at(state.input, i + 2, "HU") {
    if (i == 1 && dm_char(state.input, 0) == 65) ||
      dm_contains_any(state.input, i - 1, ["UCCEE", "UCCES"]) {
      dm_same(state, i + 3, "KS")
    } else {
      dm_same(state, i + 3, "X")
    }
  } else {
    dm_same(state, i + 2, "K")
  }
}

///|
fn dm_handle_c(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if dm_condition_c0(state.input, i) {
    dm_same(state, i + 2, "K")
  } else if i == 0 && ascii_starts_with_at(state.input, 0, "CAESAR") {
    dm_same(state, 2, "S")
  } else if ascii_starts_with_at(state.input, i, "CH") {
    dm_handle_ch(state)
  } else if ascii_starts_with_at(state.input, i, "CZ") &&
    !ascii_starts_with_at(state.input, i - 2, "WICZ") {
    dm_move(state, i + 2, "S", "X")
  } else if ascii_starts_with_at(state.input, i + 1, "CIA") {
    dm_same(state, i + 3, "X")
  } else if ascii_starts_with_at(state.input, i, "CC") &&
    !(i == 1 && dm_char(state.input, 0) == 77) {
    dm_handle_cc(state)
  } else if dm_contains_any(state.input, i, ["CK", "CG", "CQ"]) {
    dm_same(state, i + 2, "K")
  } else if dm_contains_any(state.input, i, ["CI", "CE", "CY"]) {
    if dm_contains_any(state.input, i, ["CIO", "CIE", "CIA"]) {
      dm_move(state, i + 2, "S", "X")
    } else {
      dm_same(state, i + 2, "S")
    }
  } else if dm_contains_any(state.input, i + 1, [" C", " Q", " G"]) {
    dm_same(state, i + 3, "K")
  } else if dm_contains_any(state.input, i + 1, ["C", "K", "Q"]) &&
    !dm_contains_any(state.input, i + 1, ["CE", "CI"]) {
    dm_same(state, i + 2, "K")
  } else {
    dm_same(state, i + 1, "K")
  }
}

///|
fn dm_handle_d(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if ascii_starts_with_at(state.input, i, "DG") {
    if dm_contains_any(state.input, i + 2, ["I", "E", "Y"]) {
      dm_same(state, i + 3, "J")
    } else {
      dm_same(state, i + 2, "TK")
    }
  } else if dm_contains_any(state.input, i, ["DT", "DD"]) {
    dm_same(state, i + 2, "T")
  } else {
    dm_same(state, i + 1, "T")
  }
}

///|
fn dm_handle_gh(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if i > 0 && !dm_is_vowel(dm_char(state.input, i - 1)) {
    dm_same(state, i + 2, "K")
  } else if i == 0 {
    if dm_char(state.input, i + 2) == 73 {
      dm_same(state, i + 2, "J")
    } else {
      dm_same(state, i + 2, "K")
    }
  } else if (i > 1 && dm_contains_any(state.input, i - 2, ["B", "H", "D"])) ||
    (i > 2 && dm_contains_any(state.input, i - 3, ["B", "H", "D"])) ||
    (i > 3 && dm_contains_any(state.input, i - 4, ["B", "H"])) {
    dm_same(state, i + 2, "")
  } else if i > 2 &&
    dm_char(state.input, i - 1) == 85 &&
    dm_contains_any(state.input, i - 3, ["C", "G", "L", "R", "T"]) {
    dm_same(state, i + 2, "F")
  } else if i > 0 && dm_char(state.input, i - 1) != 73 {
    dm_same(state, i + 2, "K")
  } else {
    dm_same(state, i + 2, "")
  }
}

///|
fn dm_handle_g(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  let next = dm_char(state.input, i + 1)
  if next == 72 {
    dm_handle_gh(state)
  } else if next == 78 {
    if i == 1 && dm_is_vowel(dm_char(state.input, 0)) && !state.slavo_germanic {
      dm_move(state, i + 2, "KN", "N")
    } else if !ascii_starts_with_at(state.input, i + 2, "EY") &&
      !state.slavo_germanic {
      dm_move(state, i + 2, "N", "KN")
    } else {
      dm_same(state, i + 2, "KN")
    }
  } else if ascii_starts_with_at(state.input, i + 1, "LI") &&
    !state.slavo_germanic {
    dm_move(state, i + 2, "KL", "L")
  } else if i == 0 &&
    (
      next == 89 ||
      dm_contains_any(state.input, 1, [
        "ES", "EP", "EB", "EL", "EY", "IB", "IL", "IN", "IE", "EI", "ER",
      ])
    ) {
    dm_move(state, i + 2, "K", "J")
  } else if (ascii_starts_with_at(state.input, i + 1, "ER") || next == 89) &&
    !dm_contains_any(state.input, 0, ["DANGER", "RANGER", "MANGER"]) &&
    !dm_contains_any(state.input, i - 1, ["E", "I"]) &&
    !dm_contains_any(state.input, i - 1, ["RGY", "OGY"]) {
    dm_move(state, i + 2, "K", "J")
  } else if dm_contains_any(state.input, i + 1, ["E", "I", "Y"]) ||
    dm_contains_any(state.input, i - 1, ["AGGI", "OGGI"]) {
    if dm_contains_any(state.input, 0, ["VAN ", "VON ", "SCH"]) ||
      ascii_starts_with_at(state.input, i + 1, "ET") {
      dm_same(state, i + 2, "K")
    } else if ascii_starts_with_at(state.input, i + 1, "IER") {
      dm_same(state, i + 2, "J")
    } else {
      dm_move(state, i + 2, "J", "K")
    }
  } else {
    dm_same(state, if next == 71 { i + 2 } else { i + 1 }, "K")
  }
}

///|
fn dm_handle_h(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if (i == 0 || dm_is_vowel(dm_char(state.input, i - 1))) &&
    dm_is_vowel(dm_char(state.input, i + 1)) {
    dm_same(state, i + 2, "H")
  } else {
    dm_same(state, i + 1, "")
  }
}

///|
fn dm_handle_j(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if ascii_starts_with_at(state.input, i, "JOSE") ||
    ascii_starts_with_at(state.input, 0, "SAN ") {
    if (
        i == 0 &&
        (dm_char(state.input, i + 4) == 32 || state.input.length() == 4)
      ) ||
      ascii_starts_with_at(state.input, 0, "SAN ") {
      dm_same(state, i + 1, "H")
    } else {
      dm_move(state, i + 1, "J", "H")
    }
  } else {
    let next_index = if dm_char(state.input, i + 1) == 74 {
      i + 2
    } else {
      i + 1
    }
    if i == 0 {
      dm_move(state, next_index, "J", "A")
    } else if dm_is_vowel(dm_char(state.input, i - 1)) &&
      !state.slavo_germanic &&
      (dm_char(state.input, i + 1) == 65 || dm_char(state.input, i + 1) == 79) {
      dm_move(state, next_index, "J", "H")
    } else if i == state.input.length() - 1 {
      dm_primary_only(state, next_index, "J")
    } else if !dm_contains_any(state.input, i + 1, [
        "L", "T", "K", "S", "N", "M", "B", "Z",
      ]) &&
      !dm_contains_any(state.input, i - 1, ["S", "K", "L"]) {
      dm_same(state, next_index, "J")
    } else {
      dm_same(state, next_index, "")
    }
  }
}

///|
fn dm_condition_l0(input : String, index : Int) -> Bool {
  (
    index == input.length() - 3 &&
    dm_contains_any(input, index - 1, ["ILLO", "ILLA", "ALLE"])
  ) ||
  (
    (
      dm_contains_any(input, input.length() - 2, ["AS", "OS"]) ||
      dm_contains_any(input, input.length() - 1, ["A", "O"])
    ) &&
    ascii_starts_with_at(input, index - 1, "ALLE")
  )
}

///|
fn dm_handle_l(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if dm_char(state.input, i + 1) == 76 {
    if dm_condition_l0(state.input, i) {
      dm_primary_only(state, i + 2, "L")
    } else {
      dm_same(state, i + 2, "L")
    }
  } else {
    dm_same(state, i + 1, "L")
  }
}

///|
fn dm_handle_p(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if dm_char(state.input, i + 1) == 72 {
    dm_same(state, i + 2, "F")
  } else {
    dm_same(
      state,
      if dm_contains_any(state.input, i + 1, ["P", "B"]) {
        i + 2
      } else {
        i + 1
      },
      "P",
    )
  }
}

///|
fn dm_handle_r(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  let next_index = if dm_char(state.input, i + 1) == 82 { i + 2 } else { i + 1 }
  if i == state.input.length() - 1 &&
    !state.slavo_germanic &&
    ascii_starts_with_at(state.input, i - 2, "IE") &&
    !dm_contains_any(state.input, i - 4, ["ME", "MA"]) {
    dm_alternate_only(state, next_index, "R")
  } else {
    dm_same(state, next_index, "R")
  }
}

///|
fn dm_handle_sc(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if dm_char(state.input, i + 2) == 72 {
    if dm_contains_any(state.input, i + 3, ["OO", "ER", "EN", "UY", "ED", "EM"]) {
      if dm_contains_any(state.input, i + 3, ["ER", "EN"]) {
        dm_move(state, i + 3, "X", "SK")
      } else {
        dm_same(state, i + 3, "SK")
      }
    } else if i == 0 &&
      !dm_is_vowel(dm_char(state.input, 3)) &&
      dm_char(state.input, 3) != 87 {
      dm_move(state, i + 3, "X", "S")
    } else {
      dm_same(state, i + 3, "X")
    }
  } else if dm_contains_any(state.input, i + 2, ["I", "E", "Y"]) {
    dm_same(state, i + 3, "S")
  } else {
    dm_same(state, i + 3, "SK")
  }
}

///|
fn dm_handle_s(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if dm_contains_any(state.input, i - 1, ["ISL", "YSL"]) {
    dm_same(state, i + 1, "")
  } else if i == 0 && ascii_starts_with_at(state.input, 0, "SUGAR") {
    dm_move(state, i + 1, "X", "S")
  } else if ascii_starts_with_at(state.input, i, "SH") {
    if dm_contains_any(state.input, i + 1, ["HEIM", "HOEK", "HOLM", "HOLZ"]) {
      dm_same(state, i + 2, "S")
    } else {
      dm_same(state, i + 2, "X")
    }
  } else if dm_contains_any(state.input, i, ["SIO", "SIA", "SIAN"]) {
    if state.slavo_germanic {
      dm_same(state, i + 3, "S")
    } else {
      dm_move(state, i + 3, "S", "X")
    }
  } else if (i == 0 && dm_contains_any(state.input, 1, ["M", "N", "L", "W"])) ||
    dm_char(state.input, i + 1) == 90 {
    dm_move(
      state,
      if dm_char(state.input, i + 1) == 90 {
        i + 2
      } else {
        i + 1
      },
      "S",
      "X",
    )
  } else if ascii_starts_with_at(state.input, i, "SC") {
    dm_handle_sc(state)
  } else {
    let next_index = if dm_contains_any(state.input, i + 1, ["S", "Z"]) {
      i + 2
    } else {
      i + 1
    }
    if i == state.input.length() - 1 &&
      dm_contains_any(state.input, i - 2, ["AI", "OI"]) {
      dm_alternate_only(state, next_index, "S")
    } else {
      dm_same(state, next_index, "S")
    }
  }
}

///|
fn dm_handle_t(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if ascii_starts_with_at(state.input, i, "TION") ||
    dm_contains_any(state.input, i, ["TIA", "TCH"]) {
    dm_same(state, i + 3, "X")
  } else if ascii_starts_with_at(state.input, i, "TH") ||
    ascii_starts_with_at(state.input, i, "TTH") {
    if dm_contains_any(state.input, i + 2, ["OM", "AM"]) ||
      dm_contains_any(state.input, 0, ["VAN ", "VON ", "SCH"]) {
      dm_same(state, i + 2, "T")
    } else {
      dm_move(state, i + 2, "0", "T")
    }
  } else {
    dm_same(
      state,
      if dm_contains_any(state.input, i + 1, ["T", "D"]) {
        i + 2
      } else {
        i + 1
      },
      "T",
    )
  }
}

///|
fn dm_handle_w(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if ascii_starts_with_at(state.input, i, "WR") {
    dm_same(state, i + 2, "R")
  } else if i == 0 &&
    (
      dm_is_vowel(dm_char(state.input, 1)) ||
      ascii_starts_with_at(state.input, 0, "WH")
    ) {
    if dm_is_vowel(dm_char(state.input, 1)) {
      dm_move(state, i + 1, "A", "F")
    } else {
      dm_same(state, i + 1, "A")
    }
  } else if (
      i == state.input.length() - 1 && dm_is_vowel(dm_char(state.input, i - 1))
    ) ||
    dm_contains_any(state.input, i - 1, ["EWSKI", "EWSKY", "OWSKI", "OWSKY"]) ||
    ascii_starts_with_at(state.input, 0, "SCH") {
    dm_alternate_only(state, i + 1, "F")
  } else if dm_contains_any(state.input, i, ["WICZ", "WITZ"]) {
    dm_move(state, i + 4, "TS", "FX")
  } else {
    dm_same(state, i + 1, "")
  }
}

///|
fn dm_handle_x(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if i == 0 {
    dm_same(state, i + 1, "S")
  } else {
    let next_index = if dm_contains_any(state.input, i + 1, ["C", "X"]) {
      i + 2
    } else {
      i + 1
    }
    if i == state.input.length() - 1 &&
      (
        dm_contains_any(state.input, i - 3, ["IAU", "EAU"]) ||
        dm_contains_any(state.input, i - 2, ["AU", "OU"])
      ) {
      dm_same(state, next_index, "")
    } else {
      dm_same(state, next_index, "KS")
    }
  }
}

///|
fn dm_handle_z(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  if dm_char(state.input, i + 1) == 72 {
    dm_same(state, i + 2, "J")
  } else {
    let next_index = if dm_char(state.input, i + 1) == 90 {
      i + 2
    } else {
      i + 1
    }
    if dm_contains_any(state.input, i + 1, ["ZO", "ZI", "ZA"]) ||
      (state.slavo_germanic && i > 0 && dm_char(state.input, i - 1) != 84) {
      dm_move(state, next_index, "S", "TS")
    } else {
      dm_same(state, next_index, "S")
    }
  }
}

///|
fn dm_step(state : DoubleMetaphoneState) -> DoubleMetaphoneState {
  let i = state.index
  let current = dm_char(state.input, i)
  match current {
    65 | 69 | 73 | 79 | 85 | 89 =>
      if i == 0 {
        dm_same(state, i + 1, "A")
      } else {
        dm_same(state, i + 1, "")
      }
    66 =>
      dm_same(
        state,
        if dm_char(state.input, i + 1) == 66 {
          i + 2
        } else {
          i + 1
        },
        "P",
      )
    67 => dm_handle_c(state)
    68 => dm_handle_d(state)
    70 =>
      dm_same(
        state,
        if dm_char(state.input, i + 1) == 70 {
          i + 2
        } else {
          i + 1
        },
        "F",
      )
    71 => dm_handle_g(state)
    72 => dm_handle_h(state)
    74 => dm_handle_j(state)
    75 =>
      dm_same(
        state,
        if dm_char(state.input, i + 1) == 75 {
          i + 2
        } else {
          i + 1
        },
        "K",
      )
    76 => dm_handle_l(state)
    77 => {
      let doubled = dm_char(state.input, i + 1) == 77 ||
        (
          ascii_starts_with_at(state.input, i - 1, "UMB") &&
          (
            i + 1 == state.input.length() - 1 ||
            ascii_starts_with_at(state.input, i + 2, "ER")
          )
        )
      dm_same(state, if doubled { i + 2 } else { i + 1 }, "M")
    }
    78 =>
      dm_same(
        state,
        if dm_char(state.input, i + 1) == 78 {
          i + 2
        } else {
          i + 1
        },
        "N",
      )
    80 => dm_handle_p(state)
    81 =>
      dm_same(
        state,
        if dm_char(state.input, i + 1) == 81 {
          i + 2
        } else {
          i + 1
        },
        "K",
      )
    82 => dm_handle_r(state)
    83 => dm_handle_s(state)
    84 => dm_handle_t(state)
    86 =>
      dm_same(
        state,
        if dm_char(state.input, i + 1) == 86 {
          i + 2
        } else {
          i + 1
        },
        "F",
      )
    87 => dm_handle_w(state)
    88 => dm_handle_x(state)
    90 => dm_handle_z(state)
    _ => dm_same(state, i + 1, "")
  }
}

///|
fn double_metaphone_normalized(input : String) -> EncodedKeys {
  if input.length() == 0 {
    return EncodedKeys::single("")
  }
  let start = if dm_has_silent_start(input) { 1 } else { 0 }
  let mut state : DoubleMetaphoneState = {
    input,
    index: start,
    primary: "",
    alternate: "",
    maximum: 4,
    slavo_germanic: dm_is_slavo_germanic(input),
  }
  while state.index < state.input.length() &&
        (
          state.primary.length() < state.maximum ||
          state.alternate.length() < state.maximum
        ) {
    let next = dm_step(state)
    if next.index <= state.index {
      abort("Double Metaphone rule did not advance")
    }
    state = next
  }
  EncodedKeys::new(state.primary, Some(state.alternate))
}

///|
fn double_metaphone_prepare_input(input : String) -> String {
  let mut prepared = ""
  for i = 0; i < input.length(); i = i + 1 {
    let code = input[i]
    if code == 0x00C7 || code == 0x00E7 {
      prepared = prepared + "S"
    } else if code == 0x00D1 || code == 0x00F1 {
      prepared = prepared + "N"
    } else {
      prepared = prepared + code.unsafe_to_char().to_string()
    }
  }
  prepared
}

///|
/// Encodes a Latin-script name into standard four-character primary and
/// alternate Double Metaphone keys.
pub fn double_metaphone(input : String) -> EncodedKeys {
  match
    normalize_name(
      double_metaphone_prepare_input(input),
      name_normalization_config(),
    ) {
    Ok(result) => double_metaphone_normalized(result.normalized)
    Err(_) => EncodedKeys::single("")
  }
}