|
| 1 | +package DataStructures.Caches; |
| 2 | + |
| 3 | +import java.util.HashMap; |
| 4 | +import java.util.Map; |
| 5 | + |
| 6 | +/** |
| 7 | + * Most recently used (MRU) |
| 8 | + * <p> |
| 9 | + * In contrast to Least Recently Used (LRU), MRU discards the most recently used items first. |
| 10 | + * https://en.wikipedia.org/wiki/Cache_replacement_policies#Most_recently_used_(MRU) |
| 11 | + * |
| 12 | + * @param <K> key type |
| 13 | + * @param <V> value type |
| 14 | + */ |
| 15 | +public class MRUCache<K, V> { |
| 16 | + private final Map<K, Entry<K, V>> data = new HashMap<>(); |
| 17 | + private Entry<K, V> head; |
| 18 | + private Entry<K, V> tail; |
| 19 | + private int cap; |
| 20 | + private static final int DEFAULT_CAP = 100; |
| 21 | + |
| 22 | + public MRUCache() { |
| 23 | + setCapacity(DEFAULT_CAP); |
| 24 | + } |
| 25 | + |
| 26 | + private void setCapacity(int newCapacity) { |
| 27 | + checkCapacity(newCapacity); |
| 28 | + for (int i = data.size(); i > newCapacity; i--) { |
| 29 | + Entry<K, V> evicted = evict(); |
| 30 | + data.remove(evicted.getKey()); |
| 31 | + } |
| 32 | + this.cap = newCapacity; |
| 33 | + } |
| 34 | + |
| 35 | + |
| 36 | + private void checkCapacity(int capacity) { |
| 37 | + if (capacity <= 0) { |
| 38 | + throw new RuntimeException("capacity must greater than 0!"); |
| 39 | + } |
| 40 | + } |
| 41 | + |
| 42 | + private Entry<K, V> evict() { |
| 43 | + if (head == null) { |
| 44 | + throw new RuntimeException("cache cannot be empty!"); |
| 45 | + } |
| 46 | + final Entry<K, V> evicted = this.tail; |
| 47 | + tail = evicted.getPreEntry(); |
| 48 | + tail.setNextEntry(null); |
| 49 | + evicted.setNextEntry(null); |
| 50 | + return evicted; |
| 51 | + } |
| 52 | + |
| 53 | + public MRUCache(int cap) { |
| 54 | + setCapacity(cap); |
| 55 | + } |
| 56 | + |
| 57 | + public V get(K key) { |
| 58 | + if (!data.containsKey(key)) { |
| 59 | + return null; |
| 60 | + } |
| 61 | + final Entry<K, V> entry = data.get(key); |
| 62 | + moveEntryToLast(entry); |
| 63 | + return entry.getValue(); |
| 64 | + } |
| 65 | + |
| 66 | + public void put(K key, V value) { |
| 67 | + if (data.containsKey(key)) { |
| 68 | + final Entry<K, V> exitingEntry = data.get(key); |
| 69 | + exitingEntry.setValue(value); |
| 70 | + moveEntryToLast(exitingEntry); |
| 71 | + return; |
| 72 | + } |
| 73 | + Entry<K, V> newEntry; |
| 74 | + if (data.size() == cap) { |
| 75 | + newEntry = evict(); |
| 76 | + data.remove(newEntry.getKey()); |
| 77 | + } else { |
| 78 | + newEntry = new Entry<>(); |
| 79 | + } |
| 80 | + newEntry.setKey(key); |
| 81 | + newEntry.setValue(value); |
| 82 | + addNewEntry(newEntry); |
| 83 | + data.put(key, newEntry); |
| 84 | + } |
| 85 | + |
| 86 | + private void addNewEntry(Entry<K, V> newEntry) { |
| 87 | + if (data.isEmpty()) { |
| 88 | + head = newEntry; |
| 89 | + tail = newEntry; |
| 90 | + return; |
| 91 | + } |
| 92 | + tail.setNextEntry(newEntry); |
| 93 | + newEntry.setPreEntry(tail); |
| 94 | + newEntry.setNextEntry(null); |
| 95 | + tail = newEntry; |
| 96 | + } |
| 97 | + |
| 98 | + private void moveEntryToLast(Entry<K, V> entry) { |
| 99 | + if (tail == entry) { |
| 100 | + return; |
| 101 | + } |
| 102 | + final Entry<K, V> preEntry = entry.getPreEntry(); |
| 103 | + final Entry<K, V> nextEntry = entry.getNextEntry(); |
| 104 | + if (preEntry != null) { |
| 105 | + preEntry.setNextEntry(nextEntry); |
| 106 | + } |
| 107 | + if (nextEntry != null) { |
| 108 | + nextEntry.setPreEntry(preEntry); |
| 109 | + } |
| 110 | + if (head == entry) { |
| 111 | + head = nextEntry; |
| 112 | + } |
| 113 | + tail.setNextEntry(entry); |
| 114 | + entry.setPreEntry(tail); |
| 115 | + entry.setNextEntry(null); |
| 116 | + tail = entry; |
| 117 | + } |
| 118 | + |
| 119 | + static final class Entry<I, J> { |
| 120 | + private Entry<I, J> preEntry; |
| 121 | + private Entry<I, J> nextEntry; |
| 122 | + private I key; |
| 123 | + private J value; |
| 124 | + |
| 125 | + public Entry() { |
| 126 | + } |
| 127 | + |
| 128 | + public Entry(Entry<I, J> preEntry, Entry<I, J> nextEntry, I key, J value) { |
| 129 | + this.preEntry = preEntry; |
| 130 | + this.nextEntry = nextEntry; |
| 131 | + this.key = key; |
| 132 | + this.value = value; |
| 133 | + } |
| 134 | + |
| 135 | + public Entry<I, J> getPreEntry() { |
| 136 | + return preEntry; |
| 137 | + } |
| 138 | + |
| 139 | + public void setPreEntry(Entry<I, J> preEntry) { |
| 140 | + this.preEntry = preEntry; |
| 141 | + } |
| 142 | + |
| 143 | + public Entry<I, J> getNextEntry() { |
| 144 | + return nextEntry; |
| 145 | + } |
| 146 | + |
| 147 | + public void setNextEntry(Entry<I, J> nextEntry) { |
| 148 | + this.nextEntry = nextEntry; |
| 149 | + } |
| 150 | + |
| 151 | + public I getKey() { |
| 152 | + return key; |
| 153 | + } |
| 154 | + |
| 155 | + public void setKey(I key) { |
| 156 | + this.key = key; |
| 157 | + } |
| 158 | + |
| 159 | + public J getValue() { |
| 160 | + return value; |
| 161 | + } |
| 162 | + |
| 163 | + public void setValue(J value) { |
| 164 | + this.value = value; |
| 165 | + } |
| 166 | + } |
| 167 | + |
| 168 | + public static void main(String[] args) { |
| 169 | + final MRUCache<String, Integer> cache = new MRUCache<>(2); |
| 170 | + cache.put("Key1", 1); |
| 171 | + cache.put("Key2", 2); |
| 172 | + cache.put("Key3", 3); |
| 173 | + cache.put("Key4", 4); |
| 174 | + System.out.println("getValue(Key1): " + cache.get("Key1")); |
| 175 | + System.out.println("getValue(Key2): " + cache.get("Key2")); |
| 176 | + System.out.println("getValue(Key3): " + cache.get("Key3")); |
| 177 | + System.out.println("getValue(Key4): " + cache.get("Key4")); |
| 178 | + } |
| 179 | +} |
0 commit comments