From 3c72a02284dad4ddd9df1ff6910ed1a0a4550a30 Mon Sep 17 00:00:00 2001
From: Stoycho Kyosev <stoycho.kk@gmail.com>
Date: Sun, 22 Dec 2024 13:19:05 -0500
Subject: Add seminar 10 and 11

---
 Seminar10/src/lru-cache.cpp | 45 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)
 create mode 100644 Seminar10/src/lru-cache.cpp

(limited to 'Seminar10/src/lru-cache.cpp')

diff --git a/Seminar10/src/lru-cache.cpp b/Seminar10/src/lru-cache.cpp
new file mode 100644
index 0000000..d199eb1
--- /dev/null
+++ b/Seminar10/src/lru-cache.cpp
@@ -0,0 +1,45 @@
+#include <list>
+#include <unordered_map>
+#include <stdexcept>
+
+class LRUCache
+{
+    size_t capacity;
+    std::list<std::pair<int, int>> data;
+    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> dataMap;
+
+public:
+    LRUCache(size_t capacity) : capacity(capacity) { }
+
+    int get(int key)
+    {
+        if (dataMap.find(key) == dataMap.end())
+        {
+            throw std::runtime_error("Data not in cache");
+        }
+
+        auto it = dataMap[key];
+
+        // Transfers elements from one list to another. 
+        // No elements are copied or moved, only the internal pointers of the list nodes are re-pointed.
+        data.splice(data.begin(), data, it);
+        return it->second;
+    }
+
+    void put(int key, int value)
+    {
+        if (dataMap.find(key) != dataMap.end())
+        {
+            auto it = dataMap[key];
+            data.erase(it);
+        }
+
+        data.push_front({ key, value });
+        dataMap[key] = data.begin();
+        if (data.size() > capacity)
+        {
+            dataMap.erase(data.back().first);
+            data.pop_back();
+        }
+    }
+};
\ No newline at end of file
-- 
cgit v1.3.1-23-gd82d