Repository navigation
Expand file tree
/
Copy pathLRUCache.java
More file actions
73 lines (66 loc) · 1.72 KB
/
Copy pathLRUCache.java
File metadata and controls
73 lines (66 loc) · 1.72 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
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.LinkedList;
// O(n) b/c search through Queue
// Can be O(1) is have hashmap go to node in queue.
public class LRUCache {
public static void main(String[] args)
{
LRUCache c = new LRUCache(2);
System.out.println(c.get(2));
c.set(2, 1);
c.set(2, 6);
System.out.println(c.get(1));
c.set(1, 5);
c.set(1, 2);
System.out.println(c.get(1));
System.out.println(c.get(2));
}
private int cur_size;
private int max_size;
private HashMap<Integer, Integer> cache;
private LinkedList<Integer> recent;
public LRUCache(int capacity) {
max_size = capacity;
cur_size = 0;
cache = new HashMap<Integer, Integer>();
recent = new LinkedList<Integer>();
}
public int get(int key) {
if(cache.containsKey(key))
{
recent.remove((Object) key);
recent.addFirst(key);
return cache.get(key);
}
else
return -1;
}
public void set(int key, int value) {
// Put
if(!cache.containsKey(key))
{
System.out.println("Adding " + key + ":" + value);
recent.addFirst(key);
cache.put(key, value);
cur_size++;
}
// Set
else if(cache.containsKey(key))
{
System.out.println("Setting " + key + " to " + value);
recent.remove((Object) key);
recent.addFirst(key);
cache.put(key, value);
}
// Max capacity
else if(cur_size == max_size)
{
int temp = recent.removeLast();
System.out.println("Removing " + temp + " " + cache.get(temp));
// Invalidate least recently used
cache.remove((Object) temp);
cur_size--;
}
}
}