export const topo: {
  (
    config?: TopoConfig
  ): <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>) => NodeWalker<N>
  <N, E, T extends Kind = "directed">(graph: Graph<N, E, T> | MutableGraph<N, E, T>, config?: TopoConfig): NodeWalker<N>
} = dual((args) => isGraph(args[0]), <N, E, T extends Kind = "directed">(
  graph: Graph<N, E, T> | MutableGraph<N, E, T>,
  config: TopoConfig = {}
): NodeWalker<N> => {
  if (graph.type === "undirected") {
    throw new GraphError({ message: "Cannot perform topological sort on undirected graph" })
  }

  // Check if graph is acyclic first
  if (!isAcyclic(graph)) {
    throw new GraphError({ message: "Cannot perform topological sort on cyclic graph" })
  }

  const initials = config.initials ?? []

  // Validate that all initial nodes exist
  for (const nodeIndex of initials) {
    if (!hasNode(graph, nodeIndex)) {
      throw missingNode(nodeIndex)
    }
  }

  return new Walker((f) => ({
    [Symbol.iterator]: () => {
      const inDegree = new Map<NodeIndex, number>()
      const remaining = new Set<NodeIndex>()
      const initialSet = new Set(initials)
      const queue = [...initials]

      // Initialize in-degree counts
      for (const [nodeIndex] of graph.nodes) {
        inDegree.set(nodeIndex, 0)
        remaining.add(nodeIndex)
      }

      // Calculate in-degrees
      for (const [, edgeData] of graph.edges) {
        const currentInDegree = inDegree.get(edgeData.target) || 0
        inDegree.set(edgeData.target, currentInDegree + 1)
      }

      for (const nodeIndex of initials) {
        if (inDegree.get(nodeIndex)! !== 0) {
          throw new GraphError({ message: `Initial node ${nodeIndex} has incoming edges` })
        }
      }

      // Add remaining zero in-degree nodes after prioritized initials.
      for (const [nodeIndex, degree] of inDegree) {
        if (degree === 0 && !initialSet.has(nodeIndex)) {
          queue.push(nodeIndex)
        }
      }

      const nextMapped = () => {
        while (queue.length > 0) {
          const current = queue.shift()!

          if (remaining.has(current)) {
            remaining.delete(current)

            // Process outgoing edges, reducing in-degree of targets
            const neighbors = getDirectedNeighbors(
              graph as Graph<N, E, "directed"> | MutableGraph<N, E, "directed">,
              current,
              "outgoing"
            )
            for (const neighbor of neighbors) {
              if (remaining.has(neighbor)) {
                const currentInDegree = inDegree.get(neighbor) || 0
                const newInDegree = currentInDegree - 1
                inDegree.set(neighbor, newInDegree)

                // If in-degree becomes 0, add to queue
                if (newInDegree === 0) {
                  queue.push(neighbor)
                }
              }
            }

            const nodeData = getNode(graph, current)
            if (Option.isSome(nodeData)) {
              return { done: false, value: f(current, nodeData.value) }
            }
            return nextMapped()
          }
        }

        return { done: true, value: undefined } as const
      }

      return { next: nextMapped }
    }
  }))
})