///|
/// Parameters controlling deterministic route selection.
pub struct RouteOptions {
  distance_weight : Double
  risk_weight : Double
  congestion_weight : Double
  stair_penalty : Double
  require_accessible : Bool
  maximum_risk : Double
} derive(Eq, Debug)

///|
/// A selected route through the evacuation graph.
pub struct Route {
  place_indices : Array[Int]
  passage_indices : Array[Int]
  total_cost : Double
  distance_m : Double
  maximum_risk : Double
  reachable : Bool
} derive(Eq, Debug)

///|
/// One passage with a computed dynamic cost.
pub struct EdgeCost {
  passage_index : Int
  from_index : Int
  to_index : Int
  cost : Double
  distance_m : Double
  risk : Double
  congestion : Double
} derive(Eq, Debug)

///|
/// Capacity and route pressure summary for one passage.
pub struct PassagePressure {
  passage_id : String
  assigned_people : Int
  estimated_seconds : Double
  utilization : Double
  critical : Bool
} derive(Eq, Debug)

///|
/// Create balanced routing options.
pub fn RouteOptions::balanced() -> RouteOptions {
  {
    distance_weight: 1.0,
    risk_weight: 80.0,
    congestion_weight: 12.0,
    stair_penalty: 10.0,
    require_accessible: false,
    maximum_risk: 0.85,
  }
}

///|
/// Create routing options for an assisted mobility group.
pub fn RouteOptions::accessible() -> RouteOptions {
  {
    distance_weight: 1.0,
    risk_weight: 100.0,
    congestion_weight: 15.0,
    stair_penalty: 1000000.0,
    require_accessible: true,
    maximum_risk: 0.7,
  }
}

///|
/// Create options that strongly prefer the shortest geometric route.
pub fn RouteOptions::shortest() -> RouteOptions {
  {
    distance_weight: 1.0,
    risk_weight: 0.0,
    congestion_weight: 0.0,
    stair_penalty: 0.0,
    require_accessible: false,
    maximum_risk: 1.0,
  }
}

///|
/// Create an explicit unreachable route value.
pub fn Route::no_route() -> Route {
  {
    place_indices: [],
    passage_indices: [],
    total_cost: 1000000000000.0,
    distance_m: 0.0,
    maximum_risk: 0.0,
    reachable: false,
  }
}

///|
fn safe_array_value(values : Array[Double], index : Int) -> Double {
  if index < 0 || index >= values.length() {
    0.0
  } else {
    values[index]
  }
}

///|
fn max_double(a : Double, b : Double) -> Double {
  if a > b {
    a
  } else {
    b
  }
}

///|
fn passage_dynamic_cost(
  plan : EvacuationPlan,
  passage_index : Int,
  from_index : Int,
  to_index : Int,
  risks : Array[Double],
  congestion : Array[Double],
  options : RouteOptions,
) -> EdgeCost {
  let passage = plan.passages[passage_index]
  let from_risk = safe_array_value(risks, from_index)
  let to_risk = safe_array_value(risks, to_index)
  let risk = max_double(from_risk, to_risk)
  let crowd = safe_array_value(congestion, passage_index)
  let stair = if passage.kind == Stairway { options.stair_penalty } else { 0.0 }
  let width_penalty = if passage.width_m < 0.9 {
    (0.9 - passage.width_m) * 20.0
  } else {
    0.0
  }
  let cost = passage.length_m * options.distance_weight +
    risk * options.risk_weight +
    crowd * options.congestion_weight +
    stair +
    width_penalty
  {
    passage_index,
    from_index,
    to_index,
    cost,
    distance_m: passage.length_m,
    risk,
    congestion: crowd,
  }
}

///|
fn edge_allowed(
  passage : Passage,
  destination_risk : Double,
  options : RouteOptions,
) -> Bool {
  if !passage.enabled {
    return false
  }
  if options.require_accessible && !passage.accessible {
    return false
  }
  if destination_risk > options.maximum_risk {
    return false
  }
  true
}

///|
/// Return every outgoing edge from a place under current conditions.
pub fn outgoing_edges(
  plan : EvacuationPlan,
  place_index : Int,
  risks : Array[Double],
  congestion : Array[Double],
  options : RouteOptions,
) -> Array[EdgeCost] {
  let result : Array[EdgeCost] = []
  if place_index < 0 || place_index >= plan.places.length() {
    return result
  }
  let place_id = plan.places[place_index].id
  for i = 0; i < plan.passages.length(); i = i + 1 {
    let passage = plan.passages[i]
    if passage.from_id == place_id {
      let target = plan.place_index(passage.to_id)
      if target >= 0 &&
        edge_allowed(passage, safe_array_value(risks, target), options) {
        result.push(
          passage_dynamic_cost(
            plan, i, place_index, target, risks, congestion, options,
          ),
        )
      }
    }
    if passage.bidirectional && passage.to_id == place_id {
      let target = plan.place_index(passage.from_id)
      if target >= 0 &&
        edge_allowed(passage, safe_array_value(risks, target), options) {
        result.push(
          passage_dynamic_cost(
            plan, i, place_index, target, risks, congestion, options,
          ),
        )
      }
    }
  }
  result
}

///|
fn minimum_unvisited(distance : Array[Double], visited : Array[Bool]) -> Int {
  let mut best = -1
  let mut best_distance = 1000000000000.0
  for i = 0; i < distance.length(); i = i + 1 {
    if !visited[i] && distance[i] < best_distance {
      best = i
      best_distance = distance[i]
    }
  }
  best
}

///|
fn reconstruct_route(
  plan : EvacuationPlan,
  start : Int,
  target : Int,
  previous_place : Array[Int],
  previous_passage : Array[Int],
  total_cost : Double,
  risks : Array[Double],
) -> Route {
  if target < 0 || previous_place.length() != plan.places.length() {
    return Route::no_route()
  }
  let reversed_places : Array[Int] = []
  let reversed_passages : Array[Int] = []
  let mut cursor = target
  let mut hop_count = 0
  while cursor >= 0 && hop_count <= plan.places.length() {
    reversed_places.push(cursor)
    if cursor == start {
      break
    }
    let passage = previous_passage[cursor]
    if passage < 0 {
      return Route::no_route()
    }
    reversed_passages.push(passage)
    cursor = previous_place[cursor]
    hop_count = hop_count + 1
  }
  if reversed_places.length() == 0 ||
    reversed_places[reversed_places.length() - 1] != start {
    return Route::no_route()
  }
  let places : Array[Int] = []
  let passages : Array[Int] = []
  let mut distance_m = 0.0
  let mut maximum_risk = 0.0
  for i = reversed_places.length() - 1; i >= 0; i = i - 1 {
    let place_index = reversed_places[i]
    places.push(place_index)
    maximum_risk = max_double(
      maximum_risk,
      safe_array_value(risks, place_index),
    )
  }
  for i = reversed_passages.length() - 1; i >= 0; i = i - 1 {
    let passage_index = reversed_passages[i]
    passages.push(passage_index)
    distance_m = distance_m + plan.passages[passage_index].length_m
  }
  {
    place_indices: places,
    passage_indices: passages,
    total_cost,
    distance_m,
    maximum_risk,
    reachable: true,
  }
}

///|
/// Find the lowest-cost route from a place to a particular target.
pub fn route_to_place(
  plan : EvacuationPlan,
  start : Int,
  target : Int,
  risks : Array[Double],
  congestion : Array[Double],
  options : RouteOptions,
) -> Route {
  let n = plan.places.length()
  if start < 0 || start >= n || target < 0 || target >= n {
    return Route::no_route()
  }
  let distance = Array::make(n, 1000000000000.0)
  let visited = Array::make(n, false)
  let previous_place = Array::make(n, -1)
  let previous_passage = Array::make(n, -1)
  distance[start] = 0.0
  for step = 0; step < n; step = step + 1 {
    let current = minimum_unvisited(distance, visited)
    if current < 0 {
      break
    }
    if current == target {
      break
    }
    visited[current] = true
    for edge in outgoing_edges(plan, current, risks, congestion, options) {
      let candidate = distance[current] + edge.cost
      if candidate < distance[edge.to_index] {
        distance[edge.to_index] = candidate
        previous_place[edge.to_index] = current
        previous_passage[edge.to_index] = edge.passage_index
      }
    }
  }
  if distance[target] >= 999999999999.0 {
    Route::no_route()
  } else {
    reconstruct_route(
      plan,
      start,
      target,
      previous_place,
      previous_passage,
      distance[target],
      risks,
    )
  }
}

///|
/// Find the lowest-cost reachable exit without mutating the plan.
pub fn route_to_nearest_exit(
  plan : EvacuationPlan,
  start : Int,
  risks : Array[Double],
  congestion : Array[Double],
  options : RouteOptions,
) -> Route {
  let exits = plan.exit_indices()
  let mut best = Route::no_route()
  for target in exits {
    let candidate = route_to_place(
      plan, start, target, risks, congestion, options,
    )
    if candidate.reachable &&
      (!best.reachable || candidate.total_cost < best.total_cost) {
      best = candidate
    }
  }
  best
}

///|
/// Return the destination exit id of a route.
pub fn Route::exit_id(self : Route, plan : EvacuationPlan) -> String {
  if !self.reachable || self.place_indices.length() == 0 {
    return ""
  }
  let index = self.place_indices[self.place_indices.length() - 1]
  if index < 0 || index >= plan.places.length() {
    ""
  } else {
    plan.places[index].id
  }
}

///|
/// Produce the route as place identifiers.
pub fn Route::place_ids(self : Route, plan : EvacuationPlan) -> Array[String] {
  let result : Array[String] = []
  for index in self.place_indices {
    if index >= 0 && index < plan.places.length() {
      result.push(plan.places[index].id)
    }
  }
  result
}

///|
/// Estimate travel time before queues and response delay.
pub fn Route::free_flow_seconds(self : Route, mobility : Mobility) -> Double {
  let speed_mps = 1.25 * mobility.speed_factor()
  if !self.reachable || speed_mps <= 0.0 {
    0.0
  } else {
    self.distance_m / speed_mps
  }
}

///|
/// Assign every population group to its preferred route.
pub fn planned_group_routes(
  plan : EvacuationPlan,
  risks : Array[Double],
  congestion : Array[Double],
) -> Array[Route] {
  let routes : Array[Route] = []
  for group in plan.populations {
    let start = plan.place_index(group.place_id)
    let options = if group.mobility.requires_accessible() {
      RouteOptions::accessible()
    } else {
      RouteOptions::balanced()
    }
    routes.push(route_to_nearest_exit(plan, start, risks, congestion, options))
  }
  routes
}

///|
/// Count planned people using each passage.
pub fn planned_passage_loads(
  plan : EvacuationPlan,
  routes : Array[Route],
) -> Array[Int] {
  let loads = Array::make(plan.passages.length(), 0)
  let count = if routes.length() < plan.populations.length() {
    routes.length()
  } else {
    plan.populations.length()
  }
  for i = 0; i < count; i = i + 1 {
    if routes[i].reachable {
      for passage_index in routes[i].passage_indices {
        if passage_index >= 0 && passage_index < loads.length() {
          loads[passage_index] = loads[passage_index] +
            plan.populations[i].count
        }
      }
    }
  }
  loads
}

///|
/// Estimate pressure on each passage from planned routes.
pub fn analyze_passage_pressure(
  plan : EvacuationPlan,
  routes : Array[Route],
  critical_seconds : Double,
) -> Array[PassagePressure] {
  let loads = planned_passage_loads(plan, routes)
  let result : Array[PassagePressure] = []
  for i = 0; i < plan.passages.length(); i = i + 1 {
    let passage = plan.passages[i]
    let throughput = if passage.flow_per_second > 0.0 {
      passage.flow_per_second
    } else {
      0.01
    }
    let seconds = loads[i].to_double() / throughput
    let utilization = if critical_seconds > 0.0 {
      seconds / critical_seconds
    } else {
      seconds
    }
    result.push({
      passage_id: passage.id,
      assigned_people: loads[i],
      estimated_seconds: seconds,
      utilization,
      critical: utilization >= 1.0,
    })
  }
  result
}

///|
/// Compute simple undirected degree for every place.
pub fn place_degrees(plan : EvacuationPlan) -> Array[Int] {
  let result = Array::make(plan.places.length(), 0)
  for passage in plan.passages {
    if passage.enabled {
      let a = plan.place_index(passage.from_id)
      let b = plan.place_index(passage.to_id)
      if a >= 0 {
        result[a] = result[a] + 1
      }
      if b >= 0 {
        result[b] = result[b] + 1
      }
    }
  }
  result
}

///|
/// Find places whose loss disconnects at least one occupied origin from all exits.
pub fn critical_places(plan : EvacuationPlan) -> Array[String] {
  let result : Array[String] = []
  for removed = 0; removed < plan.places.length(); removed = removed + 1 {
    if plan.places[removed].kind == Exit {
      continue
    }
    let mut affects_population = false
    for group in plan.populations {
      let start = plan.place_index(group.place_id)
      if start >= 0 &&
        start != removed &&
        !reachable_avoiding(plan, start, removed) {
        affects_population = true
      }
    }
    if affects_population {
      result.push(plan.places[removed].id)
    }
  }
  result
}

///|
fn reachable_avoiding(
  plan : EvacuationPlan,
  start : Int,
  removed : Int,
) -> Bool {
  let visited = Array::make(plan.places.length(), false)
  let queue : Array[Int] = []
  if start < 0 || start == removed {
    return false
  }
  queue.push(start)
  visited[start] = true
  let mut cursor = 0
  while cursor < queue.length() {
    let current = queue[cursor]
    cursor = cursor + 1
    if plan.places[current].kind == Exit {
      return true
    }
    for edge in outgoing_edges(plan, current, [], [], RouteOptions::shortest()) {
      if edge.to_index != removed && !visited[edge.to_index] {
        visited[edge.to_index] = true
        queue.push(edge.to_index)
      }
    }
  }
  false
}

///|
/// Describe a route in a compact stable form.
pub fn Route::summary(self : Route, plan : EvacuationPlan) -> String {
  if !self.reachable {
    return "unreachable"
  }
  let ids = self.place_ids(plan)
  let mut text = ""
  for i = 0; i < ids.length(); i = i + 1 {
    if i > 0 {
      text = text + " -> "
    }
    text = text + ids[i]
  }
  text + " (distance=\{self.distance_m}, cost=\{self.total_cost})"
}