import type { Expense, Transfer, Settlement } from './types';

/**
 * Compute net balances for each person from expenses and transfers.
 *
 * Rules:
 * - For each expense: the payer gets +amount, each person in splitAmong
 *   gets -(amount / splitAmong.length), with the first participant absorbing
 *   any remainder from integer division.
 * - For each transfer: from gains +amount to balance, to loses -amount to balance.
 *
 * @returns Map<personId, netBalanceInCents> — positive = owed money, negative = owes money
 */
export function computeBalances(
  people: string[],
  expenses: Expense[],
  transfers: Transfer[],
): Map<string, number> {
  const balances = new Map<string, number>();

  // Initialize all people at zero
  for (const personId of people) {
    balances.set(personId, 0);
  }

  // Process expenses
  for (const expense of expenses) {
    const share = Math.floor(expense.amount / expense.splitAmong.length);
    const remainder = expense.amount - share * expense.splitAmong.length;

    // Payer is credited the full amount
    balances.set(
      expense.paidBy,
      (balances.get(expense.paidBy) ?? 0) + expense.amount,
    );

    // Each participant is debited their share; first one absorbs remainder
    for (let i = 0; i < expense.splitAmong.length; i++) {
      const personId = expense.splitAmong[i];
      const debit = i === 0 ? share + remainder : share;
      balances.set(personId, (balances.get(personId) ?? 0) - debit);
    }
  }

  // Process transfers
  for (const transfer of transfers) {
    balances.set(
      transfer.from,
      (balances.get(transfer.from) ?? 0) + transfer.amount,
    );
    balances.set(
      transfer.to,
      (balances.get(transfer.to) ?? 0) - transfer.amount,
    );
  }

  return balances;
}

/**
 * Compute the minimum set of settlement payments to zero out everyone's balances.
 *
 * Uses the greedy min-cash-flow algorithm:
 * 1. Split into creditors (positive balance) and debtors (negative, stored as positive owed)
 * 2. Sort both descending by amount
 * 3. Match largest creditor with largest debtor: transfer min(creditorAmount, debtorAmount)
 * 4. Reduce both amounts, advance whoever hits zero
 * 5. Repeat until all settled
 *
 * @returns Minimum number of Settlement payments needed to settle all debts
 */
export function computeSettlements(
  balances: Map<string, number>,
): Settlement[] {
  // Split into creditors (positive = owed money) and debtors (negative = owes money)
  const creditors: { id: string; amount: number }[] = [];
  const debtors: { id: string; amount: number }[] = [];

  for (const [id, balance] of balances) {
    if (balance > 0) {
      creditors.push({ id, amount: balance });
    } else if (balance < 0) {
      debtors.push({ id, amount: -balance }); // store as positive amount owed
    }
  }

  // Sort descending by amount
  creditors.sort((a, b) => b.amount - a.amount);
  debtors.sort((a, b) => b.amount - a.amount);

  const settlements: Settlement[] = [];

  let ci = 0; // creditor index
  let di = 0; // debtor index

  while (ci < creditors.length && di < debtors.length) {
    const transferAmount = Math.min(creditors[ci].amount, debtors[di].amount);

    if (transferAmount > 0) {
      settlements.push({
        from: debtors[di].id,
        to: creditors[ci].id,
        amount: transferAmount,
      });
    }

    creditors[ci].amount -= transferAmount;
    debtors[di].amount -= transferAmount;

    if (creditors[ci].amount === 0) ci++;
    if (debtors[di].amount === 0) di++;
  }

  return settlements;
}
