///|
struct SavingsCandidate {
  left : Int
  right : Int
  saving : Double
} derive(Debug)

///|
fn route_merge(
  left_route : Array[Int],
  left_customer : Int,
  right_route : Array[Int],
  right_customer : Int,
) -> Array[Int]? {
  if left_route.is_empty() || right_route.is_empty() {
    return None
  }
  let left_first = left_route[0]
  let left_last = left_route[left_route.length() - 1]
  let right_first = right_route[0]
  let right_last = right_route[right_route.length() - 1]
  if left_last == left_customer && right_first == right_customer {
    return Some(left_route + right_route)
  }
  if left_first == left_customer && right_last == right_customer {
    return Some(right_route + left_route)
  }
  if left_last == left_customer && right_last == right_customer {
    return Some(left_route + right_route.rev())
  }
  if left_first == left_customer && right_first == right_customer {
    return Some(left_route.rev() + right_route)
  }
  None
}

///|
pub fn clarke_wright_seed(
  instance : @core.VrpInstance,
  config? : @core.SolveConfig = @core.SolveConfig::default(),
) -> @core.Solution {
  let depot_index = instance.depot_index()
  let route_of = Array::make(instance.customer_count(), -1)
  let routes : Array[Array[Int]] = []
  for customer_index in 0.. right.saving {
      -1
    } else if left.saving < right.saving {
      1
    } else {
      0
    }
  })
  for candidate in candidates {
    let left_route_index = route_of[candidate.left]
    let right_route_index = route_of[candidate.right]
    if left_route_index < 0 ||
      right_route_index < 0 ||
      left_route_index == right_route_index {
      continue
    }
    let left_route = routes[left_route_index]
    let right_route = routes[right_route_index]
    match
      route_merge(left_route, candidate.left, right_route, candidate.right) {
      None => ()
      Some(merged) => {
        let metrics = @core.evaluate_route(instance, merged)
        if metrics.feasible {
          routes[left_route_index] = merged
          routes[right_route_index] = []
          for stop in routes[left_route_index] {
            route_of[stop] = left_route_index
          }
        }
      }
    }
  }
  @core.build_solution(instance, routes, [], config)
}