Scribbling

[C++] Abstract Class, Polymorphism 본문

Computer Science/C++

[C++] Abstract Class, Polymorphism

focalpoint 2024. 9. 28. 09:48

https://www.hackerrank.com/challenges/abstract-classes-polymorphism/problem?isFullScreen=true

 

Abstract Classes - Polymorphism | HackerRank

Given an abstract class Cache, write a class LRUCache which extends the class Cache and implement an LRU cache.

www.hackerrank.com

 

#include <iostream>
#include <vector>
#include <map>
#include <string>
#include <algorithm>
#include <set>
#include <cassert>
using namespace std;

struct Node{
   Node* next;
   Node* prev;
   int value;
   int key;
   Node(Node* p, Node* n, int k, int val):prev(p),next(n),key(k),value(val){};
   Node(int k, int val):prev(NULL),next(NULL),key(k),value(val){};
};

class Cache{
   
   protected: 
   map<int,Node*> mp; //map the key to the node in the linked list
   int cp;  //capacity
   Node* tail; // double linked list tail pointer
   Node* head; // double linked list head pointer
   virtual void set(int, int) = 0; //set function
   virtual int get(int) = 0; //get function

};

class LinkedList {
private:
    int cnt;
    Node* head;
    Node* tail;
    
public:
    LinkedList() : cnt(0), head(nullptr), tail(nullptr) {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head->next = tail;
        tail->prev = head;
    }
    
    void insertNodeToTail(Node* node) {
        Node* prev = tail->prev;
        prev->next = node;
        node->prev = prev;
        node->next = tail;
        tail->prev = node;
        cnt++;
    }
    
    int popHead() {
        Node* node = head->next;
        Node* next = node->next;
        next->prev = head;
        head->next = next;
        int key = node->key;
        delete node;
        cnt--;
        return key;
    }
    
    void removeNode(Node* node) {
        Node* prev = node->prev;
        Node* next = node->next;
        prev->next = next;
        next->prev = prev;
        delete node;
        cnt--;
    }
    
    int getCnt() {
        return cnt;
    }
    
    Node* getHead() {
        return head;
    }
    
    Node* getTail() {
        return tail;
    }
    
    ~LinkedList() {
        if (head != nullptr) delete head;
        if (tail != nullptr) delete tail;
    }
};

class LRUCache : public Cache {
protected:
    int cnt;
    LinkedList ll;
public:
    LRUCache(int capacity): Cache(), cnt(0) {
        this->cp = capacity;
        tail = ll.getTail();
        head = ll.getHead();
    }
    
    void set(int key, int val) {
        if (mp.find(key) != mp.end()) {
            Node* node = mp[key];
            mp.erase(key);
            Node* newNode = new Node(key, val);
            mp[key] = newNode;
            ll.removeNode(node);
            ll.insertNodeToTail(newNode);
        } 
        else {
            // at max capacity
            if (cnt == cp) {
                int deletedKey = ll.popHead();
                mp.erase(deletedKey);
                Node* node = new Node(key, val);
                mp[key] = node;
                ll.insertNodeToTail(node);
            }
            else {
                Node* node = new Node(key, val);
                mp[key] = node;
                ll.insertNodeToTail(node);
                cnt++;
            }
        }
    }
    
    int get(int key) {
        // cache miss
        if (mp.find(key) == mp.end()) {
            return -1;
        } 
        // cache hit
        else {
            Node* node = mp[key];
            mp.erase(key);
            int val = node->value;
            Node* newNode = new Node(key, val);
            mp[key] = newNode;
            ll.removeNode(node);
            ll.insertNodeToTail(newNode);
            return val;
        }
    }
};

int main() {
   int n, capacity,i;
   cin >> n >> capacity;
   LRUCache l(capacity);
   for(i=0;i<n;i++) {
      string command;
      cin >> command;
      if(command == "get") {
         int key;
         cin >> key;
         cout << l.get(key) << endl;
      } 
      else if(command == "set") {
         int key, value;
         cin >> key >> value;
         l.set(key,value);
      }
   }
   return 0;
}

'Computer Science > C++' 카테고리의 다른 글

[C++] Object Oriented Programming  (0) 2024.10.01
[C++] Strings  (0) 2024.09.30
[C++] Virtual Functions  (0) 2024.09.28
[C++] Regular Expression Matching  (0) 2024.09.26
[C++] Priority Queue with custom data type  (0) 2024.02.22