[SDP/S05] Solved exercises from seminar 5

2 files changed, 456 insertions, 0 deletions

diff --git a/Year 2/Structures and data algorithms/05-Seminar-02.10.2022/LinkedList.hpp b/Year 2/Structures and data algorithms/05-Seminar-02.10.2022/LinkedList.hpp
new file mode 100644
index 0000000..194f087
--- /dev/null
+++ b/Year 2/Structures and data algorithms/05-Seminar-02.10.2022/LinkedList.hpp
@@ -0,0 +1,332 @@
+/* Author  : StoychoX
+ * Source  : https://github.com/stoychoX/Data-structures-and-algorithms/blob/main/Seminar05/LinkedList.hpp
+ * License : <none>
+ * Date    : 22.11.2022
+ */
+
+#ifndef _SINGLY_LINKED_LIST_IMPL
+#define _SINGLY_LINKED_LIST_IMPL
+
+#include<stdexcept>
+
+template<class T>
+class LinkedList {
+private:
+    struct LinkedListNode {
+        T data;
+        LinkedListNode* next;
+
+        LinkedListNode(const T& elem, LinkedListNode* n = nullptr) : data{ elem }, next { n } {} 
+    };
+
+    void free();
+    void copy(const LinkedList<T>&);
+public:
+    class Iterator {
+        private:
+            // Текущия възел в обхождането
+            LinkedListNode* currentNode;
+
+            Iterator(LinkedListNode* arg) : currentNode { arg } {}
+        public:
+        
+        Iterator& operator++() {
+            if(currentNode == nullptr)
+                return *this;
+            currentNode = currentNode->next;
+            return *this;
+        }
+
+        Iterator operator++(int) {
+            Iterator temp = *this;
+            ++(*this);
+            return temp;
+        }
+
+        T& operator*() {
+            return currentNode->data;
+        }
+
+        bool operator==(const Iterator& other) const {
+            return other.currentNode == currentNode;
+        }
+
+        bool operator!=(const Iterator& other) const {
+            return !(*this == other);
+        }
+
+        friend class LinkedList;
+    };
+
+    class ConstIterator {
+        private:
+            const LinkedListNode* currentNode;    // Това вече е указател към константна памет!
+
+            ConstIterator(LinkedListNode* arg) : currentNode { arg } {}  
+        public:
+
+        ConstIterator& operator++() {
+            if(currentNode == nullptr)
+                return *this;
+            
+            currentNode = currentNode->next;
+            return *this;
+        }
+
+        ConstIterator operator++(int) {
+            ConstIterator temp = *this;
+            ++(*this);
+            return temp;
+        }
+
+        const T& operator*() const {
+            return currentNode->data;
+        }
+
+        bool operator==(const ConstIterator& other) const {
+            return other.currentNode == currentNode;
+        }
+
+        bool operator!=(const ConstIterator& other) const {
+            return !(*this == other);
+        }
+
+        friend class LinkedList;
+    };
+
+    LinkedList();
+
+    LinkedList(const LinkedList<T>&);
+    LinkedList(LinkedList<T>&&);
+
+    LinkedList& operator=(const LinkedList<T>&);
+    LinkedList& operator=(LinkedList<T>&&);
+
+    Iterator begin() {
+        return Iterator(head);
+    }
+
+    Iterator end() {
+        return Iterator(nullptr);
+    }
+
+    ConstIterator begin() const {
+        return Iterator(head);
+    }
+
+    ConstIterator end() const {
+        return Iterator(nullptr);
+    }
+
+    ConstIterator cbegin() const {
+        return ConstIterator(head);
+    }
+
+    ConstIterator cend() const {
+        return ConstIterator(nullptr);
+    }
+
+    void pushBack(const T&);
+    void popBack();
+
+    void pushFront(const T&);
+    void popFront();
+
+    const T& front() const;
+    const T& back() const;
+
+    T& front();
+    T& back();
+
+    bool empty() const;
+    size_t size() const;
+
+    ~LinkedList();
+
+private:
+    LinkedListNode* head;
+    LinkedListNode* tail;
+    size_t sizeOfList;
+};
+
+template<class T>
+LinkedList<T>::LinkedList() : head {nullptr}, tail {nullptr}, sizeOfList { 0 } {}
+
+template<class T>
+void LinkedList<T>::free() {
+    while(head) {
+        LinkedListNode* toDelete = head;
+        head = head->next;
+        delete toDelete;
+    }
+    sizeOfList = 0;
+}
+
+template<class T>
+void LinkedList<T>::copy(const LinkedList<T>& other) {
+    LinkedListNode* iter = other.head;
+
+    while(iter) {
+        pushBack(iter->data);
+        iter = iter->next;
+    }
+
+    sizeOfList = other.sizeOfList;
+}
+
+template<class T>
+LinkedList<T>::LinkedList(const LinkedList<T>& other) : head {nullptr}, tail{ nullptr } {
+    copy(other);
+}
+
+template<class T>
+LinkedList<T>::LinkedList(LinkedList<T>&& other) {
+    head = other.head;
+    tail = other.tail;
+    sizeOfList = other.sizeOfList;
+
+    other.head = other.tail = nullptr;
+    other.sizeOfList = 0;
+}
+
+template<class T>
+LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& other) {
+    if(this != & other) {
+        free();
+        copy(other);
+    }
+    return *this;
+}
+
+template<class T>
+LinkedList<T>& LinkedList<T>::operator=(LinkedList<T>&& other) {
+    if(this != &other) {
+        free();
+        
+        head = other.head;
+        tail = other.tail;
+        sizeOfList = other.sizeOfList;
+
+        other.head = other.tail = nullptr;
+        other.sizeOfList = 0;
+    }
+    return *this;
+}
+
+template<class T>
+void LinkedList<T>::pushBack(const T& elem) {
+    LinkedListNode* toInsert = new LinkedListNode(elem);
+    ++sizeOfList; 
+
+    if(empty()) {
+        head = tail = toInsert;
+    }
+    else {
+        tail->next = toInsert;
+        tail = toInsert;
+    }
+}
+
+template<class T>
+void LinkedList<T>::popBack() {
+    if(empty()) {
+        throw std::runtime_error("Tried to pop back on empty list!");
+    }
+    --sizeOfList;
+
+    if(head == tail) {
+        delete tail;
+        head = tail = nullptr;
+    }
+    else {
+        LinkedListNode* newTail = head;
+
+        // O(n) за n дължината на свързания списък
+        while (newTail->next != tail) { 
+            newTail = newTail->next;
+        }
+
+        delete tail;
+        tail = newTail;
+        tail->next = nullptr;
+    }
+}
+
+template<class T>
+void LinkedList<T>::pushFront(const T& elem) {
+    LinkedListNode* toInsert = new LinkedListNode(elem, head);
+    
+    if(empty())
+        tail = toInsert;
+    
+    head = toInsert;
+
+    ++sizeOfList;
+}
+
+template<class T>
+void LinkedList<T>::popFront() {
+    if(empty()) 
+        throw std::runtime_error("Cannot pop front from empty list!");
+    
+    if(head == tail) {
+        delete tail;
+        head = tail = nullptr;
+    }
+    else {
+        LinkedListNode* toDelete = head;
+        head = head->next;
+        delete toDelete;
+    }
+
+    --sizeOfList;
+}
+
+template<class T>
+bool LinkedList<T>::empty() const {
+    return head == nullptr;
+}
+
+template<class T>
+size_t LinkedList<T>::size() const {
+    return sizeOfList;
+}
+
+template<class T>
+const T& LinkedList<T>::front() const {
+    if(empty()) 
+        throw std::runtime_error("Empty list!");
+
+    return head->data;
+}
+
+template<class T>
+T& LinkedList<T>::front() {
+    if(empty())
+        throw std::runtime_error("Empty list!");
+    
+    return head->data;
+}
+
+template<class T>
+const T& LinkedList<T>::back() const {
+    if(empty()) 
+        throw std::runtime_error("Empty list!");
+
+    return tail->data;
+}
+
+template<class T>
+T& LinkedList<T>::back() {
+    if(empty()) 
+        throw std::runtime_error("Empty list!");
+
+    return tail->data;
+}
+
+template<class T>
+LinkedList<T>::~LinkedList() {
+    free();
+}
+
+#endif
diff --git a/Year 2/Structures and data algorithms/05-Seminar-02.10.2022/exercises.cpp b/Year 2/Structures and data algorithms/05-Seminar-02.10.2022/exercises.cpp
new file mode 100644
index 0000000..0317cc3
--- /dev/null
+++ b/Year 2/Structures and data algorithms/05-Seminar-02.10.2022/exercises.cpp
@@ -0,0 +1,124 @@
+#include "LinkedList.hpp"
+#include <iostream>
+#include <stack>
+#include <queue>
+
+// Ex1
+
+template <class T>
+void shuffle(LinkedList<T>& l) {
+	auto fast = l.begin(), slow = l.begin(), end = l.end();
+	while (fast != end) {
+		++fast;
+		if (fast != end) {
+			++fast;
+			++slow;
+		}
+	}
+	int pops = 0;
+	while (++slow != end) {
+		l.pushFront(*slow);
+		pops++;
+	}
+	while (pops-- > 0)
+		l.popBack();
+}
+
+template <class T>
+void print(LinkedList<T>& l) {
+	for (const T& elem : l) {
+		std::cout << elem << " ";
+	}
+	std::cout << std::endl;
+}
+
+void ex1() {
+	LinkedList<int> l;
+	l.pushBack(1);
+	l.pushBack(2);
+	l.pushBack(3);
+	l.pushBack(4);
+	l.pushBack(5);
+
+	print(l);
+	shuffle(l);
+	print(l);
+}
+
+// Ex2
+
+void print(LinkedList<std::stack<int>*>& l) {
+	for (const std::stack<int>* elem : l) {
+		if (!elem->empty())
+			std::cout << elem->top() << " ";
+	}
+	std::cout << std::endl;
+}
+
+#define min(a,b) (a<b) ? a : b
+
+void equalize(LinkedList<std::stack<int>*>& l) {
+	std::queue<size_t> valueSize;
+	std::queue<int> valueHolder;
+	for (std::stack<int>* elem : l) {
+		valueSize.push(elem->size());
+		while (!elem->empty()) {
+			valueHolder.push(elem->top());
+			elem->pop();
+		}
+	}
+	std::queue<int> leftovers;
+	size_t amountPer = valueHolder.size() / l.size();
+	for (std::stack<int>* elem : l) {
+		size_t cpyOriginals = min(amountPer, valueSize.front());
+		for (size_t i = 0; i < cpyOriginals; i++) {
+			elem->push(valueHolder.front());
+			valueHolder.pop();
+		}
+		for (int i = valueSize.front() - amountPer; i > 0; i--) {
+			leftovers.push(valueHolder.front());
+			valueHolder.pop();
+		}
+		valueSize.pop();
+	}
+	for (std::stack<int>* elem : l) {
+		for (size_t i = amountPer - elem->size(); i > 0; i--) {
+			elem->push(leftovers.front());
+			leftovers.pop();
+		}
+	}
+}
+
+void ex2() {
+	LinkedList<std::stack<int>*> l;
+	l.pushBack(new std::stack<int>());
+	l.back()->push(1);
+	l.back()->push(2);
+	l.back()->push(3);
+	l.back()->push(4);
+	l.back()->push(5);
+	l.pushBack(new std::stack<int>());
+	l.back()->push(6);
+	l.back()->push(7);
+	l.pushBack(new std::stack<int>());
+	l.back()->push(8);
+	l.back()->push(9);
+	l.back()->push(10);
+	l.back()->push(11);
+	l.pushBack(new std::stack<int>());
+	l.back()->push(12);
+
+	print(l);
+	equalize(l);
+	print(l);
+}
+
+// Ex 3
+
+// LinkedListNode<int>* partition(LinkedListNode<int>* head, int x) {
+//
+// }
+
+int main() {
+	ex2();
+}