///|
/// # DenseGraph — flat adjacency representation for dense vertex IDs
///
/// Stores a directed graph as `Array[Array[Int]]` where vertex v's
/// successors are at `successors[v]`. Requires dense vertex IDs in
/// range 0..vertex_count-1.
///
/// ## When to use
///
/// Use `DenseGraph` when:
/// - Vertex IDs are integers in 0..n-1 (common for internal algorithms)
/// - You need maximum traversal performance (8–23x faster than AdjacencyMap)
/// - You're running algorithms repeatedly on the same graph
///
/// Use `AdjacencyMap` when:
/// - Vertex IDs are sparse or non-contiguous
/// - You need algebraic graph operations (overlay, connect)
/// - You're building graphs via the `GraphSym` construction layer
///
/// ## Conversion
///
/// `AdjacencyMap` → `DenseGraph` via `DenseGraph::from_adjacency_map`
/// (requires dense vertex IDs starting from 0).
///
/// ## Performance characteristics
///
/// | Operation        | AdjacencyMap    | DenseGraph      |
/// |------------------|-----------------|-----------------|
/// | successor lookup | O(log V) (Map)  | O(1) (Array)    |
/// | transpose        | O(1)            | O(1)            |
/// | DFS reachable    | ~94 µs (1000V)  | ~7 µs (1000V)   |
/// | SCC              | ~460 µs (1000V) | ~50 µs (1000V)  |
pub struct DenseGraph {
  successors : Array[Array[Int]]
  predecessors : Array[Array[Int]]
}

///|
/// Build from edge list. Duplicate edges are silently ignored.
///
/// Aborts if any vertex in the edge list is outside 0..vertex_count-1.
pub fn DenseGraph::from_edges(
  vertex_count : Int,
  edges : Array[(Int, Int)],
) -> DenseGraph {
  let succs : Array[Array[Int]] = Array::makei(vertex_count, fn(_i) { [] })
  let preds : Array[Array[Int]] = Array::makei(vertex_count, fn(_i) { [] })
  let seen : Array[@hashset.HashSet[Int]] = Array::makei(vertex_count, fn(_i) {
    @hashset.HashSet([])
  })
  for edge in edges {
    let u = edge.0
    let v = edge.1
    guard u >= 0 && u < vertex_count && v >= 0 && v < vertex_count else {
      abort(
        "DenseGraph::from_edges: vertex out of range 0..\{vertex_count - 1}: edge (\{u}, \{v})",
      )
    }
    if !seen[u].contains(v) {
      seen[u].add(v)
      succs[u].push(v)
      preds[v].push(u)
    }
  }
  { successors: succs, predecessors: preds }
}

///|
/// Convert from AdjacencyMap.
///
/// Aborts if the AdjacencyMap contains vertex IDs outside 0..n-1
/// (where n is the vertex count). Use only with AdjacencyMaps that
/// have dense, zero-based vertex IDs.
pub fn DenseGraph::from_adjacency_map(am : AdjacencyMap) -> DenseGraph {
  let n = am.vertex_count()
  let succs : Array[Array[Int]] = Array::makei(n, fn(_i) { [] })
  let preds : Array[Array[Int]] = Array::makei(n, fn(_i) { [] })
  for v, s in am.adjacency {
    guard v >= 0 && v < n else {
      abort(
        "DenseGraph::from_adjacency_map: vertex \{v} out of range 0..\{n - 1}",
      )
    }
    succs[v] = s.copy()
    for w in s {
      guard w >= 0 && w < n else {
        abort(
          "DenseGraph::from_adjacency_map: successor \{w} of vertex \{v} out of range 0..\{n - 1}",
        )
      }
      preds[w].push(v)
    }
  }
  { successors: succs, predecessors: preds }
}

///|
/// Reverse all edge directions. O(1) — swaps successor and predecessor arrays.
pub fn DenseGraph::transpose(self : DenseGraph) -> DenseGraph {
  { successors: self.predecessors, predecessors: self.successors }
}

///|
/// Show implementation for DenseGraph.
/// Format: `DenseGraph(3 vertices, [0 -> [1, 2], 1 -> [2]])`
pub impl Show for DenseGraph with fn output(self, logger) {
  let n = self.successors.length()
  logger.write_string("DenseGraph(")
  logger.write_string(n.to_string())
  logger.write_string(" vertices, [")
  let mut first = true
  for v = 0; v < n; v = v + 1 {
    let succs = self.successors[v]
    if succs.length() > 0 {
      if !first {
        logger.write_string(", ")
      }
      first = false
      logger.write_string(v.to_string())
      logger.write_string(" -> [")
      for j, w in succs {
        if j > 0 {
          logger.write_string(", ")
        }
        logger.write_string(w.to_string())
      }
      logger.write_string("]")
    }
  }
  logger.write_string("])")
}

///|
/// Debug implementation for DenseGraph.
/// Produces structured Repr showing vertex count and edges.
pub impl Debug for DenseGraph with fn to_repr(self) {
  let fields : Map[String, @debug.Repr] = Map([])
  fields["vertex_count"] = @debug.to_repr(self.successors.length())
  let edges : Array[@debug.Repr] = []
  for v = 0; v < self.successors.length(); v = v + 1 {
    for w in self.successors[v] {
      edges.push(@debug.Repr::tuple([@debug.to_repr(v), @debug.to_repr(w)]))
    }
  }
  fields["edges"] = @debug.Repr::array(edges)
  @debug.Repr::opaque_("DenseGraph", @debug.Repr::record(fields))
}

///|
pub impl VertexSet for DenseGraph with fn iter(self) {
  (0).until(self.successors.length())
}

///|
/// O(1) override — array length, bypasses the O(V) default iteration.
pub impl VertexSet for DenseGraph with fn vertex_count(self) {
  self.successors.length()
}

///|
pub impl Successors for DenseGraph with fn successors(self, v) {
  if v >= 0 && v < self.successors.length() {
    self.successors[v].iter()
  } else {
    Iter::empty()
  }
}

///|
/// O(1) override — range check on dense 0..n-1 vertex IDs.
pub impl VertexSet for DenseGraph with fn has_vertex(self, v) {
  v >= 0 && v < self.successors.length()
}

///|
/// DFS fold with direct array access + `FixedArray[Bool]` visited set.
/// Eliminates `Map[Int, Bool]` (O(log V) → O(1)) and `each_successor`
/// callback dispatch (→ direct `Array[Int]` iteration).
pub impl Successors for DenseGraph with fn dfs_fold(self, start, init, f) {
  let n = self.successors.length()
  if start < 0 || start >= n {
    return init
  }
  let visited = FixedArray::make(n, false)
  let stack : Array[Int] = [start]
  let mut acc = init
  while stack.length() > 0 {
    let v = stack.unsafe_pop()
    if visited[v] {
      continue
    }
    visited[v] = true
    let result = f(acc, v)
    acc = result.0
    if !result.1 {
      break
    }
    let succs = self.successors[v]
    for i in (succs.length() - 1)>=..0 {
      let w = succs[i]
      if !visited[w] {
        stack.push(w)
      }
    }
  }
  acc
}

///|
/// BFS fold with direct array access + `FixedArray[Bool]` visited set.
/// Eliminates `Map[Int, Bool]` (O(log V) → O(1)) and `each_successor`
/// callback dispatch (→ direct `Array[Int]` iteration).
pub impl Successors for DenseGraph with fn bfs_fold(self, start, init, f) {
  let n = self.successors.length()
  if start < 0 || start >= n {
    return init
  }
  let visited = FixedArray::make(n, false)
  let queue : Array[Int] = [start]
  visited[start] = true
  let mut acc = init
  let mut head = 0
  while head < queue.length() {
    let v = queue[head]
    head = head + 1
    let result = f(acc, v)
    acc = result.0
    if !result.1 {
      break
    }
    let succs = self.successors[v]
    for w in succs {
      if !visited[w] {
        visited[w] = true
        queue.push(w)
      }
    }
  }
  acc
}

///|
pub impl DirectedGraph for DenseGraph

///|
pub impl Predecessors for DenseGraph with fn predecessors(self, v) {
  if v >= 0 && v < self.predecessors.length() {
    self.predecessors[v].iter()
  } else {
    Iter::empty()
  }
}

// ============================================================
// Optimized algorithms — bypass trait dispatch + callbacks
// ============================================================

///|
/// DFS reachable with direct array access. No trait dispatch, no callbacks,
/// no per-vertex allocation. Allocates a fresh visited set per call.
///
/// Returns empty array if `start` is not a valid vertex.
pub fn DenseGraph::reachable(self : DenseGraph, start : Int) -> Array[Int] {
  let n = self.successors.length()
  if start < 0 || start >= n {
    return []
  }
  let visited = FixedArray::make(n, false)
  let stack : Array[Int] = [start]
  let result : Array[Int] = []
  while stack.length() > 0 {
    let v = stack.unsafe_pop()
    if visited[v] {
      continue
    }
    visited[v] = true
    result.push(v)
    let succs = self.successors[v]
    for i in (succs.length() - 1)>=..0 {
      let w = succs[i]
      if !visited[w] {
        stack.push(w)
      }
    }
  }
  result
}

///|
/// Topological sort with direct array access.
pub fn DenseGraph::toposort(self : DenseGraph) -> Array[Int]? {
  let n = self.successors.length()
  let in_degree = Array::make(n, 0)
  for u = 0; u < n; u = u + 1 {
    for v in self.successors[u] {
      in_degree[v] = in_degree[v] + 1
    }
  }
  let queue : Array[Int] = []
  for v = 0; v < n; v = v + 1 {
    if in_degree[v] == 0 {
      queue.push(v)
    }
  }
  let result : Array[Int] = []
  let mut head = 0
  while head < queue.length() {
    let v = queue[head]
    head = head + 1
    result.push(v)
    for w in self.successors[v] {
      in_degree[w] = in_degree[w] - 1
      if in_degree[w] == 0 {
        queue.push(w)
      }
    }
  }
  if result.length() == n {
    Some(result)
  } else {
    None
  }
}

///|
pub fn DenseGraph::has_cycle(self : DenseGraph) -> Bool {
  self.toposort() is None
}

///|
/// Strongly connected components via Kosaraju's algorithm.
/// Both DFS passes and transpose use direct array access.
pub fn DenseGraph::scc(self : DenseGraph) -> Array[Array[Int]] {
  let n = self.successors.length()
  let visited = FixedArray::make(n, false)
  let finish_order : Array[Int] = []
  // Pass 1: forward DFS — record finish order
  for root = 0; root < n; root = root + 1 {
    if visited[root] {
      continue
    }
    let stack : Array[(Int, Int)] = [(root, 0)]
    visited[root] = true
    while stack.length() > 0 {
      let top_idx = stack.length() - 1
      let v = stack[top_idx].0
      let si = stack[top_idx].1
      let succs = self.successors[v]
      if si < succs.length() {
        stack[top_idx] = (v, si + 1)
        let w = succs[si]
        if !visited[w] {
          visited[w] = true
          stack.push((w, 0))
        }
      } else {
        let _ = stack.unsafe_pop()
        finish_order.push(v)
      }
    }
  }
  // Pass 2: transpose (flat → flat)
  let transposed = self.transpose()
  // Pass 3: backward DFS in reverse finish order
  let visited2 = FixedArray::make(n, false)
  let components : Array[Array[Int]] = []
  for i in (finish_order.length() - 1)>=..0 {
    let root = finish_order[i]
    if visited2[root] {
      continue
    }
    let component : Array[Int] = []
    let stack : Array[Int] = [root]
    visited2[root] = true
    while stack.length() > 0 {
      let v = stack.unsafe_pop()
      component.push(v)
      let succs = transposed.successors[v]
      for j in (succs.length() - 1)>=..0 {
        let w = succs[j]
        if !visited2[w] {
          visited2[w] = true
          stack.push(w)
        }
      }
    }
    components.push(component)
  }
  components
}

///|
/// DFS event iterator — classifies every edge and emits vertex enter/exit events.
///
/// Uses `FixedArray[Int]` (0=white, 1=gray, 2=black) for O(1) vertex state
/// lookups instead of the generic `Map[Int, Bool]` (O(log V)). Same event
/// ordering as `@alga.dfs_events` for any `DirectedGraph`.
///
/// 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 0..n-1.
///
/// Time: O(V + E). Space: O(V).
pub fn DenseGraph::dfs_events(self : DenseGraph) -> Iter[DfsEvent] {
  let n = self.successors.length()
  // 0 = white (undiscovered), 1 = gray (on stack), 2 = black (finished)
  let state = FixedArray::make(n, 0)
  let frames : Array[(Int, Iter[Int])] = []
  let mut root_idx = 0
  // 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] = 1
          frames.push((v, self.successors[v].iter()))
          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[w] {
              0 => {
                enter_pending = Some(w)
                break Some(TreeEdge(v, w))
              }
              1 => break Some(BackEdge(v, w))
              2 => break Some(CrossForwardEdge(v, w))
              _ => abort(
                "DenseGraph::dfs_events: invalid state \{state[w]} for vertex \{w}",
              )
            }
          None => {
            state[v] = 2
            let _ = frames.unsafe_pop()
            break Some(Finish(v))
          }
        }
      }
      let mut found_root = false
      while root_idx < n {
        if state[root_idx] == 0 {
          enter_pending = Some(root_idx)
          root_idx = root_idx + 1
          found_root = true
          break
        }
        root_idx = root_idx + 1
      }
      if !found_root {
        break None
      }
    } nobreak {
      None
    }
  })
}

// ============================================================
// GenCounter methods — reusable FixedArray[Int] + generation counter
// ============================================================

///|
/// Early-exit reachability query using a reusable generation-counter buffer.
///
/// Like `@alga.is_reachable` but eliminates per-call `FixedArray[Bool]`
/// allocation + zeroing by reusing `marks: FixedArray[Int]` across calls.
/// Each call consumes one generation token — increment `gen` between calls.
///
/// Stops as soon as `to` is discovered without materializing the full
/// reachable set.
///
/// ## Contract
///
/// - `marks.length()` must be ≥ the graph's vertex count. Aborts otherwise.
/// - `gen` must be ≠ 0 (0 is the initial blank state). Start at gen = 1
///   and increment between calls.
/// - Caller is responsible for resetting the buffer before gen wraps
///   (see `reachable_gen` doc for overflow guidance).
///
/// Returns `false` if `from` is not a valid vertex.
///
/// Time: O(V' + E') where V'/E' are visited before encountering `to`.
/// ~1.2× faster than repeated `DenseGraph::reachable` on deep graphs.
pub fn DenseGraph::is_reachable_gen(
  self : DenseGraph,
  from : Int,
  to : Int,
  marks : FixedArray[Int],
  gen : Int,
) -> Bool {
  let n = self.successors.length()
  guard marks.length() >= n else {
    abort(
      "DenseGraph::is_reachable_gen: marks.length() = \{marks.length()} < vertex_count = \{n}",
    )
  }
  guard gen != 0 else {
    abort("DenseGraph::is_reachable_gen: gen must be ≠ 0")
  }
  if from < 0 || from >= n {
    return false
  }
  if from == to {
    return true
  }
  let stack : Array[Int] = [from]
  while stack.length() > 0 {
    let v = stack.unsafe_pop()
    if marks[v] == gen {
      continue
    }
    marks[v] = gen
    let succs = self.successors[v]
    for i in (succs.length() - 1)>=..0 {
      let w = succs[i]
      if w == to {
        return true
      }
      if marks[w] != gen {
        stack.push(w)
      }
    }
  }
  false
}

///|
/// All vertices reachable from `start` using a reusable generation-counter
/// buffer.
///
/// Like `DenseGraph::reachable` but eliminates per-call `FixedArray[Bool]`
/// allocation + zeroing by reusing `marks: FixedArray[Int]` across calls.
/// Each call consumes one generation token — increment `gen` between calls.
///
/// ## Contract
///
/// - `marks.length()` must be ≥ the graph's vertex count. Aborts otherwise.
/// - `gen` must be ≠ 0 (0 is the initial blank state). Start at gen = 1
///   and increment between calls.
/// - No entry in `marks[0.. Array[Int] {
  let n = self.successors.length()
  guard marks.length() >= n else {
    abort(
      "DenseGraph::reachable_gen: marks.length() = \{marks.length()} < vertex_count = \{n}",
    )
  }
  guard gen != 0 else {
    abort("DenseGraph::reachable_gen: gen must be ≠ 0")
  }
  if start < 0 || start >= n {
    return []
  }
  let stack : Array[Int] = [start]
  let result : Array[Int] = []
  while stack.length() > 0 {
    let v = stack.unsafe_pop()
    if marks[v] == gen {
      continue
    }
    marks[v] = gen
    result.push(v)
    let succs = self.successors[v]
    for i in (succs.length() - 1)>=..0 {
      let w = succs[i]
      if marks[w] != gen {
        stack.push(w)
      }
    }
  }
  result
}