2020-07-02 16:06:02 +05:30
|
|
|
class LRUCache {
|
|
|
|
|
// LRU Cache to store a given capacity of data
|
2022-03-27 12:37:54 +06:00
|
|
|
#capacity
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* @param {number} capacity - the capacity of LRUCache
|
|
|
|
|
* @returns {LRUCache} - sealed
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
constructor(capacity) {
|
2022-03-27 12:37:54 +06:00
|
|
|
if (!Number.isInteger(capacity) || capacity < 0) {
|
|
|
|
|
throw new TypeError('Invalid capacity')
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
this.#capacity = ~~capacity
|
|
|
|
|
this.misses = 0
|
2020-07-02 16:06:02 +05:30
|
|
|
this.hits = 0
|
2022-03-27 12:37:54 +06:00
|
|
|
this.cache = new Map()
|
|
|
|
|
|
|
|
|
|
return Object.seal(this)
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
get info() {
|
2022-03-27 12:37:54 +06:00
|
|
|
return Object.freeze({
|
|
|
|
|
misses: this.misses,
|
|
|
|
|
hits: this.hits,
|
|
|
|
|
capacity: this.capacity,
|
|
|
|
|
size: this.size
|
|
|
|
|
})
|
|
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
get size() {
|
2022-03-27 12:37:54 +06:00
|
|
|
return this.cache.size
|
2020-07-02 16:06:02 +05:30
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
get capacity() {
|
2022-03-27 12:37:54 +06:00
|
|
|
return this.#capacity
|
2020-07-02 16:06:02 +05:30
|
|
|
}
|
|
|
|
|
|
2023-10-03 23:08:19 +02:00
|
|
|
set capacity(newCapacity) {
|
2022-03-27 12:37:54 +06:00
|
|
|
if (newCapacity < 0) {
|
|
|
|
|
throw new RangeError('Capacity should be greater than 0')
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
if (newCapacity < this.capacity) {
|
|
|
|
|
let diff = this.capacity - newCapacity
|
|
|
|
|
|
|
|
|
|
while (diff--) {
|
|
|
|
|
this.#removeLeastRecentlyUsed()
|
|
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
this.#capacity = newCapacity
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
2023-10-03 23:08:19 +02:00
|
|
|
* delete oldest key existing in map by the help of iterator
|
|
|
|
|
*/
|
|
|
|
|
#removeLeastRecentlyUsed() {
|
2022-03-27 12:37:54 +06:00
|
|
|
this.cache.delete(this.cache.keys().next().value)
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* @param {string} key
|
|
|
|
|
* @returns {*}
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
has(key) {
|
2022-03-27 12:37:54 +06:00
|
|
|
key = String(key)
|
|
|
|
|
|
|
|
|
|
return this.cache.has(key)
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* @param {string} key
|
|
|
|
|
* @param {*} value
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
set(key, value) {
|
2022-03-27 12:37:54 +06:00
|
|
|
key = String(key)
|
2021-11-25 12:33:10 +05:30
|
|
|
// Sets the value for the input key and if the key exists it updates the existing key
|
2022-03-27 12:37:54 +06:00
|
|
|
if (this.size === this.capacity) {
|
|
|
|
|
this.#removeLeastRecentlyUsed()
|
2020-07-02 16:06:02 +05:30
|
|
|
}
|
2022-03-27 12:37:54 +06:00
|
|
|
|
2021-11-25 12:33:10 +05:30
|
|
|
this.cache.set(key, value)
|
2020-07-02 16:06:02 +05:30
|
|
|
}
|
|
|
|
|
|
2022-03-27 12:37:54 +06:00
|
|
|
/**
|
|
|
|
|
* @param {string} key
|
|
|
|
|
* @returns {*}
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
get(key) {
|
2022-03-27 12:37:54 +06:00
|
|
|
key = String(key)
|
2021-11-25 12:33:10 +05:30
|
|
|
// Returns the value for the input key. Returns null if key is not present in cache
|
|
|
|
|
if (this.cache.has(key)) {
|
|
|
|
|
const value = this.cache.get(key)
|
2022-03-27 12:37:54 +06:00
|
|
|
|
2021-11-25 12:33:10 +05:30
|
|
|
// refresh the cache to update the order of key
|
|
|
|
|
this.cache.delete(key)
|
|
|
|
|
this.cache.set(key, value)
|
2022-03-27 12:37:54 +06:00
|
|
|
|
|
|
|
|
this.hits++
|
2021-11-25 12:33:10 +05:30
|
|
|
return value
|
2020-07-02 16:06:02 +05:30
|
|
|
}
|
2022-03-27 12:37:54 +06:00
|
|
|
|
|
|
|
|
this.misses++
|
|
|
|
|
return null
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* @param {JSON} json
|
|
|
|
|
* @returns {LRUCache}
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
parse(json) {
|
2022-03-27 12:37:54 +06:00
|
|
|
const { misses, hits, cache } = JSON.parse(json)
|
|
|
|
|
|
|
|
|
|
this.misses += misses ?? 0
|
|
|
|
|
this.hits += hits ?? 0
|
|
|
|
|
|
|
|
|
|
for (const key in cache) {
|
|
|
|
|
this.set(key, cache[key])
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return this
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
/**
|
|
|
|
|
* @param {number} indent
|
|
|
|
|
* @returns {JSON} - string
|
|
|
|
|
*/
|
2023-10-03 23:08:19 +02:00
|
|
|
toString(indent) {
|
2022-03-27 12:37:54 +06:00
|
|
|
const replacer = (_, value) => {
|
|
|
|
|
if (value instanceof Set) {
|
|
|
|
|
return [...value]
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
if (value instanceof Map) {
|
|
|
|
|
return Object.fromEntries(value)
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return value
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
return JSON.stringify(this, replacer, indent)
|
2020-07-02 16:06:02 +05:30
|
|
|
}
|
|
|
|
|
}
|
|
|
|
|
|
2022-03-27 12:37:54 +06:00
|
|
|
export default LRUCache
|
