1+ package com .caching ;
2+
3+ import java .util .HashMap ;
4+ import java .util .NoSuchElementException ;
5+ import java .util .TreeMap ;
6+
7+ /**
8+ * Your LFUCache object can be instantiated and called as such: LFUCache
9+ * lfuCache = new LFUCache(capacity); lfuCache.put(key,value); int param_1 =
10+ * lfuCache.get(key);
11+ */
12+ class LFUCache <T > {
13+ // internal Node to store cache element
14+ private class Node {
15+ int key ;
16+ T value ;
17+ int freq ;
18+ Node next ;
19+ Node pre ;
20+
21+ public Node (int key ,T value ,int freq ) {
22+ this .key =key ;
23+ this .value =value ;
24+ this .freq =freq ;
25+ next =pre =null ;
26+ }
27+
28+ public String toString () {
29+ return " Key: " +key +"Value: " +value +"Freq: " +freq ;
30+ }
31+
32+ }
33+
34+ // internal Doubly Linked List to store cache nodes
35+ private class DLL {
36+ Node head ;
37+ Node tail ;
38+ int len ;
39+
40+ public DLL () {
41+ head =new Node (-1 ,null , -1 );
42+ tail =new Node (-1 ,null , -1 );
43+ head .next =tail ;
44+ tail .pre =head ;
45+ len =0 ;
46+ }
47+
48+ public void addToHead (Node node ) {
49+ node .next =head .next ;
50+ head .next .pre =node ;
51+ head .next =node ;
52+ node .pre =head ;
53+ len ++;
54+ }
55+
56+ public void deleteNode (Node node ) {
57+ node .pre .next =node .next ;
58+ node .next .pre =node .pre ;
59+ len --;
60+ }
61+
62+ }
63+
64+ private int capacity ;
65+ private int size ;
66+ private TreeMap <Integer ,DLL >freq ;
67+ private HashMap <Integer ,Node >map ;
68+
69+ /**
70+ * instantiates LFUCache with fixed capacity
71+ *
72+ * @param capacity The capacity of the cache. Once the cache reaches capacity,
73+ * new elements will replace old elements in LFU manner
74+ */
75+ public LFUCache (int capacity ) {
76+ this .capacity =capacity ;
77+ size =0 ;
78+ freq =new TreeMap <Integer ,DLL >();
79+ map =new HashMap <Integer ,Node >();
80+ System .out .println ("LFUCache initialised with capacity: " +capacity );
81+ }
82+
83+ /**
84+ * To get the cached value for given key
85+ *
86+ * @param key The key (int) of the expected value
87+ * @return corresponding value for input key
88+ * @throws NoSuchElementException if key is absent
89+ */
90+ public T get (int key ) {
91+ // Cache hit condition
92+ if (map .containsKey (key )) {
93+ Node node =map .get (key );
94+ System .out .println ("Returning value from cache:" +node .toString ());
95+ DLL dll =freq .get (node .freq );
96+ dll .deleteNode (node );
97+ if (dll .len ==0 )
98+ freq .remove (node .freq );
99+ node .freq +=1 ;
100+ dll =freq .computeIfAbsent (node .freq ,k ->new DLL ());
101+ dll .addToHead (node );
102+ return node .value ;
103+ }
104+ // Cache miss condition
105+ throw new NoSuchElementException ("No element for key: " +key );
106+ }
107+
108+ /**
109+ * To put a value in LFU cache with corresponding key
110+ *
111+ * @param key The key (int)
112+ * @param value The value to be cached
113+ */
114+ public void put (int key ,T value ) {
115+ if (capacity ==0 ) {
116+ System .out .println ("Cache set to 0 capacity. No element will be cached" );
117+ return ;
118+ }
119+ if (map .containsKey (key )) {
120+ System .out .println ("Key " +key +" already present in cache.Value will be replaced" );
121+ Node node =map .get (key );
122+ node .value =value ;
123+ DLL dll =freq .get (node .freq );
124+ dll .deleteNode (node );
125+ if (dll .len ==0 )
126+ freq .remove (node .freq );
127+ node .freq +=1 ;
128+ dll =freq .computeIfAbsent (node .freq ,k ->new DLL ());
129+ dll .addToHead (node );
130+ }else {
131+ System .out .println ("Adding new key " +key +" to cache" );
132+ Node node =new Node (key ,value ,1 );
133+ map .put (key ,node );
134+
135+ if (size <capacity ) {
136+ size ++;
137+ DLL dll =freq .computeIfAbsent (1 ,k ->new DLL ());
138+ dll .addToHead (node );
139+ }else {
140+ System .out .println ("Cache at peak capacity.Old values will be removed in LFU fashion" );
141+ Integer lowest =freq .firstKey ();
142+ DLL dll =freq .get (lowest );
143+ map .remove (dll .tail .pre .key );
144+ System .out .println ("Value removed:" +dll .tail .pre .value .toString ());
145+ dll .deleteNode (dll .tail .pre );
146+ if (dll .len ==0 &&lowest !=1 )
147+ freq .remove (lowest );
148+ DLL freq_one =freq .computeIfAbsent (1 ,k ->new DLL ());
149+ freq_one .addToHead (node );
150+ }
151+ }
152+
153+ }
154+
155+ }