///|
/// Performs Dijkstra's shortest path search on a weighted grid
/// from `start` to `goal`.
///
/// Unlike BFS, Dijkstra respects terrain weights: moving through
/// a `Weighted(c)` cell costs `c` instead of 1. This makes it
/// suitable for maps with varying terrain costs.
///
/// Uses a min-heap priority queue (binary heap) to always expand
/// the node with the lowest accumulated cost first.
///
/// # Movement
/// Uses four-way movement by default. Neighbor generation includes
/// cell costs.
///
/// # Errors
/// Returns a failure result if:
/// - `start` or `goal` is out of bounds
/// - `start` or `goal` is blocked
/// - No path exists from start to goal
pub fn dijkstra(grid : Grid, start : Point, goal : Point) -> SearchResult {
  dijkstra_with_movement(grid, start, goal, Movement::FourWay)
}

///|
/// Performs Dijkstra search with configurable four-way or eight-way movement.
/// Eight-way diagonal movement costs `sqrt(2)` times the destination terrain
/// cost, matching the movement model used by A*.
pub fn dijkstra_with_movement(
  grid : Grid,
  start : Point,
  goal : Point,
  movement : Movement,
) -> SearchResult {
  // --- Input validation ---
  if !grid.is_valid_search(start, goal) {
    return SearchResult::failure(0, 0)
  }

  // --- Trivial case ---
  if start == goal {
    let path = Array::new()
    path.push(start)
    return SearchResult::success(path, 0.0, 1, 0)
  }

  let size = grid.size()
  let start_idx = start.y * grid.width + start.x
  let goal_idx = goal.y * grid.width + goal.x

  // Best known cost to each node (Double::MAX equivalent: very large)
  let infinity = 1.0e300
  let costs = Array::make(size, infinity)
  costs[start_idx] = 0.0

  // Parent tracking
  let parent = Array::make(size, -1)

  // Min-heap priority queue
  let heap = MinHeap::new()
  heap.push(0.0, start_idx)

  let discovered = Array::make(size, false)
  discovered[start_idx] = true
  let mut nodes_visited = 1
  let mut nodes_expanded = 0
  let mut found = false

  let get_neighbors = match movement {
    Movement::FourWay => four_way_neighbors_with_cost
    Movement::EightWay => eight_way_neighbors_with_cost
  }

  while !heap.is_empty() {
    match heap.pop() {
      None => break
      Some((current_cost, current_idx)) => {
        // Lazy deletion: skip if we already have a better cost for this node
        if current_cost > costs[current_idx] {
          continue
        }

        if current_idx == goal_idx {
          found = true
          break
        }
        nodes_expanded = nodes_expanded + 1

        let cx = current_idx % grid.width
        let cy = current_idx / grid.width
        let neighbors = get_neighbors(grid, Point::new(cx, cy))

        for i = 0; i < neighbors.length(); i = i + 1 {
          let (n, edge_cost) = neighbors[i]
          let n_idx = n.y * grid.width + n.x
          let new_cost = current_cost + edge_cost

          if new_cost < costs[n_idx] {
            costs[n_idx] = new_cost
            parent[n_idx] = current_idx
            heap.push(new_cost, n_idx)
            if !discovered[n_idx] {
              discovered[n_idx] = true
              nodes_visited = nodes_visited + 1
            }
          }
        }
      }
    }
  }

  if !found {
    return SearchResult::failure(nodes_visited, nodes_expanded)
  }

  let path = reconstruct_path(parent, start_idx, goal_idx, grid.width)
  SearchResult::success(path, costs[goal_idx], nodes_visited, nodes_expanded)
}