Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit81c771b

Browse files
authored
merge: ImprovedLRUCache (#953)
* feat: added new validation test casses & methods* style: formated with standard* feat: added parse method & test cases* docs: added js docs* chore: added default import export
1 parent55da7a1 commit81c771b

File tree

2 files changed

+164
-21
lines changed

2 files changed

+164
-21
lines changed

‎Cache/LRUCache.js

Lines changed: 120 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,40 +1,146 @@
11
classLRUCache{
22
// LRU Cache to store a given capacity of data
3+
#capacity
4+
5+
/**
6+
*@param {number} capacity - the capacity of LRUCache
7+
*@returns {LRUCache} - sealed
8+
*/
39
constructor(capacity){
4-
this.cache=newMap()
5-
this.capacity=capacity
10+
if(!Number.isInteger(capacity)||capacity<0){
11+
thrownewTypeError('Invalid capacity')
12+
}
13+
14+
this.#capacity=~~capacity
15+
this.misses=0
616
this.hits=0
7-
this.miss=0
17+
this.cache=newMap()
18+
19+
returnObject.seal(this)
20+
}
21+
22+
getinfo(){
23+
returnObject.freeze({
24+
misses:this.misses,
25+
hits:this.hits,
26+
capacity:this.capacity,
27+
size:this.size
28+
})
29+
}
30+
31+
getsize(){
32+
returnthis.cache.size
833
}
934

10-
cacheInfo(){
11-
// Return the details for the cache instance [hits, misses, capacity, current_size]
12-
return`CacheInfo(hits=${this.hits}, misses=${this.miss}, capacity=${this.capacity}, current size=${this.cache.size})`
35+
getcapacity(){
36+
returnthis.#capacity
1337
}
1438

39+
setcapacity(newCapacity){
40+
if(newCapacity<0){
41+
thrownewRangeError('Capacity should be greater than 0')
42+
}
43+
44+
if(newCapacity<this.capacity){
45+
letdiff=this.capacity-newCapacity
46+
47+
while(diff--){
48+
this.#removeLeastRecentlyUsed()
49+
}
50+
}
51+
52+
this.#capacity=newCapacity
53+
}
54+
55+
/**
56+
* delete oldest key existing in map by the help of iterator
57+
*/
58+
#removeLeastRecentlyUsed(){
59+
this.cache.delete(this.cache.keys().next().value)
60+
}
61+
62+
/**
63+
*@param {string} key
64+
*@returns {*}
65+
*/
66+
has(key){
67+
key=String(key)
68+
69+
returnthis.cache.has(key)
70+
}
71+
72+
/**
73+
*@param {string} key
74+
*@param {*} value
75+
*/
1576
set(key,value){
77+
key=String(key)
1678
// Sets the value for the input key and if the key exists it updates the existing key
17-
if(this.cache.size===this.capacity){
18-
// delete oldest key existing in map
19-
this.cache.delete(this.cache.keys().next().value)
79+
if(this.size===this.capacity){
80+
this.#removeLeastRecentlyUsed()
2081
}
82+
2183
this.cache.set(key,value)
2284
}
2385

86+
/**
87+
*@param {string} key
88+
*@returns {*}
89+
*/
2490
get(key){
91+
key=String(key)
2592
// Returns the value for the input key. Returns null if key is not present in cache
2693
if(this.cache.has(key)){
2794
constvalue=this.cache.get(key)
95+
2896
// refresh the cache to update the order of key
2997
this.cache.delete(key)
3098
this.cache.set(key,value)
31-
this.hits+=1
99+
100+
this.hits++
32101
returnvalue
33-
}else{
34-
this.miss+=1
35-
returnnull
36102
}
103+
104+
this.misses++
105+
returnnull
106+
}
107+
108+
/**
109+
*@param {JSON} json
110+
*@returns {LRUCache}
111+
*/
112+
parse(json){
113+
const{ misses, hits, cache}=JSON.parse(json)
114+
115+
this.misses+=misses??0
116+
this.hits+=hits??0
117+
118+
for(constkeyincache){
119+
this.set(key,cache[key])
120+
}
121+
122+
returnthis
123+
}
124+
125+
/**
126+
*@param {number} indent
127+
*@returns {JSON} - string
128+
*/
129+
toString(indent){
130+
constreplacer=(_,value)=>{
131+
if(valueinstanceofSet){
132+
return[...value]
133+
}
134+
135+
if(valueinstanceofMap){
136+
returnObject.fromEntries(value)
137+
}
138+
139+
returnvalue
140+
}
141+
142+
returnJSON.stringify(this,replacer,indent)
37143
}
38144
}
39145

40-
export{LRUCache}
146+
exportdefaultLRUCache

‎Cache/test/LRUCache.test.js

Lines changed: 44 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,19 @@
1-
import{LRUCache}from'../LRUCache'
1+
importLRUCachefrom'../LRUCache'
22
import{fibonacciCache}from'./cacheTest'
33

4-
describe('LRUCache',()=>{
5-
it('Example 1 (Small Cache, size=2)',()=>{
6-
constcache=newLRUCache(2)
4+
describe('Testing LRUCache',()=>{
5+
it('Testing with invalid capacity',()=>{
6+
expect(()=>newLRUCache()).toThrow()
7+
expect(()=>newLRUCache('Invalid')).toThrow()
8+
expect(()=>newLRUCache(-1)).toThrow()
9+
expect(()=>newLRUCache(Infinity)).toThrow()
10+
})
11+
12+
it('Example 1 (Small Cache, size = 2)',()=>{
13+
constcache=newLRUCache(1)// initially capacity
14+
15+
cache.capacity++// now the capacity is increasing by one
16+
717
cache.set(1,1)
818
cache.set(2,2)
919

@@ -24,14 +34,41 @@ describe('LRUCache', () => {
2434
expect(cache.get(3)).toBe(3)
2535
expect(cache.get(4)).toBe(4)
2636

27-
expect(cache.cacheInfo()).toBe('CacheInfo(hits=6, misses=3, capacity=2, current size=2)')
37+
expect(cache.info).toEqual({
38+
misses:3,
39+
hits:6,
40+
capacity:2,
41+
size:2
42+
})
43+
44+
constjson='{"misses":3,"hits":6,"cache":{"3":3,"4":4}}'
45+
expect(cache.toString()).toBe(json)
46+
47+
// merge with json
48+
cache.parse(json)
49+
50+
cache.capacity--// now the capacity decreasing by one
51+
52+
expect(cache.info).toEqual({
53+
misses:6,
54+
hits:12,
55+
capacity:1,
56+
size:1
57+
})
2858
})
2959

30-
it('Example 2 (Computing Fibonacci Series, size=100)',()=>{
60+
it('Example 2 (Computing Fibonacci Series, size =100)',()=>{
3161
constcache=newLRUCache(100)
62+
3263
for(leti=1;i<=100;i++){
3364
fibonacciCache(i,cache)
3465
}
35-
expect(cache.cacheInfo()).toBe('CacheInfo(hits=193, misses=103, capacity=100, current size=98)')
66+
67+
expect(cache.info).toEqual({
68+
misses:103,
69+
hits:193,
70+
capacity:100,
71+
size:98
72+
})
3673
})
3774
})

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp