Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.6 kB
1
Indexable
Never
class node{
    public:
    int key;
    int data;
    node* next;
    node* prev;
    node(int key,int value){
        this->key=key;
        data=value;
        next=NULL;
        prev=NULL;
    }
};


class LRUCache {
public:
    
    node* head= new node(-1,-1);
    node* tail =new node(-1,-1);
    int cap=0;;
    unordered_map<int,node*> cache;  //key,node format
    
    void addafterhead(node* tmp){


    }

    void delnode(node *del){


    }

    void empty cache(){


    }

    LRUCache(int capacity) {
        cap=capacity;
        head->next=tail;
        tail->prev=head;
    }
    
    int get(int key) {
        if(cache.find(key)!=cache.end()){ //present in cache
            node* tmp=cache[key];
            //maintain the linkes between next and prev o cache
            tmp->next->prev=tmp->prev;
            tmp->prev->next=tmp->next;
            int res=tmp->data;
            //linking, even accessing chnages it used status so we need to update the LL
            tmp->next=head->next;
            head->next->prev=tmp;
            tmp->prev=head;
            head->next=tmp;

            return res;
        }
        else return -1;
    }
    
    void put(int key, int value) {
        if(cache.find(key)!=cache.end()){//present in cache , update its value and used status
            node* del=cache[key];
            int delkey=del->key;
            del->next->prev=del->prev;
            del->prev->next=del->next;
            del->next=NULL;
            del->prev=NULL;
            delete del;
            
            cache.erase(delkey);
            node* tmp= new node(key,value);
            cache[key]=tmp;

            tmp->next=head->next;
            head->next->prev=tmp;
            tmp->prev=head;
            head->next=tmp;
        }
        else{ //not present in cache , make new /insert
            if(cache.size()==cap){ // delete least recently used and insert
                node* del=tail->prev;
                int delkey =del->key;
                del->next->prev=del->prev;
                del->prev->next=del->next;
                del->next=NULL;
                del->prev=NULL;
                delete del;
                cache.erase(delkey);
                node* tmp= new node(key,value);
                cache[key]=tmp;

                tmp->next=head->next;
                head->next->prev=tmp;
                tmp->prev=head;
                head->next=tmp;
            }

            else{ //just insert
                node* tmp= new node(key,value);
                cache[key]=tmp;

                tmp->next=head->next;
                head->next->prev=tmp;
                tmp->prev=head;
                head->next=tmp;
            }
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */


 /* class LRUCache {// doesnt take care of recent usage
public:
    unordered_map<int,int> m;
    int cursize,maxsize;
    LRUCache(int capacity) {
        cursize=0;
        maxsize=capacity;
    }
    
    int get(int key) {
        if(m.find(key) !=m.end()) return m[key];
        else return -1;
    }
    
    void put(int key, int value) {
        if(cursize >=maxsize) return;
        if(m.find(key) !=m.end()){ //updtae
            m[key]=value;
            return;
        }
        m.insert(make_pair(key,value));  //insert
        cursize++;
    }
}; */