Website Summary Files Commits Branches @commit @diff @stats
diff options
context:
space:
mode:
Commitad40e20b8983831400502fa9617f4c842ae23b78 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-11-12 17:20:20 -0500
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-11-12 17:20:20 -0500
Filesa05c75eb0d2ed18672a5cd599f044173ac6371a0
Data-structures-and-algorithms-ad40e20b8983831400502fa9617f4c842ae23b78.tar
Data-structures-and-algorithms-ad40e20b8983831400502fa9617f4c842ae23b78.tar.gz
Data-structures-and-algorithms-ad40e20b8983831400502fa9617f4c842ae23b78.zip
Parent450101630aeebfb92da99417a6a71570bdfeb3e6 (diff)
Add Seminar05
diff --git a/Seminar05/src/deque/deque-tests.cpp b/Seminar05/src/deque/deque-tests.cpp
new file mode 100644
index 0000000..091e15c
--- /dev/null
+++ b/Seminar05/src/deque/deque-tests.cpp
@@ -0,0 +1,404 @@
+#include "deque.hpp"
+#include <iostream>
+
+bool testPushBack()
+{
+ deque<int> deque;
+ deque.push_back(10);
+ deque.push_back(20);
+ deque.push_back(30);
+
+ return deque.size() == 3 && deque[0] == 10 && deque[1] == 20 && deque[2] == 30;
+}
+
+bool testPushFront()
+{
+ deque<int> deque;
+ deque.push_front(10);
+ deque.push_front(20);
+ deque.push_front(30);
+
+ return deque.size() == 3 && deque[0] == 30 && deque[1] == 20 && deque[2] == 10;
+}
+
+bool testPopBack()
+{
+ deque<int> deque;
+ deque.push_back(10);
+ deque.push_back(20);
+ deque.push_back(30);
+ deque.pop_back();
+
+ return deque.size() == 2 && deque[0] == 10 && deque[1] == 20;
+}
+
+bool testPopFront()
+{
+ deque<int> deque;
+ deque.push_back(10);
+ deque.push_back(20);
+ deque.push_back(30);
+ deque.pop_front();
+
+ return deque.size() == 2 && deque[0] == 20 && deque[1] == 30;
+}
+
+bool testEmplaceBack()
+{
+ deque<std::string> deque;
+ deque.emplace_back(3, 'a'); // Adds "aaa" to the back
+
+ return deque.size() == 1 && deque[0] == "aaa";
+}
+
+bool testEmplaceFront()
+{
+ deque<std::string> deque;
+ deque.emplace_front(3, 'b'); // Adds "bbb" to the front
+
+ return deque.size() == 1 && deque[0] == "bbb";
+}
+
+bool testFrontBackAccess()
+{
+ deque<int> deque;
+ deque.push_back(10);
+ deque.push_back(20);
+ deque.push_front(5);
+
+ return deque.front() == 5 && deque.back() == 20;
+}
+
+bool testIsEmpty()
+{
+ deque<int> deque;
+ return deque.empty();
+}
+
+bool testResize()
+{
+ deque<int> deque;
+ for (int i = 0; i < 20; ++i)
+ {
+ deque.push_back(i);
+ }
+ bool success = true;
+ for (int i = 0; i < 20; ++i)
+ {
+ success = success && deque[i] == i;
+ }
+ return success && deque.size() == 20;
+}
+
+bool testShrinkToFit()
+{
+ deque<int> deque;
+
+ // Step 1: Add elements to exceed the initial currCapacity and trigger resize
+ for (int i = 0; i < 20; ++i)
+ {
+ deque.push_back(i);
+ }
+
+ // Step 2: Remove a few elements to create extra currCapacity
+ for (int i = 0; i < 10; ++i)
+ {
+ deque.pop_front();
+ }
+
+ // Step 3: Call shrink_to_fit to reduce currCapacity to match the current size
+ size_t sizeBeforeShrink = deque.size();
+ deque.shrink_to_fit();
+
+ // Step 4: Check if the currCapacity matches the current size
+ bool capacityMatchesSize = (deque.size() == sizeBeforeShrink && deque.capacity() == deque.size());
+
+ // Step 5: Verify elements are in the correct order after shrinking
+ bool elementsIntact = true;
+ for (size_t i = 0; i < deque.size(); ++i)
+ {
+ if (deque[i] != i + 10) // Elements should be [10, 11, ..., 19] after popping
+ {
+ elementsIntact = false;
+ break;
+ }
+ }
+
+ if (!(capacityMatchesSize && elementsIntact))
+ return false;
+
+ // Step 6: Empty the whole deque then try shrink_to_fit
+ // on an empty container.
+ while (deque.size())
+ {
+ deque.pop_front();
+ }
+ deque.shrink_to_fit();
+ if (deque.size() != 0)
+ return false;
+
+ deque.push_back(1);
+ deque.push_back(2);
+ deque.push_back(3);
+ deque.push_back(4);
+
+ if (deque.size() != 4 || deque.front() != 1 || deque.back() != 4)
+ return false;
+
+ return true;
+}
+
+bool testIteratorIncrement()
+{
+ deque<int> deque;
+ deque.push_back(1);
+ deque.push_back(2);
+ deque.push_back(3);
+
+ auto it = deque.begin();
+ if (*it != 1)
+ return false;
+
+ it++;
+ if (*it != 2)
+ return false;
+
+ ++it;
+ if (*it != 3)
+ return false;
+
+ return it == deque.end() - 1;
+}
+
+bool testIteratorDecrement()
+{
+ deque<int> deque;
+ deque.push_back(1);
+ deque.push_back(2);
+ deque.push_back(3);
+
+ auto it = deque.end() - 1;
+ if (*it != 3)
+ return false;
+
+ it--;
+ if (*it != 2)
+ return false;
+
+ --it;
+ if (*it != 1)
+ return false;
+
+ return it == deque.begin();
+}
+
+bool testIteratorEquality()
+{
+ deque<int> deque;
+ deque.push_back(10);
+ deque.push_back(20);
+
+ auto it1 = deque.begin();
+ auto it2 = deque.begin();
+ if (it1 != it2)
+ return false;
+
+ ++it2;
+ if (it1 == it2)
+ return false;
+
+ return true;
+}
+
+bool testConstIterator()
+{
+ deque<int> f_deque;
+ f_deque.push_back(5);
+ f_deque.push_back(15);
+ f_deque.push_back(25);
+
+ const deque<int>& constDeque = f_deque;
+ auto it = constDeque.begin();
+
+ if (*it != 5)
+ return false;
+ ++it;
+ if (*it != 15)
+ return false;
+ ++it;
+ if (*it != 25)
+ return false;
+
+ return it == constDeque.end() - 1;
+}
+
+bool testIteratorDereference()
+{
+ deque<int> deque;
+ deque.push_back(100);
+ deque.push_back(200);
+ deque.push_back(300);
+
+ auto it = deque.begin();
+ if (*it != 100)
+ return false;
+
+ ++it;
+ if (*it != 200)
+ return false;
+
+ it++;
+ if (*it != 300)
+ return false;
+
+ return true;
+}
+
+bool testCopyConstructor()
+{
+ deque<int> f_deque;
+ f_deque.push_back(1);
+ f_deque.push_back(2);
+ f_deque.push_back(3);
+
+ deque<int> copy(f_deque);
+
+ if (f_deque.size() != copy.size())
+ return false;
+
+ while (copy.size())
+ {
+ if (copy.front() != f_deque.front())
+ return false;
+ copy.pop_front();
+ f_deque.pop_front();
+ }
+
+ if (f_deque.size() != copy.size())
+ return false;
+
+ return true;
+}
+
+bool testMoveAndAssignment()
+{
+ constexpr size_t SIZE = 4;
+
+ deque<int> d;
+
+ for (size_t i = 0; i < SIZE; i++)
+ d.push_back(i);
+
+ deque<int> d1;
+ d1 = d;
+
+ for (size_t i = 0; i < d1.size(); i++)
+ if (d1[i] != d[i])
+ return false;
+
+ deque<int> moved(std::move(d1));
+
+ if (moved.size() != SIZE || d1.size() != 0)
+ return false;
+
+ d1 = std::move(moved);
+ moved = std::move(d1);
+
+ if (moved.size() != SIZE || d1.size() != 0)
+ return false;
+
+ for (size_t i = 0; i < d1.size(); i++)
+ if (moved[i] != d[i])
+ return false;
+
+ while (moved.size())
+ {
+ if (moved.front() != d.front() || moved.back() != d.back())
+ return false;
+ moved.pop_back();
+ d.pop_back();
+
+ if (moved.empty() || d.empty())
+ break;
+
+ moved.pop_front();
+ d.pop_front();
+ }
+
+ if (!moved.empty() || !d.empty())
+ return false;
+
+ return true;
+}
+
+bool resize_tests()
+{
+ deque<int> d;
+
+ d.resize(10);
+
+ d.resize(20);
+ d.resize(15);
+
+ d.emplace_back(1);
+ d.emplace_back(2);
+ d.emplace_back(3);
+ d.emplace_front(0);
+
+ if (d.size() != 4 || d.front() != 0 || d.back() != 3)
+ {
+ return false;
+ }
+
+ d.resize(30);
+
+ if (d.size() != 4 || d.front() != 0 || d.back() != 3)
+ {
+ return false;
+ }
+
+ d.resize(4);
+
+ if (d.size() != 4 || d.front() != 0 || d.back() != 3)
+ {
+ return false;
+ }
+
+ for (size_t i = 0; i < 100; i++)
+ {
+ d.push_back(i);
+ }
+
+ if(d.back() != 99 || d.size() != 104)
+ {
+ return false;
+ }
+
+ d.resize(10);
+
+ return true;
+}
+
+int main()
+{
+ std::cout << "Test Push Back: " << (testPushBack() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Push Front: " << (testPushFront() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Pop Back: " << (testPopBack() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Pop Front: " << (testPopFront() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Emplace Back: " << (testEmplaceBack() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Emplace Front: " << (testEmplaceFront() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Front and Back Access: " << (testFrontBackAccess() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Is Empty: " << (testIsEmpty() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Resize: " << (testResize() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Shrink To Fit: " << (testShrinkToFit() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Iterator Increment: " << (testIteratorIncrement() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Iterator Decrement: " << (testIteratorDecrement() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Iterator Equality: " << (testIteratorEquality() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Const Iterator: " << (testConstIterator() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Iterator Dereference: " << (testIteratorDereference() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Copy Cnstructor: " << (testCopyConstructor() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test Move Constructor And Assignment: " << (testMoveAndAssignment() ? "PASSED" : "FAILED") << "\n";
+ std::cout << "Test resize: " << (resize_tests() ? "PASSED" : "FAILED") << "\n";
+
+ return 0;
+} \ No newline at end of file
diff --git a/Seminar05/src/deque/deque.hpp b/Seminar05/src/deque/deque.hpp
new file mode 100644
index 0000000..fa2d9df
--- /dev/null
+++ b/Seminar05/src/deque/deque.hpp
@@ -0,0 +1,472 @@
+#pragma once
+#include <memory>
+#include <stdexcept>
+
+template <class T, class Allocator = std::allocator<T>>
+class deque
+{
+ private:
+ T* _data = nullptr;
+
+ size_t _size = 0;
+ size_t _capacity = 0;
+
+ size_t _head = 0;
+ size_t _tail = 0;
+
+ Allocator _allocator;
+
+ void move_index(size_t& idx, bool forward) const;
+ size_t calculate_capacity() const;
+
+ void move(deque&& other) noexcept;
+ void copy(const deque& other);
+ void free();
+
+ public:
+ deque() = default;
+ deque(const deque& other);
+ deque(deque&& other) noexcept;
+
+ deque& operator=(const deque& other);
+ deque& operator=(deque&& other) noexcept;
+
+ void push_back(const T& element);
+ void push_front(const T& element);
+
+ void pop_back();
+ void pop_front();
+
+ T& front();
+ T& back();
+
+ void shrink_to_fit();
+
+ T& operator[](size_t idx);
+ const T& operator[](size_t idx) const;
+
+ void resize(size_t new_capacity);
+
+ const T& front() const;
+ const T& back() const;
+
+ template <class... Args>
+ void emplace_front(Args&&... args);
+
+ template <class... Args>
+ void emplace_back(Args&&... args);
+
+ size_t size() const;
+ size_t capacity() const;
+
+ bool empty() const;
+
+ class iterator
+ {
+ friend class deque;
+ deque<T, Allocator>& _deque;
+ size_t _index; // (not in the physical array)
+
+ iterator(deque& deque, size_t index)
+ : _deque(deque)
+ , _index(index)
+ {}
+
+ public:
+ iterator& operator++(int)
+ {
+ _index++;
+ return *this;
+ }
+
+ iterator operator++()
+ {
+ iterator old = *this;
+ _index++;
+ return old;
+ }
+
+ iterator& operator--(int)
+ {
+ _index--;
+ return *this;
+ }
+
+ iterator operator--()
+ {
+ iterator old = *this;
+ _index--;
+ return old;
+ }
+
+ iterator operator+(int n)
+ {
+ return iterator(_deque, _index + n);
+ }
+
+ iterator operator-(int n)
+ {
+ return iterator(_deque, _index - n);
+ }
+
+ T& operator*()
+ {
+ return _deque[_index];
+ }
+
+ bool operator==(const iterator& other)
+ {
+ return _index == other._index;
+ }
+ bool operator!=(const iterator& other)
+ {
+ return _index != other._index;
+ }
+ };
+
+ class const_iterator
+ {
+ friend class deque;
+ const deque<T, Allocator>& _deque;
+ size_t _index; // semantic index (not in the physical array)
+
+ const_iterator(const deque<T, Allocator>& deque, int index)
+ : _deque(deque)
+ , _index(index)
+ {}
+
+ public:
+ const_iterator& operator++(int)
+ {
+ _index++;
+ return *this;
+ }
+
+ const_iterator operator++()
+ {
+ const_iterator old = *this;
+ _index++;
+ return old;
+ }
+
+ const_iterator& operator--(int)
+ {
+ _index--;
+ return *this;
+ }
+
+ const_iterator operator--()
+ {
+ const_iterator old = *this;
+ _index--;
+ return old;
+ }
+
+ const_iterator operator+(int n)
+ {
+ return const_iterator(_deque, _index + n);
+ }
+
+ const_iterator operator-(int n)
+ {
+ return const_iterator(_deque, _index - n);
+ }
+
+ const T& operator*() const
+ {
+ return _deque[_index];
+ }
+
+ bool operator==(const const_iterator& other)
+ {
+ return _index == other._index;
+ }
+ bool operator!=(const const_iterator& other)
+ {
+ return _index != other._index;
+ }
+ };
+
+ deque::iterator begin()
+ {
+ return iterator(*this, 0);
+ }
+
+ deque::iterator end()
+ {
+ return iterator(*this, size());
+ }
+
+ deque::const_iterator begin() const
+ {
+ return const_iterator(*this, 0);
+ }
+
+ deque::const_iterator end() const
+ {
+ return const_iterator(*this, size());
+ }
+
+ ~deque();
+};
+
+template <class T, class Allocator>
+void deque<T, Allocator>::move_index(size_t& idx, bool forward) const
+{
+ if (forward)
+ {
+ ++idx;
+ idx %= _capacity;
+ }
+ else
+ {
+ idx = (idx == 0) ? (_capacity - 1) : idx - 1;
+ }
+}
+
+template <class T, class Allocator>
+deque<T, Allocator>::deque(const deque<T, Allocator>& other)
+{
+ copy(other);
+}
+
+template <class T, class Allocator>
+deque<T, Allocator>::deque(deque<T, Allocator>&& other) noexcept
+{
+ move(std::move(other));
+}
+
+template <class T, class Allocator>
+deque<T, Allocator>& deque<T, Allocator>::operator=(const deque<T, Allocator>& other)
+{
+ if (this != &other)
+ {
+ free();
+ copy(other);
+ }
+ return *this;
+}
+
+template <class T, class Allocator>
+deque<T, Allocator>& deque<T, Allocator>::operator=(deque<T, Allocator>&& other) noexcept
+{
+ if (this != &other)
+ {
+ free();
+ move(std::move(other));
+ }
+ return *this;
+}
+
+template <class T, class Allocator>
+void deque<T, Allocator>::push_back(const T& element)
+{
+ if (size() == capacity())
+ resize(calculate_capacity());
+
+ _allocator.construct(_data + _tail, element);
+ move_index(_tail, true);
+ ++_size;
+}
+
+template <class T, class Allocator>
+template <class... Args>
+void deque<T, Allocator>::emplace_back(Args&&... args)
+{
+ if (size() == capacity())
+ resize(calculate_capacity());
+
+ _allocator.construct(_data + _tail, std::forward<Args>(args)...);
+ move_index(_tail, true);
+ ++_size;
+}
+
+template <class T, class Allocator>
+void deque<T, Allocator>::resize(size_t new_capacity)
+{
+ if(new_capacity == 0) new_capacity = calculate_capacity();
+
+ T* new_data = _allocator.allocate(new_capacity);
+
+ // If the current size is greater than `new_capacity`,
+ // the container is reduced to its first `new_capacity` elements.
+ size_t elements_included = std::min(new_capacity, size());
+ for (size_t i = 0; i < elements_included; i++)
+ {
+ _allocator.construct(new_data + i, std::move(operator[](i)));
+ _allocator.destroy(_data + ((_head + i) % _capacity));
+ }
+
+ _allocator.deallocate(_data, _capacity);
+
+ _head = 0;
+ _tail = size() % new_capacity;
+ _capacity = new_capacity;
+ _data = new_data;
+}
+
+template <class T, class Allocator>
+void deque<T, Allocator>::shrink_to_fit()
+{
+ if (_capacity > _size)
+ {
+ if(_size == 0)
+ {
+ free();
+ return;
+ }
+
+ resize(_size);
+ }
+}
+
+template <class T, class Allocator>
+void deque<T, Allocator>::push_front(const T& element)
+{
+ if (size() == capacity())
+ resize(calculate_capacity());
+
+ move_index(_head, false);
+ _allocator.construct(_data + _head, element);
+ ++_size;
+}
+
+template <class T, class Allocator>
+template <class... Args>
+void deque<T, Allocator>::emplace_front(Args&&... args)
+{
+ if (size() == capacity())
+ resize(calculate_capacity());
+
+ move_index(_head, false);
+ _allocator.construct(_data + _head, std::forward<Args>(args)...);
+ ++_size;
+}
+
+template <class T, class Allocator>
+void deque<T, Allocator>::pop_back()
+{
+ if (empty())
+ throw std::out_of_range("Trying to pop_back on empty deque.");
+
+ move_index(_tail, false);
+ _allocator.destroy(_data + _tail);
+ --_size;
+}
+
+template <class T, class Allocator>
+void deque<T, Allocator>::pop_front()
+{
+ if (empty())
+ throw std::out_of_range("Trying to pop_back on empty deque.");
+
+ _allocator.destroy(_data + _head);
+ move_index(_head, true);
+ --_size;
+}
+
+template <class T, class Allocator>
+T& deque<T, Allocator>::operator[](size_t idx)
+{
+ return _data[(_head + idx) % _capacity];
+}
+template <class T, class Allocator>
+const T& deque<T, Allocator>::operator[](size_t idx) const
+{
+ return _data[(_head + idx) % _capacity];
+}
+
+template <class T, class Allocator>
+void deque<T, Allocator>::copy(const deque<T, Allocator>& other)
+{
+ _data = _allocator.allocate(other.capacity());
+ _capacity = other.capacity();
+
+ for (size_t i = 0; i < other.size(); i++)
+ {
+ push_back(other[i]);
+ }
+}
+
+template <class T, class Allocator>
+T& deque<T, Allocator>::front()
+{
+ return _data[_head];
+}
+
+template <class T, class Allocator>
+T& deque<T, Allocator>::back()
+{
+ unsigned last_element_idx = (_tail ? _tail : _capacity) - 1;
+ return _data[last_element_idx];
+}
+
+template <class T, class Allocator>
+const T& deque<T, Allocator>::front() const
+{
+ return _data[_head];
+}
+
+template <class T, class Allocator>
+const T& deque<T, Allocator>::back() const
+{
+ unsigned last_element_idx = (_tail ? _tail : _capacity) - 1;
+ return _data[last_element_idx];
+}
+
+template <class T, class Allocator>
+void deque<T, Allocator>::move(deque<T, Allocator>&& other) noexcept
+{
+ _data = other._data;
+ _size = other._size;
+ _capacity = other._capacity;
+ _head = other._head;
+ _tail = other._tail;
+
+ other._size = other._capacity = 0;
+ other._head = other._tail = 0;
+ other._data = nullptr;
+}
+
+template <class T, class Allocator>
+void deque<T, Allocator>::free()
+{
+ while (_head != _tail)
+ {
+ _allocator.destroy(_data + _head);
+ move_index(_head, true);
+ }
+ _allocator.deallocate(_data, capacity());
+ _size = _capacity = 0;
+ _data = nullptr;
+}
+
+template <class T, class Allocator>
+deque<T, Allocator>::~deque()
+{
+ free();
+}
+
+template <class T, class Allocator>
+size_t deque<T, Allocator>::calculate_capacity() const
+{
+ return empty() ? 1 : 2 * capacity();
+}
+
+template <class T, class Allocator>
+size_t deque<T, Allocator>::size() const
+{
+ return _size;
+}
+
+template <class T, class Allocator>
+size_t deque<T, Allocator>::capacity() const
+{
+ return _capacity;
+}
+
+template <class T, class Allocator>
+bool deque<T, Allocator>::empty() const
+{
+ return _size == 0;
+} \ No newline at end of file
diff --git a/Seminar05/src/singly-linked-list/merge-sort.cpp b/Seminar05/src/singly-linked-list/merge-sort.cpp
new file mode 100644
index 0000000..aaeb6ef
--- /dev/null
+++ b/Seminar05/src/singly-linked-list/merge-sort.cpp
@@ -0,0 +1,81 @@
+#include "node_utils.h"
+#include <iostream>
+
+template <class T>
+node<T>* merge(node<T>* lhs, node<T>* rhs)
+{
+ // result linked list
+ node<T>* head = nullptr;
+ node<T>* tail = nullptr;
+
+ while (lhs && rhs)
+ {
+ if (lhs->data < rhs->data)
+ {
+ append_back(head, tail, lhs);
+ lhs = lhs->next;
+ }
+ else
+ {
+ append_back(head, tail, rhs);
+ rhs = rhs->next;
+ }
+ }
+
+ if (lhs)
+ {
+ tail->next = lhs;
+ }
+
+ if (rhs)
+ {
+ tail->next = rhs;
+ }
+
+ return head;
+}
+
+template <class T>
+node<T>* get_middle(node<T>* list)
+{
+ if (!list || !list->next)
+ return list;
+
+ node<T>* fast = list->next;
+ node<T>* slow = list;
+
+ while (fast && fast->next)
+ {
+ slow = slow->next;
+ fast = fast->next->next;
+ }
+ return slow;
+}
+
+template <class T>
+node<T>* merge_sort(node<T>* list)
+{
+ if (!list || !list->next)
+ return list;
+
+ node<T>* middle = get_middle(list);
+
+ node<T>* right_part = middle->next;
+ middle->next = nullptr;
+
+ node<T>* left_sorted = merge_sort(list);
+ node<T>* right_sorted = merge_sort(right_part);
+
+ return merge(left_sorted, right_sorted);
+}
+
+int main()
+{
+ node<int>* ll = new node(1, new node(0, new node(2, new node(-1, new node(10)))));
+ ll = merge_sort(ll);
+ if (is_sorted(ll) && list_size(ll) == 5)
+ std::cout << "passed";
+ else
+ std::cout << "failed";
+ free_list(ll);
+} \ No newline at end of file
diff --git a/Seminar05/src/singly-linked-list/node_utils.h b/Seminar05/src/singly-linked-list/node_utils.h
new file mode 100644
index 0000000..b439d4a
--- /dev/null
+++ b/Seminar05/src/singly-linked-list/node_utils.h
@@ -0,0 +1,79 @@
+#pragma once
+
+// We represent a singly linked list
+// with an pointer to its first element.
+template <class T>
+struct node
+{
+ T data;
+ node* next;
+
+ node(const T& data_, node* next_ = nullptr) :
+ data(data_),
+ next(next_) {}
+};
+
+template <class T>
+void append_back(node<T>*& head, node<T>*& tail, node<T>* element)
+{
+ if(head == nullptr)
+ {
+ head = tail = element;
+ }
+ else
+ {
+ tail->next = element;
+ tail = tail->next;
+ }
+}
+
+
+template <class T>
+bool is_sorted(node<T>* list)
+{
+ if(!list || !list->next)
+ return true;
+
+ node<T>* prev = list;
+ node<T>* next = list->next;
+
+ while(next)
+ {
+ if(prev->data > next->data)
+ {
+ return false;
+ }
+ prev = prev->next;
+ next = next->next;
+ }
+ return true;
+}
+
+template <class T>
+void free_list(node<T>* ll)
+{
+ while(ll)
+ {
+ node<T>* to_delete = ll;
+ ll = ll->next;
+ delete to_delete;
+ }
+}
+
+template <class T>
+unsigned list_size(node<T>* list)
+{
+ unsigned size = 0;
+ while(list)
+ {
+ ++size;
+ list = list->next;
+ }
+ return size;
+}
+
+template <class T>
+node<T>* push_front(node<T>* head, const T& data)
+{
+ return new node<T>(data, head);
+} \ No newline at end of file
diff --git a/Seminar05/src/singly-linked-list/quick_sort.cpp b/Seminar05/src/singly-linked-list/quick_sort.cpp
new file mode 100644
index 0000000..ed8044e
--- /dev/null
+++ b/Seminar05/src/singly-linked-list/quick_sort.cpp
@@ -0,0 +1,136 @@
+#include "node_utils.h"
+#include <cassert>
+#include <iostream>
+
+// Implementation is inspired by:
+// https://github.com/Angeld55/Data_structures_and_algorithms_FMI/blob/main/Miscellaneous/singlyLinkedList_quickSort.cpp
+
+template <class T>
+using list_info = std::pair<node<T>*, node<T>*>;
+
+template <class T, class Predicate>
+list_info<T> partition(node<T>* list, Predicate pred)
+{
+ node<T>* true_begin = nullptr;
+ node<T>* true_end = nullptr;
+
+ node<T>* false_begin = nullptr;
+ node<T>* false_end = nullptr;
+
+ while (list)
+ {
+ if (pred(list->data))
+ {
+ append_back(true_begin, true_end, list);
+ }
+ else
+ {
+ append_back(false_begin, false_end, list);
+ }
+ list = list->next;
+ }
+
+ if (true_end)
+ {
+ true_end->next = nullptr;
+ }
+ if (false_end)
+ {
+ false_end->next = nullptr;
+ }
+
+ return {true_begin, false_begin};
+}
+
+template <class T>
+list_info<T> concat_lists(list_info<T> left, list_info<T> right)
+{
+ if (left.first == nullptr)
+ return right;
+ if (right.first == nullptr)
+ return left;
+
+ left.second->next = right.first;
+ return {left.first, right.second};
+}
+
+template <class T>
+list_info<T> quick_sort_impl(node<T>* list)
+{
+ if (!list || !list->next)
+ return {list, list};
+
+ const T& pivot_element = list->data;
+ list_info<T> result = partition(list, [&pivot_element](const T& element) { return element < pivot_element; });
+
+ node<T>* pivot = result.second;
+
+ list_info<T> left_sorted = quick_sort_impl(result.first);
+
+ // Skip the pivot element.
+ list_info<T> right_sorted = quick_sort_impl(result.second->next);
+
+ // Attach pivot as the first element.
+ pivot->next = right_sorted.first;
+ right_sorted.first = pivot;
+
+ if (!right_sorted.second)
+ right_sorted.second = pivot;
+
+ return concat_lists(left_sorted, right_sorted);
+}
+
+template <class T>
+void quick_sort(node<T>*& list)
+{
+ list_info<T> result = quick_sort_impl(list);
+ list = result.first;
+}
+
+void tests()
+{
+ using inode = node<int>;
+
+ // test empty list
+ inode* ll = nullptr;
+ quick_sort(ll);
+ assert(ll == nullptr);
+
+ // One element case
+ ll = new inode(1);
+ quick_sort(ll);
+ assert(ll && ll->data == 1 && !ll->next);
+
+ // Two elements case (sorted & unsorted)
+ ll->next = new inode(0);
+ quick_sort(ll);
+ assert(ll && ll->data == 0 && ll->next && ll->next->data == 1 && !ll->next->next);
+ quick_sort(ll);
+ assert(ll && ll->data == 0 && ll->next && ll->next->data == 1 && !ll->next->next);
+
+ ll = push_front(ll, 2);
+ ll = push_front(ll, 3);
+
+ quick_sort(ll);
+ assert(is_sorted(ll) && list_size(ll) == 4);
+ quick_sort(ll);
+ assert(is_sorted(ll) && list_size(ll) == 4);
+
+ // Random elements
+ srand(time(0));
+
+ for (size_t i = 0; i < 1000; i++)
+ {
+ ll = push_front(ll, rand() % 10000);
+ }
+ assert(list_size(ll) == 1004);
+ quick_sort(ll);
+ assert(is_sorted(ll) && list_size(ll) == 1004);
+
+ free_list(ll);
+}
+
+int main()
+{
+ tests();
+} \ No newline at end of file
diff --git a/Seminar05/src/singly-linked-list/singly-linked-list-tests.cpp b/Seminar05/src/singly-linked-list/singly-linked-list-tests.cpp
new file mode 100644
index 0000000..89fe680
--- /dev/null
+++ b/Seminar05/src/singly-linked-list/singly-linked-list-tests.cpp
@@ -0,0 +1,98 @@
+#include "singly-linked-list.hpp"
+#include <iostream>
+#include <cassert>
+#include <forward_list>
+
+void push_tests()
+{
+ singly_linked_list<int> ll;
+ ll.push_back(1);
+
+ assert(ll.front() == 1 && ll.size() == 1);
+ ll.push_front(0);
+ assert(ll.front() == 0 && ll.back() == 1 && ll.size() == 2);
+
+ for (size_t i = 2; i < 100; i++)
+ ll.push_back(i);
+
+ assert(ll.size() == 100);
+
+ auto it = ll.begin();
+
+ for (size_t i = 0; i < 100; i++)
+ {
+ assert(*it == i);
+ ++it;
+ }
+
+ ll.remove_after(ll.begin());
+ assert(*(++ll.begin()) == 2 && ll.size() == 99);
+}
+
+void construct_tests()
+{
+ singly_linked_list<int> ll;
+ for (size_t i = 0; i < 100; i++)
+ {
+ ll.push_back(i);
+ }
+
+ singly_linked_list<int> copy(ll);
+
+ auto it = ll.begin();
+ auto it_copy = copy.begin();
+
+ while (true)
+ {
+ assert(*it == *it_copy);
+ ++it;
+ ++it_copy;
+
+ if(it == ll.end() || it_copy == copy.end())
+ break;
+ }
+
+ assert(ll.size() == copy.size());
+
+ singly_linked_list<int> move(std::move(ll));
+ ll = std::move(move);
+ move = std::move(ll);
+
+ auto its = move.begin();
+ for(const auto& x : copy)
+ {
+ assert(x == *its);
+ assert(its != move.end());
+ ++its;
+ }
+ assert(its == move.end());
+ assert(move.size() == 100);
+}
+
+void concat_tests()
+{
+ singly_linked_list<int> ll;
+ singly_linked_list<int> lls;
+
+ for (size_t i = 0; i < 50; i++)
+ {
+ ll.push_back(i);
+ lls.push_back(50 + i);
+ }
+
+ singly_linked_list<int> cat = concat(ll, lls);
+ assert(cat.size() == 100);
+ int val = 0;
+
+ for(const auto& x : cat)
+ {
+ assert(x == val++);
+ }
+}
+
+int main()
+{
+ push_tests();
+ construct_tests();
+ concat_tests();
+} \ No newline at end of file
diff --git a/Seminar05/src/singly-linked-list/singly-linked-list.hpp b/Seminar05/src/singly-linked-list/singly-linked-list.hpp
new file mode 100644
index 0000000..3ad895e
--- /dev/null
+++ b/Seminar05/src/singly-linked-list/singly-linked-list.hpp
@@ -0,0 +1,418 @@
+#pragma once
+#include <cstddef>
+#include <utility>
+
+template <typename T>
+class singly_linked_list
+{
+private:
+ struct node
+ {
+ T data;
+ node* next;
+
+ node(const T& data_, node* next_ = nullptr) :
+ data(data_),
+ next(next_) {}
+ };
+
+ node* _head = nullptr;
+ node* _tail = nullptr;
+ size_t _size = 0;
+public:
+ singly_linked_list() = default;
+ singly_linked_list(const singly_linked_list<T>& other);
+ singly_linked_list(singly_linked_list<T>&& other);
+ singly_linked_list<T>& operator=(const singly_linked_list<T>& other);
+ singly_linked_list<T>& operator=(singly_linked_list<T>&& other);
+ ~singly_linked_list();
+
+ void push_front(const T& el);
+ void push_back(const T& el);
+
+ void pop_front();
+
+ const T& front() const;
+ const T& back() const;
+
+ T& front();
+ T& back();
+
+ size_t size() const;
+ bool empty() const;
+
+ template <typename U>
+ friend singly_linked_list<U> concat(singly_linked_list<U>& lhs, singly_linked_list<U>& rhs);
+
+ class sll_iterator
+ {
+ node* currentElementPtr;
+
+ friend class singly_linked_list;
+ public:
+
+ sll_iterator(node* currentElementPtr = nullptr) : currentElementPtr(currentElementPtr) {}
+
+ T& operator*()
+ {
+ return currentElementPtr->data;
+ }
+
+ T* operator->()
+ {
+ return &currentElementPtr->data;
+ }
+
+ sll_iterator& operator++()
+ {
+ if (currentElementPtr)
+ currentElementPtr = currentElementPtr->next;
+ return *this;
+ }
+
+ sll_iterator operator++(int)
+ {
+ sll_iterator copy(*this);
+ ++(*this);
+ return copy;
+ }
+
+ sll_iterator& operator+=(size_t s)
+ {
+
+ while (s--)
+ ++(*this);
+
+ return *this;
+ }
+
+ sll_iterator operator+(int i) const
+ {
+
+ sll_iterator res(*this);
+ return res += i;
+ }
+
+ bool operator==(const sll_iterator& rhs) const { return currentElementPtr == rhs.currentElementPtr; }
+ bool operator!=(const sll_iterator& rhs) const { return !(rhs == *this); }
+
+ };
+
+ class const_sll_iterator
+ {
+ node* currentElementPtr;
+
+ friend class singly_linked_list;
+ public:
+ const_sll_iterator(const sll_iterator& nonConstIter) : currentElementPtr(nonConstIter.currentElementPtr) {}
+ const_sll_iterator(node* currentElementPtr = nullptr) : currentElementPtr(currentElementPtr) {}
+
+ const T& operator*() const
+ {
+ return currentElementPtr->data;
+ }
+
+ const T* operator->() const
+ {
+ return &currentElementPtr->data;
+ }
+
+ const_sll_iterator& operator++()
+ {
+ if (currentElementPtr)
+ currentElementPtr = currentElementPtr->next;
+ return *this;
+ }
+
+ const_sll_iterator operator++(int)
+ {
+ const_sll_iterator copy(*this);
+ ++(*this);
+ return copy;
+ }
+
+ const_sll_iterator& operator+=(size_t s)
+ {
+
+ while (s--)
+ ++(*this);
+
+ return *this;
+ }
+
+ const_sll_iterator operator+(int i) const
+ {
+
+ const_sll_iterator res(*this);
+ return res += i;
+ }
+
+ bool operator==(const const_sll_iterator& rhs) const { return currentElementPtr == rhs.currentElementPtr; }
+ bool operator!=(const const_sll_iterator& rhs) const { return !(rhs == *this); }
+
+ };
+
+ const_sll_iterator begin()
+ {
+ return sll_iterator(_head);
+ }
+ sll_iterator end()
+ {
+ return sll_iterator(nullptr);
+ }
+
+ const_sll_iterator cbegin() const
+ {
+ return const_sll_iterator(_head);
+ }
+ const_sll_iterator cend() const
+ {
+ return const_sll_iterator(nullptr);
+ }
+
+ sll_iterator insert_after(const T& element, const const_sll_iterator& it);
+ sll_iterator remove_after(const const_sll_iterator& it);
+
+private:
+ void copy(const singly_linked_list<T>& other);
+ void move(singly_linked_list<T>&& other);
+ void free();
+};
+
+template <typename T>
+void singly_linked_list<T>::push_front(const T& el)
+{
+ node* new_node = new node(el);
+
+ if (empty())
+ {
+ _head = _tail = new_node;
+ }
+ else
+ {
+ new_node->next = _head;
+ _head = new_node;
+ }
+ _size++;
+
+}
+template <typename T>
+void singly_linked_list<T>::push_back(const T& el)
+{
+ node* new_node = new node(el);
+
+ if (empty())
+ {
+ _head = _tail = new_node;
+ }
+ else
+ {
+ _tail->next = new_node;
+ _tail = new_node;
+ }
+ _size++;
+
+}
+
+template <typename T>
+void singly_linked_list<T>::pop_front()
+{
+ if (empty())
+ return;
+
+ if (_head == _tail)
+ {
+ delete _head;
+ _head = _tail = nullptr;
+ }
+ else
+ {
+ node* to_delete = _head;
+ _head = _head->next;
+ delete to_delete;
+ }
+ _size--;
+}
+
+template <typename T>
+const T& singly_linked_list<T>::front() const
+{
+ return _head->data;
+}
+
+template <typename T>
+const T& singly_linked_list<T>::back() const
+{
+ return _tail->data;
+}
+
+template <typename T>
+T& singly_linked_list<T>::front()
+{
+ return _head->data;
+}
+
+template <typename T>
+T& singly_linked_list<T>::back()
+{
+ return _tail->data;
+}
+
+template <typename T>
+singly_linked_list<T> concat(singly_linked_list<T>& lhs, singly_linked_list<T>& rhs)
+{
+ singly_linked_list<T> result;
+
+ if (!lhs._head)
+ {
+ result._head = rhs._head;
+ result._tail = rhs._tail;
+ }
+ else if (!rhs._head)
+ {
+ result._head = lhs._head;
+ result._tail = lhs._tail;
+ }
+ else
+ {
+ lhs._tail->next = rhs._head;
+ result._head = lhs._head;
+ result._tail = rhs._tail;
+ }
+ result._size = rhs._size + lhs._size;
+ rhs._size = lhs._size = 0;
+ rhs._head = rhs._tail = lhs._head = lhs._tail = nullptr;
+
+ return result;
+}
+
+template <typename T>
+typename singly_linked_list<T>::sll_iterator singly_linked_list<T>::insert_after(const T& element, const typename singly_linked_list<T>::const_sll_iterator& it)
+{
+ if(it == end())
+ return end();
+
+ node* new_node = new node(element);
+ node* itNode = it.currentElementPtr;
+
+ new_node->next = itNode->next;
+ itNode->next = new_node;
+ _size++;
+ return singly_linked_list<T>::sll_iterator(new_node);
+}
+
+
+template <typename T>
+typename singly_linked_list<T>::sll_iterator singly_linked_list<T>::remove_after(const typename singly_linked_list<T>::const_sll_iterator& it)
+{
+ if(it == end() || size() == 1)
+ return end();
+
+ node* to_delete = (it + 1).currentElementPtr;
+
+ node* new_next = to_delete->next;
+
+ it.currentElementPtr->next = new_next;
+ _size--;
+
+ if(to_delete == _tail)
+ {
+ _tail = it.currentElementPtr;
+ }
+
+ delete to_delete;
+
+ return singly_linked_list<T>::sll_iterator(new_next);
+}
+
+template <typename T>
+bool singly_linked_list<T>::empty() const
+{
+ return size() == 0;
+}
+
+template <typename T>
+size_t singly_linked_list<T>::size() const
+{
+ return _size;
+}
+
+template <typename T>
+singly_linked_list<T>::singly_linked_list(const singly_linked_list<T>& other)
+{
+ copy(other);
+}
+
+
+template <typename T>
+singly_linked_list<T>::singly_linked_list(singly_linked_list<T>&& other)
+{
+ move(std::move(other));
+}
+
+template <typename T>
+singly_linked_list<T>& singly_linked_list<T>::operator=(const singly_linked_list<T>& other)
+{
+ if (this != &other)
+ {
+ free();
+ copy(other);
+ }
+
+ return *this;
+}
+
+template <typename T>
+singly_linked_list<T>& singly_linked_list<T>::operator=(singly_linked_list<T>&& other)
+{
+ if (this != &other)
+ {
+ free();
+ move(std::move(other));
+ }
+
+ return *this;
+}
+template <typename T>
+singly_linked_list<T>::~singly_linked_list()
+{
+ free();
+}
+
+template <typename T>
+void singly_linked_list<T>::copy(const singly_linked_list<T>& other)
+{
+ node* iter = other._head;
+
+ while (iter)
+ {
+ push_back(iter->data);
+ iter = iter->next;
+ }
+}
+
+template <typename T>
+void singly_linked_list<T>::move(singly_linked_list<T>&& other)
+{
+ _head = other._head;
+ _tail = other._tail;
+ _size = other.size();
+
+ other._head = other._tail = nullptr;
+ other._size = 0;
+}
+
+template <typename T>
+void singly_linked_list<T>::free()
+{
+ node* iter = _head;
+
+ while (iter)
+ {
+ node* to_delete = iter;
+ iter = iter->next;
+ delete to_delete;
+ }
+ _head = _tail = nullptr;
+ _size = 0;
+} \ No newline at end of file