///|
/// Construction strategies exposed by the library.
pub(all) enum ConstructionStrategy {
  ClarkeWright
  NearestNeighbor
  CheapestInsertion
  DemandFirst
  Radial
  Balanced
} derive(Debug, Eq, ToJson)

///|
fn route_can_append(
  instance : @core.VrpInstance,
  route : Array[Int],
  customer_index : Int,
) -> Bool {
  @core.evaluate_route(instance, route + [customer_index]).feasible
}

///|
fn choose_nearest(
  instance : @core.VrpInstance,
  route : Array[Int],
  remaining : Array[Int],
) -> Int? {
  let previous = if route.is_empty() {
    instance.depot_index()
  } else {
    route[route.length() - 1]
  }
  let mut chosen = -1
  let mut chosen_distance = 1_000_000_000.0
  for customer_index in remaining {
    if !route_can_append(instance, route, customer_index) {
      continue
    }
    let distance = instance.distance(previous, customer_index)
    if distance < chosen_distance ||
      (distance == chosen_distance && customer_index < chosen) {
      chosen = customer_index
      chosen_distance = distance
    }
  }
  if chosen < 0 {
    None
  } else {
    Some(chosen)
  }
}

///|
/// Builds routes by repeatedly appending the closest feasible customer.
pub fn nearest_neighbor_seed(
  instance : @core.VrpInstance,
  config : @core.SolveConfig,
) -> @core.Solution {
  let remaining = @core.all_customer_indices(instance)
  let routes : Array[Array[Int]] = []
  while !remaining.is_empty() &&
        routes.length() < instance.vehicle().fleet_size() {
    let route : Array[Int] = []
    while true {
      match choose_nearest(instance, route, remaining) {
        None => break
        Some(customer_index) => {
          route.push(customer_index)
          match remaining.search(customer_index) {
            None => break
            Some(position) => ignore(remaining.remove(position))
          }
        }
      }
    }
    if route.is_empty() {
      break
    }
    routes.push(route)
  }
  @core.build_solution(instance, routes, remaining, config)
}

///|
fn candidate_is_route_feasible(candidate : @core.CandidateInsertion) -> Bool {
  let solution = candidate.result()
  solution.total_capacity_violation() == 0.0 &&
  solution.total_time_violation() == 0.0 &&
  solution.total_duration_violation() == 0.0
}

///|
/// Repeatedly inserts the customer/position pair with the lowest penalized cost.
pub fn cheapest_insertion_seed(
  instance : @core.VrpInstance,
  config : @core.SolveConfig,
) -> @core.Solution {
  let mut current = @core.empty_solution(instance, config)
  while !current.unassigned_customers().is_empty() {
    let mut chosen_customer = -1
    let mut chosen_objective = 1_000_000_000_000.0
    let mut chosen_solution = current
    for customer_index in current.unassigned_customers() {
      let candidates = @core.best_insertions_for_customer(
        instance, current, customer_index, config,
      )
      for candidate in candidates {
        if candidate_is_route_feasible(candidate) &&
          candidate.objective() < chosen_objective {
          chosen_customer = customer_index
          chosen_objective = candidate.objective()
          chosen_solution = candidate.result()
        }
      }
    }
    if chosen_customer < 0 {
      break
    }
    current = chosen_solution
  }
  current
}

///|
fn demand_order(instance : @core.VrpInstance) -> Array[Int] {
  let indices = @core.all_customer_indices(instance)
  indices.sort_by(fn(left, right) {
    let left_demand = instance.customer(left).demand()
    let right_demand = instance.customer(right).demand()
    let order = Double::compare(right_demand, left_demand)
    if order == 0 {
      left - right
    } else {
      order
    }
  })
  indices
}

///|
/// Builds capacity-first routes, placing large deliveries before small ones.
pub fn demand_first_seed(
  instance : @core.VrpInstance,
  config : @core.SolveConfig,
) -> @core.Solution {
  let routes : Array[Array[Int]] = []
  let remaining = demand_order(instance)
  for customer_index in remaining {
    let mut placed = false
    for route in routes {
      if !placed && route_can_append(instance, route, customer_index) {
        route.push(customer_index)
        placed = true
      }
    }
    if !placed && routes.length() < instance.vehicle().fleet_size() {
      if route_can_append(instance, [], customer_index) {
        routes.push([customer_index])
        placed = true
      }
    }
    ignore(placed)
  }
  let assigned : Array[Int] = routes.fold(init=[], fn(all, route) {
    all + route
  })
  let unassigned = @core.all_customer_indices(instance).filter(fn(index) {
    !assigned.contains(index)
  })
  @core.build_solution(instance, routes, unassigned, config)
}

///|
/// Selects a construction heuristic for applications and benchmarks.
pub fn seed_by_strategy(
  instance : @core.VrpInstance,
  strategy : ConstructionStrategy,
  config : @core.SolveConfig,
) -> @core.Solution {
  match strategy {
    ConstructionStrategy::ClarkeWright => clarke_wright_seed(instance, config~)
    ConstructionStrategy::NearestNeighbor =>
      nearest_neighbor_seed(instance, config)
    ConstructionStrategy::CheapestInsertion =>
      cheapest_insertion_seed(instance, config)
    ConstructionStrategy::DemandFirst => demand_first_seed(instance, config)
    ConstructionStrategy::Radial => radial_seed(instance, config)
    ConstructionStrategy::Balanced => balanced_seed(instance, config)
  }
}