LRU Cache - Alphasights - Search and Discovery - Full Stack - 12/15/21

// Implement an LRU (Least recently used) cache

// Let T be the total possible page numbers that can be referred. Let N be the total number of page frames that the cache can hold at any time. The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache.

// Example:

// Consider the following sequential reference string, with N = 3:

// 1, 2, 3, 4, 2, 5, 1, 2, 3, 4, 5


// First we put 1,2 and then 3 into the cache. When 4 is referenced, it causes a fault since the cache is full but 4 is not in the cache. We eject 1 (the least recently used) resulting in 2, 3 and 4 in the cache. When page 2 it is in the cache, so the contents of the cache do not change. When 5 is referenced, it is not in the cache, so it causes another fault, so 3 gets ejected leading to 4, 2 and 5 being in the cache. Etc.

class lruCache {
    constructor(n) {
        this.n = n;
        this.cache = [];
        this.map = {};
    }
    
    eject(value) {
       //this.map[value] = null; 
       //this.map.remove(value);

        delete this.map[this.cache.shift()];
    }
    
    put(value) {
        if (this.map[value] != null) {
            return;
        } else {
             if (this.cache.length >= cacheSize) {
                this.eject(value);
            }
    
            this.cache.push(value);
            this.map[value] = true; 
        }
       
    }
    
    // get cache() {
    //     return this.cache;
    // }

}

const cacheSize = 3; 
// const cache = [];

// function eject() {
    
// }

// function put(value) {
//     if (cache.length >= cacheSize) {
//          eject();
//     }
    
//     cache.push(value);
// }

const input = [1, 2, 3, 4, 2, 5, 1, 2, 3, 4, 5]
function main(insertValues) {
    let cache = new lruCache(cacheSize);
    
    insertValues.forEach((insertValue) => {
        cache.put(insertValue);
        console.log(cache.cache);
        //console.log(cache.map)
    })
}

main(input);