From 593e009ac517b305dd6af7656c635f900715ce13 Mon Sep 17 00:00:00 2001 From: Syndamia Date: Sun, 25 Dec 2022 12:40:28 +0200 Subject: [SDP/P05-06] Fixed folder dates --- .../05-Seminar-02.10.2022/LinkedList.hpp | 332 --------------------- .../05-Seminar-02.10.2022/exercises.cpp | 124 -------- .../05-Seminar-02.11.2022/LinkedList.hpp | 332 +++++++++++++++++++++ .../05-Seminar-02.11.2022/exercises.cpp | 124 ++++++++ .../06-Seminar-09.10.2022/DoublyLinkedList.hpp | 294 ------------------ .../06-Seminar-09.10.2022/exercises.cpp | 131 -------- .../06-Seminar-09.11.2022/DoublyLinkedList.hpp | 294 ++++++++++++++++++ .../06-Seminar-09.11.2022/exercises.cpp | 131 ++++++++ 8 files changed, 881 insertions(+), 881 deletions(-) delete mode 100644 Year 2/Structures and data algorithms/05-Seminar-02.10.2022/LinkedList.hpp delete mode 100644 Year 2/Structures and data algorithms/05-Seminar-02.10.2022/exercises.cpp create mode 100644 Year 2/Structures and data algorithms/05-Seminar-02.11.2022/LinkedList.hpp create mode 100644 Year 2/Structures and data algorithms/05-Seminar-02.11.2022/exercises.cpp delete mode 100644 Year 2/Structures and data algorithms/06-Seminar-09.10.2022/DoublyLinkedList.hpp delete mode 100644 Year 2/Structures and data algorithms/06-Seminar-09.10.2022/exercises.cpp create mode 100644 Year 2/Structures and data algorithms/06-Seminar-09.11.2022/DoublyLinkedList.hpp create mode 100644 Year 2/Structures and data algorithms/06-Seminar-09.11.2022/exercises.cpp 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 deleted file mode 100644 index 194f087..0000000 --- a/Year 2/Structures and data algorithms/05-Seminar-02.10.2022/LinkedList.hpp +++ /dev/null @@ -1,332 +0,0 @@ -/* Author : StoychoX - * Source : https://github.com/stoychoX/Data-structures-and-algorithms/blob/main/Seminar05/LinkedList.hpp - * License : - * Date : 22.11.2022 - */ - -#ifndef _SINGLY_LINKED_LIST_IMPL -#define _SINGLY_LINKED_LIST_IMPL - -#include - -template -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&); -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&); - LinkedList(LinkedList&&); - - LinkedList& operator=(const LinkedList&); - LinkedList& operator=(LinkedList&&); - - 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 -LinkedList::LinkedList() : head {nullptr}, tail {nullptr}, sizeOfList { 0 } {} - -template -void LinkedList::free() { - while(head) { - LinkedListNode* toDelete = head; - head = head->next; - delete toDelete; - } - sizeOfList = 0; -} - -template -void LinkedList::copy(const LinkedList& other) { - LinkedListNode* iter = other.head; - - while(iter) { - pushBack(iter->data); - iter = iter->next; - } - - sizeOfList = other.sizeOfList; -} - -template -LinkedList::LinkedList(const LinkedList& other) : head {nullptr}, tail{ nullptr } { - copy(other); -} - -template -LinkedList::LinkedList(LinkedList&& other) { - head = other.head; - tail = other.tail; - sizeOfList = other.sizeOfList; - - other.head = other.tail = nullptr; - other.sizeOfList = 0; -} - -template -LinkedList& LinkedList::operator=(const LinkedList& other) { - if(this != & other) { - free(); - copy(other); - } - return *this; -} - -template -LinkedList& LinkedList::operator=(LinkedList&& 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 -void LinkedList::pushBack(const T& elem) { - LinkedListNode* toInsert = new LinkedListNode(elem); - ++sizeOfList; - - if(empty()) { - head = tail = toInsert; - } - else { - tail->next = toInsert; - tail = toInsert; - } -} - -template -void LinkedList::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 -void LinkedList::pushFront(const T& elem) { - LinkedListNode* toInsert = new LinkedListNode(elem, head); - - if(empty()) - tail = toInsert; - - head = toInsert; - - ++sizeOfList; -} - -template -void LinkedList::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 -bool LinkedList::empty() const { - return head == nullptr; -} - -template -size_t LinkedList::size() const { - return sizeOfList; -} - -template -const T& LinkedList::front() const { - if(empty()) - throw std::runtime_error("Empty list!"); - - return head->data; -} - -template -T& LinkedList::front() { - if(empty()) - throw std::runtime_error("Empty list!"); - - return head->data; -} - -template -const T& LinkedList::back() const { - if(empty()) - throw std::runtime_error("Empty list!"); - - return tail->data; -} - -template -T& LinkedList::back() { - if(empty()) - throw std::runtime_error("Empty list!"); - - return tail->data; -} - -template -LinkedList::~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 deleted file mode 100644 index 0317cc3..0000000 --- a/Year 2/Structures and data algorithms/05-Seminar-02.10.2022/exercises.cpp +++ /dev/null @@ -1,124 +0,0 @@ -#include "LinkedList.hpp" -#include -#include -#include - -// Ex1 - -template -void shuffle(LinkedList& 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 -void print(LinkedList& l) { - for (const T& elem : l) { - std::cout << elem << " "; - } - std::cout << std::endl; -} - -void ex1() { - LinkedList 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*>& l) { - for (const std::stack* elem : l) { - if (!elem->empty()) - std::cout << elem->top() << " "; - } - std::cout << std::endl; -} - -#define min(a,b) (a*>& l) { - std::queue valueSize; - std::queue valueHolder; - for (std::stack* elem : l) { - valueSize.push(elem->size()); - while (!elem->empty()) { - valueHolder.push(elem->top()); - elem->pop(); - } - } - std::queue leftovers; - size_t amountPer = valueHolder.size() / l.size(); - for (std::stack* 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* elem : l) { - for (size_t i = amountPer - elem->size(); i > 0; i--) { - elem->push(leftovers.front()); - leftovers.pop(); - } - } -} - -void ex2() { - LinkedList*> l; - l.pushBack(new std::stack()); - 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()); - l.back()->push(6); - l.back()->push(7); - l.pushBack(new std::stack()); - l.back()->push(8); - l.back()->push(9); - l.back()->push(10); - l.back()->push(11); - l.pushBack(new std::stack()); - l.back()->push(12); - - print(l); - equalize(l); - print(l); -} - -// Ex 3 - -// LinkedListNode* partition(LinkedListNode* head, int x) { -// -// } - -int main() { - ex2(); -} diff --git a/Year 2/Structures and data algorithms/05-Seminar-02.11.2022/LinkedList.hpp b/Year 2/Structures and data algorithms/05-Seminar-02.11.2022/LinkedList.hpp new file mode 100644 index 0000000..194f087 --- /dev/null +++ b/Year 2/Structures and data algorithms/05-Seminar-02.11.2022/LinkedList.hpp @@ -0,0 +1,332 @@ +/* Author : StoychoX + * Source : https://github.com/stoychoX/Data-structures-and-algorithms/blob/main/Seminar05/LinkedList.hpp + * License : + * Date : 22.11.2022 + */ + +#ifndef _SINGLY_LINKED_LIST_IMPL +#define _SINGLY_LINKED_LIST_IMPL + +#include + +template +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&); +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&); + LinkedList(LinkedList&&); + + LinkedList& operator=(const LinkedList&); + LinkedList& operator=(LinkedList&&); + + 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 +LinkedList::LinkedList() : head {nullptr}, tail {nullptr}, sizeOfList { 0 } {} + +template +void LinkedList::free() { + while(head) { + LinkedListNode* toDelete = head; + head = head->next; + delete toDelete; + } + sizeOfList = 0; +} + +template +void LinkedList::copy(const LinkedList& other) { + LinkedListNode* iter = other.head; + + while(iter) { + pushBack(iter->data); + iter = iter->next; + } + + sizeOfList = other.sizeOfList; +} + +template +LinkedList::LinkedList(const LinkedList& other) : head {nullptr}, tail{ nullptr } { + copy(other); +} + +template +LinkedList::LinkedList(LinkedList&& other) { + head = other.head; + tail = other.tail; + sizeOfList = other.sizeOfList; + + other.head = other.tail = nullptr; + other.sizeOfList = 0; +} + +template +LinkedList& LinkedList::operator=(const LinkedList& other) { + if(this != & other) { + free(); + copy(other); + } + return *this; +} + +template +LinkedList& LinkedList::operator=(LinkedList&& 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 +void LinkedList::pushBack(const T& elem) { + LinkedListNode* toInsert = new LinkedListNode(elem); + ++sizeOfList; + + if(empty()) { + head = tail = toInsert; + } + else { + tail->next = toInsert; + tail = toInsert; + } +} + +template +void LinkedList::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 +void LinkedList::pushFront(const T& elem) { + LinkedListNode* toInsert = new LinkedListNode(elem, head); + + if(empty()) + tail = toInsert; + + head = toInsert; + + ++sizeOfList; +} + +template +void LinkedList::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 +bool LinkedList::empty() const { + return head == nullptr; +} + +template +size_t LinkedList::size() const { + return sizeOfList; +} + +template +const T& LinkedList::front() const { + if(empty()) + throw std::runtime_error("Empty list!"); + + return head->data; +} + +template +T& LinkedList::front() { + if(empty()) + throw std::runtime_error("Empty list!"); + + return head->data; +} + +template +const T& LinkedList::back() const { + if(empty()) + throw std::runtime_error("Empty list!"); + + return tail->data; +} + +template +T& LinkedList::back() { + if(empty()) + throw std::runtime_error("Empty list!"); + + return tail->data; +} + +template +LinkedList::~LinkedList() { + free(); +} + +#endif diff --git a/Year 2/Structures and data algorithms/05-Seminar-02.11.2022/exercises.cpp b/Year 2/Structures and data algorithms/05-Seminar-02.11.2022/exercises.cpp new file mode 100644 index 0000000..0317cc3 --- /dev/null +++ b/Year 2/Structures and data algorithms/05-Seminar-02.11.2022/exercises.cpp @@ -0,0 +1,124 @@ +#include "LinkedList.hpp" +#include +#include +#include + +// Ex1 + +template +void shuffle(LinkedList& 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 +void print(LinkedList& l) { + for (const T& elem : l) { + std::cout << elem << " "; + } + std::cout << std::endl; +} + +void ex1() { + LinkedList 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*>& l) { + for (const std::stack* elem : l) { + if (!elem->empty()) + std::cout << elem->top() << " "; + } + std::cout << std::endl; +} + +#define min(a,b) (a*>& l) { + std::queue valueSize; + std::queue valueHolder; + for (std::stack* elem : l) { + valueSize.push(elem->size()); + while (!elem->empty()) { + valueHolder.push(elem->top()); + elem->pop(); + } + } + std::queue leftovers; + size_t amountPer = valueHolder.size() / l.size(); + for (std::stack* 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* elem : l) { + for (size_t i = amountPer - elem->size(); i > 0; i--) { + elem->push(leftovers.front()); + leftovers.pop(); + } + } +} + +void ex2() { + LinkedList*> l; + l.pushBack(new std::stack()); + 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()); + l.back()->push(6); + l.back()->push(7); + l.pushBack(new std::stack()); + l.back()->push(8); + l.back()->push(9); + l.back()->push(10); + l.back()->push(11); + l.pushBack(new std::stack()); + l.back()->push(12); + + print(l); + equalize(l); + print(l); +} + +// Ex 3 + +// LinkedListNode* partition(LinkedListNode* head, int x) { +// +// } + +int main() { + ex2(); +} diff --git a/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/DoublyLinkedList.hpp b/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/DoublyLinkedList.hpp deleted file mode 100644 index f1bb01e..0000000 --- a/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/DoublyLinkedList.hpp +++ /dev/null @@ -1,294 +0,0 @@ -#ifndef DOUBLY_LINKED_LIST_IMPL_ -#define DOUBLY_LINKED_LIST_IMPL_ - -#include - -template -class DoublyLinkedList { -private: - struct DLListNode { - T data; - DLListNode* next; - DLListNode* prev; - - DLListNode(const T& d, DLListNode* n = nullptr, DLListNode* p = nullptr) : - data {d}, - next {n}, - prev {p} {} - }; - - using Node = DLListNode; - - Node* head; - Node* tail; - - void copy(const DoublyLinkedList& other); - void free(); - - class Iterator { - private: - Node* current; - Iterator(Node* c = nullptr) : current { c } {} - - public: - Iterator& operator++() { - if(current == nullptr) - return *this; - current = current->next; - return *this; - } - - Iterator operator++(int) { - if(current == nullptr) - return *this; - - Iterator tmp = *this; - current = current->next; - return tmp; - } - - Iterator& operator--() { - if(current == nullptr) - return *this; - - current = current->prev; - return *this; - } - - Iterator operator--(int) { - if(current == nullptr) - return *this; - - Iterator tmp = *this; - current = current->prev; - return tmp; - } - - const T& operator*() { - if(current == nullptr) - throw std::exception(); - - return current->data; - } - - bool operator==(const Iterator& other) const { - return current == other.current; - } - - bool operator!=(const Iterator& other) const { - return !(*this == other); - } - - friend class DoublyLinkedList; - }; - -public: - DoublyLinkedList(); - - DoublyLinkedList(const DoublyLinkedList&); - DoublyLinkedList& operator=(const DoublyLinkedList&); - - DoublyLinkedList(DoublyLinkedList&&); - DoublyLinkedList& operator=(DoublyLinkedList&&); - - void pushBack(const T&); - void popBack(); - - void pushFront(const T&); - void popFront(); - - bool empty() const; - - const T& back() const; - const T& front() const; - - Iterator begin(); - Iterator end(); - - void insert(Iterator at, const T& elem); - - ~DoublyLinkedList(); -}; - -template -DoublyLinkedList::DoublyLinkedList() : head { nullptr }, tail { nullptr } {} - -template -DoublyLinkedList::DoublyLinkedList(const DoublyLinkedList& other) : head {nullptr}, tail {nullptr} { - copy(other); -} - -template -DoublyLinkedList& DoublyLinkedList::operator=(const DoublyLinkedList& other) { - if(this != &other) { - free(); - copy(other); - } - return *this; -} - -template -DoublyLinkedList::DoublyLinkedList(DoublyLinkedList&& other) { - head = other.head; - tail = other.tail; - - other.head = other.tail = nullptr; -} - -template -DoublyLinkedList& DoublyLinkedList::operator=(DoublyLinkedList&& other) { - if(this != &other) { - free(); - - head = other.head; - tail = other.tail; - - other.head = other.tail = nullptr; - } - return *this; -} - -template -void DoublyLinkedList::copy(const DoublyLinkedList& other) { - Node* iter = other.head; - - while(iter) { - pushBack(iter->data); - iter = iter->next; - } -} - -template -void DoublyLinkedList::free() { - while(head) { - Node* toDelete = head; - head = head->next; - delete toDelete; - } -} - -template -bool DoublyLinkedList::empty() const { - return head == nullptr; -} - -template -void DoublyLinkedList::pushBack(const T& elem) { - Node* toInsert = new Node(elem); - - if(empty()) { - head = tail = toInsert; - } - else { - toInsert->prev = tail; - tail->next = toInsert; - tail = toInsert; - } -} - -template -void DoublyLinkedList::pushFront(const T& elem) { - Node* toInsert = new Node(elem); - - if(empty()) { - head = tail = toInsert; - } - else { - toInsert->next = head; - head->prev = toInsert; - head = toInsert; - } -} - -template -void DoublyLinkedList::popBack() { - if(empty()) - throw std::exception(); - - if(tail == head) { - delete head; - tail = head = nullptr; - return; - } - - tail->prev->next = nullptr; - - Node* toDelete = tail; - tail = tail->prev; - delete toDelete; -} - - -template -void DoublyLinkedList::popFront() { - if(empty()) - throw std::exception(); - - Node* toDelete = head; - - if(head == tail) { - delete toDelete; - head = tail = nullptr; - return; - } - - head->next->prev = nullptr; - head = head->next; - delete toDelete; -} - -template -typename DoublyLinkedList::Iterator DoublyLinkedList::begin() { - return Iterator(head); -} - -template -typename DoublyLinkedList::Iterator DoublyLinkedList::end() { - return Iterator(nullptr); -} - -template -void DoublyLinkedList::insert(Iterator at, const T& elem) { - // Ако е nullptr предполагам, че са подали .end() и добавям в края - if(at.current == nullptr) { - tail->next = new Node(elem, nullptr, tail); - tail = tail->next; - return; - } - - Node* toInsert = new Node(elem, at.current, at.current->prev); - - if(at.current->prev != nullptr) - at.current->prev->next = toInsert; - - at.current->prev = toInsert; - - if(at.current == head) - head = toInsert; - - if(at.current == tail) - tail = toInsert; - - at.current = toInsert; -} - -template -const T& DoublyLinkedList::back() const { - if(empty()) - throw std::exception(); - - return tail->data; -} - -template -const T& DoublyLinkedList::front() const { - if(empty()) - throw std::exception(); - - return head->data; -} - -template -DoublyLinkedList::~DoublyLinkedList(){ free(); } - -#endif \ No newline at end of file diff --git a/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/exercises.cpp b/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/exercises.cpp deleted file mode 100644 index 1981501..0000000 --- a/Year 2/Structures and data algorithms/06-Seminar-09.10.2022/exercises.cpp +++ /dev/null @@ -1,131 +0,0 @@ -#include -#include -#include -#include "DoublyLinkedList.hpp" - -// Ex1 - -template -void insertSorted(std::list& ll, const T& elem) { - auto iter = ll.cbegin(); - while (*iter < elem) - ++iter; - ll.insert(iter, elem); -} - -void ex1() { - std::list l; - l.push_back(1); - l.push_back(2); - l.push_back(4); - l.push_back(5); - - for (int n : l) std::cout << n << " "; - std::cout << std::endl; - insertSorted(l, 3); - for (int n : l) std::cout << n << " "; - std::cout << std::endl; -} - -// Ex2 - -void print(DoublyLinkedList*>& dll) { - for (std::queue* val : dll) - std::cout << val->front() << " "; - std::cout << std::endl; -} - -int operate(int a, int b, char op) { - switch(op) { - case '+': return a + b; - case '-': return a - b; - case '*': return a * b; - case '/': return a / b; - default: return 0; - } -} - -int evaluateRPQueue(std::queue& eq) { - int accum = eq.front() - '0'; - eq.pop(); - char buf; - while (!eq.empty()) { - buf = eq.front(); - eq.pop(); - accum = operate(accum, buf - '0', eq.front()); - eq.pop(); - } - return accum; -} - -void evaluateQueues(DoublyLinkedList*>& dll) { - for (std::queue* eq : dll) { - eq->push(evaluateRPQueue(*eq)); - } -} - -template -bool isSymmetricBad(DoublyLinkedList*> dll) { - while (!dll.empty()) { - if (dll.back()->front() != dll.front()->front()) - return false; - dll.popBack(); - if (dll.empty()) return true; - dll.popFront(); - } - return true; -} - -template -bool isSymmetric(DoublyLinkedList*>& dll) { - auto frontIter = dll.begin(); - auto backIter = --dll.end(); - - while (frontIter != backIter) { - if ((*frontIter)->front() != (*backIter)->front()) - return false; - ++frontIter; - if (frontIter == backIter) return true; - --backIter; - } - return true; -} - -void ex2() { - DoublyLinkedList*> dll; - dll.pushBack(new std::queue()); - dll.back()->push('4'); - dll.back()->push('5'); - dll.back()->push('+'); - dll.pushBack(new std::queue()); - dll.back()->push('1'); - dll.back()->push('6'); - dll.back()->push('+'); - dll.back()->push('7'); - dll.back()->push('*'); - dll.pushBack(new std::queue()); - dll.back()->push('8'); - dll.pushBack(new std::queue()); - dll.back()->push('1'); - dll.back()->push('7'); - dll.back()->push('*'); - dll.back()->push('7'); - dll.back()->push('*'); - dll.pushBack(new std::queue()); - dll.back()->push('2'); - dll.back()->push('3'); - dll.back()->push('*'); - dll.back()->push('3'); - dll.back()->push('+'); - - print(dll); - - evaluateQueues(dll); - print(dll); - - std::cout << isSymmetric(dll) << std::endl; -} - -int main() { - ex2(); -} diff --git a/Year 2/Structures and data algorithms/06-Seminar-09.11.2022/DoublyLinkedList.hpp b/Year 2/Structures and data algorithms/06-Seminar-09.11.2022/DoublyLinkedList.hpp new file mode 100644 index 0000000..f1bb01e --- /dev/null +++ b/Year 2/Structures and data algorithms/06-Seminar-09.11.2022/DoublyLinkedList.hpp @@ -0,0 +1,294 @@ +#ifndef DOUBLY_LINKED_LIST_IMPL_ +#define DOUBLY_LINKED_LIST_IMPL_ + +#include + +template +class DoublyLinkedList { +private: + struct DLListNode { + T data; + DLListNode* next; + DLListNode* prev; + + DLListNode(const T& d, DLListNode* n = nullptr, DLListNode* p = nullptr) : + data {d}, + next {n}, + prev {p} {} + }; + + using Node = DLListNode; + + Node* head; + Node* tail; + + void copy(const DoublyLinkedList& other); + void free(); + + class Iterator { + private: + Node* current; + Iterator(Node* c = nullptr) : current { c } {} + + public: + Iterator& operator++() { + if(current == nullptr) + return *this; + current = current->next; + return *this; + } + + Iterator operator++(int) { + if(current == nullptr) + return *this; + + Iterator tmp = *this; + current = current->next; + return tmp; + } + + Iterator& operator--() { + if(current == nullptr) + return *this; + + current = current->prev; + return *this; + } + + Iterator operator--(int) { + if(current == nullptr) + return *this; + + Iterator tmp = *this; + current = current->prev; + return tmp; + } + + const T& operator*() { + if(current == nullptr) + throw std::exception(); + + return current->data; + } + + bool operator==(const Iterator& other) const { + return current == other.current; + } + + bool operator!=(const Iterator& other) const { + return !(*this == other); + } + + friend class DoublyLinkedList; + }; + +public: + DoublyLinkedList(); + + DoublyLinkedList(const DoublyLinkedList&); + DoublyLinkedList& operator=(const DoublyLinkedList&); + + DoublyLinkedList(DoublyLinkedList&&); + DoublyLinkedList& operator=(DoublyLinkedList&&); + + void pushBack(const T&); + void popBack(); + + void pushFront(const T&); + void popFront(); + + bool empty() const; + + const T& back() const; + const T& front() const; + + Iterator begin(); + Iterator end(); + + void insert(Iterator at, const T& elem); + + ~DoublyLinkedList(); +}; + +template +DoublyLinkedList::DoublyLinkedList() : head { nullptr }, tail { nullptr } {} + +template +DoublyLinkedList::DoublyLinkedList(const DoublyLinkedList& other) : head {nullptr}, tail {nullptr} { + copy(other); +} + +template +DoublyLinkedList& DoublyLinkedList::operator=(const DoublyLinkedList& other) { + if(this != &other) { + free(); + copy(other); + } + return *this; +} + +template +DoublyLinkedList::DoublyLinkedList(DoublyLinkedList&& other) { + head = other.head; + tail = other.tail; + + other.head = other.tail = nullptr; +} + +template +DoublyLinkedList& DoublyLinkedList::operator=(DoublyLinkedList&& other) { + if(this != &other) { + free(); + + head = other.head; + tail = other.tail; + + other.head = other.tail = nullptr; + } + return *this; +} + +template +void DoublyLinkedList::copy(const DoublyLinkedList& other) { + Node* iter = other.head; + + while(iter) { + pushBack(iter->data); + iter = iter->next; + } +} + +template +void DoublyLinkedList::free() { + while(head) { + Node* toDelete = head; + head = head->next; + delete toDelete; + } +} + +template +bool DoublyLinkedList::empty() const { + return head == nullptr; +} + +template +void DoublyLinkedList::pushBack(const T& elem) { + Node* toInsert = new Node(elem); + + if(empty()) { + head = tail = toInsert; + } + else { + toInsert->prev = tail; + tail->next = toInsert; + tail = toInsert; + } +} + +template +void DoublyLinkedList::pushFront(const T& elem) { + Node* toInsert = new Node(elem); + + if(empty()) { + head = tail = toInsert; + } + else { + toInsert->next = head; + head->prev = toInsert; + head = toInsert; + } +} + +template +void DoublyLinkedList::popBack() { + if(empty()) + throw std::exception(); + + if(tail == head) { + delete head; + tail = head = nullptr; + return; + } + + tail->prev->next = nullptr; + + Node* toDelete = tail; + tail = tail->prev; + delete toDelete; +} + + +template +void DoublyLinkedList::popFront() { + if(empty()) + throw std::exception(); + + Node* toDelete = head; + + if(head == tail) { + delete toDelete; + head = tail = nullptr; + return; + } + + head->next->prev = nullptr; + head = head->next; + delete toDelete; +} + +template +typename DoublyLinkedList::Iterator DoublyLinkedList::begin() { + return Iterator(head); +} + +template +typename DoublyLinkedList::Iterator DoublyLinkedList::end() { + return Iterator(nullptr); +} + +template +void DoublyLinkedList::insert(Iterator at, const T& elem) { + // Ако е nullptr предполагам, че са подали .end() и добавям в края + if(at.current == nullptr) { + tail->next = new Node(elem, nullptr, tail); + tail = tail->next; + return; + } + + Node* toInsert = new Node(elem, at.current, at.current->prev); + + if(at.current->prev != nullptr) + at.current->prev->next = toInsert; + + at.current->prev = toInsert; + + if(at.current == head) + head = toInsert; + + if(at.current == tail) + tail = toInsert; + + at.current = toInsert; +} + +template +const T& DoublyLinkedList::back() const { + if(empty()) + throw std::exception(); + + return tail->data; +} + +template +const T& DoublyLinkedList::front() const { + if(empty()) + throw std::exception(); + + return head->data; +} + +template +DoublyLinkedList::~DoublyLinkedList(){ free(); } + +#endif \ No newline at end of file diff --git a/Year 2/Structures and data algorithms/06-Seminar-09.11.2022/exercises.cpp b/Year 2/Structures and data algorithms/06-Seminar-09.11.2022/exercises.cpp new file mode 100644 index 0000000..1981501 --- /dev/null +++ b/Year 2/Structures and data algorithms/06-Seminar-09.11.2022/exercises.cpp @@ -0,0 +1,131 @@ +#include +#include +#include +#include "DoublyLinkedList.hpp" + +// Ex1 + +template +void insertSorted(std::list& ll, const T& elem) { + auto iter = ll.cbegin(); + while (*iter < elem) + ++iter; + ll.insert(iter, elem); +} + +void ex1() { + std::list l; + l.push_back(1); + l.push_back(2); + l.push_back(4); + l.push_back(5); + + for (int n : l) std::cout << n << " "; + std::cout << std::endl; + insertSorted(l, 3); + for (int n : l) std::cout << n << " "; + std::cout << std::endl; +} + +// Ex2 + +void print(DoublyLinkedList*>& dll) { + for (std::queue* val : dll) + std::cout << val->front() << " "; + std::cout << std::endl; +} + +int operate(int a, int b, char op) { + switch(op) { + case '+': return a + b; + case '-': return a - b; + case '*': return a * b; + case '/': return a / b; + default: return 0; + } +} + +int evaluateRPQueue(std::queue& eq) { + int accum = eq.front() - '0'; + eq.pop(); + char buf; + while (!eq.empty()) { + buf = eq.front(); + eq.pop(); + accum = operate(accum, buf - '0', eq.front()); + eq.pop(); + } + return accum; +} + +void evaluateQueues(DoublyLinkedList*>& dll) { + for (std::queue* eq : dll) { + eq->push(evaluateRPQueue(*eq)); + } +} + +template +bool isSymmetricBad(DoublyLinkedList*> dll) { + while (!dll.empty()) { + if (dll.back()->front() != dll.front()->front()) + return false; + dll.popBack(); + if (dll.empty()) return true; + dll.popFront(); + } + return true; +} + +template +bool isSymmetric(DoublyLinkedList*>& dll) { + auto frontIter = dll.begin(); + auto backIter = --dll.end(); + + while (frontIter != backIter) { + if ((*frontIter)->front() != (*backIter)->front()) + return false; + ++frontIter; + if (frontIter == backIter) return true; + --backIter; + } + return true; +} + +void ex2() { + DoublyLinkedList*> dll; + dll.pushBack(new std::queue()); + dll.back()->push('4'); + dll.back()->push('5'); + dll.back()->push('+'); + dll.pushBack(new std::queue()); + dll.back()->push('1'); + dll.back()->push('6'); + dll.back()->push('+'); + dll.back()->push('7'); + dll.back()->push('*'); + dll.pushBack(new std::queue()); + dll.back()->push('8'); + dll.pushBack(new std::queue()); + dll.back()->push('1'); + dll.back()->push('7'); + dll.back()->push('*'); + dll.back()->push('7'); + dll.back()->push('*'); + dll.pushBack(new std::queue()); + dll.back()->push('2'); + dll.back()->push('3'); + dll.back()->push('*'); + dll.back()->push('3'); + dll.back()->push('+'); + + print(dll); + + evaluateQueues(dll); + print(dll); + + std::cout << isSymmetric(dll) << std::endl; +} + +int main() { + ex2(); +} -- cgit v1.3.1-26-gb76a