1 /*
  2     Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
  3 
  4     get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
  5     set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, 
  6                   it should invalidate the least recently used item before inserting a new item. 
  7     Problem link: https://oj.leetcode.com/problems/lru-cache/
  8 
  9     Author: Vincent Zhang
 10 */
 11 
 12 #include <map>
 13 using namespace std;
 14 
 15 struct CacheNode {
 16     int key;
 17     int value;
 18     CacheNode* prev;
 19     CacheNode* next;
 20     CacheNode(int k,int v) : key(k), value(v), prev(NULL), next(NULL) {}
 21 };
 22 
 23 class LRUCache{
 24 public:
 25     LRUCache(int capacity) {
 26         this->cache_capacity = capacity;
 27         head = NULL;
 28         tail = NULL;        
 29     }
 30 
 31     int get(int key) {
 32         map<int,CacheNode*>::iterator it = cache_map.find(key);
 33         if (it == cache_map.end())
 34             return -1;
 35         else
 36         {
 37             CacheNode *tp = it->second;
 38             moveToHead(tp);
 39             return tp->value;
 40         }
 41     }
 42 
 43     void set(int key, int value) {
 44         map<int,CacheNode*>::iterator it = cache_map.find(key);
 45         // new key and value
 46         if (it == cache_map.end())
 47         {    
 48             // cache is full, release the LRU one and add new
 49             if (cache_map.size() == cache_capacity)
 50             {
 51                 cache_map.erase(tail->key);
 52                 tail->key = key;
 53                 tail->value =http://www.mamicode.com/ value;
 54                 CacheNode *tp = tail;
 55                 moveToHead(tp);
 56 
 57                 cache_map.insert(map<int,CacheNode*>::value_type(key,tp));
 58             }
 59             else    // cache is not full, add new
 60             {
 61                 CacheNode *newNode = new CacheNode(key,value);
 62                 attachToHead(newNode);
 63                 cache_map.insert(map<int,CacheNode*>::value_type(key,newNode));
 64             }
 65             
 66         }
 67         else    // has an exist node
 68         {
 69             CacheNode *tp = it->second;
 70             tp->value =http://www.mamicode.com/ value;
 71 
 72             isolateNode(tp);
 73             attachToHead(tp);
 74         }
 75 
 76     }
 77 private:
 78     int cache_capacity;
 79     CacheNode *head,*tail;
 80     map<int,CacheNode*> cache_map;
 81 
 82     void moveToHead(CacheNode *node)
 83     {
 84         if (node == head)
 85             return;
 86         else
 87         {
 88             isolateNode(node);
 89             attachToHead(node);
 90         }
 91     }
 92     void isolateNode(CacheNode* node)
 93     {
 94         if (node->prev != NULL)        
 95             node->prev->next = node->next;
 96         else // node is head
 97             head = node->next;
 98         
 99         if (node->next !=NULL)
100             node->next->prev = node->prev;
101         else    // node is tail
102             tail = node->prev;
103 
104         node->next = NULL;
105         node->prev = NULL;        
106     }
107     void attachToHead(CacheNode* node)
108     {
109         // head is null, list is empty
110         if (head == NULL)
111         {
112             head = node;
113             tail = head;
114         }
115         else
116         {
117             node->next = head;
118             head->prev = node;
119             head = node;
120         }
121     }
122 };