///|
fn dedup_input_order(left : DedupInput, right : DedupInput) -> Int {
  if left.id < right.id {
    -1
  } else if left.id > right.id {
    1
  } else {
    0
  }
}

///|
fn dedup_group_order(left : DedupGroup, right : DedupGroup) -> Int {
  dedup_input_order(left.representative, right.representative)
}

///|
fn find_dedup_input_index(records : Array[DedupInput], id : String) -> Int {
  for index = 0; index < records.length(); index = index + 1 {
    if records[index].id == id {
      return index
    }
  }
  -1
}

///|
fn canonical_candidate_pair(left : Int, right : Int) -> (Int, Int) {
  if left < right {
    (left, right)
  } else {
    (right, left)
  }
}

///|
fn collect_candidate_pairs(
  index : NameIndex,
  records : Array[DedupInput],
) -> Array[(Int, Int)] {
  let pairs : Array[(Int, Int)] = []
  for entry in index.buckets.to_array() {
    let ids = entry.1
    for left = 0; left < ids.length(); left = left + 1 {
      for right = left + 1; right < ids.length(); right = right + 1 {
        let left_index = find_dedup_input_index(records, ids[left])
        let right_index = find_dedup_input_index(records, ids[right])
        if left_index >= 0 && right_index >= 0 && left_index != right_index {
          let pair = canonical_candidate_pair(left_index, right_index)
          if !pairs.contains(pair) {
            pairs.push(pair)
          }
        }
      }
    }
  }
  pairs.sort_by(fn(left, right) {
    if left.0 < right.0 {
      -1
    } else if left.0 > right.0 {
      1
    } else if left.1 < right.1 {
      -1
    } else if left.1 > right.1 {
      1
    } else {
      0
    }
  })
  pairs
}

///|
fn collect_dedup_groups(
  sets : UnionFind,
  records : Array[DedupInput],
  include_singletons : Bool,
) -> Result[(Array[DedupGroup], Array[DedupInput], Int), DedupError] {
  let members_by_root : Map[Int, Array[DedupInput]] = Map([])
  for index = 0; index < sets.length(); index = index + 1 {
    let root = match sets.find(index) {
      Err(error) => return Err(error)
      Ok(value) => value
    }
    match members_by_root.get(root) {
      Some(members) => members.push(records[index])
      None => members_by_root.set(root, [records[index]])
    }
  }
  let groups : Array[DedupGroup] = []
  let singletons : Array[DedupInput] = []
  let mut ungrouped_count = 0
  for entry in members_by_root.to_array() {
    let members = entry.1
    members.sort_by(dedup_input_order)
    if members.length() > 1 {
      groups.push({ representative: members[0], members })
    } else {
      ungrouped_count = ungrouped_count + 1
      if include_singletons {
        singletons.push(members[0])
      }
    }
  }
  groups.sort_by(dedup_group_order)
  singletons.sort_by(dedup_input_order)
  Ok((groups, singletons, ungrouped_count))
}

///|
/// Groups records connected by accepted, phonetic-blocked matching edges.
pub fn deduplicate_names(
  inputs : Array[DedupInput],
  config : MatchConfig,
  blocking_algorithms : Array[Algorithm],
  include_singletons : Bool,
) -> Result[DedupReport, DedupError] {
  let records = inputs.copy()
  records.sort_by(dedup_input_order)
  for index = 1; index < records.length(); index = index + 1 {
    if records[index - 1].id == records[index].id {
      return Err(DuplicateInputId(records[index].id))
    }
  }
  let index = match NameIndex::new(config, blocking_algorithms) {
    Err(error) => return Err(DedupIndexFailed(error))
    Ok(value) => value
  }
  for record in records {
    match index.insert(record.id, record.name) {
      Err(error) => return Err(DedupIndexFailed(error))
      Ok(_) => ()
    }
  }
  let candidate_pairs = collect_candidate_pairs(index, records)
  let sets = match UnionFind::new(records.length()) {
    Err(error) => return Err(error)
    Ok(value) => value
  }
  let accepted_edges : Array[DedupEdge] = []
  for pair in candidate_pairs {
    let left = records[pair.0]
    let right = records[pair.1]
    let evidence = match match_names(left.name, right.name, config) {
      Err(error) => return Err(DedupMatchFailed(error))
      Ok(value) => value
    }
    if evidence.matched {
      match sets.union(pair.0, pair.1) {
        Err(error) => return Err(error)
        Ok(_) => ()
      }
      accepted_edges.push({ left_id: left.id, right_id: right.id, evidence })
    }
  }
  let (groups, singletons, ungrouped_count) = match
    collect_dedup_groups(sets, records, include_singletons) {
    Err(error) => return Err(error)
    Ok(value) => value
  }
  Ok({
    groups,
    singletons,
    accepted_edges,
    summary: {
      input_count: records.length(),
      candidate_pair_count: candidate_pairs.length(),
      comparison_count: candidate_pairs.length(),
      accepted_edge_count: accepted_edges.length(),
      group_count: groups.length(),
      ungrouped_count,
    },
  })
}