///|
/// Classification of one deterministic alignment step.
pub(all) enum AlignmentKind {
  AlignmentMatch
  AlignmentInsertion
  AlignmentDeletion
  AlignmentSubstitution
  AlignmentEquivalence
} derive(Eq, Debug)

///|
/// One immutable step in a normalized Pinyin alignment.
pub struct AlignmentStep {
  kind_value : AlignmentKind
  left_start_value : Int
  left_end_value : Int
  right_start_value : Int
  right_end_value : Int
  left_fragment_value : String
  right_fragment_value : String
  cost_value : Double
} derive(Eq, Debug)

///|
/// Ordered edit evidence and aggregate operation counts.
pub struct PinyinAlignment {
  left_normalized_value : String
  right_normalized_value : String
  step_values : Array[AlignmentStep]
  total_cost_value : Double
  match_count : Int
  insertion_count : Int
  deletion_count : Int
  substitution_count : Int
  equivalence_count : Int
} derive(Eq, Debug)

///|
/// Facts proven by validating alignment coverage, costs, and counters.
pub struct AlignmentIntegrity {
  left_covered_value : Int
  right_covered_value : Int
  step_count_value : Int
  total_cost_value : Double
  full_coverage_value : Bool
} derive(Eq, Debug)

///|
priv struct AlignmentCell {
  reachable : Bool
  total : Double
  operation_count : Int
  previous_left : Int
  previous_right : Int
  transition_kind : AlignmentKind
  transition_rank : Int
}

///|
fn alignment_fragment(value : String, start : Int, width : Int) -> String {
  let mut output = ""
  for index = start; index < start + width; index = index + 1 {
    output = output + value[index].unsafe_to_char().to_string()
  }
  output
}

///|
fn unreachable_alignment_cell() -> AlignmentCell {
  {
    reachable: false,
    total: 1000000000.0,
    operation_count: 0,
    previous_left: -1,
    previous_right: -1,
    transition_kind: AlignmentMatch,
    transition_rank: 100,
  }
}

///|
fn root_alignment_cell() -> AlignmentCell {
  {
    reachable: true,
    total: 0.0,
    operation_count: 0,
    previous_left: -1,
    previous_right: -1,
    transition_kind: AlignmentMatch,
    transition_rank: 0,
  }
}

///|
fn alignment_transition_rank(kind : AlignmentKind) -> Int {
  match kind {
    AlignmentMatch => 0
    AlignmentEquivalence => 1
    AlignmentSubstitution => 2
    AlignmentDeletion => 3
    AlignmentInsertion => 4
  }
}

///|
fn alignment_candidate(
  current : AlignmentCell,
  previous_left : Int,
  previous_right : Int,
  kind : AlignmentKind,
  cost : Double,
) -> AlignmentCell {
  {
    reachable: true,
    total: current.total + cost,
    operation_count: current.operation_count + 1,
    previous_left,
    previous_right,
    transition_kind: kind,
    transition_rank: alignment_transition_rank(kind),
  }
}

///|
fn alignment_candidate_better(
  candidate : AlignmentCell,
  current : AlignmentCell,
) -> Bool {
  if !current.reachable {
    return true
  }
  if candidate.total < current.total {
    return true
  }
  if candidate.total > current.total {
    return false
  }
  if candidate.operation_count < current.operation_count {
    return true
  }
  if candidate.operation_count > current.operation_count {
    return false
  }
  if candidate.transition_rank < current.transition_rank {
    return true
  }
  if candidate.transition_rank > current.transition_rank {
    return false
  }
  if candidate.previous_left < current.previous_left {
    return true
  }
  candidate.previous_left == current.previous_left &&
  candidate.previous_right < current.previous_right
}

///|
fn relax_alignment_cell(
  cells : Array[AlignmentCell],
  index : Int,
  candidate : AlignmentCell,
) -> Unit {
  if alignment_candidate_better(candidate, cells[index]) {
    cells[index] = candidate
  }
}

///|
fn relax_character_transition(
  cells : Array[AlignmentCell],
  columns : Int,
  left : String,
  right : String,
  left_index : Int,
  right_index : Int,
  current : AlignmentCell,
  profile : FuzzyProfile,
) -> Unit {
  if left[left_index] == right[right_index] {
    relax_alignment_cell(
      cells,
      (left_index + 1) * columns + right_index + 1,
      alignment_candidate(current, left_index, right_index, AlignmentMatch, 0.0),
    )
  } else if can_n_l(left, left_index, right, right_index, profile.rules()) {
    relax_alignment_cell(
      cells,
      (left_index + 1) * columns + right_index + 1,
      alignment_candidate(
        current,
        left_index,
        right_index,
        AlignmentEquivalence,
        profile.equivalence_cost(),
      ),
    )
  } else {
    relax_alignment_cell(
      cells,
      (left_index + 1) * columns + right_index + 1,
      alignment_candidate(
        current,
        left_index,
        right_index,
        AlignmentSubstitution,
        profile.substitution_cost(),
      ),
    )
  }
}

///|
fn relax_pair_transitions(
  cells : Array[AlignmentCell],
  columns : Int,
  left : String,
  right : String,
  left_index : Int,
  right_index : Int,
  current : AlignmentCell,
  profile : FuzzyProfile,
) -> Unit {
  if can_single_pair(left, left_index, right, right_index, profile.rules()) {
    relax_alignment_cell(
      cells,
      (left_index + 1) * columns + right_index + 2,
      alignment_candidate(
        current,
        left_index,
        right_index,
        AlignmentEquivalence,
        profile.equivalence_cost(),
      ),
    )
  }
  if can_single_pair(right, right_index, left, left_index, profile.rules()) {
    relax_alignment_cell(
      cells,
      (left_index + 2) * columns + right_index + 1,
      alignment_candidate(
        current,
        left_index,
        right_index,
        AlignmentEquivalence,
        profile.equivalence_cost(),
      ),
    )
  }
}

///|
fn build_alignment_cells(
  left : String,
  right : String,
  profile : FuzzyProfile,
) -> Array[AlignmentCell] {
  let rows = left.length() + 1
  let columns = right.length() + 1
  let cells = Array::make(rows * columns, unreachable_alignment_cell())
  cells[0] = root_alignment_cell()
  for left_index = 0; left_index < rows; left_index = left_index + 1 {
    for right_index = 0; right_index < columns; right_index = right_index + 1 {
      let current = cells[left_index * columns + right_index]
      if !current.reachable {
        continue
      }
      if left_index < left.length() && right_index < right.length() {
        relax_character_transition(
          cells, columns, left, right, left_index, right_index, current, profile,
        )
        relax_pair_transitions(
          cells, columns, left, right, left_index, right_index, current, profile,
        )
      }
      if left_index < left.length() {
        relax_alignment_cell(
          cells,
          (left_index + 1) * columns + right_index,
          alignment_candidate(
            current,
            left_index,
            right_index,
            AlignmentDeletion,
            profile.deletion_cost(),
          ),
        )
      }
      if right_index < right.length() {
        relax_alignment_cell(
          cells,
          left_index * columns + right_index + 1,
          alignment_candidate(
            current,
            left_index,
            right_index,
            AlignmentInsertion,
            profile.insertion_cost(),
          ),
        )
      }
    }
  }
  cells
}

///|
fn alignment_step_from_cell(
  left : String,
  right : String,
  left_end : Int,
  right_end : Int,
  cell : AlignmentCell,
) -> AlignmentStep {
  let left_width = left_end - cell.previous_left
  let right_width = right_end - cell.previous_right
  let cost = match cell.transition_kind {
    AlignmentMatch => 0.0
    AlignmentEquivalence => cell.total
    AlignmentSubstitution => cell.total
    AlignmentDeletion => cell.total
    AlignmentInsertion => cell.total
  }
  {
    kind_value: cell.transition_kind,
    left_start_value: cell.previous_left,
    left_end_value: left_end,
    right_start_value: cell.previous_right,
    right_end_value: right_end,
    left_fragment_value: alignment_fragment(
      left,
      cell.previous_left,
      left_width,
    ),
    right_fragment_value: alignment_fragment(
      right,
      cell.previous_right,
      right_width,
    ),
    cost_value: cost,
  }
}

///|
fn alignment_step_cost(kind : AlignmentKind, profile : FuzzyProfile) -> Double {
  match kind {
    AlignmentMatch => 0.0
    AlignmentInsertion => profile.insertion_cost()
    AlignmentDeletion => profile.deletion_cost()
    AlignmentSubstitution => profile.substitution_cost()
    AlignmentEquivalence => profile.equivalence_cost()
  }
}

///|
fn collect_alignment_steps(
  left : String,
  right : String,
  profile : FuzzyProfile,
  cells : Array[AlignmentCell],
) -> Array[AlignmentStep] {
  let columns = right.length() + 1
  let reversed : Array[AlignmentStep] = []
  let mut left_end = left.length()
  let mut right_end = right.length()
  while left_end > 0 || right_end > 0 {
    let cell = cells[left_end * columns + right_end]
    let raw = alignment_step_from_cell(left, right, left_end, right_end, cell)
    reversed.push({
      ..raw,
      cost_value: alignment_step_cost(raw.kind(), profile),
    })
    left_end = cell.previous_left
    right_end = cell.previous_right
  }
  let ordered : Array[AlignmentStep] = []
  let mut index = reversed.length()
  while index > 0 {
    index = index - 1
    ordered.push(reversed[index])
  }
  ordered
}

///|
fn summarize_alignment(
  left : String,
  right : String,
  steps : Array[AlignmentStep],
) -> PinyinAlignment {
  let mut total = 0.0
  let mut matches = 0
  let mut insertions = 0
  let mut deletions = 0
  let mut substitutions = 0
  let mut equivalences = 0
  for step in steps {
    total = total + step.cost()
    match step.kind() {
      AlignmentMatch => matches = matches + 1
      AlignmentInsertion => insertions = insertions + 1
      AlignmentDeletion => deletions = deletions + 1
      AlignmentSubstitution => substitutions = substitutions + 1
      AlignmentEquivalence => equivalences = equivalences + 1
    }
  }
  {
    left_normalized_value: left,
    right_normalized_value: right,
    step_values: steps,
    total_cost_value: total,
    match_count: matches,
    insertion_count: insertions,
    deletion_count: deletions,
    substitution_count: substitutions,
    equivalence_count: equivalences,
  }
}

///|
fn alignment_step_shape_valid(step : AlignmentStep) -> Bool {
  let left_width = step.left_end() - step.left_start()
  let right_width = step.right_end() - step.right_start()
  match step.kind() {
    AlignmentMatch | AlignmentSubstitution =>
      left_width == 1 && right_width == 1
    AlignmentInsertion => left_width == 0 && right_width == 1
    AlignmentDeletion => left_width == 1 && right_width == 0
    AlignmentEquivalence =>
      (left_width == 1 && right_width == 1) ||
      (left_width == 1 && right_width == 2) ||
      (left_width == 2 && right_width == 1)
  }
}

///|
fn alignment_step_fragments_valid(
  alignment : PinyinAlignment,
  step : AlignmentStep,
) -> Bool {
  let left_width = step.left_end() - step.left_start()
  let right_width = step.right_end() - step.right_start()
  step.left_fragment() ==
  alignment_fragment(
    alignment.left_normalized_value,
    step.left_start(),
    left_width,
  ) &&
  step.right_fragment() ==
  alignment_fragment(
    alignment.right_normalized_value,
    step.right_start(),
    right_width,
  )
}

///|
fn alignment_equivalence_valid(
  alignment : PinyinAlignment,
  step : AlignmentStep,
  rules : FuzzyRules,
) -> Bool {
  let left_width = step.left_end() - step.left_start()
  let right_width = step.right_end() - step.right_start()
  if left_width == 1 && right_width == 1 {
    can_n_l(
      alignment.left_normalized_value,
      step.left_start(),
      alignment.right_normalized_value,
      step.right_start(),
      rules,
    )
  } else if left_width == 1 && right_width == 2 {
    can_single_pair(
      alignment.left_normalized_value,
      step.left_start(),
      alignment.right_normalized_value,
      step.right_start(),
      rules,
    )
  } else if left_width == 2 && right_width == 1 {
    can_single_pair(
      alignment.right_normalized_value,
      step.right_start(),
      alignment.left_normalized_value,
      step.left_start(),
      rules,
    )
  } else {
    false
  }
}

///|
fn alignment_step_semantics_valid(
  alignment : PinyinAlignment,
  step : AlignmentStep,
  profile : FuzzyProfile,
) -> Bool {
  match step.kind() {
    AlignmentMatch => step.left_fragment() == step.right_fragment()
    AlignmentSubstitution => step.left_fragment() != step.right_fragment()
    AlignmentInsertion | AlignmentDeletion => true
    AlignmentEquivalence =>
      alignment_equivalence_valid(alignment, step, profile.rules())
  }
}

///|
fn alignment_step_cost_valid(
  step : AlignmentStep,
  profile : FuzzyProfile,
) -> Bool {
  !step.cost().is_nan() &&
  !step.cost().is_inf() &&
  step.cost() >= 0.0 &&
  step.cost() == alignment_step_cost(step.kind(), profile)
}

///|
fn invalid_alignment(
  reason : String,
) -> Result[AlignmentIntegrity, PinyinError] {
  Err(InvalidAlignment(reason))
}

///|
/// Validates path continuity, fragments, enabled rules, costs, and counters.
pub fn validate_pinyin_alignment(
  alignment : PinyinAlignment,
  profile : FuzzyProfile,
) -> Result[AlignmentIntegrity, PinyinError] {
  let steps = alignment.steps()
  let mut left_covered = 0
  let mut right_covered = 0
  let mut total = 0.0
  let mut matches = 0
  let mut insertions = 0
  let mut deletions = 0
  let mut substitutions = 0
  let mut equivalences = 0
  for step in steps {
    if step.left_start() != left_covered || step.right_start() != right_covered {
      return invalid_alignment("non_contiguous_path")
    }
    if step.left_end() < step.left_start() ||
      step.right_end() < step.right_start() {
      return invalid_alignment("negative_step_width")
    }
    if step.left_end() > alignment.left_normalized_value.length() ||
      step.right_end() > alignment.right_normalized_value.length() {
      return invalid_alignment("step_outside_input")
    }
    if !alignment_step_shape_valid(step) {
      return invalid_alignment("invalid_step_shape")
    }
    if !alignment_step_fragments_valid(alignment, step) {
      return invalid_alignment("fragment_mismatch")
    }
    if !alignment_step_semantics_valid(alignment, step, profile) {
      return invalid_alignment("operation_semantics_mismatch")
    }
    if !alignment_step_cost_valid(step, profile) {
      return invalid_alignment("step_cost_mismatch")
    }
    left_covered = step.left_end()
    right_covered = step.right_end()
    total = total + step.cost()
    match step.kind() {
      AlignmentMatch => matches = matches + 1
      AlignmentInsertion => insertions = insertions + 1
      AlignmentDeletion => deletions = deletions + 1
      AlignmentSubstitution => substitutions = substitutions + 1
      AlignmentEquivalence => equivalences = equivalences + 1
    }
  }
  if left_covered != alignment.left_normalized_value.length() ||
    right_covered != alignment.right_normalized_value.length() {
    return invalid_alignment("incomplete_coverage")
  }
  if total != alignment.total_cost_value {
    return invalid_alignment("total_cost_mismatch")
  }
  if matches != alignment.match_count ||
    insertions != alignment.insertion_count ||
    deletions != alignment.deletion_count ||
    substitutions != alignment.substitution_count ||
    equivalences != alignment.equivalence_count {
    return invalid_alignment("operation_count_mismatch")
  }
  Ok({
    left_covered_value: left_covered,
    right_covered_value: right_covered,
    step_count_value: steps.length(),
    total_cost_value: total,
    full_coverage_value: true,
  })
}

///|
/// Aligns two normalized Pinyin inputs with deterministic edit evidence.
pub fn align_pinyin(
  left_input : String,
  right_input : String,
  profile : FuzzyProfile,
) -> PinyinAlignment {
  let left = normalize_literal(left_input)
  let right = normalize_literal(right_input)
  let cells = build_alignment_cells(left, right, profile)
  summarize_alignment(
    left,
    right,
    collect_alignment_steps(left, right, profile, cells),
  )
}

///|
pub fn AlignmentStep::kind(self : AlignmentStep) -> AlignmentKind {
  self.kind_value
}

///|
pub fn AlignmentStep::left_start(self : AlignmentStep) -> Int {
  self.left_start_value
}

///|
pub fn AlignmentStep::left_end(self : AlignmentStep) -> Int {
  self.left_end_value
}

///|
pub fn AlignmentStep::right_start(self : AlignmentStep) -> Int {
  self.right_start_value
}

///|
pub fn AlignmentStep::right_end(self : AlignmentStep) -> Int {
  self.right_end_value
}

///|
pub fn AlignmentStep::left_fragment(self : AlignmentStep) -> String {
  self.left_fragment_value
}

///|
pub fn AlignmentStep::right_fragment(self : AlignmentStep) -> String {
  self.right_fragment_value
}

///|
pub fn AlignmentStep::cost(self : AlignmentStep) -> Double {
  self.cost_value
}

///|
pub fn PinyinAlignment::left_normalized(self : PinyinAlignment) -> String {
  self.left_normalized_value
}

///|
pub fn PinyinAlignment::right_normalized(self : PinyinAlignment) -> String {
  self.right_normalized_value
}

///|
pub fn PinyinAlignment::steps(self : PinyinAlignment) -> Array[AlignmentStep] {
  self.step_values.copy()
}

///|
pub fn PinyinAlignment::total_cost(self : PinyinAlignment) -> Double {
  self.total_cost_value
}

///|
pub fn PinyinAlignment::matches(self : PinyinAlignment) -> Int {
  self.match_count
}

///|
pub fn PinyinAlignment::insertions(self : PinyinAlignment) -> Int {
  self.insertion_count
}

///|
pub fn PinyinAlignment::deletions(self : PinyinAlignment) -> Int {
  self.deletion_count
}

///|
pub fn PinyinAlignment::substitutions(self : PinyinAlignment) -> Int {
  self.substitution_count
}

///|
pub fn PinyinAlignment::equivalences(self : PinyinAlignment) -> Int {
  self.equivalence_count
}

///|
pub fn PinyinAlignment::operations(self : PinyinAlignment) -> Int {
  self.step_values.length()
}

///|
pub fn AlignmentIntegrity::left_covered(self : AlignmentIntegrity) -> Int {
  self.left_covered_value
}

///|
pub fn AlignmentIntegrity::right_covered(self : AlignmentIntegrity) -> Int {
  self.right_covered_value
}

///|
pub fn AlignmentIntegrity::steps(self : AlignmentIntegrity) -> Int {
  self.step_count_value
}

///|
pub fn AlignmentIntegrity::total_cost(self : AlignmentIntegrity) -> Double {
  self.total_cost_value
}

///|
pub fn AlignmentIntegrity::has_full_coverage(self : AlignmentIntegrity) -> Bool {
  self.full_coverage_value
}