Java/src/main/java/com/caching/LFUCache.java at Development · iDev-git/Java · GitHub

Repository navigation

History

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

143

144

145

146

147

148

149

150

151

152

153

154

155

package com.caching;

import java.util.HashMap;

import java.util.NoSuchElementException;

import java.util.TreeMap;

/**

* Your LFUCache object can be instantiated and called as such: LFUCache

* lfuCache = new LFUCache(capacity); lfuCache.put(key,value); int param_1 =

* lfuCache.get(key);

class LFUCache<T> {

// internal Node to store cache element

private class Node {

int key;

T value;

int freq;

Node next;

Node pre;

public Node(int key, T value, int freq) {

this.key = key;

this.value = value;

this.freq = freq;

next = pre = null;

}

public String toString() {

return " Key: " + key + "Value: " + value + "Freq: " + freq;

}

// internal Doubly Linked List to store cache nodes

private class DLL {

Node head;

Node tail;

int len;

public DLL() {

head = new Node(-1, null, -1);

tail = new Node(-1, null, -1);

head.next = tail;

tail.pre = head;

len = 0;

}

public void addToHead(Node node) {

node.next = head.next;

head.next.pre = node;

head.next = node;

node.pre = head;

len++;

}

public void deleteNode(Node node) {

node.pre.next = node.next;

node.next.pre = node.pre;

len--;

}

private int capacity;

private int size;

private TreeMap<Integer, DLL> freq;

private HashMap<Integer, Node> map;

/**

* instantiates LFUCache with fixed capacity

* @param capacity The capacity of the cache. Once the cache reaches capacity,

* new elements will replace old elements in LFU manner

public LFUCache(int capacity) {

this.capacity = capacity;

size = 0;

freq = new TreeMap<>();

map = new HashMap<>();

System.out.println("LFUCache initialised with capacity: " + capacity);

}

/**

* To get the cached value for given key

* @param key The key (int) of the expected value

* @return corresponding value for input key

* @throws NoSuchElementException if key is absent

public T get(int key) {

// Cache hit condition

if (map.containsKey(key)) {

Node node = map.get(key);

System.out.println("Returning value from cache:" + node.toString());

DLL dll = freq.get(node.freq);

dll.deleteNode(node);

if (dll.len == 0)

freq.remove(node.freq);

node.freq += 1;

dll = freq.computeIfAbsent(node.freq, k -> new DLL());

dll.addToHead(node);

return node.value;

}

// Cache miss condition

throw new NoSuchElementException("No element for key: " + key);

}

/**

* To put a value in LFU cache with corresponding key

* @param key The key (int)

* @param value The value to be cached

public void put(int key, T value) {

if (capacity == 0) {

System.out.println("Cache set to 0 capacity. No element will be cached");

return;

}

if (map.containsKey(key)) {

System.out.println("Key " + key + " already present in cache.Value will be replaced");

Node node = map.get(key);

node.value = value;

DLL dll = freq.get(node.freq);

dll.deleteNode(node);

if (dll.len == 0)

freq.remove(node.freq);

node.freq += 1;

dll = freq.computeIfAbsent(node.freq, k -> new DLL());

dll.addToHead(node);

} else {

System.out.println("Adding new key " + key + " to cache");

Node node = new Node(key, value, 1);

map.put(key, node);

if (size < capacity) {

size++;

DLL dll = freq.computeIfAbsent(1, k -> new DLL());

dll.addToHead(node);

} else {

System.out.println("Cache at peak capacity.Old values will be removed in LFU fashion");

Integer lowest = freq.firstKey();

DLL dll = freq.get(lowest);

map.remove(dll.tail.pre.key);

System.out.println("Value removed:" + dll.tail.pre.value.toString());

dll.deleteNode(dll.tail.pre);

if (dll.len == 0 && lowest != 1)

freq.remove(lowest);

DLL freqOne = freq.computeIfAbsent(1, k -> new DLL());

freqOne.addToHead(node);

}

Java/src/main/java/com/caching/LFUCache.java at Development · iDev-git/Java · GitHub

Repository navigation

Expand file tree

Breadcrumbs

LFUCache.java

Latest commit

History

Breadcrumbs

LFUCache.java

File metadata and controls