import { comparisonGroupKey, modalCluster } from "./partition.js";
import type {
  MeasuredLayoutCellEvidence,
  MeasuredLayoutMatrixEvidence,
  MeasuredLayoutNode,
  MeasuredLayoutViolationFact,
} from "./types.js";

const GRID_TRACK_RULE_ID = "UI-096" as const;

function compareUnicodeScalars(left: string, right: string): number {
  let leftIndex = 0;
  let rightIndex = 0;
  while (leftIndex < left.length && rightIndex < right.length) {
    const leftCode = left.codePointAt(leftIndex);
    const rightCode = right.codePointAt(rightIndex);
    if (leftCode === undefined || rightCode === undefined) break;
    if (leftCode !== rightCode) return leftCode < rightCode ? -1 : 1;
    leftIndex += leftCode > 0xffff ? 2 : 1;
    rightIndex += rightCode > 0xffff ? 2 : 1;
  }
  return left.length - right.length;
}

export function isSettledCell(cell: MeasuredLayoutCellEvidence): boolean {
  const settled = cell.measuredLayoutProbe.settledState;
  return settled.atRest && !settled.timedOut && settled.scrollX === 0 && settled.scrollY === 0;
}

export function isAxisAligned(node: MeasuredLayoutNode): boolean {
  return node.transform.axisAligned && node.transform.normalized;
}

function isVisibleTrack(node: MeasuredLayoutNode): boolean {
  return node.visibility.visible && !node.visibility.zeroArea && node.borderBox.width > 0 && node.borderBox.height > 0;
}

export function isMasonryGrid(parent: MeasuredLayoutNode): boolean {
  const topology = parent.flexGridTopology;
  return topology.kind === "grid" && (topology.gridTrackCount === null || topology.gridTrackCount < 1);
}

export function isHorizontallyScrollableCarousel(parent: MeasuredLayoutNode): boolean {
  const scroll = parent.scrollContainerState;
  return scroll.isScrollContainer && scroll.scrollWidth > scroll.clientWidth && scroll.overflowX !== "visible";
}

export function isPartiallyVisibleTrack(parent: MeasuredLayoutNode, child: MeasuredLayoutNode): boolean {
  const content = parent.contentBox;
  const rect = child.borderBox;
  return rect.x < content.x
    || rect.x + rect.width > content.x + content.width
    || rect.y < content.y
    || rect.y + rect.height > content.y + content.height;
}

function logicalTrackOrder(parent: MeasuredLayoutNode, children: MeasuredLayoutNode[]): MeasuredLayoutNode[] {
  return [...children].sort((left, right) => {
    const horizontal = parent.direction === "rtl"
      ? right.borderBox.x - left.borderBox.x
      : left.borderBox.x - right.borderBox.x;
    return horizontal || compareUnicodeScalars(left.identity, right.identity);
  });
}

function perpendicularOverlap(left: MeasuredLayoutNode, right: MeasuredLayoutNode): boolean {
  return Math.min(left.borderBox.y + left.borderBox.height, right.borderBox.y + right.borderBox.height)
    > Math.max(left.borderBox.y, right.borderBox.y);
}

function overlappingProjectionGroups(parent: MeasuredLayoutNode, children: MeasuredLayoutNode[]): MeasuredLayoutNode[][] {
  const remaining = logicalTrackOrder(parent, children);
  const groups: MeasuredLayoutNode[][] = [];
  while (remaining.length > 0) {
    const seed = remaining.shift();
    if (seed === undefined) break;
    const group = [seed];
    for (let index = remaining.length - 1; index >= 0; index -= 1) {
      const candidate = remaining[index];
      if (candidate !== undefined && group.some((member) => perpendicularOverlap(member, candidate))) {
        group.push(candidate);
        remaining.splice(index, 1);
      }
    }
    groups.push(logicalTrackOrder(parent, group));
  }
  return groups;
}

// Children arrive in logical track order. Auto-placed items resolve
// grid-column-start to "auto", so explicit line numbers exist only when every
// child is explicitly placed; otherwise the measured ordinal is the authority.
function spanTopology(children: MeasuredLayoutNode[]): string | undefined {
  const explicitColumns = children.map((child) => child.flexGridTopology.gridColumn);
  const allExplicit = explicitColumns.every(
    (column) => column !== null && Number.isInteger(column) && column >= 1,
  );
  const entries = children.map((child, index) => {
    const column = allExplicit ? explicitColumns[index] : index + 1;
    const span = child.flexGridTopology.gridColumnSpan;
    if (column === undefined || column === null || span === null || !Number.isInteger(span) || span < 1) {
      return undefined;
    }
    return `${String(column)}:${String(span)}`;
  });
  return entries.some((entry) => entry === undefined) ? undefined : entries.join(",");
}

function isMeasuredGridContainer(parent: MeasuredLayoutNode, children: readonly MeasuredLayoutNode[]): boolean {
  if (parent.flexGridTopology.kind === "grid") return true;
  return children.some((child) => child.parent === parent.identity && child.flexGridTopology.kind === "grid");
}

function gridContainerTopology(parent: MeasuredLayoutNode, children: readonly MeasuredLayoutNode[]): MeasuredLayoutNode["flexGridTopology"] {
  if (parent.flexGridTopology.kind === "grid") return parent.flexGridTopology;
  const child = children.find((candidate) => candidate.parent === parent.identity && candidate.flexGridTopology.kind === "grid");
  if (child === undefined) throw new Error("grid track container is missing measured grid topology");
  return child.flexGridTopology;
}

function groupTopology(parent: MeasuredLayoutNode, children: MeasuredLayoutNode[]): string | undefined {
  const spans = spanTopology(children);
  if (spans === undefined) return undefined;
  const topology = gridContainerTopology(parent, children);
  return JSON.stringify({
    parent: parent.structuralSignature,
    state: parent.stateSignature,
    responsive: JSON.stringify({ count: topology.gridTrackCount, resolvedCount: topology.gridTrackWidths.length }),
    spans,
    direction: parent.direction,
  });
}

function jitterField(cell: MeasuredLayoutCellEvidence, node: MeasuredLayoutNode, field: string): number | undefined {
  const nodeIndex = cell.measuredLayoutProbe.measuredLayoutGraph.nodes.findIndex((candidate) => candidate.identity === node.identity);
  if (nodeIndex < 0) return undefined;
  const value = cell.measuredLayoutProbe.jitterEnvelope.maxDeltaByField[`nodes[${String(nodeIndex)}].${field}`];
  return value === undefined || !Number.isFinite(value) || value < 0 ? undefined : value;
}

function ratioTolerance(
  numerator: number,
  numeratorDelta: number,
  denominator: number,
  denominatorDelta: number,
): number | undefined {
  if (
    !Number.isFinite(numerator) || !Number.isFinite(numeratorDelta) || !Number.isFinite(denominator) || !Number.isFinite(denominatorDelta)
    || numerator < 0 || numeratorDelta < 0 || denominator <= 0 || denominatorDelta < 0 || denominatorDelta >= denominator
  ) {
    return undefined;
  }
  return (numerator + numeratorDelta) / (denominator - denominatorDelta) - numerator / denominator;
}

function coordinateTolerances(
  cell: MeasuredLayoutCellEvidence,
  parent: MeasuredLayoutNode,
  ordered: MeasuredLayoutNode[],
  widths: number[],
  gaps: number[],
): number[] | undefined {
  const parentWidthDelta = jitterField(cell, parent, "contentBox.width");
  if (parentWidthDelta === undefined) return undefined;
  const widthTolerances = ordered.map((child, index) => {
    const width = widths[index];
    const widthDelta = jitterField(cell, child, "borderBox.width");
    return width === undefined || widthDelta === undefined
      ? undefined
      : ratioTolerance(width, widthDelta, parent.contentBox.width, parentWidthDelta);
  });
  const gapTolerances = gaps.map((gap, index) => {
    const previous = ordered[index];
    const next = ordered[index + 1];
    if (previous === undefined || next === undefined) return undefined;
    const previousXDelta = jitterField(cell, previous, "borderBox.x");
    const previousWidthDelta = jitterField(cell, previous, "borderBox.width");
    const nextXDelta = jitterField(cell, next, "borderBox.x");
    if (previousXDelta === undefined || previousWidthDelta === undefined || nextXDelta === undefined) return undefined;
    return ratioTolerance(gap, previousXDelta + previousWidthDelta + nextXDelta, parent.contentBox.width, parentWidthDelta);
  });
  const tolerances = [...widthTolerances, ...gapTolerances];
  return tolerances.some((tolerance) => tolerance === undefined) ? undefined : tolerances as number[];
}

type GridTrackMeasurement = {
  cell: MeasuredLayoutCellEvidence;
  parent: MeasuredLayoutNode;
  children: MeasuredLayoutNode[];
  topology: string;
  vector: number[];
  coordinateTolerances: number[];
  rawMeasurement: Record<string, unknown>;
};

function coordinateModalCluster(
  values: number[][],
  tolerances: number[],
): { memberIndexes: number[]; modalValue: number[] } | undefined {
  if (
    values.length === 0 || tolerances.length === 0
    || values.some((value) => value.length !== tolerances.length || value.some((entry) => !Number.isFinite(entry)))
    || tolerances.some((tolerance) => !Number.isFinite(tolerance) || tolerance < 0)
  ) {
    return undefined;
  }
  const exactRanks = tolerances.map((tolerance, coordinate) => tolerance === 0
    ? new Map([...new Set(values.map((value) => value[coordinate]))].sort((left, right) => (left ?? 0) - (right ?? 0)).map((value, rank) => [value, rank * 2]))
    : undefined);
  const normalized = values.map((value) => value.map((entry, coordinate) => {
    const tolerance = tolerances[coordinate];
    if (tolerance === undefined) throw new Error("grid-track tolerance coordinate is missing");
    if (tolerance > 0) return entry / tolerance;
    const rank = exactRanks[coordinate]?.get(entry);
    if (rank === undefined) throw new Error("exact grid-track coordinate is missing its rank");
    return rank;
  }));
  const mode = modalCluster(normalized, 1);
  if (mode === undefined) return undefined;
  return {
    memberIndexes: mode.memberIndexes,
    modalValue: tolerances.map((_, coordinate) => {
      const sorted = mode.memberIndexes
        .map((index) => values[index]?.[coordinate])
        .filter((entry): entry is number => entry !== undefined)
        .sort((left, right) => left - right);
      return sorted[Math.floor((sorted.length - 1) / 2)] ?? 0;
    }),
  };
}

function measurementForGroup(
  cell: MeasuredLayoutCellEvidence,
  parent: MeasuredLayoutNode,
  children: MeasuredLayoutNode[],
): GridTrackMeasurement | undefined {
  if (children.length < 2 || children.some((child) => isPartiallyVisibleTrack(parent, child))) return undefined;
  const topology = groupTopology(parent, children);
  if (topology === undefined) return undefined;
  const ordered = logicalTrackOrder(parent, children);
  const parentContentWidth = parent.contentBox.width;
  const orderedTrackWidths = ordered.map((child) => child.borderBox.width);
  const interTrackGaps = ordered.slice(1).map((child, index) => {
    const previous = ordered[index];
    if (previous === undefined) throw new Error("grid track group is missing a preceding track");
    return parent.direction === "rtl"
      ? previous.borderBox.x - (child.borderBox.x + child.borderBox.width)
      : child.borderBox.x - (previous.borderBox.x + previous.borderBox.width);
  });
  if (interTrackGaps.some((gap) => gap < 0)) return undefined;
  const widthRatios = orderedTrackWidths.map((width) => width / parentContentWidth);
  const gapRatios = interTrackGaps.map((gap) => gap / parentContentWidth);
  const coordinateToleranceValues = coordinateTolerances(cell, parent, ordered, orderedTrackWidths, interTrackGaps);
  if (coordinateToleranceValues === undefined) return undefined;
  return {
    cell,
    parent,
    children: ordered,
    topology,
    vector: [...widthRatios, ...gapRatios],
    coordinateTolerances: coordinateToleranceValues,
    rawMeasurement: {
      parentContentWidth,
      orderedTrackWidths,
      interTrackGaps,
      widthRatios,
      gapRatios,
      resolvedGridTemplateColumns: [...parent.flexGridTopology.gridTrackWidths],
      resolvedColumnGaps: [...parent.flexGridTopology.gridTrackGaps],
    },
  };
}

function measurementsForCell(cell: MeasuredLayoutCellEvidence): GridTrackMeasurement[] {
  if (!isSettledCell(cell)) return [];
  const nodes = cell.measuredLayoutProbe.measuredLayoutGraph.nodes;
  const childrenByParent = new Map<string, MeasuredLayoutNode[]>();
  for (const node of nodes) {
    if (node.parent === null || !isVisibleTrack(node) || !isAxisAligned(node)) continue;
    const siblings = childrenByParent.get(node.parent) ?? [];
    siblings.push(node);
    childrenByParent.set(node.parent, siblings);
  }
  const byIdentity = new Map(nodes.map((node) => [node.identity, node]));
  const results: GridTrackMeasurement[] = [];
  for (const [parentIdentity, children] of childrenByParent) {
    const parent = byIdentity.get(parentIdentity);
    if (
      parent === undefined || !isMeasuredGridContainer(parent, children) || !isAxisAligned(parent)
      || isMasonryGrid(parent) || isHorizontallyScrollableCarousel(parent)
    ) {
      continue;
    }
    for (const group of overlappingProjectionGroups(parent, children)) {
      const measurement = measurementForGroup(cell, parent, group);
      if (measurement !== undefined) results.push(measurement);
    }
  }
  return results;
}

export function detectGridTrackOutliers(
  matrix: MeasuredLayoutMatrixEvidence,
): MeasuredLayoutViolationFact[] {
  const partitions = new Map<string, GridTrackMeasurement[]>();
  for (const cell of matrix.cells) {
    for (const measurement of measurementsForCell(cell)) {
      const key = JSON.stringify({ group: comparisonGroupKey(cell), topology: measurement.topology });
      const values = partitions.get(key) ?? [];
      values.push(measurement);
      partitions.set(key, values);
    }
  }
  const findings: MeasuredLayoutViolationFact[] = [];
  for (const measurements of partitions.values()) {
    const sorted = [...measurements].sort((left, right) =>
      compareUnicodeScalars(`${left.cell.cell.id}\u0000${left.parent.identity}`, `${right.cell.cell.id}\u0000${right.parent.identity}`),
    );
    const vectorLength = sorted[0]?.vector.length;
    if (
      vectorLength === undefined
      || sorted.some((measurement) => measurement.vector.length !== vectorLength || measurement.coordinateTolerances.length !== vectorLength)
    ) {
      continue;
    }
    const tolerances = Array.from(
      { length: vectorLength },
      (_, coordinate) => Math.max(...sorted.map((measurement) => measurement.coordinateTolerances[coordinate] ?? 0)),
    );
    const mode = coordinateModalCluster(sorted.map((measurement) => measurement.vector), tolerances);
    if (mode === undefined) continue;
    const peerIdentities = mode.memberIndexes.map((index) => {
      const measurement = sorted[index];
      if (measurement === undefined) throw new Error("modal grid-track peer is missing");
      return `${measurement.cell.cell.id}:${measurement.parent.identity}`;
    }).sort(compareUnicodeScalars);
    for (let index = 0; index < sorted.length; index += 1) {
      if (mode.memberIndexes.includes(index)) continue;
      const measurement = sorted[index];
      if (measurement === undefined) continue;
      findings.push({
        ruleId: GRID_TRACK_RULE_ID,
        kind: "grid-track-outlier",
        cellId: measurement.cell.cell.id,
        locator: `${measurement.cell.cell.id}:${measurement.parent.identity}`,
        blamedIdentity: measurement.parent.identity,
        summary: "Measured grid track ratios differ from the strict-majority peer topology.",
        measurement: {
          rawMeasurement: measurement.rawMeasurement,
          modalValue: mode.modalValue,
          peerIdentities,
          topology: measurement.topology,
          coordinateTolerances: tolerances,
        },
      });
    }
  }
  return findings.sort((left, right) =>
    compareUnicodeScalars(
      `${left.locator}\u0000${JSON.stringify(left.measurement.rawMeasurement)}`,
      `${right.locator}\u0000${JSON.stringify(right.measurement.rawMeasurement)}`,
    ),
  );
}