LeetCode/0146-lru-cache.cpp at master · benwu25/LeetCode · GitHub

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
140
141
142
#include <bits/stdc++.h>
using namespace std;

class LRUCache {
public:
    struct Node {
        int key;
        int value;
        Node *next;
        Node *prev;
        Node (int key, int value) : key(key), value(value), next(nullptr), prev(nullptr) { }
    };

    Node *front;
    Node *back;

    unordered_map<int, Node *> key_map;

    int capacity;

    LRUCache(int capacity) : capacity(capacity), front(nullptr), back(nullptr) { }

    void move_to_front(Node *place) {
        // check new node
        if (!place->next && !place->prev) {
            // save old front
            place->next = front;

            // set old front prev if valid
            if (front)
                front->prev = place;

            // update front
            front = place;
        }

        // pre-existing node

        if (place == front)
            return;
        if (place == back) {
            // update back
            back = place->prev;

            // new back should have no next pointer
            place->prev->next = nullptr;

            // save old front
            place->next = front;

            // set old front prev
            front->prev = place;

            // front has no prev pointer
            place->prev = nullptr;

            // update front
            front = place;
        } else {
            // link prev to next
            place->prev->next = place->next;

            // link next to prev
            place->next->prev = place->prev;

            // save old front
            place->next = front;

            // set old front prev
            front->prev = place;

            // front has no prev pointer
            place->prev = nullptr;

            // update front
            front = place;
        }
    }

    int get(int key) {
        if (!key_map.contains(key))
            return -1;
        Node *place = key_map[key];
        int value = place->value;
        move_to_front(place);
        return value;
    }

    void put(int key, int value) {
        if (key_map.contains(key)) {
            Node *place = key_map[key];
            place->value = value;
            move_to_front(place);
        } else if (key_map.size() < capacity) {
            // construct new node
            Node *place = new Node(key, value);

            // move to front
            move_to_front(place);

            // update key_map
            key_map[key] = place;

            // update back if one node
            if (key_map.size() == 1)
                back = place;
        } else {
            // identify LRU
            Node *lru = back;

            // erase from key_map
            key_map.erase(lru->key);

            // update back
            back = lru->prev;

            // if back, new back should have no next pointer
            if (back)
                lru->prev->next = nullptr;

            // construct new node
            Node *place = new Node(key, value);

            // move to front
            move_to_front(place);

            // update key_map
            key_map[key] = place;

            // update back if one node
            if (key_map.size() == 1)
                back = place;
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */