Spaces:
Sleeping
Sleeping
File size: 1,870 Bytes
d180c31 5918e23 d180c31 5918e23 d180c31 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | 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;
}
|