import type { BalanceView as GroupBalance } from '@prisma/client';

export function simplifyDebts(groupBalances: GroupBalance[]): GroupBalance[] {
  const currencies = new Set(groupBalances.map((balance) => balance.currency));
  const nodes = new Set<number>();
  groupBalances.forEach((balance) => {
    nodes.add(balance.userId);
    nodes.add(balance.friendId);
  });
  const result: GroupBalance[] = [];

  for (const currency of currencies) {
    const balances = groupBalances.filter((balance) => balance.currency === currency);
    const simplified = simplifyDebtsForSingleCurrency(balances, Array.from(nodes.values()));
    result.push(...simplified);
  }

  return result;
}

function simplifyDebtsForSingleCurrency(
  groupBalances: GroupBalance[],
  nodes: number[],
): GroupBalance[] {
  if (groupBalances.length === 0) {
    return [];
  }

  const adjMatrix = new Array<bigint[]>(nodes.length)
    .fill([])
    .map(() => new Array<bigint>(nodes.length).fill(0n));

  const nonResidualBalances = groupBalances.filter((balance) => 0 < balance.amount);

  nonResidualBalances.forEach((balance) => {
    const source = nodes.indexOf(balance.userId);
    const sink = nodes.indexOf(balance.friendId);
    adjMatrix[source]![sink] = balance.amount;
  });

  const simplified = minCashFlow(adjMatrix);

  const result = getMirrorBalances(
    simplified.flatMap((row, source) => {
      const res: GroupBalance[] = [];
      row.forEach((amount, sink) => {
        if (0n === amount) {
          return;
        }

        const balance =
          groupBalances.find(
            (candidate) => candidate.userId === nodes[source] && candidate.friendId === nodes[sink],
          ) ?? {};

        res.push({
          ...groupBalances[0]!,
          userId: nodes[source]!,
          friendId: nodes[sink]!,
          ...balance,
          amount,
        });
      });
      return res;
    }),
  );

  groupBalances.forEach((balance) => {
    const found = result.find(
      (graphBalance) =>
        graphBalance.userId === balance.userId && graphBalance.friendId === balance.friendId,
    );
    if (!found) {
      result.push({ ...balance, amount: 0n });
    }
  });

  return result;
}

// Based on https://www.geeksforgeeks.org/minimize-cash-flow-among-given-set-friends-borrowed-money/
const minCashFlow = (graph: bigint[][]): bigint[][] => {
  const n = graph.length;

  const amounts = new Array<bigint>(n).fill(0n);
  for (let i = 0; i < n; ++i) {
    for (let j = 0; j < n; ++j) {
      const diff = graph[j]![i]! - graph[i]![j]!;
      amounts[i]! += diff;
    }
  }
  return solveTransaction(amounts);
};

const solveTransaction = (amounts: bigint[]): bigint[][] => {
  const [minQ, maxQ] = constructMinMaxQ(amounts);

  const result = new Array<bigint[]>(amounts.length)
    .fill([])
    .map(() => new Array<bigint>(amounts.length).fill(0n));

  while (0 < minQ.length && 0 < maxQ.length) {
    const maxCreditEntry = maxQ.pop()!;
    const maxDebitEntry = minQ.pop()!;

    const transaction_val = maxCreditEntry.value + maxDebitEntry.value;

    const debtor = maxDebitEntry.key;
    const creditor = maxCreditEntry.key;
    let owed_amount = maxCreditEntry.value;

    if (0 > transaction_val) {
      maxDebitEntry.value = transaction_val;
      minQ.push(maxDebitEntry);
      minQ.sort(compareAsc);
      minQ.reverse();
    } else {
      owed_amount = -maxDebitEntry.value;
      maxCreditEntry.value = transaction_val;
      maxQ.push(maxCreditEntry);
      maxQ.sort(compareAsc);
    }

    result[debtor]![creditor] = owed_amount;
  }

  return result;
};

const compareAsc = (p1: Entry, p2: Entry): number => Number(p1.value - p2.value);

const constructMinMaxQ = (amounts: bigint[]): [Entry[], Entry[]] => {
  const minQ: Entry[] = [];
  const maxQ: Entry[] = [];
  amounts.forEach((amount, index) => {
    if (0n === amount) {
      return;
    }
    if (0 < amount) {
      maxQ.push({ key: index, value: amount });
    } else {
      minQ.push({ key: index, value: amount });
    }
  });

  maxQ.sort(compareAsc);
  minQ.sort(compareAsc);
  minQ.reverse();

  return [minQ, maxQ];
};

const getMirrorBalances = (groupBalances: GroupBalance[]): GroupBalance[] => {
  const result = [...groupBalances];

  groupBalances.forEach((balance) => {
    result.push({
      ...balance,
      userId: balance.friendId,
      friendId: balance.userId,
      amount: 0 < balance.amount ? -balance.amount : 0n,
    });
  });

  return result;
};

interface Entry {
  key: number;
  value: bigint;
}