-
Notifications
You must be signed in to change notification settings - Fork 1
/
LRUCache.cs
134 lines (115 loc) · 3.88 KB
/
LRUCache.cs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
using System;
using System.Collections.Generic;
namespace CSharp.DS.Cache
{
public class LRUCache
{
public class LRUCacheNode
{
public LRUCacheNode prev;
public LRUCacheNode next;
public string key;
public int val;
public LRUCacheNode(string key, int val)
{
this.key = key;
this.val = val;
}
/// <summary>
/// Helper function to detach a node from the DLL List
/// </summary>
public void Detach()
{
if (prev != null)
{
prev.next = next;
}
if (next != null)
{
next.prev = prev;
}
prev = null;
next = null;
}
}
private readonly int _maxSize;
public int _currentSize;
public LRUCacheNode _head; // Most Recently Used
public LRUCacheNode _tail; // Least Recently Used
public Dictionary<string, LRUCacheNode> _keyToNodeDictionary;
public LRUCache(int size)
{
if (size < 1)
{
throw new ArgumentException("Size of LRU Cache must be greater than 0", nameof(size));
}
_maxSize = size;
_keyToNodeDictionary = new Dictionary<string, LRUCacheNode>(size);
}
/// <summary>
/// Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
/// </summary>
/// <param name="key"></param>
/// <param name="value"></param>
public void Insert(string key, int value)
{
LRUCacheNode newEntry;
if (_keyToNodeDictionary.ContainsKey(key))
{
_keyToNodeDictionary[key].val = value;
newEntry = _keyToNodeDictionary[key];
// Update MRU and LRU in case they point to this node
if (newEntry == _tail)
_tail = _tail.prev;
else if (newEntry == _head)
_head = _head.next;
// Detach from DLL
newEntry.Detach();
}
else
{
newEntry = new LRUCacheNode(key, value);
// Eviction based on LRU
if (_currentSize == _maxSize)
Evict();
else
_currentSize++; // Only increment if it is not contained and currentSize < maxsize
_keyToNodeDictionary.Add(newEntry.key, newEntry);
}
// Update MRU
var prevHead = _head;
_head = newEntry;
_head.next = prevHead;
if (prevHead != null)
prevHead.prev = _head;
if (_tail == null)
_tail = newEntry;
}
/// <summary>
/// Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
/// </summary>
/// <param name="key"></param>
/// <returns></returns>
public int? GetValue(string key)
{
if (!_keyToNodeDictionary.ContainsKey(key))
{
return null;
}
// Fake-update the value to sift the mru to the current key
Insert(key, _keyToNodeDictionary[key].val);
return _keyToNodeDictionary[key].val;
}
public string GetMostRecentKey()
{
return _head?.key;
}
private void Evict()
{
_keyToNodeDictionary.Remove(_tail.key);
_tail = _tail?.prev;
if (_tail?.next != null)
_tail.next = null;
}
}
}