import { Octree } from './octree';
import type { GraphEdge, GraphLayout, GraphNode, GraphNodeState } from './graph.types';

export interface ForceSettings {
  /** Node-node repulsion. Larger spreads the graph out. @default 900 */
  repulsion?: number;
  /** Edge spring stiffness, 0-1. @default 0.08 */
  springStrength?: number;
  /** Preferred edge length at rest. @default 70 */
  springLength?: number;
  /** Pull toward the origin, which stops islands drifting away. @default 0.015 */
  centering?: number;
  /** Velocity retained per tick. @default 0.82 */
  damping?: number;
  /** Barnes-Hut accuracy; see `octree.ts`. @default 0.8 */
  theta?: number;
  /** Below this total movement the layout is considered settled. @default 0.05 */
  settleThreshold?: number;
  /**
   * Floor on the separation used for repulsion, in layout units.
   * @default 6
   */
  minDistance?: number;
  /**
   * Hard cap on how far a node may move in one tick.
   *
   * A speed limit is what keeps a bad initial configuration from throwing nodes
   * off to infinity before damping has any chance to bite.
   * @default 30
   */
  maxVelocity?: number;
  /**
   * Fraction of the remaining energy shed each tick.
   *
   * This is what *guarantees* termination: forces are scaled by a cooling alpha,
   * so the layout always converges instead of orbiting forever and pinning a CPU
   * core on a dashboard nobody is looking at.
   * @default 0.022
   */
  alphaDecay?: number;
  /** Alpha below which the layout is done. @default 0.002 */
  alphaMin?: number;
}

const DEFAULTS: Required<ForceSettings> = {
  repulsion: 900,
  springStrength: 0.08,
  springLength: 70,
  centering: 0.015,
  damping: 0.82,
  theta: 0.8,
  settleThreshold: 0.05,
  minDistance: 6,
  maxVelocity: 30,
  alphaDecay: 0.022,
  alphaMin: 0.002,
};

/**
 * Deterministic pseudo-random, so the same graph always lays out the same way.
 *
 * A layout that reshuffles on every mount makes a diagram impossible to talk
 * about — "the node on the left" has to keep meaning something.
 */
function seededRandom(seed: number): () => number {
  let state = seed >>> 0 || 1;

  return () => {
    state ^= state << 13;
    state ^= state >>> 17;
    state ^= state << 5;
    return ((state >>> 0) % 100000) / 100000;
  };
}

function hashId(id: string): number {
  let hash = 2166136261;
  for (let i = 0; i < id.length; i += 1) {
    hash ^= id.charCodeAt(i);
    hash = Math.imul(hash, 16777619);
  }
  return hash >>> 0;
}

/** Places nodes on a sphere (or circle in 2D) before the forces take over. */
export function seedPositions(nodes: GraphNode[], layout: GraphLayout): GraphNodeState[] {
  const random = seededRandom(nodes.length + 1);
  const radius = 40 + Math.cbrt(Math.max(1, nodes.length)) * 22;

  return nodes.map(node => {
    if (node.position) {
      return {
        id: node.id,
        ...node.position,
        z: layout === '2d' ? 0 : node.position.z,
        vx: 0,
        vy: 0,
        vz: 0,
        pinned: Boolean(node.pinned),
        mass: node.weight ?? 1,
      };
    }

    // Hashing the id keeps a node's seed stable when its neighbours change.
    const local = seededRandom(hashId(node.id));
    const theta = local() * Math.PI * 2;
    const phi = layout === '2d' ? Math.PI / 2 : Math.acos(2 * local() - 1);
    const r = radius * (0.6 + random() * 0.4);

    return {
      id: node.id,
      x: r * Math.sin(phi) * Math.cos(theta),
      y: r * Math.sin(phi) * Math.sin(theta),
      z: layout === '2d' ? 0 : r * Math.cos(phi),
      vx: 0,
      vy: 0,
      vz: 0,
      pinned: Boolean(node.pinned),
      mass: node.weight ?? 1,
    };
  });
}

export interface TickResult {
  /** Average distance a node moved this tick. */
  movement: number;
  settled: boolean;
  /** Remaining energy, to be fed into the next tick. */
  alpha: number;
}

/**
 * Advances the layout by one step.
 *
 * @description
 * Three forces: Barnes-Hut repulsion between all nodes, Hooke springs along the
 * edges, and a weak pull toward the origin so disconnected components do not
 * drift off screen forever.
 *
 * `states` is mutated in place — a tick allocates only the octree, which matters
 * when this runs sixty times a second over thousands of nodes.
 */
export function tick(
  states: GraphNodeState[],
  edges: GraphEdge[],
  indexById: Map<string, number>,
  layout: GraphLayout,
  settings: ForceSettings = {},
  /** Remaining energy, from the previous tick. */
  alpha = 1
): TickResult {
  const {
    repulsion,
    springStrength,
    springLength,
    centering,
    damping,
    theta,
    settleThreshold,
    minDistance,
    maxVelocity,
    alphaDecay,
    alphaMin,
  } = { ...DEFAULTS, ...settings };

  if (states.length === 0) return { movement: 0, settled: true, alpha: 0 };

  const nextAlpha = alpha * (1 - alphaDecay);

  /* --- Repulsion ---------------------------------------------------------- */

  // `GraphNodeState` already satisfies `OctreeBody`, so it is passed straight
  // through. Copying it allocated one object per node per tick — five thousand
  // nodes at sixty frames a second is nine hundred thousand throwaway objects a
  // second, for nothing.
  const tree = new Octree(states);
  const force = { fx: 0, fy: 0, fz: 0 };

  for (const state of states) {
    force.fx = 0;
    force.fy = 0;
    force.fz = 0;

    // Negative strength: the octree accumulates attraction, so flip the sign.
    tree.accumulate(state, -repulsion, theta, force, minDistance);

    state.vx += force.fx * alpha;
    state.vy += force.fy * alpha;
    state.vz += force.fz * alpha;
  }

  /* --- Springs ------------------------------------------------------------ */

  for (const edge of edges) {
    const a = indexById.get(edge.source);
    const b = indexById.get(edge.target);
    if (a === undefined || b === undefined || a === b) continue;

    const source = states[a];
    const target = states[b];

    const dx = target.x - source.x;
    const dy = target.y - source.y;
    const dz = target.z - source.z;

    const distance = Math.sqrt(dx * dx + dy * dy + dz * dz) || 1e-3;
    const rest = edge.length ?? springLength;
    const pull = ((distance - rest) / distance) * springStrength * (edge.strength ?? 1) * alpha;

    source.vx += dx * pull;
    source.vy += dy * pull;
    source.vz += dz * pull;
    target.vx -= dx * pull;
    target.vy -= dy * pull;
    target.vz -= dz * pull;
  }

  /* --- Centering and integration ------------------------------------------ */

  let movement = 0;

  for (const state of states) {
    if (state.pinned) {
      state.vx = 0;
      state.vy = 0;
      state.vz = 0;
      continue;
    }

    /*
     * Scaled by alpha like the other two forces. Left unscaled, it is the only
     * force still acting once the layout cools, and it crushes the whole graph
     * into a ball at the origin — nodes ended up closer together than their own
     * diameter, which read as "the circles are too big".
     */
    state.vx -= state.x * centering * alpha;
    state.vy -= state.y * centering * alpha;
    state.vz -= state.z * centering * alpha;

    state.vx *= damping;
    state.vy *= damping;
    state.vz *= damping;

    // Speed limit, applied after damping so it bounds the actual step taken.
    const speed = Math.sqrt(state.vx * state.vx + state.vy * state.vy + state.vz * state.vz);
    if (speed > maxVelocity) {
      const brake = maxVelocity / speed;
      state.vx *= brake;
      state.vy *= brake;
      state.vz *= brake;
    }

    state.x += state.vx;
    state.y += state.vy;
    state.z += layout === '2d' ? 0 : state.vz;

    if (layout === '2d') {
      state.z = 0;
      state.vz = 0;
    }

    movement += Math.abs(state.vx) + Math.abs(state.vy) + Math.abs(state.vz);
  }

  const average = movement / states.length;

  return {
    movement: average,
    // Either the graph stopped moving, or it ran out of energy to keep going.
    settled: average < settleThreshold || nextAlpha < alphaMin,
    alpha: nextAlpha,
  };
}

/**
 * Runs the layout to rest without animating.
 *
 * Used when the viewer asked for reduced motion, and when producing a static
 * image: the diagram appears already arranged rather than visibly settling.
 */
export function runToSettle(
  states: GraphNodeState[],
  edges: GraphEdge[],
  indexById: Map<string, number>,
  layout: GraphLayout,
  settings: ForceSettings = {},
  maxIterations = 300
): number {
  let alpha = 1;

  for (let i = 0; i < maxIterations; i += 1) {
    const result = tick(states, edges, indexById, layout, settings, alpha);
    alpha = result.alpha;
    if (result.settled) return i + 1;
  }

  return maxIterations;
}