diff options
Add Seminar05
7 files changed, 1688 insertions, 0 deletions
| -rw-r--r-- | Seminar05/src/deque/deque-tests.cpp | 404 | ||||
| -rw-r--r-- | Seminar05/src/deque/deque.hpp | 472 | ||||
| -rw-r--r-- | Seminar05/src/singly-linked-list/merge-sort.cpp | 81 | ||||
| -rw-r--r-- | Seminar05/src/singly-linked-list/node_utils.h | 79 | ||||
| -rw-r--r-- | Seminar05/src/singly-linked-list/quick_sort.cpp | 136 | ||||
| -rw-r--r-- | Seminar05/src/singly-linked-list/singly-linked-list-tests.cpp | 98 | ||||
| -rw-r--r-- | Seminar05/src/singly-linked-list/singly-linked-list.hpp | 418 |
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 ¤tElementPtr->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 ¤tElementPtr->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 |
