///|
fn insertion_score(
  instance : @core.VrpInstance,
  route : Array[Int],
  customer_index : Int,
  position : Int,
) -> Double? {
  let plan = @core.build_route(instance, route)
  @core.insertion_delta(instance, plan, customer_index, position)
}

///|
/// Returns the cheapest feasible insertion in one route.
pub fn cheapest_route_insertion(
  instance : @core.VrpInstance,
  route : Array[Int],
  customer_index : Int,
  config : @core.SolveConfig,
) -> (Int, @core.RoutePlan)? {
  ignore(config)
  let mut best_position = -1
  let mut best_score = 1_000_000_000.0
  let mut best_route : @core.RoutePlan? = None
  for position in 0..<=route.length() {
    match insertion_score(instance, route, customer_index, position) {
      None => ()
      Some(score) => {
        let next_stops = route.copy()
        next_stops.insert(position, customer_index)
        let next_route = @core.build_route(instance, next_stops)
        if next_route.metrics().is_feasible() && score < best_score {
          best_position = position
          best_score = score
          best_route = Some(next_route)
        }
      }
    }
  }
  match best_route {
    None => None
    Some(route_plan) => Some((best_position, route_plan))
  }
}

///|
/// Inserts a customer into the best existing route, creating a route only
/// when the fleet still has an unused vehicle.
pub fn insert_customer(
  instance : @core.VrpInstance,
  solution : @core.Solution,
  customer_index : Int,
  config : @core.SolveConfig,
) -> @core.Solution {
  let candidates = @core.best_insertions_for_customer(
    instance, solution, customer_index, config,
  )
  let mut selected : @core.Solution? = None
  let mut selected_objective = 1_000_000_000_000.0
  for candidate in candidates {
    let result = candidate.result()
    if result.total_capacity_violation() == 0.0 &&
      result.total_time_violation() == 0.0 &&
      result.total_duration_violation() == 0.0 &&
      candidate.objective() < selected_objective {
      selected_objective = candidate.objective()
      selected = Some(result)
    }
  }
  match selected {
    Some(result) => result
    None => solution.copy()
  }
}

///|
/// Repairs every unassigned customer in order of descending demand.
pub fn demand_ordered_insertion(
  instance : @core.VrpInstance,
  solution : @core.Solution,
  config : @core.SolveConfig,
) -> @core.Solution {
  let customers = solution.unassigned_customers()
  customers.sort_by(fn(left, right) {
    Double::compare(
      instance.customer(right).demand(),
      instance.customer(left).demand(),
    )
  })
  let mut current = solution
  for customer_index in customers {
    current = insert_customer(instance, current, customer_index, config)
  }
  current
}