Match.ts

import { LedgerEntry } from "./LedgerEntry";

export class Matcher {
    creeps: Creep[];
    entries: LedgerEntry[];
    creepsFree: { [creepId: string]: boolean };
    entriesFree: { [entryId: string]: boolean };
    creepPrefs: Map<Creep, LedgerEntry[]>;
    entryPrefs: Map<LedgerEntry, Creep[]>;
    assignments: Map<Creep, LedgerEntry>;

    constructor(creepPrefs: Map<Creep, LedgerEntry[]>, entryPrefs: Map<LedgerEntry, Creep[]>) {
        this.creepPrefs = creepPrefs
        this.entryPrefs = entryPrefs
        this.creeps = Array.from(creepPrefs.keys())
        this.entries = Array.from(entryPrefs.keys())
        this.creepsFree = _.zipObject(
            this.creeps.map(creep => creep.id),
            this.creeps.map(() => true)
        )
        this.entriesFree = _.zipObject(
            this.entries.map(entry => entry.id),
            this.entries.map(() => true)
        )
        this.assignments = new Map()
    }

    /* Return whether the entry prefers creep1 over creep2 */
    private prefers(entry: LedgerEntry, creep1: Creep, creep2: Creep): boolean {
        const prefs = this.entryPrefs.get(entry)
        if (!prefs) return false
        return prefs.indexOf(creep1) < prefs.indexOf(creep2)
    }

    /* Engage a creep with a LedgerEntry */
    private engage(creep: Creep, entry: LedgerEntry): void {
        this.creepsFree[creep.id] = false
        this.entriesFree[entry.id] = false
        this.assignments.set(creep, entry)

        const prefs = this.creepPrefs.get(creep)
        if (prefs) {
            _.remove(prefs, e => e.id === entry.id)
        }
    }

    /* Break up a creep and LedgerEntry */
    private breakup(creep: Creep, entry: LedgerEntry): void {
        this.creepsFree[creep.id] = true
        this.entriesFree[entry.id] = true
        this.assignments.delete(creep)
    }

    /* Return the next free creep with remaining preferences */
    private nextCreep(): Creep | undefined {
        return this.creeps.find(
            creep => this.creepsFree[creep.id] && (this.creepPrefs.get(creep)?.length || 0) > 0
        )
    }

    match(): Map<Creep, LedgerEntry> {
        const MAX_ITERATIONS = 1000
        let count = 0
        let creep = this.nextCreep()

        while (creep) {
            if (count > MAX_ITERATIONS) {
                console.log("Stable matching timed out!")
                return this.assignments
            }

            const entry = this.creepPrefs.get(creep)?.[0]
            if (!entry) continue

            if (this.entriesFree[entry.id]) {
                this.engage(creep, entry)
            } else {
                const currentCreep = Array.from(this.assignments.entries()).find(([_, e]) => e.id === entry.id)?.[0]
                if (currentCreep && this.prefers(entry, creep, currentCreep)) {
                    this.breakup(currentCreep, entry)
                    this.engage(creep, entry)
                } else {
                    const prefs = this.creepPrefs.get(creep)
                    if (prefs) {
                        _.remove(prefs, e => e.id === entry.id)
                    }
                }
            }

            creep = this.nextCreep()
            count++
        }

        return this.assignments
    }
}