///|
/// An overlap between the suffix of one contig and the prefix of another.
pub struct ContigOverlap {
  left_index : Int
  right_index : Int
  overlap : Int
  merged_length : Int
} derive(Debug, Eq)

///|
/// Result of a deterministic greedy contig merge.
pub struct AssemblyResult {
  sequence : String
  contig_count : Int
  merged_count : Int
  overlaps : Array[ContigOverlap]
  unresolved : Array[String]
} derive(Debug, Eq)

///|
/// Find the longest suffix/prefix overlap subject to a minimum length.
pub fn suffix_prefix_overlap(
  left : String,
  right : String,
  minimum : Int,
) -> Int {
  let a = normalize_sequence(left)
  let b = normalize_sequence(right)
  let lower = Int::max(1, minimum)
  let maximum = Int::min(a.length(), b.length())
  let mut overlap = maximum
  while overlap >= lower {
    let suffix = a.unsafe_substring(start=a.length() - overlap, end=a.length())
    let prefix = b.unsafe_substring(start=0, end=overlap)
    if suffix == prefix {
      return overlap
    }
    overlap -= 1
  }
  0
}

///|
/// Compare every ordered contig pair and choose the strongest available join.
pub fn best_contig_overlap(
  contigs : Array[String],
  minimum : Int,
) -> ContigOverlap? {
  let mut best : ContigOverlap? = None
  for left in 0..= minimum => best = Some(candidate)
          Some(current) if overlap > current.overlap => best = Some(candidate)
          _ => ()
        }
      }
    }
  }
  best
}

///|
/// Greedily merge the strongest suffix/prefix join until no join remains.
pub fn greedy_assemble(
  contigs : Array[String],
  minimum_overlap : Int,
) -> AssemblyResult {
  let working = contigs.map(normalize_sequence).filter(fn(item) { item != "" })
  let overlaps : Array[ContigOverlap] = []
  let mut merged = 0
  while true {
    match best_contig_overlap(working, minimum_overlap) {
      None => break
      Some(join) => {
        let left = working[join.left_index]
        let right = working[join.right_index]
        let suffix_start = left.length() - join.overlap
        let combined = left +
          right.unsafe_substring(start=join.overlap, end=right.length())
        overlaps.push({
          left_index: join.left_index,
          right_index: join.right_index,
          overlap: join.overlap,
          merged_length: combined.length(),
        })
        let next : Array[String] = []
        for index, item in working {
          if index != join.left_index && index != join.right_index {
            next.push(item)
          }
        }
        ignore(suffix_start)
        next.push(combined)
        working.clear()
        working.append(next)
        merged += 1
      }
    }
  }
  let unresolved = working.copy()
  {
    sequence: working.join(""),
    contig_count: contigs.length(),
    merged_count: merged,
    overlaps,
    unresolved,
  }
}

///|
/// Return a stable length vector for assembled contigs.
pub fn assembly_contig_lengths(result : AssemblyResult) -> Array[Int] {
  result.unresolved.map(fn(item) { item.length() })
}

///|
/// Export assembly diagnostics as JSON for pipeline artifacts.
pub fn AssemblyResult::to_json_string(self : AssemblyResult) -> String {
  let overlap_json = self.overlaps
    .map(fn(item) {
      "{\"left_index\":" +
      item.left_index.to_string() +
      ",\"right_index\":" +
      item.right_index.to_string() +
      ",\"overlap\":" +
      item.overlap.to_string() +
      ",\"merged_length\":" +
      item.merged_length.to_string() +
      "}"
    })
    .join(",")
  "{\"sequence\":" +
  json_string(self.sequence) +
  ",\"contig_count\":" +
  self.contig_count.to_string() +
  ",\"merged_count\":" +
  self.merged_count.to_string() +
  ",\"overlaps\":[" +
  overlap_json +
  "],\"unresolved\":[" +
  self.unresolved.map(json_string).join(",") +
  "]}"
}

///|
/// Format an assembly as a FASTA record for downstream tools.
pub fn assembly_to_fasta(result : AssemblyResult, id : String) -> String {
  { id, description: "greedy assembly", sequence: result.sequence }.to_fasta(60)
}