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;
}