///|
fn canonical_entity_precedes(left : Entity, right : Entity) -> Bool {
  if left.id == right.id {
    left.name.to_upper() < right.name.to_upper()
  } else {
    left.id < right.id
  }
}

///|
fn canonical_sorted_entities(entities : Array[Entity]) -> Array[Entity] {
  let result = entities.copy()
  for i in 0.. (Array[Entity], Int) {
  let seen : Map[Int, Bool] = Map([])
  let result : Array[Entity] = []
  let mut duplicates = 0
  for entity in entities {
    if seen.contains(entity.id) {
      duplicates += 1
    } else {
      seen[entity.id] = true
      result.push(entity)
    }
  }
  (result, duplicates)
}

///|

///|
/// Produce a deterministic entity order while preserving all argument values.
pub fn canonical_model(model : Model, deduplicate? : Bool = false) -> Model {
  let entities = if deduplicate {
    let (unique, _) = canonical_unique_entities(model.entities)
    unique
  } else {
    model.entities.copy()
  }
  Model::new(header=model.header, entities=canonical_sorted_entities(entities))
}

///|
pub fn canonicalize_step(
  source : String,
  deduplicate? : Bool = false,
) -> String raise ParseError {
  canonical_model(parse(source), deduplicate~).to_step()
}

///|
pub fn canonical_step_stats(
  source : String,
) -> CanonicalStepStats raise ParseError {
  let model = parse(source)
  let canonical = canonical_model(model)
  let (_, duplicates) = canonical_unique_entities(model.entities)
  {
    source_length: source.length(),
    canonical_length: canonical.to_step().length(),
    entity_count: model.entities.length(),
    changed: source != canonical.to_step(),
    duplicate_id_count: duplicates,
    line_count: source_line_count(source),
  }
}

///|
pub fn CanonicalStepStats::compression_ratio(
  self : CanonicalStepStats,
) -> Double {
  if self.source_length == 0 {
    1.0
  } else {
    self.canonical_length.to_double() / self.source_length.to_double()
  }
}

///|
pub fn CanonicalStepStats::has_duplicates(self : CanonicalStepStats) -> Bool {
  self.duplicate_id_count > 0
}

///|
pub fn CanonicalStepStats::headline(self : CanonicalStepStats) -> String {
  "entities=" +
  self.entity_count.to_string() +
  " source=" +
  self.source_length.to_string() +
  " canonical=" +
  self.canonical_length.to_string() +
  " changed=" +
  self.changed.to_string() +
  " duplicates=" +
  self.duplicate_id_count.to_string()
}

///|
pub fn CanonicalStepStats::to_json(self : CanonicalStepStats) -> String {
  "{\"source_length\":" +
  self.source_length.to_string() +
  ",\"canonical_length\":" +
  self.canonical_length.to_string() +
  ",\"entity_count\":" +
  self.entity_count.to_string() +
  ",\"changed\":" +
  self.changed.to_string() +
  ",\"duplicate_id_count\":" +
  self.duplicate_id_count.to_string() +
  ",\"compression_ratio\":" +
  self.compression_ratio().to_string() +
  "}"
}

///|
pub fn canonical_entity_ids(model : Model) -> Array[Int] {
  canonical_model(model).entities.map(entity => entity.id)
}

///|
pub fn canonical_entity_names(model : Model) -> Array[String] {
  canonical_model(model).entities.map(entity => entity.name)
}

///|
pub fn duplicate_entity_ids(model : Model) -> Array[Int] {
  let (_, _) = canonical_unique_entities(model.entities)
  let counts : Map[Int, Int] = Map([])
  for entity in model.entities {
    counts.update_or_default(entity.id, 1, count => count + 1)
  }
  let result : Array[Int] = []
  for id, count in counts {
    if count > 1 {
      result.push(id)
    }
  }
  result
}

///|
pub fn canonical_model_without_duplicates(model : Model) -> Model {
  canonical_model(model, deduplicate=true)
}

///|
pub fn canonical_record_text(entity : Entity) -> String {
  "#" +
  entity.id.to_string() +
  "=" +
  entity.name.to_upper() +
  "(" +
  entity.arguments.map(value => value.to_step_lossless()).join(",") +
  ");"
}

///|
pub fn canonical_records(model : Model) -> Array[String] {
  canonical_model(model).entities.map(entity => canonical_record_text(entity))
}

///|
pub fn canonical_model_hash(model : Model) -> Int {
  canonical_records(model).join("").hash()
}

///|
pub fn canonical_models_equal(left : Model, right : Model) -> Bool {
  canonical_records(left) == canonical_records(right) &&
  left.schema() == right.schema()
}

///|
pub fn canonical_diff(left : Model, right : Model) -> Array[String] {
  let result : Array[String] = []
  let left_records = canonical_records(left)
  let right_records = canonical_records(right)
  if left.schema() != right.schema() {
    result.push("schema changed: " + left.schema() + " -> " + right.schema())
  }
  for record in left_records {
    if !right_records.contains(record) {
      result.push("removed: " + record)
    }
  }
  for record in right_records {
    if !left_records.contains(record) {
      result.push("added: " + record)
    }
  }
  result
}

///|
pub fn canonical_step_summary(
  source : String,
) -> Array[String] raise ParseError {
  let stats = canonical_step_stats(source)
  [stats.headline(), "ratio=" + stats.compression_ratio().to_string()]
}