Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar05 / src / deque
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 /Seminar05/src/deque
Data-structures-and-algorithms-ad40e20b8983831400502fa9617f4c842ae23b78.tar
Data-structures-and-algorithms-ad40e20b8983831400502fa9617f4c842ae23b78.tar.gz
Data-structures-and-algorithms-ad40e20b8983831400502fa9617f4c842ae23b78.zip
Parent450101630aeebfb92da99417a6a71570bdfeb3e6 (diff)
Add Seminar05
2 files changed, 876 insertions, 0 deletions
-rw-r--r--Seminar05/src/deque/deque-tests.cpp404
-rw-r--r--Seminar05/src/deque/deque.hpp472
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