impl/typescript.ts

Imports name this capability’s declared dependencies, which fune builds next to it in your project; each one links to its page.

import { allocate } from "./money_allocate.ts";  ← from money.allocate ^1.0.0 · built alongside by fune
import { type Money, money } from "./money_amount.ts";  ← from money.amount ^1.0.0 · built alongside by fune
import { applyRate } from "./money_apply_rate.ts";  ← from money.apply-rate ^1.0.0 · built alongside by fune
import { sumMoney } from "./money_sum.ts";  ← from money.sum ^1.0.0 · built alongside by fune
import { type PromoLine, type Promotion, type PromotionResult, type PricedLine, type AppliedPromotion } from "./retail_promotion_apply_types.ts";

const MAX_COMPETING = 6;

interface Unit {
  line: number;
  price: number;
}

interface Group {
  units: number[];
  discount: number;
}

function checkPromotion(p: Promotion, currency: string): void {
  if (!Number.isInteger(p.groupSize) || p.groupSize < 1) {
    throw new RangeError(`promotion "${p.id}": groupSize must be 1 or more`);
  }
  if (p.kind === "free-items") {
    if (p.freeItems < 1 || p.freeItems >= p.groupSize) {
      throw new RangeError(`promotion "${p.id}": freeItems must be from 1 to groupSize - 1`);
    }
  } else if (p.kind === "percent-off") {
    if (p.basisPoints < 1 || p.basisPoints > 10000) {
      throw new RangeError(`promotion "${p.id}": basisPoints must be from 1 to 10000`);
    }
  } else if (p.kind === "amount-off" || p.kind === "group-price") {
    if (p.amount === null) throw new RangeError(`promotion "${p.id}" needs an amount`);
    if (p.amount.currency !== currency) {
      throw new RangeError(`currency mismatch: ${currency} and ${p.amount.currency}`);
    }
    if (p.amount.minor < 0) throw new RangeError(`promotion "${p.id}": amount must not be negative`);
  } else {
    throw new RangeError(`promotion "${p.id}": unknown kind "${p.kind}"`);
  }
}

// The groups one promotion makes from the units nobody has claimed yet: the
// qualifying units from dearest to cheapest (ties in basket order), cut into
// consecutive groups of groupSize. Groups that would save nothing are skipped.
function evaluate(p: Promotion, units: Unit[], skus: string[], claimed: boolean[], currency: string): Group[] {
  const pool: number[] = [];
  units.forEach((u, i) => {
    if (!claimed[i] && p.skus.includes(skus[u.line])) pool.push(i);
  });
  pool.sort((a, b) => units[b].price - units[a].price || a - b);
  const groups: Group[] = [];
  for (let start = 0; start + p.groupSize <= pool.length; start += p.groupSize) {
    const members = pool.slice(start, start + p.groupSize);
    const prices = members.map((i) => units[i].price);
    const total = prices.reduce((s, x) => s + x, 0);
    let discount = 0;
    if (p.kind === "free-items") {
      discount = prices.slice(p.groupSize - p.freeItems).reduce((s, x) => s + x, 0);
    } else if (p.kind === "percent-off") {
      discount = applyRate(money(total, currency), p.basisPoints, "half-up").minor;
    } else if (p.kind === "amount-off") {
      discount = Math.min((p.amount as Money).minor, total);
    } else {
      discount = Math.max(total - (p.amount as Money).minor, 0);
    }
    if (discount > 0) groups.push({ units: members, discount });
  }
  return groups;
}

// Apply promotions in the given order, each claiming the units it groups.
function run(
  order: number[],
  promotions: readonly Promotion[],
  units: Unit[],
  skus: string[],
  claimed: boolean[],
  currency: string,
): { total: number; groups: Map<number, Group[]> } {
  const groups = new Map<number, Group[]>();
  let total = 0;
  for (const index of order) {
    const made = evaluate(promotions[index], units, skus, claimed, currency);
    for (const g of made) {
      for (const u of g.units) claimed[u] = true;
      total += g.discount;
    }
    groups.set(index, made);
  }
  return { total, groups };
}

// Next permutation in lexicographic order, in place; false after the last.
function nextPermutation(a: number[]): boolean {
  let i = a.length - 2;
  while (i >= 0 && a[i] >= a[i + 1]) i--;
  if (i < 0) return false;
  let j = a.length - 1;
  while (a[j] <= a[i]) j--;
  [a[i], a[j]] = [a[j], a[i]];
  for (let l = i + 1, r = a.length - 1; l < r; l++, r--) [a[l], a[r]] = [a[r], a[l]];
  return true;
}

/**
 * Price a basket under competing promotions: the customer gets the order of
 * application that saves the most, and each deal's saving is allocated back
 * to the lines in its groups exactly.
 */
export function applyPromotions(lines: readonly PromoLine[], promotions: readonly Promotion[]): PromotionResult {
  if (lines.length === 0) throw new RangeError("a basket needs at least one line");
  const currency = lines[0].unitPrice.currency;
  const units: Unit[] = [];
  const skus = lines.map((l) => l.sku);
  lines.forEach((line, index) => {
    if (line.unitPrice.currency !== currency) {
      throw new RangeError(`currency mismatch: ${currency} and ${line.unitPrice.currency}`);
    }
    if (!Number.isInteger(line.quantity) || line.quantity < 1) {
      throw new RangeError(`quantity must be 1 or more, received ${line.quantity}`);
    }
    if (line.unitPrice.minor < 0) throw new RangeError(`unitPrice must not be negative, received ${line.unitPrice.minor}`);
    for (let q = 0; q < line.quantity; q++) units.push({ line: index, price: line.unitPrice.minor });
  });
  const seen = new Set<string>();
  for (const p of promotions) {
    if (seen.has(p.id)) throw new RangeError(`duplicate promotion id "${p.id}"`);
    seen.add(p.id);
    checkPromotion(p, currency);
  }

  // Promotions with something to act on, joined into sets that share a SKU
  // present in the basket. Only promotions in the same set compete.
  const basketSkus = new Set(skus);
  const relevant = promotions.map((_, i) => i).filter((i) => promotions[i].skus.some((s) => basketSkus.has(s)));
  const parent = new Map<number, number>(relevant.map((i) => [i, i]));
  const find = (i: number): number => {
    while (parent.get(i) !== i) i = parent.get(i) as number;
    return i;
  };
  for (let x = 0; x < relevant.length; x++) {
    for (let y = x + 1; y < relevant.length; y++) {
      const a = promotions[relevant[x]];
      const b = promotions[relevant[y]];
      if (a.skus.some((s) => basketSkus.has(s) && b.skus.includes(s))) {
        const ra = find(relevant[x]);
        const rb = find(relevant[y]);
        if (ra !== rb) parent.set(Math.max(ra, rb), Math.min(ra, rb));
      }
    }
  }
  const components: number[][] = [];
  const byRoot = new Map<number, number[]>();
  for (const i of relevant) {
    const root = find(i);
    if (!byRoot.has(root)) {
      byRoot.set(root, []);
      components.push(byRoot.get(root) as number[]);
    }
    (byRoot.get(root) as number[]).push(i);
  }

  const claimed = units.map(() => false);
  const chosen = new Map<number, Group[]>();
  for (const component of components) {
    if (component.length > MAX_COMPETING) {
      throw new RangeError(
        `more than ${MAX_COMPETING} promotions compete for the same items: ${component.map((i) => promotions[i].id).join(", ")}`,
      );
    }
    const order = [...component];
    let bestOrder = [...order];
    let bestTotal = -1;
    do {
      const { total } = run(order, promotions, units, skus, [...claimed], currency);
      if (total > bestTotal) {
        bestTotal = total;
        bestOrder = [...order];
      }
    } while (nextPermutation(order));
    const { groups } = run(bestOrder, promotions, units, skus, claimed, currency);
    for (const [index, made] of groups) chosen.set(index, made);
  }

  const lineDiscount = lines.map(() => 0);
  const applied: AppliedPromotion[] = [];
  promotions.forEach((p, index) => {
    const made = chosen.get(index) ?? [];
    if (made.length === 0) return;
    let saved = 0;
    for (const g of made) {
      const shares = allocate(
        money(g.discount, currency),
        g.units.map((u) => units[u].price),
      );
      g.units.forEach((u, k) => {
        lineDiscount[units[u].line] += shares[k].minor;
      });
      saved += g.discount;
    }
    applied.push({ id: p.id, groups: made.length, discount: money(saved, currency) });
  });

  const priced: PricedLine[] = lines.map((line, index) => {
    const gross = line.unitPrice.minor * line.quantity;
    return {
      sku: line.sku,
      quantity: line.quantity,
      gross: money(gross, currency),
      discount: money(lineDiscount[index], currency),
      net: money(gross - lineDiscount[index], currency),
    };
  });
  const subtotal = sumMoney(priced.map((l) => l.gross), currency);
  const discount = sumMoney(priced.map((l) => l.discount), currency);
  return {
    lines: priced,
    applied,
    subtotal,
    discount,
    total: money(subtotal.minor - discount.minor, currency),
  };
}