///|
/// # Topological Sort (Kahn's Algorithm)
///
/// A topological ordering of a directed acyclic graph (DAG) is a linear
/// ordering of vertices such that for every edge u → v, u comes before v.
/// If the graph has a cycle, no topological ordering exists.
///
/// ## Algorithm: Kahn (1962)
///
/// 1. Compute in-degree (number of incoming edges) for each vertex.
/// 2. Enqueue all vertices with in-degree 0 (no dependencies).
/// 3. Repeatedly dequeue a vertex, add it to the result, and decrement
///    the in-degree of all its successors. When a successor's in-degree
///    reaches 0, enqueue it.
/// 4. If the result contains all vertices, return it. Otherwise, the
///    remaining vertices form a cycle — return None.
///
/// This is equivalent to repeatedly removing "ready" nodes — nodes with
/// no unsatisfied dependencies. It's the same principle behind build
/// systems (Make), package managers (dependency resolution), and
/// spreadsheet recalculation order.
///
/// ## Subset variant
///
/// `toposort_subset` sorts only a given subset of vertices, considering
/// only edges in the induced subgraph (both endpoints in the subset).
/// Scales with the subset size, not the full graph.
///
/// ## Cycle detection
///
/// Kahn's algorithm naturally detects cycles: if the result is shorter
/// than the vertex count, some vertices could never reach in-degree 0
/// because they're in a cycle. `has_cycle` is simply
/// `toposort(graph) is None`.
///
/// Time: O(V + E). Space: O(V).

///|
/// Compute in-degrees for all vertices. Shared by toposort and topo_levels.
/// Returns a Map where every vertex has an entry (0 if no incoming edges).
fn[G : DirectedGraph] compute_in_degrees(graph : G) -> Map[Int, Int] {
  let in_degree : Map[Int, Int] = Map([])
  G::each_vertex(graph, fn(v) { in_degree[v] = 0 })
  G::each_vertex(graph, fn(v) {
    G::each_successor(graph, v, fn(w) {
      let d = match in_degree.get(w) {
        Some(n) => n
        None => 0
      }
      in_degree[w] = d + 1
    })
  })
  in_degree
}

///|
/// Topological sort via Kahn's algorithm.
/// Returns `Some(ordering)` for DAGs, `None` if the graph has a cycle.
///
/// **Warning:** Self-loops (edges v -> v) are treated as cycles and cause
/// this function to return `None`. If your graph may contain self-loops
/// that you want to ignore, call `remove_self_loops()` first.
pub fn[G : DirectedGraph] toposort(graph : G) -> Array[Int]? {
  let in_degree = compute_in_degrees(graph)
  // Seed queue with zero-in-degree vertices
  let queue : Array[Int] = []
  for v, d in in_degree {
    if d == 0 {
      queue.push(v)
    }
  }
  // Process queue, building topological order
  let result : Array[Int] = []
  let mut head = 0
  while head < queue.length() {
    let v = queue[head]
    head = head + 1
    result.push(v)
    G::each_successor(graph, v, fn(w) {
      let d = match in_degree.get(w) {
        Some(n) => n
        None => 0
      }
      in_degree[w] = d - 1
      if d - 1 == 0 {
        queue.push(w)
      }
    })
  }
  // Check completeness — incomplete means a cycle exists
  let vc = G::vertex_count(graph)
  if result.length() == vc {
    Some(result)
  } else {
    None
  }
}

///|
/// Returns true if the graph contains a directed cycle.
/// A self-loop (v → v) counts as a cycle.
pub fn[G : DirectedGraph] has_cycle(graph : G) -> Bool {
  toposort(graph) is None
}

///|
/// Find a directed cycle, if any.
///
/// Returns `Some(path)` where `path = [v0, v1, ..., vk]` and there is an
/// edge `vk -> v0` closing the cycle, or `None` if the graph is acyclic.
/// Self-loops are returned as `[v]` (single vertex; the closing edge is
/// `v -> v`).
///
/// ## Algorithm
///
/// Iterative three-color DFS (white = unseen, gray = on current path,
/// black = finished). When a gray successor is found, the cycle runs from
/// that ancestor down through the current DFS frame stack. The closing
/// edge is from the last element back to the first.
///
/// The returned path is one witness — there may be others. No ordering
/// guarantee across graphs, but for a given graph traversal the output is
/// deterministic (controlled by `iter` and `successors` order).
///
/// Time: O(V + E) worst case (acyclic graph). Early-exits on first cycle.
/// Space: O(V).
pub fn[G : DirectedGraph] find_cycle(graph : G) -> Array[Int]? {
  // state: absent = white, true = gray (on stack), false = black (finished)
  let state : Map[Int, Bool] = Map([])
  // position[v] = frame index of v while v is gray, enabling O(1) cycle
  // extraction when a back-edge is encountered.
  let position : Map[Int, Int] = Map([])
  let frames : Array[(Int, Iter[Int])] = []
  for root in G::iter(graph) {
    if state.contains(root) {
      continue
    }
    state[root] = true
    position[root] = 0
    frames.push((root, G::successors(graph, root)))
    while 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 => {
              // Tree edge: descend into w
              state[w] = true
              position[w] = frames.length()
              frames.push((w, G::successors(graph, w)))
            }
            Some(true) => {
              // Back edge v -> w: w is an ancestor on the current path.
              // Extract cycle from frames[position[w]..=top_idx].
              let start = position[w]
              let cycle : Array[Int] = []
              for i in start..<=top_idx {
                cycle.push(frames[i].0)
              }
              return Some(cycle)
            }
            Some(false) => ()
            // Cross/forward edge — not a cycle on this path
          }
        None => {
          // All successors done — finish v
          state[v] = false
          position.remove(v)
          let _ = frames.unsafe_pop()
        }
      }
    }
  }
  None
}

///|
/// Topological sort that returns the witnessing cycle on failure.
///
/// `Ok(ordering)` for DAGs, `Err(cycle)` where `cycle = [v0, ..., vk]` with
/// a closing edge `vk -> v0` when the graph has a cycle. Strictly more
/// informative than `toposort` — use this when the caller wants to
/// diagnose or report the cycle (reactive-graph cycle paths, movable-tree
/// conflict diagnostics, build-system dependency errors).
///
/// Runs `toposort` first (O(V+E), Kahn's algorithm) and falls back to
/// `find_cycle` on failure — so the acyclic path pays the same cost as
/// plain `toposort`.
pub fn[G : DirectedGraph] toposort_or_cycle(
  graph : G,
) -> Result[Array[Int], Array[Int]] {
  match toposort(graph) {
    Some(order) => Ok(order)
    None =>
      match find_cycle(graph) {
        Some(cycle) => Err(cycle)
        // Only reachable if the `DirectedGraph` contract is violated:
        // `toposort` counts `successors(v)` vertices missing from `iter()`
        // against its completeness check, while `find_cycle` only roots
        // from `iter()`. On contract-compliant graphs this branch is dead.
        // Return an empty witness rather than panic.
        None => Err([])
      }
  }
}

///|
/// # Topological Levels
///
/// Computes the length of the longest path from any source (zero-in-degree
/// vertex) to each vertex in a DAG. Sources get level 0, their successors
/// get level 1, and so on.
///
/// ## Why longest path, not shortest?
///
/// Shortest-path levels are insufficient for glitch-free scheduling.
/// Consider: if vertex C has predecessors A (level 0) and B (level 1),
/// shortest-path would assign C level 1, allowing C to fire before B
/// updates — a glitch. Longest-path assigns C level 2, guaranteeing
/// both A and B fire before C.
///
/// This is exactly the level-sorted BFS schedule used by reactive
/// frameworks like incr for glitch-free push propagation: process
/// vertices in ascending level order and every node sees all its
/// dependencies before it fires.
///
/// ## Cycle detection
///
/// Like `toposort`, this is a modified Kahn's algorithm. If not all
/// vertices are processed, a cycle exists and the function returns `None`.
/// Self-loops (v → v) count as cycles.
///
/// ## Return value
///
/// `Map[Int, Int]?` mapping each vertex to its level, or `None` if the
/// graph has a cycle. The map preserves the original vertex IDs (works
/// for both sparse `AdjacencyMap` and dense `DenseGraph` IDs).
///
/// Time: O(V + E). Space: O(V).
pub fn[G : DirectedGraph] topo_levels(graph : G) -> Map[Int, Int]? {
  let in_degree = compute_in_degrees(graph)
  // Step 1: Seed queue with sources (in-degree 0) at level 0
  let levels : Map[Int, Int] = Map([])
  let queue : Array[Int] = []
  for v, d in in_degree {
    if d == 0 {
      levels[v] = 0
      queue.push(v)
    }
  }
  // Step 3: BFS — propagate levels through the graph.
  // Each vertex's level = max(predecessor_level + 1) across all predecessors.
  // This ensures longest-path semantics for glitch-free scheduling.
  let mut head = 0
  let mut processed = 0
  while head < queue.length() {
    let v = queue[head]
    head = head + 1
    processed = processed + 1
    let v_level = match levels.get(v) {
      Some(l) => l
      None => 0
    }
    G::each_successor(graph, v, fn(w) {
      let d = match in_degree.get(w) {
        Some(n) => n
        None => 0
      }
      in_degree[w] = d - 1
      // Update w's level to the max across all predecessors
      let current_level = match levels.get(w) {
        Some(l) => l
        None => 0
      }
      let new_level = v_level + 1
      if new_level > current_level {
        levels[w] = new_level
      }
      if d - 1 == 0 {
        queue.push(w)
      }
    })
  }
  // Step 4: Check completeness — if fewer vertices processed than exist,
  // the remainder are in a cycle and could never reach in-degree 0.
  if processed != in_degree.length() {
    return None
  }
  Some(levels)
}

///|
/// Topological sort over the induced subgraph of `vertices`.
///
/// Only edges where both endpoints are in `vertices` are considered.
/// Returns `Some(ordering)` if the induced subgraph is a DAG, `None`
/// if it contains a cycle. Returns `Some([])` for an empty vertex set.
/// Duplicate vertices in the input are handled correctly.
///
/// **Input validation:** Invalid vertex IDs (not present in the graph)
/// are silently filtered out rather than causing errors or panics.
/// This makes `toposort_subset` composable — callers don't need to
/// pre-validate their vertex list against the graph, which matters
/// when the list may lag behind graph mutations. The filtering cost
/// is O(k) with O(1) `has_vertex` overrides (AdjacencyMap, DenseGraph),
/// or O(k * V) for types using the O(V) default.
///
/// Time: O(V_sub + E_sub). Space: O(V_sub).
pub fn[G : DirectedGraph] toposort_subset(
  graph : G,
  vertices : Array[Int],
) -> Array[Int]? {
  // Build membership set and deduplicated vertex list (preserves input order).
  // has_vertex filters out IDs not in the graph — prevents panics on
  // DenseGraph (out-of-bounds) and inconsistent results on AdjacencyMap
  // (unknown IDs treated as isolated vertices with in-degree 0).
  let subset : @hashset.HashSet[Int] = @hashset.HashSet([])
  let unique : Array[Int] = []
  for v in vertices {
    if !subset.contains(v) && G::has_vertex(graph, v) {
      subset.add(v)
      unique.push(v)
    }
  }
  let n = unique.length()
  if n == 0 {
    return Some([])
  }
  // Compute in-degrees within the induced subgraph
  let in_degree : @hashmap.HashMap[Int, Int] = @hashmap.HashMap([])
  for v in unique {
    G::each_successor(graph, v, fn(w) {
      if subset.contains(w) {
        match in_degree.get(w) {
          Some(d) => in_degree[w] = d + 1
          None => in_degree[w] = 1
        }
      }
    })
  }
  // Seed queue with zero-in-degree subset vertices (input order)
  let queue : Array[Int] = []
  for v in unique {
    if !in_degree.contains(v) {
      queue.push(v)
    }
  }
  // Process queue
  let result : Array[Int] = []
  let mut head = 0
  while head < queue.length() {
    let v = queue[head]
    head = head + 1
    result.push(v)
    G::each_successor(graph, v, fn(w) {
      if subset.contains(w) {
        match in_degree.get(w) {
          Some(d) => {
            in_degree[w] = d - 1
            if d - 1 == 0 {
              queue.push(w)
            }
          }
          None => ()
        }
      }
    })
  }
  if result.length() == n {
    Some(result)
  } else {
    None
  }
}