/**
 * lib/graph.ts — Shared graph algorithms for BA planning CLIs.
 *
 * Provides cycle detection (Tarjan SCC) and cycle collapsing for topological
 * sort. Used by both create-plan-development and create-ba-order.
 */

// ---------------------------------------------------------------------------
// Types
// ---------------------------------------------------------------------------

export interface CollapsedGraph {
  /** Adjacency of group IDs (group = cycle members or single node). */
  collapsedAdj: Map<string, Set<string>>;
  /** Map each node key to its group ID. */
  nodeToGroup: Map<string, string>;
  /** Map each group ID to its member node keys. */
  groupMembers: Map<string, string[]>;
}

// ---------------------------------------------------------------------------
// Tarjan's SCC — finds all strongly connected components of size > 1 (cycles)
// ---------------------------------------------------------------------------

/**
 * Detect cycles in a directed graph using Tarjan's algorithm.
 * Returns an array of cycles (each cycle = array of node keys).
 * Only reports SCCs with size > 1 (actual cycles).
 * Complexity: O(V + E).
 */
export function tarjanSCC(
  nodes: string[],
  adjacency: Map<string, Set<string>>,
): string[][] {
  let index = 0;
  const stack: string[] = [];
  const onStack = new Set<string>();
  const indices = new Map<string, number>();
  const lowlinks = new Map<string, number>();
  const sccs: string[][] = [];

  function strongConnect(v: string): void {
    indices.set(v, index);
    lowlinks.set(v, index);
    index++;
    stack.push(v);
    onStack.add(v);

    const neighbors = adjacency.get(v) ?? new Set();
    for (const w of neighbors) {
      if (!indices.has(w)) {
        strongConnect(w);
        lowlinks.set(v, Math.min(lowlinks.get(v)!, lowlinks.get(w)!));
      } else if (onStack.has(w)) {
        lowlinks.set(v, Math.min(lowlinks.get(v)!, indices.get(w)!));
      }
    }

    if (lowlinks.get(v) === indices.get(v)) {
      const scc: string[] = [];
      let w: string;
      do {
        w = stack.pop()!;
        onStack.delete(w);
        scc.push(w);
      } while (w !== v);

      // Only report cycles (SCC with more than 1 node)
      if (scc.length > 1) {
        sccs.push(scc);
      }
    }
  }

  for (const node of nodes) {
    if (!indices.has(node)) {
      strongConnect(node);
    }
  }

  return sccs;
}

// ---------------------------------------------------------------------------
// Collapse cycles into virtual group nodes for Kahn's
// ---------------------------------------------------------------------------

/**
 * Replace each cycle with a single virtual group node so that the graph
 * becomes a DAG suitable for Kahn's topological sort.
 *
 * Non-cycle nodes become their own 1-member group (groupId = node key).
 * Cycle members share a group (groupId = `cycle_0`, `cycle_1`, …).
 */
export function collapseCycles(
  nodes: string[],
  adjacency: Map<string, Set<string>>,
  cycles: string[][],
): CollapsedGraph {
  const nodeToGroup = new Map<string, string>();
  const groupMembers = new Map<string, string[]>();

  // Assign cycle members to their group
  for (let i = 0; i < cycles.length; i++) {
    const groupId = `cycle_${i}`;
    groupMembers.set(groupId, cycles[i]);
    for (const member of cycles[i]) {
      nodeToGroup.set(member, groupId);
    }
  }

  // Assign non-cycle nodes to their own group
  for (const node of nodes) {
    if (!nodeToGroup.has(node)) {
      nodeToGroup.set(node, node);
      groupMembers.set(node, [node]);
    }
  }

  // Build collapsed adjacency
  const collapsedAdj = new Map<string, Set<string>>();
  for (const groupId of groupMembers.keys()) {
    collapsedAdj.set(groupId, new Set());
  }

  for (const node of nodes) {
    const fromGroup = nodeToGroup.get(node)!;
    const neighbors = adjacency.get(node) ?? new Set();
    for (const neighbor of neighbors) {
      const toGroup = nodeToGroup.get(neighbor);
      if (toGroup && toGroup !== fromGroup) {
        collapsedAdj.get(fromGroup)!.add(toGroup);
      }
    }
  }

  return { collapsedAdj, nodeToGroup, groupMembers };
}