export const astar: {
  <E, N>(
    config: AstarConfig<E, N>
  ): <T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => Option.Option<PathResult<E>>
  <N, E, T extends Kind = "directed">(
    graph: Graph<N, E, T> | MutableGraph<N, E, T>,
    config: AstarConfig<E, N>
  ): Option.Option<PathResult<E>>
} = dual(2, <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config: AstarConfig<E, N>
): Option.Option<PathResult<E>> => {
  // Validate that source and target nodes exist
  if (!graph.nodes.has(config.source)) {
    throw missingNode(config.source)
  }
  if (!graph.nodes.has(config.target)) {
    throw missingNode(config.target)
  }

  const edgeWeights = validateNonNegativeEdgeWeights(graph, config.cost, "A* algorithm")

  // Early return if source equals target
  if (config.source === config.target) {
    return Option.some({
      path: [config.source],
      distance: 0,
      costs: []
    })
  }

  // Get target node data for heuristic calculations
  const targetNodeData = getNode(graph, config.target)
  if (Option.isNone(targetNodeData)) {
    throw new GraphError({ message: `Missing node data for target node ${config.target}` })
  }

  // Distance tracking (g-score) and f-score (g + h)
  const gScore = new Map<NodeIndex, number>()
  const fScore = new Map<NodeIndex, number>()
  const previous = new Map<NodeIndex, { node: NodeIndex; edgeData: E } | null>()
  const visited = new Set<NodeIndex>()

  // Initialize scores
  // Iterate directly over node keys
  for (const node of graph.nodes.keys()) {
    gScore.set(node, node === config.source ? 0 : Infinity)
    fScore.set(node, Infinity)
    previous.set(node, null)
  }

  // Calculate initial f-score for source
  const sourceNodeData = getNode(graph, config.source)
  if (Option.isSome(sourceNodeData)) {
    const h = config.heuristic(sourceNodeData.value, targetNodeData.value)
    fScore.set(config.source, h)
  }

  // Priority queue using f-score (total estimated cost)
  const openSet: Array<{ node: NodeIndex; fScore: number }> = [
    { node: config.source, fScore: fScore.get(config.source)! }
  ]

  while (openSet.length > 0) {
    // Find node with lowest f-score
    let minIndex = 0
    for (let i = 1; i < openSet.length; i++) {
      if (openSet[i].fScore < openSet[minIndex].fScore) {
        minIndex = i
      }
    }

    const current = openSet.splice(minIndex, 1)[0]
    const currentNode = current.node

    // Skip if already visited
    if (visited.has(currentNode)) {
      continue
    }

    visited.add(currentNode)

    // Early termination if we reached the target
    if (currentNode === config.target) {
      break
    }

    // Get current g-score
    const currentGScore = gScore.get(currentNode)!

    // Examine all outgoing edges
    const adjacencyList = graph.adjacency.get(currentNode)
    if (adjacencyList !== undefined) {
      for (const edgeIndex of adjacencyList) {
        const edge = graph.edges.get(edgeIndex)
        if (edge !== undefined) {
          const neighbor = getTraversableNeighbor(graph, currentNode, edge)
          const weight = edgeWeights.get(edgeIndex)!

          const tentativeGScore = currentGScore + weight
          const neighborGScore = gScore.get(neighbor)!

          // If this path to neighbor is better than any previous one
          if (tentativeGScore < neighborGScore) {
            // Update g-score and previous
            gScore.set(neighbor, tentativeGScore)
            previous.set(neighbor, { node: currentNode, edgeData: edge.data })

            // Calculate f-score using heuristic
            const neighborNodeData = getNode(graph, neighbor)
            if (Option.isSome(neighborNodeData)) {
              const h = config.heuristic(neighborNodeData.value, targetNodeData.value)
              const f = tentativeGScore + h
              fScore.set(neighbor, f)

              // Add to open set if not visited
              if (!visited.has(neighbor)) {
                openSet.push({ node: neighbor, fScore: f })
              }
            }
          }
        }
      }
    }
  }

  // Check if target is reachable
  const distance = gScore.get(config.target)!
  if (distance === Infinity) {
    return Option.none() // No path exists
  }

  // Reconstruct path
  const path: Array<NodeIndex> = []
  const costs: Array<E> = []
  let currentNode: NodeIndex | null = config.target

  while (currentNode !== null) {
    path.unshift(currentNode)
    const prev: { node: NodeIndex; edgeData: E } | null = previous.get(currentNode) ?? null
    if (prev !== null) {
      costs.unshift(prev.edgeData)
      currentNode = prev.node
    } else {
      currentNode = null
    }
  }

  return Option.some({
    path,
    distance,
    costs
  })
})