diff options
Add Seminar05
2 files changed, 876 insertions, 0 deletions
| -rw-r--r-- | Seminar05/src/deque/deque-tests.cpp | 404 | ||||
| -rw-r--r-- | Seminar05/src/deque/deque.hpp | 472 |
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 |
