Spaces:
Sleeping
Sleeping
| import type { Expense, Settlement } from './types'; | |
| export interface Debt { | |
| from: string; | |
| to: string; | |
| cents: number; | |
| } | |
| /** Positive = is owed money; negative = owes money. Only users touched by any item appear. */ | |
| export function computeNets(expenses: Iterable<Expense>, settlements: Iterable<Settlement>): Map<string, number> { | |
| const nets = new Map<string, number>(); | |
| const add = (id: string, delta: number) => nets.set(id, (nets.get(id) ?? 0) + delta); | |
| for (const e of expenses) { | |
| add(e.paidBy, e.amountCents); | |
| for (const [uid, cents] of Object.entries(e.shares)) add(uid, -cents); | |
| } | |
| for (const s of settlements) { | |
| add(s.from, s.amountCents); | |
| add(s.to, -s.amountCents); | |
| } | |
| return nets; | |
| } | |
| const byMagnitudeThenId = (a: [string, number], b: [string, number]) => | |
| Math.abs(b[1]) - Math.abs(a[1]) || (a[0] < b[0] ? -1 : a[0] > b[0] ? 1 : 0); | |
| /** | |
| * Greedy pairing of largest debtor with largest creditor. Deterministic; at most n-1 transfers. | |
| * Precondition: nets must sum to zero. | |
| */ | |
| export function simplifyDebts(nets: Map<string, number>): Debt[] { | |
| const total = [...nets.values()].reduce((a, b) => a + b, 0); | |
| if (total !== 0) throw new Error(`Balances do not sum to zero (got ${total})`); | |
| const creditors = [...nets].filter(([, v]) => v > 0).sort(byMagnitudeThenId); | |
| const debtors = [...nets] | |
| .filter(([, v]) => v < 0) | |
| .map(([id, v]) => [id, -v] as [string, number]) | |
| .sort(byMagnitudeThenId); | |
| const debts: Debt[] = []; | |
| let i = 0; | |
| let j = 0; | |
| while (i < debtors.length && j < creditors.length) { | |
| const [debtor, owes] = debtors[i]; | |
| const [creditor, owed] = creditors[j]; | |
| const cents = Math.min(owes, owed); | |
| debts.push({ from: debtor, to: creditor, cents }); | |
| debtors[i] = [debtor, owes - cents]; | |
| creditors[j] = [creditor, owed - cents]; | |
| if (debtors[i][1] === 0) i++; | |
| if (creditors[j][1] === 0) j++; | |
| } | |
| return debts; | |
| } | |