///|
/// Manhattan distance is deterministic, integer-only and easy to audit.
pub fn location_distance(left : Location, right : Location) -> Int {
  abs_int(left.x - right.x) + abs_int(left.y - right.y)
}

///|
/// Estimated travel minutes between two locations under one policy.
pub fn travel_minutes(
  left : Location,
  right : Location,
  policy : SchedulePolicy,
) -> Int {
  let movement = location_distance(left, right) * policy.travel_minutes_per_unit
  if left.zone == right.zone {
    movement
  } else {
    movement + policy.cross_zone_penalty_minutes
  }
}

///|
/// Travel leg retained for route explanations and reports.
pub(all) struct TravelLeg {
  worker_id : String
  from_location_id : String
  to_location_id : String
  depart_minute : Int
  arrive_minute : Int
  travel_minutes : Int
  cross_zone : Bool
} derive(Debug, Eq)

///|
/// Construct a travel leg from a departure time.
pub fn travel_leg(
  worker_id : String,
  from : Location,
  to : Location,
  depart_minute : Int,
  policy : SchedulePolicy,
) -> TravelLeg {
  let duration = travel_minutes(from, to, policy)
  {
    worker_id,
    from_location_id: from.id,
    to_location_id: to.id,
    depart_minute,
    arrive_minute: depart_minute + duration,
    travel_minutes: duration,
    cross_zone: from.zone != to.zone,
  }
}

///|
/// Resolve the visit location for an assignment.
pub fn assignment_location(
  assignment : Assignment,
  visits : Array[Visit],
) -> Location? {
  match find_visit(visits, assignment.visit_id) {
    Some(value) => Some(value.location)
    None => None
  }
}

///|
/// Sort a worker's assignments by start minute and then visit id.
pub fn sort_assignments_by_time(
  values : Array[Assignment],
) -> Array[Assignment] {
  let sorted = copy_array(values)
  for index = 1; index < sorted.length(); index = index + 1 {
    let current = sorted[index]
    let mut position = index
    while position > 0 {
      let previous = sorted[position - 1]
      let should_move = previous.start_minute > current.start_minute ||
        (
          previous.start_minute == current.start_minute &&
          previous.visit_id > current.visit_id
        )
      if !should_move {
        break
      }
      sorted[position] = previous
      position = position - 1
    }
    sorted[position] = current
  }
  sorted
}

///|
/// Find the assignment immediately before a proposed start.
pub fn previous_assignment(
  assignments : Array[Assignment],
  worker_id : String,
  start_minute : Int,
) -> Assignment? {
  let sorted = sort_assignments_by_time(
    assignments_for_worker(assignments, worker_id),
  )
  let mut result : Assignment? = None
  for assignment in sorted {
    if assignment.end_minute <= start_minute {
      result = Some(assignment)
    }
  }
  result
}

///|
/// Find the assignment immediately after a proposed end.
pub fn next_assignment(
  assignments : Array[Assignment],
  worker_id : String,
  end_minute : Int,
) -> Assignment? {
  let sorted = sort_assignments_by_time(
    assignments_for_worker(assignments, worker_id),
  )
  for assignment in sorted {
    if assignment.start_minute >= end_minute {
      return Some(assignment)
    }
  }
  None
}

///|
/// Location occupied immediately before a proposed visit.
pub fn previous_location(
  worker : Worker,
  assignments : Array[Assignment],
  visits : Array[Visit],
  start_minute : Int,
) -> Location {
  match previous_assignment(assignments, worker.id, start_minute) {
    Some(value) =>
      match assignment_location(value, visits) {
        Some(place) => place
        None => worker.home
      }
    None => worker.home
  }
}

///|
/// Estimated travel before a proposed assignment.
pub fn travel_before_candidate(
  worker : Worker,
  visit : Visit,
  assignments : Array[Assignment],
  visits : Array[Visit],
  policy : SchedulePolicy,
  start_minute : Int,
) -> Int {
  let from = previous_location(worker, assignments, visits, start_minute)
  travel_minutes(from, visit.location, policy)
}

///|
/// Total travel minutes represented by a schedule.
pub fn total_schedule_travel(assignments : Array[Assignment]) -> Int {
  let mut total = 0
  for assignment in assignments {
    total = total + assignment.travel_before_minutes
  }
  total
}

///|
/// Route description suitable for CLI and Markdown output.
pub fn describe_travel(
  from : Location,
  to : Location,
  policy : SchedulePolicy,
) -> String {
  let distance = location_distance(from, to)
  let minutes = travel_minutes(from, to, policy)
  let zone_note = if from.zone == to.zone { "same zone" } else { "cross-zone" }
  "\{from.id} -> \{to.id}: \{distance} units, \{minutes} minutes (\{zone_note})"
}