// Pure Auto-Layout for the VSM editor canvas (Wertstrom P3, KAR-878/KAR-986,
// Capability-Matrix A2). Deterministic, no React/DOM — same "pure geometry"
// discipline as vsm-geometry.ts (NODE_W/getNodeH reused from there, not
// redefined). Callable from both the Quick-Start-Wizard (initial layout of a
// freshly generated Wertstrom, vsm-wizard-logic.ts) and the editor's
// "Automatisch anordnen" button (re-layout of an existing, possibly
// hand-arranged graph, vsm-editor.tsx) — same function, same rules, per the
// P3-Brief ("Aufrufbar aus Wizard UND als Button im Editor").
//
// execution-prompt §10.5/§11.1: supplier left, customer right, production
// control/information flows above, inventories between processes, timeline
// below (the timeline itself is vsm-timeline-ladder.tsx, not this module).
//
// Algorithm (three passes, cheapest-first):
//  1. "Chain" nodes (supplier/customer/process/machine/transport/timevalue,
//     MINUS any "information-only" node from pass 3, MINUS inventory) are
//     ordered by a topological sort over materialFlow connections (Kahn's
//     algorithm, deterministic tie-break = original `nodes` array index) and
//     placed left-to-right at a fixed pitch on one baseline row, vertically
//     centered against the tallest chain node type (process/machine, 110px —
//     shorter types like supplier/customer/transport/timevalue, 80px, are
//     nudged down 15px so their vertical centers line up). A perfectly
//     linear chain (the Wizard's own output, or any well-formed manual
//     Wertstrom) sorts into exactly its natural order; anything the graph
//     can't resolve (disconnected nodes, a cycle) is appended in original
//     array order rather than dropped or throwing — Auto-Layout must never
//     lose a node.
//  2. Inventory nodes are placed on a row BELOW the chain, at the x-midpoint
//     between their resolved chain predecessor/successor (found via a
//     materialFlow connection touching them — since every node shares the
//     same NODE_W, averaging left-edge x's centers the inventory node
//     exactly between its neighbors' centers). Unresolvable inventory (no
//     such neighbor — an orphan node) falls back to sequential placement
//     after the chain. Two inventories that resolve to the exact same slot
//     are staggered (offset further down) — the "versetzt" the P3-Brief asks
//     for — deterministic by original array order.
//  3. "Information-only" nodes — anything not supplier/customer/inventory
//     whose EVERY connection is `kind === 'information'` (at least one such
//     connection; a node with zero connections is never info-only, it's an
//     ordinary disconnected chain node handled by pass 1) — are placed on a
//     row ABOVE the chain, x = average of their connected neighbors'
//     resolved x (already placed in pass 1/2), falling back to sequential
//     placement when no neighbor has resolved yet. Same same-slot stagger
//     as pass 2 (offset further UP instead of down) — Review-Fix F4.
//
// Same known limitation lib/vsm-engine documents elsewhere (Gap G6): a
// linear/topological ordering, not a true DAG layout — a genuinely branching
// value stream (two parallel process paths merging into one customer) still
// gets ONE single-file ordering, not a multi-lane layout. Acceptable for the
// Simplicity-Doktrin's primary case (a normal linear value stream, §10.5)
// and documented here, not hidden.

import type { VsmConnection, VsmNode } from '@/lib/vsm-types'
import { NODE_W, getNodeH } from './vsm-geometry'

export interface AutoLayoutPosition {
  x: number
  y: number
}

const START_X = 40
const GAP_X = 40
const Y_MAIN = 200
const MAIN_ROW_H = getNodeH('process') // 110 — the tallest main-row node type
const Y_INVENTORY_ROW = Y_MAIN + MAIN_ROW_H + 60
const Y_INFO_GAP_ABOVE = 60
// Review-Fix F9: was a freestanding magic number (50) smaller than
// getNodeH('inventory') (80) — two staggered inventories at the same x-slot
// overlapped by 30px (the second box started before the first one ended).
// Tied to getNodeH('inventory') + a small safety gap so staggered nodes
// never touch, independent of future height changes.
const STAGGER_Y = getNodeH('inventory') + 10

function isMaterialFlow(c: VsmConnection): boolean {
  return c.kind === undefined || c.kind === 'materialFlow'
}

/** A node is "information-only" when it is not supplier/customer/inventory
 * (those have a fixed structural role regardless of what they're connected
 * to) AND every connection touching it is `kind === 'information'` AND it
 * has at least one such connection — a bare disconnected node is never
 * info-only, see module doc. */
function isInformationOnly(node: VsmNode, connections: VsmConnection[]): boolean {
  if (node.type === 'supplier' || node.type === 'customer' || node.type === 'inventory') return false
  const touching = connections.filter((c) => c.fromNodeId === node.id || c.toNodeId === node.id)
  if (touching.length === 0) return false
  return touching.every((c) => c.kind === 'information')
}

/**
 * Kahn's topological sort restricted to `ids`, using only materialFlow
 * connections between members of `ids` (self-loops ignored). Deterministic
 * tie-break: the original index in `order` (the full node array) — never
 * Set/Map iteration order, and re-applied every time a new node becomes
 * ready (not just at start), so a late-readied node is inserted ahead of an
 * earlier-readied one when its original position says it should come first.
 * Nodes the graph can't place (a cycle, or unreachable from any in-degree-0
 * start) are appended at the end in original order, never dropped.
 */
function topoOrder(ids: string[], connections: VsmConnection[], order: Map<string, number>): string[] {
  const idSet = new Set(ids)
  const edges = connections.filter((c) => isMaterialFlow(c) && idSet.has(c.fromNodeId) && idSet.has(c.toNodeId) && c.fromNodeId !== c.toNodeId)
  const inDegree = new Map<string, number>(ids.map((id) => [id, 0]))
  const outgoing = new Map<string, string[]>(ids.map((id) => [id, []]))
  for (const e of edges) {
    inDegree.set(e.toNodeId, (inDegree.get(e.toNodeId) ?? 0) + 1)
    outgoing.get(e.fromNodeId)?.push(e.toNodeId)
  }

  const byOriginalOrder = (a: string, b: string) => (order.get(a) ?? 0) - (order.get(b) ?? 0)
  const ready = ids.filter((id) => (inDegree.get(id) ?? 0) === 0).sort(byOriginalOrder)
  const result: string[] = []
  const visited = new Set<string>()

  while (ready.length > 0) {
    const id = ready.shift() as string
    if (visited.has(id)) continue
    visited.add(id)
    result.push(id)
    const next = (outgoing.get(id) ?? []).slice().sort(byOriginalOrder)
    for (const n of next) {
      if (visited.has(n)) continue
      const remaining = (inDegree.get(n) ?? 0) - 1
      inDegree.set(n, remaining)
      if (remaining === 0) {
        const idx = ready.findIndex((r) => byOriginalOrder(r, n) > 0)
        if (idx === -1) ready.push(n)
        else ready.splice(idx, 0, n)
      }
    }
  }

  const leftover = ids.filter((id) => !visited.has(id)).sort(byOriginalOrder)
  return [...result, ...leftover]
}

/**
 * A2 Auto-Layout. Returns the new `{x,y}` for every node in `nodes` — the
 * caller applies it (e.g. `setNodes(prev => prev.map(n => ({ ...n,
 * ...positions[n.id] })))`); this function never mutates or reads DOM/React
 * state. Manual layout is never read back — a re-run always repositions
 * every node from scratch, deterministically, from `nodes`/`connections`
 * alone (see vsm-editor.tsx's "Automatisch anordnen" button, which confirms
 * with the user first — this function itself has no notion of "confirmed").
 */
export function computeAutoLayout(nodes: VsmNode[], connections: VsmConnection[]): Record<string, AutoLayoutPosition> {
  const order = new Map(nodes.map((n, i) => [n.id, i]))
  const positions: Record<string, AutoLayoutPosition> = {}

  const infoOnlyIds = new Set(nodes.filter((n) => isInformationOnly(n, connections)).map((n) => n.id))
  const inventoryNodes = nodes.filter((n) => n.type === 'inventory')
  const chainNodes = nodes.filter((n) => n.type !== 'inventory' && !infoOnlyIds.has(n.id))
  const nodeById = new Map(nodes.map((n) => [n.id, n]))

  // Pass 1 — chain (supplier/process/machine/transport/timevalue/customer).
  const chainOrder = topoOrder(
    chainNodes.map((n) => n.id),
    connections,
    order,
  )
  chainOrder.forEach((id, i) => {
    const node = nodeById.get(id)
    if (!node) return
    positions[id] = {
      x: START_X + i * (NODE_W + GAP_X),
      y: Y_MAIN + (MAIN_ROW_H - getNodeH(node.type)) / 2,
    }
  })

  // Pass 2 — inventory, spliced between its resolved predecessor/successor.
  const inventorySlotCollisions = new Map<number, number>()
  let inventoryFallbackIndex = chainOrder.length
  for (const invNode of inventoryNodes) {
    const pred = connections.find((c) => isMaterialFlow(c) && c.toNodeId === invNode.id && positions[c.fromNodeId])
    const succ = connections.find((c) => isMaterialFlow(c) && c.fromNodeId === invNode.id && positions[c.toNodeId])
    let x: number
    if (pred && succ) {
      x = Math.round((positions[pred.fromNodeId].x + positions[succ.toNodeId].x) / 2)
    } else if (pred) {
      x = positions[pred.fromNodeId].x
    } else if (succ) {
      x = positions[succ.toNodeId].x
    } else {
      x = START_X + inventoryFallbackIndex * (NODE_W + GAP_X)
      inventoryFallbackIndex++
    }
    const collision = inventorySlotCollisions.get(x) ?? 0
    inventorySlotCollisions.set(x, collision + 1)
    positions[invNode.id] = { x, y: Y_INVENTORY_ROW + collision * STAGGER_Y }
  }

  // Pass 3 — information-only nodes, row above the chain. Review-Fix F4:
  // same collision-staggering idea as Pass 2's inventorySlotCollisions —
  // without it, two info-only nodes that resolve to the identical x slot
  // (e.g. both hang off the same single neighbor) landed on the exact same
  // {x,y} (y depends only on node type, so same-type collisions overlapped
  // fully). Each further collision on a slot is staggered ADDITIONALLY
  // further up (away from the chain), mirroring Pass 2's "further down".
  const infoSlotCollisions = new Map<number, number>()
  let infoFallbackIndex = 0
  for (const node of nodes) {
    if (!infoOnlyIds.has(node.id)) continue
    const neighborX = connections
      .filter((c) => c.kind === 'information' && (c.fromNodeId === node.id || c.toNodeId === node.id))
      .map((c) => (c.fromNodeId === node.id ? c.toNodeId : c.fromNodeId))
      .filter((id) => positions[id])
      .map((id) => positions[id].x)
    let x: number
    if (neighborX.length > 0) {
      x = Math.round(neighborX.reduce((sum, v) => sum + v, 0) / neighborX.length)
    } else {
      x = START_X + infoFallbackIndex * (NODE_W + GAP_X)
      infoFallbackIndex++
    }
    const collision = infoSlotCollisions.get(x) ?? 0
    infoSlotCollisions.set(x, collision + 1)
    positions[node.id] = { x, y: Y_MAIN - Y_INFO_GAP_ABOVE - getNodeH(node.type) - collision * STAGGER_Y }
  }

  return positions
}