oopsDesign/LRUCache.cpp at master · hariomkushwaha/oopsDesign · 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
#include <bits/stdc++.h>

using namespace std;

 class Node
 {
 public:
 	int key;
 	int val;
 	Node* next;
 	Node* pre;
 	Node(int key,int val){
 		this->key=key;
 		this->val=val;
 	}
 };

 class LRUCache
 {
 private:

 	unordered_map<int,Node*>ump;

 	int cap;
 	Node *head=new Node(-1,-1);
 	Node *tail=new Node(-1,-1);

 public:
 	LRUCache(int cap){
 		this->cap=cap;
 		head->next=tail;
 		tail->pre =head;
 	}


 	 	void addNode(Node* delnod){
 		Node * temp=head->next;
 		delnod->next=temp;
 		delnod->pre=head;
 		head->next=delnod;
 		temp->pre=delnod;
 	}


 	void deleteNode(Node* delnod){
 		Node *delnext=delnod->next;
 		Node *delpre=delnod->pre;

 		delnext->pre=delpre;
 		delpre->next=delnext;
 	}

 	void put(int key,int val){
 		if(ump.find(key)!=ump.end()){
 			Node *delnod=ump[key];
 			ump.erase(key);
 			deleteNode(delnod);
 		}

 		if(cap==mp.size()){
 			ump.erase(tail->pre->val);
 			deleteNode(tail->pre);
 		}

 		addNode(new Node(key,val));
 		ump[key]=head->next;
 	}

 	int get(int key){
 		if(ump.find(key)!=ump.end()){
 			Node *delnod=ump[key];
 			int ans= delnod->val;
 			ump.erase(key);
 			deleteNode(delnod);
 			addNode(delnod);
 			ump[key]=head->next;
 			return ans;
 		}
 		return -1;
 	}


 };


int main(){

	LRUCache * obj= new LRUCache(3);

	obj->put(3,34);
	obj->put(2,35);
	obj->put(4,1);
	cout<<obj->get(3)<<endl;
	cout<<obj->get(2)<<endl;
	cout<<obj->get(4)<<endl;

	obj->put(3,4);
	obj->put(2,5);
	obj->put(4,10);
	cout<<obj->get(4)<<endl;
	cout<<obj->get(3)<<endl;
	cout<<obj->get(2)<<endl;


	return 0;
}