/**
 * Fixed-sheet packer for printers that sell set sheet lengths.
 *
 * Designs are packed into sheets of the film width and one of the offered
 * lengths. The packer compares several deterministic plans and returns the
 * cheapest one it finds. It is an efficient plan, not a proven cheapest plan,
 * except for small jobs where an exact search over every grouping is used.
 */

import {
  StripPackError,
  createPackRunCache,
  expandInstances,
  fitsWidth,
  packInstancesCore,
  toStripResult,
  validateStripInput,
  type CorePackResult,
  type PackGeometry,
  type PackInstance,
  type PackRunCache,
  type StripPackInput,
  type StripPackResult,
} from "./strip";

export interface FixedSheetOption {
  id: string;
  lengthMm: number;
  pricePence: number;
}

export interface FixedSheetPlan {
  sheets: { optionId: string; result: StripPackResult }[];
  totalPence: number;
  /**
   * Addition to the L1 contract: item ids that fit on no offered sheet in any
   * allowed orientation (too wide for the film or too long for the longest sheet).
   */
  unplaced: string[];
}

/** Jobs with this many copies or fewer use the exact search over every grouping. */
export const FIXED_SHEETS_EXACT_MAX_INSTANCES = 8;

/** Work budget for the bounded search, counted in design copies packed. */
const SEARCH_BUDGET_INSTANCES = 60_000;

/**
 * Sheet fills shared between calls, for example between printers that use the
 * same film width, sheet lengths, spacing and designs. Reusing a fill gives the
 * same result as packing again, so plans do not depend on the cache.
 */
export interface FixedSheetCache {
  /** Keyed by bin size, spacing and the design sizes of the remaining copies. */
  fills: Map<string, { instances: PackInstance[]; core: CorePackResult }>;
  /**
   * Single packer runs, reused by fills with different copy counts once a
   * design no longer fits (see PackRunCache). Without it every fill packs
   * every run; plans are the same either way.
   */
  runs?: PackRunCache;
  /**
   * The job's copies, made once and used by every call with the same designs. A fill
   * shared between two calls then holds the same copies, so it is used as it is,
   * without moving it onto new copies (see relabel).
   */
  expanded?: { key: string; instances: PackInstance[] };
}

/** Most fills a cache keeps. When full, new fills are packed but not kept. */
const CACHE_MAX_FILLS = 20_000;

export function createFixedSheetCache(): FixedSheetCache {
  return { fills: new Map(), runs: createPackRunCache() };
}

interface Context {
  input: StripPackInput;
  usableWidth: number;
  options: FixedSheetOption[];
  /**
   * Pack cache keyed by option id and remaining copies. It also decides what
   * counts against the budget: only a new key does. `null` means the key was
   * counted but its fill was not needed yet, so it is packed on first use.
   */
  cache: Map<string, Map<string, CorePackResult | null>>;
  shared: FixedSheetCache;
}

interface SheetStep {
  option: FixedSheetOption;
  core: CorePackResult;
}

interface Candidate {
  steps: SheetStep[];
  total: number;
}

function validateOptions(options: FixedSheetOption[]) {
  if (!Array.isArray(options) || options.length === 0) {
    throw new StripPackError("At least one sheet option is required.");
  }
  const seen = new Set<string>();
  for (const option of options) {
    if (!option || typeof option.id !== "string" || option.id.length === 0) {
      throw new StripPackError("Every sheet option needs a non-empty id.");
    }
    if (seen.has(option.id)) throw new StripPackError(`Sheet option id "${option.id}" is used more than once.`);
    seen.add(option.id);
    if (!Number.isSafeInteger(option.lengthMm) || option.lengthMm < 1) {
      throw new StripPackError(`Length of sheet "${option.id}" must be a positive whole number of millimetres.`);
    }
    if (!Number.isSafeInteger(option.pricePence) || option.pricePence < 0) {
      throw new StripPackError(`Price of sheet "${option.id}" must be a whole number of pence, zero or more.`);
    }
  }
}

function usableLength(ctx: Context, option: FixedSheetOption) {
  return option.lengthMm - 2 * ctx.input.edgeMarginMm;
}

/** True when one copy fits on an empty sheet of this option. */
function fitsSheet(ctx: Context, inst: PackInstance, option: FixedSheetOption) {
  const w = ctx.usableWidth;
  const l = usableLength(ctx, option);
  return (
    (inst.widthMm <= w && inst.heightMm <= l) || (inst.allowRotation && inst.heightMm <= w && inst.widthMm <= l)
  );
}

function geometryFor(ctx: Context, option: FixedSheetOption): PackGeometry {
  return {
    binWidth: ctx.usableWidth + ctx.input.spacingMm,
    binHeight: usableLength(ctx, option) + ctx.input.spacingMm,
    spacingMm: ctx.input.spacingMm,
  };
}

/** Remaining lists are reused across sheet options, so each key is made once. */
const remainingKeys = new WeakMap<PackInstance[], string>();

/** One character per copy index (indices stay below STRIP_MAX_INSTANCES, well under 65,536). */
function remainingKey(remaining: PackInstance[]) {
  let key = remainingKeys.get(remaining);
  if (key === undefined) {
    key = "";
    for (const inst of remaining) key += String.fromCharCode(inst.index);
    remainingKeys.set(remaining, key);
  }
  return key;
}

/**
 * Key for a remaining list that ignores which copies it holds and keeps only
 * their sizes in order. The packer reads a copy's index only to break ties in
 * sorting, so two lists with the same sizes in the same order pack the same way:
 * copy k of one list lands where copy k of the other does. Lists are always in
 * index order, and design sizes are written once per run of equal sizes.
 */
function shapeKey(geometry: PackGeometry, remaining: PackInstance[]) {
  let key = `${geometry.binWidth}|${geometry.binHeight}|${geometry.spacingMm}|`;
  let i = 0;
  while (i < remaining.length) {
    const first = remaining[i];
    let j = i + 1;
    while (
      j < remaining.length &&
      remaining[j].widthMm === first.widthMm &&
      remaining[j].heightMm === first.heightMm &&
      remaining[j].allowRotation === first.allowRotation
    ) {
      j += 1;
    }
    key += `${first.widthMm}x${first.heightMm}${first.allowRotation ? "r" : ""}*${j - i};`;
    i = j;
  }
  return key;
}

/** Moves a fill packed for `from` onto `to`, copy k to copy k (same sizes, same order). */
function relabel(core: CorePackResult, from: PackInstance[], to: PackInstance[]): CorePackResult {
  if (from === to || (from.length === to.length && from.every((inst, k) => inst === to[k]))) return core;
  // Position of each copy in `from`, by copy index (indices are unique and small).
  let maxIndex = 0;
  for (const inst of from) if (inst.index > maxIndex) maxIndex = inst.index;
  const position = new Int32Array(maxIndex + 1);
  from.forEach((inst, k) => (position[inst.index] = k));
  const map = (inst: PackInstance) => to[position[inst.index]];
  return {
    placements: core.placements.map((p) => ({ ...p, inst: map(p.inst) })),
    leftover: core.leftover.map(map),
    bottom: core.bottom,
    placedArea: core.placedArea,
  };
}

/** This option's fills in the pack cache, keyed by remaining copies. */
function fillsFor(ctx: Context, option: FixedSheetOption) {
  let byRemaining = ctx.cache.get(option.id);
  if (byRemaining === undefined) {
    byRemaining = new Map();
    ctx.cache.set(option.id, byRemaining);
  }
  return byRemaining;
}

/** Fills one sheet of the option with as much of the remaining work as the packer places. */
function fillSheet(ctx: Context, remaining: PackInstance[], option: FixedSheetOption, budget: { left: number }) {
  const byRemaining = fillsFor(ctx, option);
  const key = remainingKey(remaining);
  const hit = byRemaining.get(key);
  if (hit) return hit;
  // The budget counts every new remaining list, whether or not the shared cache
  // already holds its fill, so the search visits the same plans either way.
  if (hit === undefined) budget.left -= remaining.length;
  const geometry = geometryFor(ctx, option);
  const sharedKey = shapeKey(geometry, remaining);
  const known = ctx.shared.fills.get(sharedKey);
  let core: CorePackResult;
  if (known) {
    core = relabel(known.core, known.instances, remaining);
  } else {
    core = packInstancesCore(remaining, geometry, ctx.shared.runs);
    if (ctx.shared.fills.size < CACHE_MAX_FILLS) ctx.shared.fills.set(sharedKey, { instances: remaining, core });
  }
  byRemaining.set(key, core);
  return core;
}

/**
 * Counts a fill against the budget exactly as fillSheet would, without packing
 * it. Used when the search can already tell that the fill cannot change the plan.
 */
function countFill(ctx: Context, remaining: PackInstance[], option: FixedSheetOption, budget: { left: number }) {
  const byRemaining = fillsFor(ctx, option);
  const key = remainingKey(remaining);
  if (byRemaining.has(key)) return;
  budget.left -= remaining.length;
  byRemaining.set(key, null);
}

function total(steps: SheetStep[]) {
  return steps.reduce((sum, step) => sum + step.option.pricePence, 0);
}

/** Fewer pence wins, then fewer sheets; earlier candidates win exact ties. */
function better(a: Candidate, b: Candidate | null) {
  return b === null || a.total < b.total || (a.total === b.total && a.steps.length < b.steps.length);
}

/** Repeats one sheet size until every copy is placed. Returns null if a copy never fits. */
function allOfOneSize(
  ctx: Context,
  instances: PackInstance[],
  option: FixedSheetOption,
  budget: { left: number },
): Candidate | null {
  if (!instances.every((inst) => fitsSheet(ctx, inst, option))) return null;
  const steps: SheetStep[] = [];
  let remaining = instances;
  while (remaining.length > 0) {
    const core = fillSheet(ctx, remaining, option, budget);
    if (core.placements.length === 0) return null;
    steps.push({ option, core });
    remaining = core.leftover;
  }
  return { steps, total: total(steps) };
}

/**
 * Fills the longest sheet while the remainder does not fit on one sheet, and at
 * every step also tries finishing the remainder on each single sheet size.
 */
function largestFirst(
  ctx: Context,
  instances: PackInstance[],
  byLength: FixedSheetOption[],
  budget: { left: number },
): Candidate[] {
  const found: Candidate[] = [];
  const largest = byLength[byLength.length - 1];
  const steps: SheetStep[] = [];
  let remaining = instances;
  while (remaining.length > 0 && budget.left > 0) {
    const area = remaining.reduce((sum, inst) => sum + inst.widthMm * inst.heightMm, 0);
    for (const option of byLength) {
      if (!remaining.every((inst) => fitsSheet(ctx, inst, option))) continue;
      if (area > ctx.usableWidth * usableLength(ctx, option)) {
        // More design area than the sheet holds, so it cannot finish the job.
        countFill(ctx, remaining, option, budget);
        continue;
      }
      const core = fillSheet(ctx, remaining, option, budget);
      if (core.leftover.length === 0) {
        const finished = [...steps, { option, core }];
        found.push({ steps: finished, total: total(finished) });
      }
    }
    const core = fillSheet(ctx, remaining, largest, budget);
    if (core.placements.length === 0) break;
    steps.push({ option: largest, core });
    remaining = core.leftover;
    if (remaining.length === 0) found.push({ steps: [...steps], total: total(steps) });
  }
  return found;
}

/**
 * Small branch-and-bound search over sheet sequences. Each branch fills one
 * sheet of one size with the remaining work. A lower bound from design area
 * and the cheapest price per usable square millimetre prunes the search, and a
 * work budget keeps it bounded.
 */
function boundedSearch(
  ctx: Context,
  instances: PackInstance[],
  incumbent: Candidate | null,
  budget: { left: number },
): Candidate | null {
  const cheapestPerArea = Math.min(
    ...ctx.options.map((o) => o.pricePence / (ctx.usableWidth * Math.max(1, usableLength(ctx, o)))),
  );
  // Try the best value per usable area first.
  const order = [...ctx.options].sort(
    (a, b) =>
      a.pricePence / Math.max(1, usableLength(ctx, a)) - b.pricePence / Math.max(1, usableLength(ctx, b)) ||
      b.lengthMm - a.lengthMm,
  );
  let best = incumbent;

  /**
   * Upper bound on the design area one sheet of `option` can hold. Designs sit
   * inside the usable area, and each one with its spacing on two sides must
   * fit in the bin (usable area plus one spacing each way), so the area is at
   * most the bin area times the largest share of design in its spaced box.
   */
  const placeableArea = (remaining: PackInstance[], option: FixedSheetOption) => {
    const length = Math.max(0, usableLength(ctx, option));
    const s = ctx.input.spacingMm;
    let share = 0;
    for (const inst of remaining) {
      share = Math.max(share, (inst.widthMm * inst.heightMm) / ((inst.widthMm + s) * (inst.heightMm + s)));
    }
    // Rounded up with a margin, so floating-point error never makes the bound too small.
    const spaced = Math.ceil(share * (ctx.usableWidth + s) * (length + s) * (1 + 1e-9)) + 1;
    return Math.min(ctx.usableWidth * length, spaced);
  };

  /**
   * True when the branch after filling one sheet of `option` returns at once,
   * whatever the fill places. That branch either finishes the job (a candidate
   * that must beat `best`) or keeps some copies, and then its lower bound, with
   * at most the sheet's usable area placed, must stay below `best`.
   */
  const childCannotImprove = (
    incumbentPlan: Candidate,
    childCost: number,
    childSteps: number,
    remaining: PackInstance[],
    remainingArea: number,
    option: FixedSheetOption,
  ) => {
    const finishes =
      childCost < incumbentPlan.total ||
      (childCost === incumbentPlan.total && childSteps < incumbentPlan.steps.length);
    const sheetArea = placeableArea(remaining, option);
    if (finishes && remainingArea <= sheetArea) return false;
    // A new fill that uses up the budget leaves a branch that returns at once
    // unless it finishes the job.
    if (budget.left - remaining.length <= 0 && !fillsFor(ctx, option).has(remainingKey(remaining))) return true;
    // Some copies are left over: the child's lower bound is at least this.
    const leftAreaAtLeast = Math.max(0, remainingArea - sheetArea);
    const childBound = Math.floor(leftAreaAtLeast * cheapestPerArea * (1 - 1e-9));
    return childCost + childBound >= incumbentPlan.total;
  };

  /**
   * Cost and sheet count of every earlier visit, by remaining copies. Different
   * sheet orders often leave the same copies, and their fills are cached, so
   * without this the search can revisit a state very many times. A visit that
   * costs at least as much, with at least as many sheets, as an earlier one
   * changes nothing: the earlier visit already saw every plan below it at a
   * lower or equal price, pruning only gets stronger as `best` improves, and
   * every fill below it is already counted. So it returns at once.
   */
  const explored = new Map<string, number[]>();

  const visit = (remaining: PackInstance[], steps: SheetStep[], cost: number) => {
    if (remaining.length === 0) {
      const candidate = { steps: [...steps], total: cost };
      if (better(candidate, best)) best = candidate;
      return;
    }
    const key = remainingKey(remaining);
    const earlier = explored.get(key);
    if (earlier === undefined) {
      explored.set(key, [cost, steps.length]);
    } else {
      for (let i = 0; i < earlier.length; i += 2) {
        if (earlier[i] <= cost && earlier[i + 1] <= steps.length) return;
      }
      earlier.push(cost, steps.length);
    }
    if (budget.left <= 0) return;
    const area = remaining.reduce((sum, inst) => sum + inst.widthMm * inst.heightMm, 0);
    // Integer lower bound on the pence still needed (rounded down, so it never over-prunes).
    const lowerBound = Math.floor(area * cheapestPerArea * (1 - 1e-9));
    if (best !== null && cost + lowerBound >= best.total) return;
    for (const option of order) {
      if (budget.left <= 0) return;
      if (!remaining.some((inst) => fitsSheet(ctx, inst, option))) continue;
      if (best !== null && childCannotImprove(best, cost + option.pricePence, steps.length + 1, remaining, area, option)) {
        // Packing this sheet could only lead to a branch that returns at once,
        // so skip the packing but count it against the budget as before.
        countFill(ctx, remaining, option, budget);
        continue;
      }
      const core = fillSheet(ctx, remaining, option, budget);
      if (core.placements.length === 0) continue;
      steps.push({ option, core });
      visit(core.leftover, steps, cost + option.pricePence);
      steps.pop();
    }
  };
  visit(instances, [], 0);
  return best;
}

/**
 * Exact search for small jobs: packs every subset of copies as an open strip,
 * then a dynamic programme over subsets finds the cheapest grouping into sheets.
 * A subset is placed on the cheapest sheet whose length holds its packed strip.
 */
function exactSearch(ctx: Context, instances: PackInstance[]): Candidate | null {
  const n = instances.length;
  const full = (1 << n) - 1;
  const strip: PackGeometry = {
    binWidth: ctx.usableWidth + ctx.input.spacingMm,
    binHeight: null,
    spacingMm: ctx.input.spacingMm,
  };
  const e = ctx.input.edgeMarginMm;
  const s = ctx.input.spacingMm;
  // Cheapest option for each subset, or null if no sheet holds it.
  const sheetFor: (FixedSheetOption | null)[] = new Array(full + 1).fill(null);
  const packed: CorePackResult[] = new Array(full + 1);
  const byPrice = [...ctx.options].sort((a, b) => a.pricePence - b.pricePence || a.lengthMm - b.lengthMm);
  for (let mask = 1; mask <= full; mask += 1) {
    const subset = instances.filter((_, i) => mask & (1 << i));
    const core = packInstancesCore(subset, strip);
    packed[mask] = core;
    const needed = e + (core.bottom - s) + e;
    sheetFor[mask] = byPrice.find((option) => option.lengthMm >= needed) ?? null;
  }

  const cost: number[] = new Array(full + 1).fill(Number.POSITIVE_INFINITY);
  const count: number[] = new Array(full + 1).fill(Number.POSITIVE_INFINITY);
  const choice: number[] = new Array(full + 1).fill(0);
  cost[0] = 0;
  count[0] = 0;
  for (let mask = 1; mask <= full; mask += 1) {
    const low = mask & -mask;
    // Every submask that contains the lowest set bit, so each grouping is seen once.
    for (let sub = mask; sub > 0; sub = (sub - 1) & mask) {
      if (!(sub & low)) continue;
      const option = sheetFor[sub];
      if (!option) continue;
      const c = cost[mask ^ sub] + option.pricePence;
      const k = count[mask ^ sub] + 1;
      if (c < cost[mask] || (c === cost[mask] && k < count[mask])) {
        cost[mask] = c;
        count[mask] = k;
        choice[mask] = sub;
      }
    }
  }
  if (!Number.isFinite(cost[full])) return null;

  const steps: SheetStep[] = [];
  for (let mask = full; mask > 0; mask ^= choice[mask]) {
    const sub = choice[mask];
    // The open-strip layout already fits inside this sheet's length.
    steps.push({ option: sheetFor[sub] as FixedSheetOption, core: packed[sub] });
  }
  return { steps, total: cost[full] };
}

function toPlan(ctx: Context, candidate: Candidate | null, unplaced: string[]): FixedSheetPlan {
  if (candidate === null) return { sheets: [], totalPence: 0, unplaced };
  const sheets = candidate.steps.map((step) => ({
    optionId: step.option.id,
    result: toStripResult(ctx.input, step.core, [], step.option.lengthMm),
  }));
  return { sheets, totalPence: candidate.total, unplaced };
}

/** The job's copies, reused from `shared` when an earlier call had the same designs. */
function sharedInstances(shared: FixedSheetCache, items: StripPackInput["items"]) {
  const key = JSON.stringify(items.map((item) => [item.id, item.widthMm, item.heightMm, item.quantity, item.allowRotation]));
  if (shared.expanded?.key !== key) shared.expanded = { key, instances: expandInstances(items) };
  return shared.expanded.instances;
}

function setup(input: StripPackInput, options: FixedSheetOption[], shared = createFixedSheetCache()) {
  const usableWidth = validateStripInput(input);
  validateOptions(options);
  const ctx: Context = { input, usableWidth, options, cache: new Map(), shared };
  const all = sharedInstances(shared, input.items);
  const byLength = [...options].sort(
    (a, b) => a.lengthMm - b.lengthMm || a.pricePence - b.pricePence || options.indexOf(a) - options.indexOf(b),
  );
  const largest = byLength[byLength.length - 1];
  const placeable = all.filter((inst) => fitsWidth(inst, usableWidth) && fitsSheet(ctx, inst, largest));
  const placeableIds = new Set(placeable.map((inst) => inst.itemId));
  const unplaced = input.items.filter((i) => i.quantity > 0 && !placeableIds.has(i.id)).map((i) => i.id);
  return { ctx, placeable, byLength, largest, unplaced };
}

/**
 * Baseline plan that uses only one sheet size, filling each sheet in turn.
 * Returns null when a design does not fit that size.
 */
export function packAllOfOneSize(input: StripPackInput, options: FixedSheetOption[], optionId: string) {
  const { ctx, placeable, unplaced } = setup(input, options);
  const option = options.find((o) => o.id === optionId);
  if (!option) throw new StripPackError(`Unknown sheet option "${optionId}".`);
  const candidate = allOfOneSize(ctx, placeable, option, { left: Number.POSITIVE_INFINITY });
  return candidate === null ? null : toPlan(ctx, candidate, unplaced);
}

/**
 * Packs designs onto fixed-length sheets and returns the cheapest plan found.
 * Price ties go to fewer sheets. Designs that fit on no sheet are in `unplaced`.
 * Pass one `cache` to several calls for the same job (for example one per
 * printer) to reuse sheet fills; the plan is the same with or without it.
 */
export function packFixedSheets(
  input: StripPackInput,
  options: FixedSheetOption[],
  cache?: FixedSheetCache,
): FixedSheetPlan {
  const { ctx, placeable, byLength, unplaced } = setup(input, options, cache);
  if (placeable.length === 0) return toPlan(ctx, null, unplaced);

  if (placeable.length <= FIXED_SHEETS_EXACT_MAX_INSTANCES) {
    const exact = exactSearch(ctx, placeable);
    if (exact !== null) {
      // The exact search uses open-strip lengths; keep the heuristics as a
      // safety net in case a bounded sheet packs a subset the strip did not.
      let best: Candidate | null = exact;
      for (const option of byLength) {
        const candidate = allOfOneSize(ctx, placeable, option, { left: Number.POSITIVE_INFINITY });
        if (candidate && better(candidate, best)) best = candidate;
      }
      return toPlan(ctx, best, unplaced);
    }
  }

  const budget = { left: SEARCH_BUDGET_INSTANCES };
  let best: Candidate | null = null;
  // 1. One sheet size for everything, for each size. These run outside the
  //    budget so the all-longest-sheet baseline is always considered.
  for (const option of [...byLength].reverse()) {
    const candidate = allOfOneSize(ctx, placeable, option, { left: Number.POSITIVE_INFINITY });
    if (candidate && better(candidate, best)) best = candidate;
  }
  // 2. Longest sheets first, then the cheapest single sheet that finishes the job.
  for (const candidate of largestFirst(ctx, placeable, byLength, budget)) {
    if (better(candidate, best)) best = candidate;
  }
  // 3. Bounded search over mixed sheet sequences.
  best = boundedSearch(ctx, placeable, best, budget);
  return toPlan(ctx, best, unplaced);
}