Abstract Classes - Polymorphism

  • + 0 comments

    Here is an easy solution, correctly done, with head, tail, etc. and also deleting the pointers, not simply removing them from the map 'mp':

    class LRUCache:Cache {
    public:
    LRUCache(int capacity){
          this->cp = capacity;
    }
    void insert_node(int k, Node* node){
       //Set head
       this->head = node;
       if (mp.empty()) this->tail = node; //Set tail
       else node->next = mp.begin()->second; //Set next node
       
       //Insert new node
       mp.insert(mp.begin(), std::pair<int, Node*>(k, node));
       if (node->next!=nullptr) node->next->prev = node;
    }
    void set(int k, int v){
       Node* node = new Node(k,v);
       std::map<int, Node*>::iterator duplicate = this->mp.find(k);
    
       //If key exists
       if(duplicate!=this->mp.end()){
    
          //Remove old key
          if (node->next!=nullptr) node->next->prev = node->prev;
          if (node->prev!=nullptr){
             node->prev->next = node->next;
             if (node->next==nullptr) this->tail = node->prev;
          }
          delete(mp.at(k));
          mp.erase(k);
          
          //Insert at 0
          insert_node(k, node);
       }
       else {
          //If size is at max capacity
          if(this->mp.size()==this->cp){
    
             //Remove tail
             if(this->tail->prev!=nullptr) this->tail->prev->next=nullptr;
             delete(this->tail);
             mp.erase(this->tail->key);
          }
    
          //Insert at 0
          insert_node(k, node);
       }
    }
    int get(int k) {
       return (this->mp.find(k)!=this->mp.end())? this->mp.at(k)->value : -1;
    }
    };