460. LFU Cache

/*

unordered_map<int, my_val_t*>    m_node;  // map node

map<int, my_val_t*>              m_fr;    // map frenquency

int                             m_cap;   // capacity

算法思想：

    另个map，

1. 1个map存贮key对应的数据的指针。（很快找到这个元素的在双向链表中的位置）2. 每个数据用双向链表链接起来，用双向链表的原因是删除、增加快。

3. 用指针的目的是，能很快的找到key所对应的key/value的指针，然后通过指针能很快的定位这个key/value所在的双向链表的位置。

    1个map存对应的频率所对应的key/value

1. 如果frequency所对应的链表为空(head->pre == head)就把它从map中删除掉。

2. 保证map的第一个元素是频率最小的节点的集合。

3. 从这个集合的尾部元素是频率最小，没有试用的时间最长。

4. 不用unordered_map是为了找到频率最小的元素的集合。

*/

typedef struct my_val my_val_t;
struct my_val {
int     key;
int     val;
int     frequency;
my_val_t* next;
my_val_t* pre;
my_val(int k, int v) { key = k;val = v;frequency = 1;next = NULL;pre = NULL; };
};
class LFUCache {
public:
LFUCache(int capacity) {
m_cap = capacity;
}


int get(int key) {
if (m_node.count(key))
{
my_val_t* p = m_node[key];
int fr = p->frequency;
int ans = p->val;
// get off the node from original frequency
my_val_t* head = m_fr[fr];
getoffNode(p);


//the original changed to empty , erase this frequency.
if (head->next == head)
{
delete head;
head = NULL;
m_fr.erase(fr);
}
// insert the  the node to the new frequency
p->frequency = ++fr;
// if the new frequency not empty
if (m_fr.count(fr))
{
my_val_t* headNew = m_fr[fr];
insertNodeTofirst(headNew, p);
}
else
{
m_fr[fr] = insertNodeTofirst(NULL, p);
}


return ans;
}
else
{
return -1;
}
}


void put(int key, int value) {


int ret = get(key);
if (ret != -1)
{
m_node[key]->val = value;
return;
}
if (0 == m_cap)
{
return;
};
my_val_t* p = new my_val_t(key,value);
if (m_node.size()<m_cap)
{
int fr = p->frequency;
if (m_fr.count(fr))
{
my_val_t* headNew = m_fr[fr];
insertNodeTofirst(headNew, p);
}
else
{
m_fr[fr] = insertNodeTofirst(NULL, p);
}


}
else
{
// find the min frenquency list
my_val_t* pHead = (*(m_fr.begin())).second;
// get rid of the last node;
my_val_t* pFree = pHead->pre;
getoffNode(pHead->pre);
// free pHead->pre
// get rid of pHead->pre from m_node
if (pHead->pre == pHead)
{
delete pHead;
pHead = NULL;
m_fr.erase(m_fr.begin());
}
m_node.erase(pFree->key);
delete pFree;
pFree = NULL;
int fr = p->frequency;
if (m_fr.count(fr))
{
my_val_t* headNew = m_fr[fr];
insertNodeTofirst(headNew, p);
}
else
{
m_fr[fr] = insertNodeTofirst(NULL, p);
}
}


m_node[key] = p;
}
private:
unordered_map<int, my_val_t*>    m_node;  // map node
map<int, my_val_t*>              m_fr;    // map frenquency
int                             m_cap;   // capacity
private:
void getoffNode(my_val_t* p)
{
p->pre->next = p->next;
p->next->pre = p->pre;
};
my_val_t* insertNodeTofirst(my_val_t* head, my_val_t* p)
{
if (head == NULL)
{
head = new my_val_t(0,0);
head->next = head;
head->pre = head;
}
p->next = head->next;
head->next->pre = p;
head->next = p;
p->pre = head;
return head;
}
};