///|
/// Quality indicators for comparing constructive heuristics.
pub struct SeedQuality {
  strategy : ConstructionStrategy
  objective : Double
  assigned_count : Int
  route_count : Int
  average_stops : Double
  feasible : Bool
} derive(Debug, ToJson)

///|
pub fn SeedQuality::strategy(self : SeedQuality) -> ConstructionStrategy {
  self.strategy
}

///|
pub fn SeedQuality::objective(self : SeedQuality) -> Double {
  self.objective
}

///|
pub fn SeedQuality::assigned_count(self : SeedQuality) -> Int {
  self.assigned_count
}

///|
pub fn SeedQuality::route_count(self : SeedQuality) -> Int {
  self.route_count
}

///|
pub fn SeedQuality::average_stops(self : SeedQuality) -> Double {
  self.average_stops
}

///|
pub fn SeedQuality::is_feasible(self : SeedQuality) -> Bool {
  self.feasible
}

///|
pub fn evaluate_seed(
  strategy : ConstructionStrategy,
  solution : @core.Solution,
) -> SeedQuality {
  let route_count = solution.route_count()
  let average_stops = if route_count == 0 {
    0.0
  } else {
    Double::from_int(solution.assigned_customers().length()) /
    Double::from_int(route_count)
  }
  {
    strategy,
    objective: solution.objective_value(),
    assigned_count: solution.assigned_customers().length(),
    route_count,
    average_stops,
    feasible: solution.is_feasible(),
  }
}

///|
fn radial_order(instance : @core.VrpInstance) -> Array[Int] {
  let depot = instance.depot()
  let indices = @core.all_customer_indices(instance)
  indices.sort_by(fn(left, right) {
    let left_customer = instance.customer(left)
    let right_customer = instance.customer(right)
    let left_distance = instance
      .distance_metric()
      .distance(
        depot.x_coord(),
        depot.y_coord(),
        left_customer.x_coord(),
        left_customer.y_coord(),
      )
    let right_distance = instance
      .distance_metric()
      .distance(
        depot.x_coord(),
        depot.y_coord(),
        right_customer.x_coord(),
        right_customer.y_coord(),
      )
    let order = Double::compare(left_distance, right_distance)
    if order == 0 {
      left - right
    } else {
      order
    }
  })
  indices
}

///|
/// Packs customers in radial order, opening a new route at each capacity break.
pub fn radial_seed(
  instance : @core.VrpInstance,
  config : @core.SolveConfig,
) -> @core.Solution {
  let routes : Array[Array[Int]] = []
  let unassigned : Array[Int] = []
  for customer_index in radial_order(instance) {
    let mut placed = false
    for route in routes {
      if !placed {
        let candidate = route + [customer_index]
        if @core.evaluate_route(instance, candidate).feasible {
          route.push(customer_index)
          placed = true
        }
      }
    }
    if !placed && routes.length() < instance.vehicle().fleet_size() {
      if @core.evaluate_route(instance, [customer_index]).feasible {
        routes.push([customer_index])
        placed = true
      }
    }
    if !placed {
      unassigned.push(customer_index)
    }
  }
  @core.build_solution(instance, routes, unassigned, config)
}

///|
/// Chooses the feasible route with the lowest post-insertion load ratio.
pub fn balanced_seed(
  instance : @core.VrpInstance,
  config : @core.SolveConfig,
) -> @core.Solution {
  let routes : Array[Array[Int]] = []
  let unassigned : Array[Int] = []
  let customers = @core.all_customer_indices(instance)
  customers.sort_by(fn(left, right) {
    Double::compare(
      instance.customer(right).demand(),
      instance.customer(left).demand(),
    )
  })
  for customer_index in customers {
    let mut selected = -1
    let mut selected_load = 1_000_000_000.0
    for route_index, route in routes {
      let candidate = @core.evaluate_route(instance, route + [customer_index])
      if candidate.feasible && candidate.load < selected_load {
        selected = route_index
        selected_load = candidate.load
      }
    }
    if selected >= 0 {
      routes[selected].push(customer_index)
    } else if routes.length() < instance.vehicle().fleet_size() &&
      @core.evaluate_route(instance, [customer_index]).feasible {
      routes.push([customer_index])
    } else {
      unassigned.push(customer_index)
    }
  }
  @core.build_solution(instance, routes, unassigned, config)
}

///|
/// Solves once from each supplied strategy and returns the best result.
pub fn best_seed(
  instance : @core.VrpInstance,
  strategies : Array[ConstructionStrategy],
  config : @core.SolveConfig,
) -> @core.Solution {
  let selected = if strategies.is_empty() {
    [ConstructionStrategy::ClarkeWright]
  } else {
    strategies
  }
  let mut best = seed_by_strategy(instance, selected[0], config)
  for strategy in selected[1:] {
    let candidate = 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)
    }
    if candidate.objective_value() < best.objective_value() {
      best = candidate
    }
  }
  best
}