[LeetCode]LRU Cache

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
public class LRUCache {
    class CacheEntry{
		int key;
		int value;
		CacheEntry pre;
		CacheEntry next;
		public CacheEntry(int k, int v) {
			this.key = k;
			this.value = v;
		}
	}
	int l_capacity;
	HashMap<Integer, CacheEntry> l_HashMapmap;
	CacheEntry head, tail;
	// use two way linklist
	public LRUCache(int capacity) {
		l_capacity = capacity;
		l_HashMapmap = new HashMap<>(capacity);
		head = new CacheEntry(-1, -1);
		tail = new CacheEntry(1, 1);
		head.next = tail;
		tail.pre = head;
    }
    
    public int get(int key) {//if contains key, just get value and update
        if(l_HashMapmap.containsKey(key)){
        	CacheEntry cEntry = l_HashMapmap.get(key);
        	MoveToHead(cEntry);
        	return cEntry.value;
        }
        else return -1;
    }
    
    public void set(int key, int value) {
        if(l_HashMapmap.containsKey(key)){//if map contains key, just update value
        	CacheEntry cEntry = l_HashMapmap.get(key);
        	cEntry.value = value;
        	MoveToHead(cEntry);
        }else if(l_HashMapmap.size()<l_capacity){//not contain & smaller the size
			CacheEntry cEntry = new CacheEntry(key, value);
			MoveToHead(cEntry);
			l_HashMapmap.put(key, cEntry);
		}else {//not contain key and over the size
			CacheEntry cEntry = new CacheEntry(key, value);
			MoveToHead(cEntry);
			l_HashMapmap.put(key, cEntry);
			int endIndex = removeEnd();
			l_HashMapmap.remove(endIndex);
		}
    }
    
    private int removeEnd() {
		// TODO Auto-generated method stub
    	CacheEntry cEntry = tail.pre;
    	tail.pre.pre.next = tail;
    	tail.pre = cEntry.pre;
    	cEntry.pre = null;
    	cEntry.next = null;
		return cEntry.key;
	}

	private void MoveToHead(CacheEntry cEntry) {
		// TODO Auto-generated method stub
		if(cEntry.next!=null && cEntry.pre!=null){
			cEntry.pre.next = cEntry.next;
			cEntry.next.pre = cEntry.pre;
		}
		cEntry.pre = head;
		cEntry.next = head.next;
		head.next.pre = cEntry;
		head.next = cEntry;
	}
}

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
class LRUCache{
public:
    struct CacheEntry{
        public:
            int key;
            int value;
            CacheEntry(int k, int v): key(k), value(v){}
    };

    LRUCache(int capacity){
        m_capacity = capacity;
    }

    int get(int key){
        if(m_map.find(key)==m_map.end())
            return -1;
        MoveToHead(key);
        return m_map[key]->value;
    }

    void set(int key, int value){
        if(m_map.find(key)==m_map.end()){
            CacheEntry newItem(key, value);
            if(m_LRU_cache.size()>=m_capacity){//remove from tail
                m_map.erase(m_LRU_cache.back().key);
                m_LRU_cache.pop_back();
            }
            //insert in head
            m_LRU_cache.push_front(newItem);
            m_map[key] = m_LRU_cache.begin();
            return;
        }
        m_map[key]->value = value;
        MoveToHead(key);
    }
private:
    int m_capacity;
    list<CacheEntry> m_LRU_cache;
    unordered_map<int, list<CacheEntry>::iterator> m_map;

    void MoveToHead(int key){
        auto updateEntry = *m_map[key];
        m_LRU_cache.erase(m_map[key]);
        m_LRU_cache.push_front(updateEntry);
        m_map[key] = m_LRU_cache.begin();
    }
};