2022-03-21 22:43:45 +06:00
class CacheNode {
2023-10-03 23:08:19 +02:00
constructor ( key , value , frequency ) {
2020-07-07 12:38:18 +05:30
this . key = key
2022-03-21 22:43:45 +06:00
this . value = value
this . frequency = frequency
return Object . seal ( this )
2020-07-07 12:38:18 +05:30
}
}
2022-03-21 22:43:45 +06:00
// This frequency map class will act like javascript Map DS with more two custom method refresh & insert
class FrequencyMap extends Map {
2023-10-03 23:08:19 +02:00
static get [ Symbol . species ] ( ) {
return Map
} // for using Symbol.species we can access Map constructor @see -> https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Map/@@species
get [ Symbol . toStringTag ] ( ) {
return ''
}
2020-07-07 12:38:18 +05:30
2022-03-21 22:43:45 +06:00
/**
2023-10-03 23:08:19 +02:00
* @method refresh
* @description - It's revive a CacheNode, increment of this nodes frequency and refresh the frequencyMap via new incremented nodes frequency
* @param {CacheNode} node
*/
refresh ( node ) {
2022-03-21 22:43:45 +06:00
const { frequency } = node
const freqSet = this . get ( frequency )
freqSet . delete ( node )
node . frequency ++
2020-07-07 12:38:18 +05:30
2022-03-21 22:43:45 +06:00
this . insert ( node )
2020-07-07 12:38:18 +05:30
}
2022-03-21 22:43:45 +06:00
/**
* @method insert
* @description - Add new CacheNode into HashSet by the frequency
* @param {CacheNode} node
*/
2023-10-03 23:08:19 +02:00
insert ( node ) {
2022-03-21 22:43:45 +06:00
const { frequency } = node
2020-07-07 12:38:18 +05:30
2022-03-21 22:43:45 +06:00
if ( ! this . has ( frequency ) ) {
this . set ( frequency , new Set ( ) )
}
this . get ( frequency ) . add ( node )
2020-07-07 12:38:18 +05:30
}
}
class LFUCache {
2022-10-16 12:39:56 +02:00
# capacity
# frequencyMap
2020-07-07 12:38:18 +05:30
2022-10-16 12:39:56 +02:00
/**
2023-10-03 23:08:19 +02:00
* @param {number} capacity - The range of LFUCache
* @returns {LFUCache} - sealed
*/
constructor ( capacity ) {
2022-10-16 12:39:56 +02:00
this . # capacity = capacity
this . # frequencyMap = new FrequencyMap ( )
this . misses = 0
this . hits = 0
this . cache = new Map ( )
return Object . seal ( this )
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
/**
2022-03-21 22:43:45 +06:00
* Get the capacity of the LFUCache
* @returns {number}
*/
2023-10-03 23:08:19 +02:00
get capacity ( ) {
2022-10-16 12:39:56 +02:00
return this . # capacity
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
/**
2022-03-21 22:43:45 +06:00
* Get the current size of LFUCache
* @returns {number}
*/
2023-10-03 23:08:19 +02:00
get size ( ) {
2022-10-16 12:39:56 +02:00
return this . cache . size
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
/**
2023-10-03 23:08:19 +02:00
* Set the capacity of the LFUCache if you decrease the capacity its removed CacheNodes following the LFU - least frequency used
*/
set capacity ( newCapacity ) {
2022-10-16 12:39:56 +02:00
if ( this . # capacity > newCapacity ) {
let diff = this . # capacity - newCapacity // get the decrement number of capacity
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
while ( diff -- ) {
this . # removeCacheNode ( )
2020-07-07 12:38:18 +05:30
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
this . cache . size === 0 && this . # frequencyMap . clear ( )
2020-07-07 12:38:18 +05:30
}
2022-10-16 12:39:56 +02:00
this . # capacity = newCapacity
}
2022-03-21 22:43:45 +06:00
2023-10-03 23:08:19 +02:00
get info ( ) {
2022-10-16 12:39:56 +02:00
return Object . freeze ( {
misses : this . misses ,
hits : this . hits ,
capacity : this . capacity ,
currentSize : this . size ,
leastFrequency : this . leastFrequency
} )
}
2022-03-21 22:43:45 +06:00
2023-10-03 23:08:19 +02:00
get leastFrequency ( ) {
2022-10-16 12:39:56 +02:00
const freqCacheIterator = this . # frequencyMap . keys ( )
let leastFrequency = freqCacheIterator . next ( ) . value || null
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
// select the non-empty frequency Set
while ( this . # frequencyMap . get ( leastFrequency ) ? . size === 0 ) {
leastFrequency = freqCacheIterator . next ( ) . value
2022-03-21 22:43:45 +06:00
}
2022-10-16 12:39:56 +02:00
return leastFrequency
}
2022-03-21 22:43:45 +06:00
2023-10-03 23:08:19 +02:00
# removeCacheNode ( ) {
2022-10-16 12:39:56 +02:00
const leastFreqSet = this . # frequencyMap . get ( this . leastFrequency )
// Select the least recently used node from the least Frequency set
const LFUNode = leastFreqSet . values ( ) . next ( ) . value
leastFreqSet . delete ( LFUNode )
this . cache . delete ( LFUNode . key )
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
/**
2022-03-21 22:43:45 +06:00
* if key exist then return true otherwise false
* @param {any} key
* @returns {boolean}
*/
2023-10-03 23:08:19 +02:00
has ( key ) {
2022-10-16 12:39:56 +02:00
key = String ( key ) // converted to string
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
return this . cache . has ( key )
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
/**
2023-10-03 23:08:19 +02:00
* @method get
* @description - This method return the value of key & refresh the frequencyMap by the oldNode
* @param {string} key
* @returns {any}
*/
get ( key ) {
2022-10-16 12:39:56 +02:00
key = String ( key ) // converted to string
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
if ( this . cache . has ( key ) ) {
const oldNode = this . cache . get ( key )
this . # frequencyMap . refresh ( oldNode )
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
this . hits ++
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
return oldNode . value
2022-03-21 22:43:45 +06:00
}
2022-10-16 12:39:56 +02:00
this . misses ++
return null
}
/**
2023-10-03 23:08:19 +02:00
* @method set
* @description - This method stored the value by key & add frequency if it doesn't exist
* @param {string} key
* @param {any} value
* @param {number} frequency
* @returns {LFUCache}
*/
set ( key , value , frequency = 1 ) {
2022-10-16 12:39:56 +02:00
key = String ( key ) // converted to string
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
if ( this . # capacity === 0 ) {
throw new RangeError ( 'LFUCache ERROR: The Capacity is 0' )
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
if ( this . cache . has ( key ) ) {
const node = this . cache . get ( key )
node . value = value
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
this . # frequencyMap . refresh ( node )
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
return this
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
// if the cache size is full, then it's delete the Least Frequency Used node
if ( this . # capacity === this . cache . size ) {
this . # removeCacheNode ( )
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
const newNode = new CacheNode ( key , value , frequency )
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
this . cache . set ( key , newNode )
this . # frequencyMap . insert ( newNode )
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
return this
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
/**
2023-10-03 23:08:19 +02:00
* @method parse
* @description - This method receive a valid LFUCache JSON & run JSON.prase() method and merge with existing LFUCache
* @param {JSON} json
* @returns {LFUCache} - merged
*/
parse ( json ) {
2022-10-16 12:39:56 +02:00
const { misses , hits , cache } = JSON . parse ( json )
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
this . misses += misses ? ? 0
this . hits += hits ? ? 0
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
for ( const key in cache ) {
const { value , frequency } = cache [ key ]
this . set ( key , value , frequency )
2022-03-21 22:43:45 +06:00
}
2022-10-16 12:39:56 +02:00
return this
}
/**
2023-10-03 23:08:19 +02:00
* @method clear
* @description - This method cleared the whole LFUCache
* @returns {LFUCache}
*/
clear ( ) {
2022-10-16 12:39:56 +02:00
this . cache . clear ( )
this . # frequencyMap . clear ( )
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
return this
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
/**
2023-10-03 23:08:19 +02:00
* @method toString
* @description - This method generate a JSON format of LFUCache & return it.
* @param {number} indent
* @returns {string} - JSON
*/
toString ( indent ) {
2022-10-16 12:39:56 +02:00
const replacer = ( _ , value ) => {
if ( value instanceof Set ) {
return [ ... value ]
}
2022-03-21 22:43:45 +06:00
2022-10-16 12:39:56 +02:00
if ( value instanceof Map ) {
return Object . fromEntries ( value )
2022-03-21 22:43:45 +06:00
}
2022-10-16 12:39:56 +02:00
return value
2020-07-07 12:38:18 +05:30
}
2022-10-16 12:39:56 +02:00
return JSON . stringify ( this , replacer , indent )
}
2020-07-07 12:38:18 +05:30
}
2022-03-21 22:43:45 +06:00
export default LFUCache
