///|
fn valid_route_position(route : RoutePlan, position : Int) -> Bool {
  position >= 0 && position < route.stops.length()
}

///|
fn make_reversed_segment(
  stops : Array[Int],
  first : Int,
  last : Int,
) -> Array[Int] {
  let next = stops.copy()
  let mut left = first
  let mut right = last
  while left < right {
    next.swap(left, right)
    left += 1
    right -= 1
  }
  next
}

///|
/// Applies a 2-opt reversal and returns None for an invalid or infeasible edit.
pub fn two_opt_route(
  instance : VrpInstance,
  route : RoutePlan,
  first : Int,
  last : Int,
  config : SolveConfig,
) -> RoutePlan? {
  ignore(config)
  if !valid_route_position(route, first) ||
    !valid_route_position(route, last) ||
    first >= last {
    return None
  }
  let next_stops = make_reversed_segment(route.stops, first, last)
  let next = build_route(instance, next_stops)
  if next.metrics.feasible {
    Some(next)
  } else {
    None
  }
}

///|
/// Returns the cost change caused by inserting a stop at a route position.
pub fn insertion_delta(
  instance : VrpInstance,
  route : RoutePlan,
  customer_index : Int,
  position : Int,
) -> Double? {
  if position < 0 || position > route.stops.length() {
    return None
  }
  let before = if position == 0 {
    instance.depot_index()
  } else {
    route.stops[position - 1]
  }
  let after = if position == route.stops.length() {
    instance.depot_index()
  } else {
    route.stops[position]
  }
  Some(
    instance.distance(before, customer_index) +
    instance.distance(customer_index, after) -
    instance.distance(before, after),
  )
}

///|
/// Returns the cost change caused by removing one stop from a route.
pub fn removal_delta(
  instance : VrpInstance,
  route : RoutePlan,
  position : Int,
) -> Double? {
  if !valid_route_position(route, position) {
    return None
  }
  let before = if position == 0 {
    instance.depot_index()
  } else {
    route.stops[position - 1]
  }
  let after = if position == route.stops.length() - 1 {
    instance.depot_index()
  } else {
    route.stops[position + 1]
  }
  let customer = route.stops[position]
  Some(
    instance.distance(before, after) -
    instance.distance(before, customer) -
    instance.distance(customer, after),
  )
}

///|
fn valid_solution_route(solution : Solution, index : Int) -> Bool {
  index >= 0 && index < solution.routes.length()
}

///|
/// Moves one customer between route positions and rebuilds all metrics.
pub fn relocate_customer(
  instance : VrpInstance,
  solution : Solution,
  from_route : Int,
  from_position : Int,
  to_route : Int,
  to_position : Int,
  config : SolveConfig,
) -> Solution? {
  if !valid_solution_route(solution, from_route) ||
    !valid_solution_route(solution, to_route) {
    return None
  }
  let routes = solution.route_stops()
  if from_position < 0 || from_position >= routes[from_route].length() {
    return None
  }
  let customer = routes[from_route].remove(from_position)
  let mut position = to_position
  if from_route == to_route && from_position < to_position {
    position -= 1
  }
  if position < 0 || position > routes[to_route].length() {
    return None
  }
  routes[to_route].insert(position, customer)
  let next = build_solution(
    instance,
    routes,
    solution.unassigned.copy(),
    config,
  )
  if next.feasible {
    Some(next)
  } else {
    None
  }
}

///|
/// Swaps two customer positions, including positions from different routes.
pub fn swap_customers(
  instance : VrpInstance,
  solution : Solution,
  left_route : Int,
  left_position : Int,
  right_route : Int,
  right_position : Int,
  config : SolveConfig,
) -> Solution? {
  if !valid_solution_route(solution, left_route) ||
    !valid_solution_route(solution, right_route) {
    return None
  }
  let routes = solution.route_stops()
  if !valid_route_position(solution.routes[left_route], left_position) ||
    !valid_route_position(solution.routes[right_route], right_position) {
    return None
  }
  let left_customer = routes[left_route][left_position]
  let right_customer = routes[right_route][right_position]
  routes[left_route][left_position] = right_customer
  routes[right_route][right_position] = left_customer
  let next = build_solution(
    instance,
    routes,
    solution.unassigned.copy(),
    config,
  )
  if next.feasible {
    Some(next)
  } else {
    None
  }
}

///|
/// Reverses a complete route when the resulting route remains feasible.
pub fn reverse_route(
  instance : VrpInstance,
  solution : Solution,
  route_index : Int,
  config : SolveConfig,
) -> Solution? {
  if !valid_solution_route(solution, route_index) {
    return None
  }
  let routes = solution.route_stops()
  routes[route_index] = routes[route_index].rev()
  let next = build_solution(
    instance,
    routes,
    solution.unassigned.copy(),
    config,
  )
  if next.feasible {
    Some(next)
  } else {
    None
  }
}

///|
/// Applies the best improving 2-opt edit found in a solution.
pub fn improve_with_two_opt(
  instance : VrpInstance,
  solution : Solution,
  config : SolveConfig,
) -> Solution {
  let mut best = solution
  for route_index in 0.. ()
          Some(next_route) => {
            let routes = best.route_stops()
            routes[route_index] = next_route.stops
            let candidate = build_solution(
              instance,
              routes,
              best.unassigned.copy(),
              config,
            )
            if candidate.objective < best.objective {
              best = candidate
            }
          }
        }
      }
    }
  }
  best
}