-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLRUCache.h
More file actions
139 lines (127 loc) · 3.68 KB
/
LRUCache.h
File metadata and controls
139 lines (127 loc) · 3.68 KB
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
135
136
137
138
139
#ifndef _LRU_CACHE_H_
#define _LRU_CACHE_H_
#include "leetcode.h"
namespace Arch
{
class LRUCache {
public:
template<typename T>
class ListNode {
public:
ListNode(T val)
: m_Data(val)
, m_pNext(nullptr)
{}
ListNode()
: ListNode(0)
{}
T m_Data;
ListNode* m_pNext;
};
using PII = pair<int, int>;
using LNPII = ListNode<PII>;
LRUCache(int capacity)
: m_nSize(0)
, m_nCapacity(capacity)
, m_pHead(nullptr)
{
}
int get(int key) {
if (!hasKey(key))
return -1;
toHead(key);
auto iter = m_vMap.find(key);
return (*(iter->second))->m_Data.second;
}
void put(int key, int value) {
if (hasKey(key))
{
auto iter = m_vMap.find(key);
(*(iter->second))->m_Data.second = value;
toHead(key);
return;
}
if (IsFull())
{
del();
}
add(key, value);
}
private:
bool empty() const { return m_nSize == 0; }
bool IsFull() const { return m_nSize == m_nCapacity; }
bool hasKey(int key) const { return m_vMap.find(key) != m_vMap.end(); }
void toHead(int key) {
if (!hasKey(key))
return;
auto iter = m_vMap.find(key);
LNPII** ppNode = iter->second;
LNPII* pNode = *ppNode;
*ppNode = pNode->m_pNext;
if (*ppNode)
update((*ppNode)->m_Data.first, ppNode);
pNode->m_pNext = m_pHead;
m_pHead = pNode;
if (pNode->m_pNext)
update(pNode->m_pNext->m_Data.first, &(pNode->m_pNext));
update(pNode->m_Data.first, &m_pHead);
}
void add(int key, int value) {
if (IsFull())
return;
LNPII* pNode = new LNPII({ key, value });
pNode->m_pNext = m_pHead;
m_pHead = pNode;
if (pNode->m_pNext)
update(pNode->m_pNext->m_Data.first, &(pNode->m_pNext));
update(pNode->m_Data.first, &m_pHead);
++m_nSize;
}
void del(int key) {
if (!hasKey(key))
return;
auto iter = m_vMap.find(key);
LNPII** ppNode = iter->second;
LNPII* pNode = *ppNode;
*ppNode = pNode->m_pNext;
delete pNode;
m_vMap.erase(key);
--m_nSize;
}
void del() {
if (!IsFull())
return;
LNPII* pNode = m_pHead;
while (pNode && pNode->m_pNext)
pNode = pNode->m_pNext;
if (pNode)
del(pNode->m_Data.first);
}
void update(int key, LNPII** ppNode) {
m_vMap[key] = ppNode;
}
private:
int m_nSize{ 0 };
int m_nCapacity{ 0 };
LNPII* m_pHead;
unordered_map<int, LNPII**> m_vMap;
};
void LRUCache_get(LRUCache& cache, int key) {
cout << cache.get(key) << endl;
}
void LRUCache_put(LRUCache& cache, int key, int value) {
cache.put(key, value);
}
void LRUCache_unitTest()
{
LRUCache cache(2);
LRUCache_get(cache, 2);
LRUCache_put(cache, 2, 6);
LRUCache_get(cache, 1);
LRUCache_put(cache, 1, 5);
LRUCache_put(cache, 1, 2);
LRUCache_get(cache, 1);
LRUCache_get(cache, 2);
}
}
#endif // !_LRU_CACHE_H_