bank.ts

/*

Bank simulation with realtime leaderboard using doubly linked list and
account position pointers to allow:

1. Account to get its rank in constant time
2. Account to climb leaderboard and balance list on update
3. Account to get top n leaderboard in O(n) time

❯ npx tsx ./bank.ts
[
  [ 1, { rank: 1, accountId: '1', volume: 500 } ],
  [ 2, { rank: 2, accountId: '2', volume: 300 } ],
  [ 3, { rank: 3, accountId: '3', volume: 0 } ],
  [ 4, { rank: 4, accountId: '4', volume: 0 } ],
  [ 5, { rank: 5, accountId: '5', volume: 0 } ],
  [ 6, { rank: 6, accountId: '6', volume: 0 } ]
]
[
  [ 1, { rank: 1, accountId: '2', volume: 600 } ],
  [ 2, { rank: 2, accountId: '1', volume: 500 } ],
  [ 3, { rank: 3, accountId: '3', volume: 0 } ],
  [ 4, { rank: 4, accountId: '4', volume: 0 } ],
  [ 5, { rank: 5, accountId: '5', volume: 0 } ],
  [ 6, { rank: 6, accountId: '6', volume: 0 } ]
]
[
  [ 1, { rank: 1, accountId: '5', volume: 860.7272694479661 } ],
  [ 2, { rank: 2, accountId: '2', volume: 600 } ],
  [ 3, { rank: 3, accountId: '1', volume: 500 } ],
  [ 4, { rank: 4, accountId: '4', volume: 460.79607088124243 } ],
  [ 5, { rank: 5, accountId: '6', volume: 244.29709796858145 } ],
  [ 6, { rank: 6, accountId: '3', volume: 4.530458329294662 } ]
]
[
  [ 1, { rank: 1, accountId: '5', volume: 860.7272694479661 } ],
  [ 2, { rank: 2, accountId: '1', volume: 600 } ],
  [ 3, { rank: 3, accountId: '2', volume: 600 } ],
  [ 4, { rank: 4, accountId: '4', volume: 460.79607088124243 } ],
  [ 5, { rank: 5, accountId: '6', volume: 244.29709796858145 } ],
  [ 6, { rank: 6, accountId: '3', volume: 4.530458329294662 } ]
]
*/

interface UserAccount {
  accountId: string;
  balance: 0;
  volume: 0;
}

class LeaderboardPosition {
  prev: LeaderboardPosition | null = null;
  next: LeaderboardPosition | null = null;
  rank: number = Number.POSITIVE_INFINITY;

  account: BankAccount<Bank>;

  constructor(account: BankAccount<Bank>, rank: number) {
    this.account = account;
    account.position = this;
    this.rank = rank;
  }

  static swapPositions(a: LeaderboardPosition, b: LeaderboardPosition) {
    const bAccount = b.account;
    const aAccount = a.account;

    a.account = bAccount;
    b.account = aAccount;

    aAccount.position = b;
    bAccount.position = a;
  }

  update() {
    const account = this.account;
    let running = true;
    while (running) {
      running = false;
      const prev = account.position.prev;
      // const next = account.position.next;

      if (prev) {
        const isVolumeBeat = prev.account.state.volume < account.state.volume;
        const isTieBeat =
          prev.account.state.volume === account.state.volume &&
          prev.account.state.accountId.localeCompare(account.state.accountId) >
            0;

        if (isVolumeBeat || isTieBeat) {
          LeaderboardPosition.swapPositions(prev, account.position);
          running = true;
        }
      }
    }
  }
}

interface LeaderboardRow {
  rank: number;
  accountId: string;
  volume: number;
}

class Leaderboard {
  head: LeaderboardPosition | null = null;
  tail: LeaderboardPosition | null = null;

  add(account: BankAccount<Bank>) {
    if (account.position) {
      return account.position;
    }

    const position = new LeaderboardPosition(
      account,
      (this.tail?.rank ?? 0) + 1
    );

    if (this.tail) {
      const prevTail = this.tail;
      prevTail.next = position;
      position.prev = prevTail;
      this.tail = position;
    } else {
      this.head = position;
      this.tail = position;
    }

    return position;
  }

  getTopLeaderboard(n = Number.POSITIVE_INFINITY) {
    if (!this.head) {
      return [];
    }

    const getLeaderboardLabel = (
      position: LeaderboardPosition
    ): [rank: number, position: LeaderboardRow] => {
      return [
        position.rank,
        {
          rank: position.rank,
          accountId: position.account.state.accountId,
          volume: position.account.state.volume,
        } as LeaderboardRow,
      ] as const;
    };

    let current: LeaderboardPosition | null = this.head;

    const leaderboard: [rank: number, position: LeaderboardRow][] = [];

    for (let i = 0; i < n || !current?.next; i += 1) {
      if (!current) {
        break;
      }
      leaderboard.push(getLeaderboardLabel(current));
      current = current.next;
    }

    return leaderboard;
  }
}

export class BankAccount<B extends Bank> {
  bank: B;
  state: UserAccount;

  position: LeaderboardPosition;

  constructor(
    bank: B,
    account: UserAccount,
    getLeaderboardPosition: (account: BankAccount<B>) => LeaderboardPosition
  ) {
    this.bank = bank;

    this.state = account;

    this.position = getLeaderboardPosition(this);
  }

  get balance() {
    return this.state.balance;
  }

  deposit(amount: number) {
    this.state.balance += amount;
    this.state.volume += amount;
    this.position.update();
  }

  withdraw(amount: number) {
    if (this.state.balance < amount) {
      return false;
    }

    this.state.balance -= amount;
    this.state.volume += amount;
    this.position.update();
  }
}

class Bank {
  #leaderboard = new Leaderboard();
  #accountMap = new Map<string, BankAccount<this>>();

  getAccount(accountId: string) {
    return this.#accountMap.get(accountId);
  }

  createAccount() {
    const accountId = String(this.#accountMap.size + 1);

    if (this.#accountMap.has(accountId)) {
      throw new Error('Account id mismatch error');
    }

    const account = new BankAccount(
      this,
      {
        accountId,
        balance: 0,
        volume: 0,
      },
      (account: BankAccount<this>) => {
        return this.#leaderboard.add(account);
      }
    );

    this.#accountMap.set(accountId, account);

    return account;
  }

  getLeaderboard(n?: number) {
    return this.#leaderboard.getTopLeaderboard(n);
  }
}

const bank = new Bank();

const one = bank.createAccount();
const two = bank.createAccount();
const accts = [
  bank.createAccount(),
  bank.createAccount(),
  bank.createAccount(),
  bank.createAccount(),
];

one.deposit(500);
two.deposit(300);

console.log(bank.getLeaderboard());

two.withdraw(300);

console.log(bank.getLeaderboard());

for (const account of accts) {
  account.deposit(Math.random() * 1000);
}

console.log(bank.getLeaderboard());

one.withdraw(100);

console.log(bank.getLeaderboard());