///|
/// # Depth-First Search (DFS)
///
/// DFS explores a graph by going as deep as possible along each branch
/// before backtracking. It's the foundation of many graph algorithms
/// (cycle detection, topological sort, SCC, path finding).
///
/// ## Implementation: iterative with explicit stack
///
/// Classic DFS is recursive, but recursion depth equals the longest path
/// in the graph — which can blow the call stack on deep graphs (we hit
/// this at ~10K vertices in WASM). The iterative version uses an explicit
/// `Array` as a stack, making it safe for arbitrarily deep graphs.
///
/// Successors are pushed directly from the `each_successor` callback
/// then reversed in place (mark-and-reverse), so the first successor is
/// processed first (matching recursive DFS order) without per-vertex
/// temporary array allocation.
///
/// ## The fold pattern
///
/// `dfs_fold` is a generalization: instead of collecting vertices into a
/// list, it folds an accumulator over visited vertices. The callback
/// returns `(new_acc, should_continue)` — returning `false` for
/// `should_continue` stops traversal early (useful for "find first" queries).
///
/// `reachable` is the common case — collects all reachable vertices.

///|
/// DFS fold over vertices reachable from `start`.
///
/// Visits each vertex exactly once. `f` receives the current accumulator
/// and the visited vertex, and returns `(new_acc, should_continue)`.
/// When `should_continue` is `false`, traversal halts immediately.
///
/// Time: O(V + E) where V and E are the reachable vertices and edges.
pub fn[G : Successors, Acc] dfs_fold(
  graph : G,
  start : Int,
  init : Acc,
  f : (Acc, Int) -> (Acc, Bool),
) -> Acc {
  graph.dfs_fold(start, init, f)
}

///|
/// All vertices reachable from `start`, in DFS pre-order.
pub fn[G : Successors] reachable(graph : G, start : Int) -> Array[Int] {
  dfs_fold(graph, start, [], fn(arr, v) {
    arr.push(v)
    (arr, true)
  })
}

///|
/// Early-exit reachability query: "is `to` reachable from `from`?"
///
/// Runs DFS from `from` and stops as soon as `to` is discovered, without
/// materializing the full reachable set. Reflexive: `is_reachable(g, v, v)`
/// is true (zero-length path), matching the behaviour of `reachable(g, v)`
/// which includes `v` in its output.
///
/// Returns `false` if `from` is not a vertex in the graph.
///
/// Time: O(V' + E') where V' and E' are the vertices and edges visited
/// before encountering `to` (bounded by the reachable subgraph from `from`).
pub fn[G : DirectedGraph] is_reachable(graph : G, from : Int, to : Int) -> Bool {
  if !G::has_vertex(graph, from) {
    return false
  }
  dfs_fold(graph, from, false, fn(_, v) {
    if v == to {
      (true, false)
    } else {
      (false, true)
    }
  })
}

///|
/// Would adding edge `u -> v` introduce a cycle?
///
/// A new edge `u -> v` closes a cycle iff there already exists a path
/// `v -> ... -> u` in the graph (then `u -> v -> ... -> u` is cyclic).
/// Self-loops (`u == v`) always create a cycle.
///
/// Useful for movable-tree CRDTs and reactive-graph libraries that must
/// reject cycle-creating edges before committing them. Strictly cheaper
/// than `has_cycle` on the hypothetical graph: early-exits as soon as the
/// closing path is found.
///
/// Does not require `u` or `v` to already be in the graph — a missing
/// endpoint cannot participate in any existing path, so no cycle is
/// possible unless `u == v`.
///
/// Time: O(V' + E') where V' and E' are the vertices and edges visited
/// searching from `v` for `u` (bounded by v's reachable subgraph).
pub fn[G : DirectedGraph] would_create_cycle(
  graph : G,
  u : Int,
  v : Int,
) -> Bool {
  if u == v {
    return true
  }
  is_reachable(graph, v, u)
}

///|
/// Multi-source DFS fold over vertices reachable from any vertex in `starts`.
///
/// Seeds the DFS stack with all start vertices instead of one, enabling
/// frontier-based traversal. Same motivation as `bfs_fold_multi` — see
/// its doc comment for the multi-source vs looping-single-source rationale.
///
/// ## Ordering
///
/// Start vertices are pushed in reverse order so `starts[0]` is on top
/// of the stack and processed first. When source sub-trees are disjoint,
/// `starts[0]` is fully explored before `starts[1]`. When sub-trees
/// overlap, vertices reachable from multiple starts are visited on first
/// encounter (from whichever source reaches them first in DFS order).
///
/// ## Seeding
///
/// - Invalid starts (not in the graph) are silently skipped via `has_vertex`
/// - Duplicate starts are deduplicated before traversal begins
///
/// Time: O(V + E) where V and E are the reachable vertices and edges.
/// Seed validation calls `has_vertex` — override it for O(1) on custom types.
pub fn[G : DirectedGraph, Acc] dfs_fold_multi(
  graph : G,
  starts : Array[Int],
  init : Acc,
  f : (Acc, Int) -> (Acc, Bool),
) -> Acc {
  let visited : Map[Int, Bool] = Map([])
  let stack : Array[Int] = []
  // Seed in reverse order so starts[0] ends up on top of the stack (LIFO).
  // Use visited for dedup — seeds are pushed but NOT marked as visited,
  // so the main loop's visited-check + fold runs normally for each seed.
  // After seeding, clear visited so the main loop starts fresh.
  let seen : @hashset.HashSet[Int] = @hashset.HashSet([])
  for i in (starts.length() - 1)>=..0 {
    let s = starts[i]
    if !seen.contains(s) && G::has_vertex(graph, s) {
      seen.add(s)
      stack.push(s)
    }
  }
  let mut acc = init
  while stack.length() > 0 {
    let v = stack.unsafe_pop()
    if visited.contains(v) {
      continue
    }
    visited[v] = true
    let result = f(acc, v)
    acc = result.0
    if !result.1 {
      break
    }
    // Push successors directly, then reverse in place so first successor
    // is on top of the stack. Avoids per-vertex temporary array allocation.
    let mark = stack.length()
    G::each_successor(graph, v, fn(w) {
      if !visited.contains(w) {
        stack.push(w)
      }
    })
    let mut lo = mark
    let mut hi = stack.length() - 1
    while lo < hi {
      let tmp = stack[lo]
      stack[lo] = stack[hi]
      stack[hi] = tmp
      lo = lo + 1
      hi = hi - 1
    }
  }
  acc
}

///|
/// All vertices reachable from any vertex in `starts`, in DFS pre-order.
///
/// Convenience wrapper around `dfs_fold_multi` — collects all reachable
/// vertices into an array. Same relationship as `reachable` to `dfs_fold`.
pub fn[G : DirectedGraph] reachable_multi(
  graph : G,
  starts : Array[Int],
) -> Array[Int] {
  dfs_fold_multi(graph, starts, [], fn(arr, v) {
    arr.push(v)
    (arr, true)
  })
}

///|
/// # DFS Edge Classification
///
/// Events emitted during a depth-first traversal. Every edge in the graph
/// is classified into exactly one of three types (tree, back, cross/forward),
/// and every vertex emits Discover (pre-order) and Finish (post-order).
///
/// ## Vertex coloring
///
/// - **White** (undiscovered): not yet seen by the DFS
/// - **Gray** (in progress): discovered but not finished — on the DFS stack
/// - **Black** (finished): all descendants fully explored
///
/// Edge classification follows from the target vertex's color when the edge
/// is examined: white → TreeEdge, gray → BackEdge, black → CrossForwardEdge.
pub(all) enum DfsEvent {
  /// Vertex entered — pre-order. Vertex transitions white → gray.
  Discover(Int)
  /// All descendants done — post-order. Vertex transitions gray → black.
  Finish(Int)
  /// (u, v): v was white. v will be discovered on the next `.next()` call.
  TreeEdge(Int, Int)
  /// (u, v): v is gray (ancestor on stack). Indicates a cycle: v →...→ u → v.
  BackEdge(Int, Int)
  /// (u, v): v is black (already finished). Merged forward + cross edges.
  CrossForwardEdge(Int, Int)
} derive(Eq, Debug)

///|
/// DFS event iterator — classifies every edge and emits vertex enter/exit events.
///
/// Returns a lazy `Iter[DfsEvent]`. Each `.next()` call advances the DFS by
/// one step and returns the next event. Handles disconnected components by
/// iterating all vertices from `graph.iter()`.
///
/// ## State machine
///
/// The closure captures:
/// - `enter_pending`: vertex awaiting Discover (checked first each call)
/// - `frames`: stack of `(vertex, Iter[Int])` for successor processing
/// - `state`: `Map[Int, Bool]` — absent = white, `true` = gray, `false` = black
/// - `roots`: `Iter[Int]` from `graph.iter()` for finding unvisited roots
///
/// ## Event ordering
///
/// `TreeEdge(u, v)` and `Discover(v)` are separate events on separate `.next()`
/// calls. `enter_pending` is checked before the stack, so `Discover(v)` fires
/// before u's remaining successors — correct DFS order.
///
/// Time: O(V + E). Space: O(V).
/// Benchmark: ~155µs chain, ~179µs cyclic, ~257µs diamond (1000 vertices, AdjacencyMap).
pub fn[G : DirectedGraph] dfs_events(graph : G) -> Iter[DfsEvent] {
  // absent = white (undiscovered), true = gray (on stack), false = black (finished)
  let state : Map[Int, Bool] = Map([])
  let frames : Array[(Int, Iter[Int])] = []
  let roots = G::iter(graph)
  // When set, the next event is Discover(v) and a frame is pushed.
  let mut enter_pending : Int? = None
  Iter::new(fn() {
    while true {
      match enter_pending {
        Some(v) => {
          enter_pending = None
          state[v] = true
          frames.push((v, G::successors(graph, v)))
          break Some(Discover(v))
        }
        None => ()
      }
      if frames.length() > 0 {
        let top_idx = frames.length() - 1
        let v = frames[top_idx].0
        let iter = frames[top_idx].1
        match iter.next() {
          Some(w) =>
            match state.get(w) {
              None => {
                enter_pending = Some(w)
                break Some(TreeEdge(v, w))
              }
              Some(true) => break Some(BackEdge(v, w))
              Some(false) => break Some(CrossForwardEdge(v, w))
            }
          None => {
            state[v] = false
            let _ = frames.unsafe_pop()
            break Some(Finish(v))
          }
        }
      }
      let mut found_root = false
      while roots.next() is Some(r) {
        if !state.contains(r) {
          enter_pending = Some(r)
          found_root = true
          break
        }
      }
      if !found_root {
        break None
      }
    } nobreak {
      None
    }
  })
}