Function partitionWork

src/orchestration/partition.ts:119–160

(
  items: WorkItem<T>[],
  opts: PartitionOptions = {},
)

 * coupled items kept together, total weight balanced via LPT.
 */
export function partitionWork<T = unknown>(
  items: WorkItem<T>[],
  opts: PartitionOptions = {},
): Partition<T>[] {
  if (!items || items.length === 0) return [];

  const units = buildUnits(items);
  const totalWeight = units.reduce((s, x) => s + x.weight, 0);
  const k = chooseK(units, totalWeight, opts);
  if (k <= 1) {
    // Single partition: keep original input order.
    const all = units.flatMap((un) => un.members);
    return [{ index: 0, items: all, totalWeight }];
  }

  // LPT: heaviest unit first; tie-break by first-appearance order then key for stability.
  const sorted = [...units].sort((a, b) =>
    b.weight - a.weight || a.order - b.order || (a.key < b.key ? -1 : a.key > b.key ? 1 : 0),
  );

  const bins: Array<{ weight: number; units: Unit<T>[] }> = Array.from({ length: k }, () => ({
    weight: 0,
    units: [],
  }));

  for (const unit of sorted) {
    // Assign to the currently-lightest bin; tie-break by lowest bin index.
    let best = 0;
    for (let i = 1; i < bins.length; i++) {
      if (bins[i]!.weight < bins[best]!.weight) best = i;
    }
    bins[best]!.units.push(unit);
    bins[best]!.weight += unit.weight;
  }

  // Flatten each bin back to items, restoring original input order within the partition.
  return bins.map((bin, index) => {
    const flat = bin.units.flatMap((un) => un.members);
    flat.sort((a, b) => items.indexOf(a) - items.indexOf(b));
    return { index, items: flat, totalWeight: bin.weight };
  });
}

/**
 * Convenience: build WorkItems from plain string ids plus optional parallel