LRU cache

lru.ts

// problems: 1ms resolution

export type LruCacheKey = string | Symbol
export type LruCacheValue = unknown

export interface ILruCache {
    set: (this: ILruCache, key: LruCacheKey, value: LruCacheValue) => ILruCache
    get: (this: ILruCache, key: LruCacheKey) => LruCacheValue | undefined
    delete: (this: ILruCache, key: LruCacheKey) => LruCache
}

class LruCache implements ILruCache {
    protected data = new Map<LruCacheKey, LruCacheValue>()
    protected accessTime = new Map<LruCacheKey, number>()

    constructor(
        protected capacity: number,
    ) {}

    protected cleanup() {
        const { accessTime } = this

        // simple way

        let earliestKey: LruCacheKey | undefined = undefined
        let earliestTime = 0

        for (const [key, time] of accessTime) {
            if (!earliestKey || time < earliestTime) {
                earliestKey = key
                earliestTime = time
            }
        }

        if (earliestKey) {
            this.delete(earliestKey)
        }

        // faster "set" slower "get":
        // keep ASC sorted keys list instead of accessTime
        // on key access: find key in array, remove it, push to the end
        // on cleanup: shift key and rm
    }

    public set(key: LruCacheKey, value: LruCacheValue): LruCache {
        const { data, accessTime, capacity } = this

        if (data.size >= capacity) {
            this.cleanup()
        }

        data.set(key, value)
        accessTime.set(key, Date.now())

        return this
    }

    public get(key: LruCacheKey): LruCacheValue | undefined {
        const { data, accessTime } = this

        accessTime.set(key, Date.now())

        return data.get(key)
    }

    public delete(key: LruCacheKey): LruCache {
        const { data, accessTime } = this

        data.delete(key)
        accessTime.delete(key)

        return this
    }
}

const users = new LruCache(2)

users.set('u11', { name: 'aa' })
users.set('u22', { name: 'bb' })

setTimeout(() => {
    users.get('u11')
    users.set('u33', { name: 'cc' })
    // we expect u22 to be removed
    console.log(users)
}, 100)